Анализ и синтез комбинационных схем

3.1.1.Типы цифровых автоматов

зависимости от типа элементов, из которых построен автомат, различают два основных типа цифровых автоматов:

v комбинационные схемы;

v цифровые автоматы с памятью.

Комбинационные схемы состоят только из логических элементов (И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и т.д.). Комбинационные схемы могут иметь несколько входов и несколько выходов (рисунок 3.1).

Рисунок 3.1

Главной особенностью комбинационных схем является то, что сигнал на
выходе комбинационных схем зависит только от комбинации сигналов на
входах схемы и не зависит ни от времени, ни от предыстории входных
сигналов. Таким образом, при многократном поступлении одного и того же
входного сигнала на выходах комбинационной схемы будет формироваться
один и тот же входной сигнал.

Цифровые автоматы с памятью состоят из логических элементов и элементов памяти (рисунок 3.2). Информация, записанная в элементах памяти
такого автомата, называется состоянием цифрового автомата. Основная
особенность цифровых автоматов с памятью состоит в том, что сигнал на
выходе автомата зависит как от входного сигнала, так иот состояния автомата.

Рисунок 3.2

В свою очередь, состояние автомата зависит от того, какие сигналы поступали на его входы до настоящего момента времени, т.е. от предыстории работы автомата. Поэтому при многократном поступлении одного и того же входного сигнала на выходах автомата с памятью могут формироваться различные сигналы.

При сопоставлении комбинационных схем и цифровых автоматов с памятью можно сделать вывод, что комбинационные схемы имеют единственное
состояние. Комбинационные схемы используются для технической реализации
логических функций. При помощи комбинационной схемы определяется
значение логической функции для заданных значений логических переменных.
В теории автоматов обычно считается, что при изменении сигналов на входах схемы выходной сигнал мгновенно принимает соответствующее значение, т.е.
задержка сигналов логическими элементами не учитывается.

В цифровых автоматах с памятью формирование выходного сигнала
занимает определенное время, которое обычно разбивается на такты. В каждом
такте в зависимости от входного сигнала и состояния автомата формируется
выходной сигнал и новое состояние. Таким образом, можно сказать, что
выходной сигнал автомата с памятью зависит от последовательности входных
сигналов, поэтому цифровые автоматы с памятью называют также
последовательностными схемами.

3.1.2. Задачи анализа и синтеза комбинационных схем

Структурно комбинационная схема может быть представлена как совокупность элементарных логических схем – логических элементов. Логические элементы выполняют над входными переменными элементарные логические операции типа И-НЕ, И, ИЛИ, ИЛИ-НЕ и т.д. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции. Графическое изображение комбинационной схемы, при котором показаны связи между различными элементами, а сами элементы представлены условными обозначениями, называется функциональной схемой.

Основными характеристиками комбинационных схем являются сложность и быстродействие.

Сложность комбинационной схемы оценивается количеством оборудования, составляющего схему. При разработке схем на основе конкретной элементной базы количество оборудования обычно измеряется числом корпусов (модулей) интегральных микросхем, используемых в схеме. В теоретических разработках ориентируются на произвольную элементную базу и поэтому для оценки затрат оборудования используется оценка сложности схем по Квайну.

Сложность (цена) по Квайну определяется суммарным числом входов логических элементов в составе схемы. При такой оценке единица сложности – один вход логического элемента. Цена инверсного входа обычно принимается равной двум (если на вход схемы сигналы поступают только в прямой форме). Такой подход к оценке сложности оправдан по следующим причинам:

Øсложность схемы легко вычисляется по логическим функциям, на основе которых строится схема: для ДНФ сложность схемы равна сумме количества букв (букве со знаком отрицания соответствует цена 2) и количества знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения;

Øвсе классические методы минимизации логических функций обеспечивают минимальность схемы именно в смысле цены по Квайну.

Практика показывает, что схема с минимальной ценой по Квайну обычно реализуется наименьшим числом конструктивных элементов – корпусов интегральных микросхем.

Быстродействие комбинационной схемы оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т.е. определяется промежутком времени от момента поступления входных сигналов до момента установления соответствующих значений выходных сигналов. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтому быстродействие схемы характеризуется значением rt, где t - задержка сигнала на одном элементе. Значение r определяется количеством уровней комбинационной схемы, которое рассчитывается следующим образом. Входам КС приписывается уровень нулевой. Логические элементы, связанные только с входами схемы относятся к уровню первому. Элемент относится к уровню k, если он связан по входам с элементами уровней k -1, k -2, и т.д. Максимальный уровень элементов r определяет количество уровней КС, называемое рангом схемы. Пример определения ранга r схемы приведён на рисунке 3.3.

	Рисунок 3.3

Как известно, любая логическая функция может быть представлена в ДНФ, которой соответствует двухуровневая комбинационная схема. Следовательно, быстродействие любой КС в принципе можно довести до 2t.

Минимизация булевой функции с целью уменьшения сложности схем обычно приводит к необходимости представления функций в скобочной форме, которой соответствуют схемы с r > 2. Таким образом, уменьшение затрат оборудования в общем случае приводит к снижению быстродействия схем.

В ходе разработки комбинационных схем приходится решать задачи анализа и синтеза.

Задача анализа состоит в определении статических и динамических свойств комбинационной схемы. В статике определяются логические функции, реализуемые комбинационной схемой по известной ей структуре. В динамике рассматривается способность надёжного функционирования схемы в переходных процессах при смене значений переменных на входах схемы, т.е. определяется наличие на выходах схемы возможных нежелательных импульсных сигналов, которые не следуют непосредственно из выражений для логических функций, реализуемых схемой.

Задача синтеза заключается в построении из заданного набора логических элементов комбинационной схемы, реализующей заданную систему логических функций.

Решение задачи синтеза не является однозначным, можно предложить различные варианты комбинационных схем, реализующих одну и ту же систему логических функций, но отличающихся по тем или иным параметрам. Разработчик комбинационных схем из этого множества вариантов выбирает один, исходя из дополнительных критериев: минимального количества логических элементов, необходимых для реализации схемы, максимального быстродействия и т.д. Существуют различные методы синтеза комбинационных схем, среди которых наиболее разработан канонический метод.

3.1.3. Анализ комбинационных схем

Задачи анализа комбинационных схем (КС) возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить логическую функцию, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся на прямые и косвенные.

В результате анализа КС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение на выходе, что позволяет записать в алгебраическом виде логическую функцию, реализуемую схемой. К прямым методам относится метод p- алгоритма.

Применение косвенных методов дает возможность определить реакцию схемы на заданный набор входных переменных в статике или проанализировать переходный процесс смены одного входного набора на другой. Примерами косвенных методов анализа являются методы синхронного и асинхронного моделирования.

Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.

Для всех методов анализа необходимо описать схему в виде схемного списка, в который включаются в общем случае следующие данные:

Ë номер ЛЭ в схеме;

Ë логическая функция, реализуемая ЛЭ;

Ë входные переменные для данного ЛЭ.

Например, на рисунке 3.4 представлена схема и список, описывающий схему.