Синтез комбинационных и конечных автоматов (стр. 2 )

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

На рисунок 1 представлены карты Карно для 3, 4 и 5 переменных.

а) б) в)

Рисунок 1 — Карты Карно для 3, 4 и 5 переменных.

Функция, представленная в СДНФ и подлежащая минимизации, зано­сится на карту Карно. При этом в клетки, соответствующие минтермам, на которых функция равна 1, записывается 1. Соседние клетки, содержащие 1, включают в контур (незамкнутый, если минтермы находятся в крайних клетках). Склеиванию по двум аргументам соответствуют контуры, охватывающие четыре соседних ячейки, расположенные в виде прямоугольника. Тупиковой ДНФ соответствуют склеивания, в которых каждый минтерм не содержит лишних покрытий, минимальной ДНФ — склеивания с наиболее рациональным распределением покрытий.

Проиллюстрируем применение карт Карно на примере. Дана функция:

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

а) б)

Рисунок 2 — Минимизация функций с помощью карт Карно.

Из рисунка 2а видно, что склеивания приводят к образованию двух импликант, покрывающих все восемь исходных минтермов. Таким обра­зом, дизъюнкция полученных импликант дает оптимальную ДНФ, которая имеет вид:

.

Особо следует остановиться на возможностях минимизации недоопре­деленных функций, т. е. функций, значения которых не определены на некоторых наборах аргументов, называемых избыточными или запре­щенными. Эти наборы аргументов никогда не поступают на входы КА. Следовательно, такую функцию можно произвольно доопределить, уста­новив её значения (0 или 1) на запрещенных наборах по своему усмотрению таким образом, чтобы результирующая минимальная ДНФ была наиболее простой.

В качестве примера синтезируем схему устройства, которое реагирует только на четные десятичные цифры от 0 до 9, подаваемые на вход в виде четырехразрядного двоичного кода. Следовательно, на выходе устройства сигнал будет равен I только в том случае, если на его входах появится комбинация сигналов, соответствующих одной из цифр 0, 2, 4, 6, 8. В случае появления других наборов сигнал на выхода равен 0. Кроме того, наборы 10, 11, 12, 13, 14, 15 никогда не встречаются. Следовательно, функция для данного устройства может быть представлена в виде:

Занесем функцию на карту Карно: клетки, соответствующие запрещенным наборам, отметим крестиком (рисунок 2б). Если принять, что на наборах, соответствующих числам 10, 12, 14, Функция равна 1 ,то контур охватит восемь клеток и минимизированная функция примет вид:

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

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

Например, имеем минимизированную функцию трех переменных:

Логическая схема, реализующая эту функцию, содержит три двухвходовых элемента И и один трёхвходовый элемент ИЛИ. Преобразуем это выражение, взяв двойное отрицание от правой части (при этом значение не изменится), и, используя закон де Моргана, получим:

Структурная схема, реализующая это выражение, представлена на рисунке 3а.

а) б)

Рисунок 3 — Варианты реализации КА.

Если базовым элементом служит элемент И-ИЛИ-НЕ, то при минимизации с помощью карт Карно часто оказывается более целесообразным применить группирование нулей, а не единиц, т. е. записать СДНФ функции и затем взять её отрицание (так называемая нондизъюнктивная форма, т. е. дизъюнктивная форм с инверсией).

Если на карте Карно для последней функции охватить контурами клетки, содержащие 0, то получим:

Инвертируем правую и левую части этого выражения:

Полученное выражение реализуется лишь одним элементом И-ИЛИ-НЕ (рисунок 3б).

Как правило, схемы, построенные в соответствии с МДНФ функцией, не является минимальными в отношении числа, как используемых элементов, так и их входов. Очень часто дальнейшего упрощения схемы можно достичь вынесением за скобки общих членов в МДНФ, т. е. использованием так называемых скобочных форм.

Например, для реализации функции:

потребуется два двухвходовых элемента И и один двухвходовый элемент ИЛИ, т. е. всего три элемента. Если эту функцию представить в виде:

то для её реализации потребуется два элемента — один двухвходовый элемент ИЛИ и один двухвходовый элемент И.

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

Рассмотрим схему, которая при трех входных сигналах a, b, c должна выдавать два выходных сигнала y и z:

Для увеличения количества совпадающих членов функция представлена не в ДНФ.

В базисе И-НЕ эти функции будут иметь вид:

На рисунке 4а представлена схема, построенная в соответствии с этими выражениями.

Применим скобочные формы для упрощения схемы. Функцию представим в виде:

Преобразуем также функцию z:

Рисунок 4 — Использование скобочных форм при реализации КА.

На рисунке 4б приведена схема КА, построенная в соответствии с последними выражениями для функций y и z. Эта схема проще ранее рассмотренной схемы, так как общеё число входов уменьшено с 21 до 15.

Существует также каноническая форма представления функции на основе алгебры Жегалкина, так называемый полином Жегалкина:

где - коэффициенты, принимающие значения 0 и 1 для конкретных функций. Как видно, полином Жегалкина есть сумма по модулю 2 произведений переменных, взятых по одному, по два, … по n и, возможно, 1 (если =1). Представление функции полиномом Жегалкина единственно.

Переход от СДНФ к полиному Жегалкина [1] :

— заменить в СДНФ знаки + на (это следует из равенств и следовательно, но ); — заменить в минтермах на ;

— раскрыть скобки и привести подобные члены, используя равенство:

Пример. Дана функция

Этот способ не применим к произвольной ДНФ, так как произведения её слагаемых могут быть и не равны 0.

Приведем правила перехода от произвольной ДНФ к полиному Жегалкина и обратно.

Для преобразования произвольной ДНФ в полином Жегалкина следует:

— используя правило де Моргана, перейти от ДНФ к форме, содержащей только операцию штрих Шеффера (И-НЕ);

— заменить все отрицания ;

— раскрыть скобки и привести подобные члены.

Пример.

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

Поставим затем 1 в те клетки, где число нечетно (0 — четное число) и известным методом минимизируем полученную функцию [4].

Пример.

Рисунок 5 — Преобразование полинома Жегалкина в ДНФ функции.

По карте Карно (рисунок 5) записываем: .

Рассмотренная методика позволяет синтезировать и более сложные КА, к которым относятся: дешифраторы, шифраторы, мультиплексоры, демультиплексоры, преобразователи кодов, схемы сравнения и т. п.

1.2 ДЕШИФРАТОРЫ И ШИФРАТОРЫ

Дешифратор, имеющий n входов, реализует все минтермов n переменных, т. е. дешифратор имеет выходов. Дешифраторы могут быть неполными, если . Такие дешифраторы используются, например, для преобразования двоично-десятичного кода в код, предназначенный для управления цифровым (или цифро-буквенным) индикатором. Дешифраторы преобразуют двоичный или двоично-десятичный код в унитарный. Унитарный код двоичного n-разрядного числа представляется разрядами, только один из которых равен 1.

Шифраторы выполняют функцию, обратную дешифраторам, т. е. преобразуют унитарный код в двоичный или двоично-десятичный.

1.3 МУЛЬТИПЛЕКСОРЫ И ДЕМУЛЬТИПЛЕКСОРЫ

Мультиплексоры имеют входов и один выход, где m — число адресных входов, а - число информационных входов мультиплексора. Адреса представляются в двоичном коде, и им присваивается номер . Каждому адресу с номером соответствует свой информационный вход , сигнал с которого при данном адресе проходит на выход. Основным назначением мультиплексора является коммутация входных сигналов на один выход.

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

Помимо основного назначения мультиплексоры могут быть использованы для построения КА.

Карта Карно, показывающая связь информационных и адресных входов для 8 — канального мультиплексора, представлена на рисунке 6а; на рисунке 6б дано условное обозначение мультиплексора.

а) б)

Рисунок 6 — Условное обозначение и связь

информационных и адресных входов мультиплексора.

Пример. Реализовать с помощью 8-канального мультиплексора функцию, заданную картой Карно (рисунок 7) .

Рисунок 7.

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

Полагаем Bj = yj и, сопоставляя рисунок 6а с рисунком 7, получим:

Пример. Пусть требуется реализовать функцию , заданную картой Карно (рисунок 8а).

Рисунок 8 — Реализация КА на мультиплексоре.

МНФ данной функции в базисе имеет вид:

Для реализации этой функции на 8-канальном мультиплексоре адрес будем определять числом

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

Это легко выполнить с помощью карты Карно (рисунок 8а), учитывая, что числа J произвели её разбиение на восемь частей, т. е. на восемь карт Карно для одной переменной , состоящих из двух клеток. Из рисунков 8а и 8б следует, что:

Схема, реализующая эту функцию, приведена на рисунок 9.

Рисунок 9.

1.4 ПРЕОБРАЗОВАТЕЛИ КОДОВ

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

1)  преобразователи с невесомым преобразованием кодов;

2)  преобразователи с весовым преобразованием кодов.

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

Код Грея построен таким образом, что при переходе от одного числа к следующему изменяется всегда только один двоичный разряд. На рисунок 9 представлены преобразователи двоичного кода в код Грея (рисунок 10, а) и кода Грея в двоичный код (рисунок 10, б), реализованные на элементах ИСКЛЮЧАЮЩЕЁ ИЛИ [5].

а) б)

Рисунок 10 — Преобразователи кодов на элементах ИСКЛЮЧАЮЩЕЁ ИЛИ.

1.5 РАБОЧИЕ ЗАДАНИЯ

1.5.1 ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ

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

Разработать и реализовать в среде моделирования электронных схем MultiSim модель преобразователя двоичного кода в код семи сегментного индикатора, который позволял бы выводить последовательно на светодиодный индикатор дату рождения студента в формате «ДДММГГГГ». Преобразователь кода выполнить на логических элементах И-НЕ. Для этого требуется выполнить следующие действия:

1) записать таблицу истинности разрабатываемого преобразователя кода;

2) записать уравнения функций для каждого сегмента индикатора;

3) минимизировать функции двумя способами: с помощью законов булевой алгебры и с помощью карт Карно;

4) представить минимизированные функции в базисе И-НЕ.

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

В качестве источника входного двоичного кода использовать WorD Generator.

1.5.2 ЗАДАНИЕ К КОНТРОЛЬНОЙ РАБОТЕ

Разработать и реализовать в среде моделирования электронных схем MultiS im модель преобразователя двоичного кода в код буквенно-цифрового индикатора, который позволял бы выводить последовательно на светодиодный индикатор фамилию студента. Преобразователь кода выполнить на логических элементах И-НЕ. Последовательность действий такая же, как и в задании к лабораторной работе.

1.6 КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение комбинационного автомата. Приведите примеры и таблицы истинности КА.

2. Реализуйте операции И, ИЛИ, НЕ на элементах ИЛИ-НЕ,

3. Занесите на карту Карно функцию 5 переменных (a, b, c, d, e).

4. Запишите теорему разложения и её тождества. Покажите на примере, как используются тождества для упрощения логических выражений.

5. Какие способы минимизации Вы знаете? Опишите порядок минимизации одним из этих способов.

6. Как преобразовать функцию в СДНФ в полином Жегалкина и как
выполнить обратное преобразование?

7. Запишите код Грея. Как сделать преобразователь двоичного
кода в код Грея?

8. Докажите равенство .

2 СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ

2.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

В конечных (последовательностных) автоматах значения выходных переменных в течение текущего такта n определяются значениями входных в течение этого, а также ряда предыдущих тактов:

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

К простейшим (элементарным) конечным автоматам относятся триггерные устройства (триггеры) с двумя устойчивыми состояниями, характеризуемыми выходным сигналом Q. В общем случае триггер имеет два выхода: прямой — и инверсный - . Триггеры отличаются друг от друга числом входов p, выполняемыми функциями, схемой построения, способом функционирования и т. д. Общеё число М различных триггеров с p входами определяется соотношением:

.

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

Классификация по функциональному признаку разделяет триггеры по виду характеристического уравнения:

.

Связывающего логические переменные на входах и выходах триггера до и после его перехода из одного состояния в другое. В соответствии с функциональной классификацией различают триггеры RS , JK, D, DV, T и др.

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

К основным схемотехническим параметрам триггера, которые необходимо учитывать при проектировании конечных автоматов, относятся [2]:

nT — нагрузочная способность триггера;

mT — коэффициент объединения по входу;

tU — минимальная длительность входного сигнала;

tз — время задержки переключения триггера;

tраз — разрешающеё время триггера.

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

На рисунке 11 приведены условные обозначения наиболее распространенных типов триггеров.

Рисунок 11 — Условные обозначения триггеров.

Триггером типа RS называют логическое устройство с двумя устойчивыми состояниями, имеющеё два информационных входа R и S . При S =1 и R=0 триггер устанавливается в состояние 1 (Q=1), а при S =0 и R=1 — в состояние 0 (Q=0).В соответствии с состоянием, принимаемым триггером, вход S называют единичным входом, в R — нулевым. Если на входы R и S одновременно подать логические 1 (S =R=1), то на выходах и триггера устанавливаются одинаковое состояние ( или ), а после окончания действия информационного сигнала триггер может перейти в состояние Q=1 или Q=0 с равной вероятностью. Поэтому логические устройства на основе RS-триггеров должны строится с учетом исключения комбинаций сигналов .

В таблице 2 приведены состояния двухвходовых триггеров при различных комбинациях сигналов на информационных входах. Такие таблицы называют таблицами истинности (функционирования) или таблицами переходов.

Таблица 2.

Сигналы на входах триггера	Сигналы на выходе триггера Qn+1
Вход 1	Вход 2	SR — триггер (S, R)	S — триггер (S1, S2)	R — триггер (R1, R2)	E — триггер (E1, E2)	JK — триггер (J, K)	DV — триггер (V, D)
0	0	Qn	Qn	Qn	Qn	Qn	Qn
1	0	1	1	1	1	1	Qn
0	1	0	0	0	0	0	0
1	1	X	1	0	Qn		1

Знаком X в таблице 2 отмечена запрещенная комбинация входных сигналов.

Характеристическое уравнение RS-триггера, составленное в соответствии с таблицей 2, после упрощения и с учетом требования записывается в виде [2]:

.

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

— S-триггер;

— R-триггер;

— E-триггер;

— JK-триггер;

— DV-триггер.

Триггеры типов D и T имеют один информационный вход (D или T). Зависимость их состояний от значений входных сигналов приведена в таблице 3.

Таблица 3.

Сигналы на управляющем входе триггера	Сигналы на выходе триггера
Вход триггера	D-триггер (D)	T-триггер (T)
0	0	Qn
1	1

Характеристические уравнения этих триггеров имеют вид: