Карты карно минимизация логических функций. Схемотехника
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно - это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, то есть 2 n . Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. К примеру, для функции двух переменных А и В (рисунок 3) карта Карно имеет вид:
Рисунок 3 - Карта Карно для булевой функции двух переменных
Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Поиск минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.
В примере на рисунке 3 пара единиц верхней строки охватывается импликантой В (т.е. обе клетки имеют общий аргумент В). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = В? B.
Если имеется несколько вариантов объединения конституент контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.
Карту Карно удобно использовать и для минимизации функций, заданных в алгебраической форме, например,
Карта Карно, состоящая из 2 3 = 8 клеток, может быть размечена, как показано на рисунке 4.
Рисунок 4 - Карта Карно для трёх переменных
При охвате единиц контурами склеивания карту Карно можно сворачивать в цилиндр, как вдоль горизонтальной, так и вертикальной оси. В результате все четыре единицы, расположенные в углах Карты, охватываются контуром с общей импликантой. Такой минимизации соответствует выражение:
Выполнение задания
Таблица 10 - Таблица истинности
Выделить в таблице истинности все строки, в которых функция принимает значения 0.
Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:
если значение переменной равно 0, то записывается сама переменная;
если значение переменной равно 1, то записывается инверсия этой переменной
Соединить элементарные дизъюнкции знаком конъюнкции.
Минимизация СКНФ с помощью Карты Карно (рисунок 5):
Рисунок 5 - Карта Карно для четырех переменных.
По закону де - Моргана (закон общей инверсии ()) инвертируем МКНФ:
Запишем функцию в МКНФ:
Исходя из задания, логические элементы представляет в виде замыкающих контактов, а - в виде размыкающих контактов. Логическую функцию F представляем в виде обмотки реле. Из данных условий построим схему релейно-контактного эквивалента логического устройства (рисунок 7):
Составляем программу на языке Паскаля:
var{описание переменных величин} X1, X2, X3, X4, Y1, Y2, Y3, Y4,F: boolean{оператор логический (булевский)};
begin{оператор начала}
write{Оператор вывода} ("Введите значение переменной X1:");
readln{Оператор ввода};
write{Оператор вывода} ("Введите значение переменной X2:");
readln{Оператор ввода};
write{Оператор вывода} ("Введите значение переменной X3:");
readln{Оператор ввода};
write{Оператор вывода} ("Введите значение переменной X4:");
readln{Оператор ввода};
Y1:={оператор присваивания}X2 and X3 and (not X4);
Y2:={оператор присваивания}(not X1) and X2 and X4;
Y3:={оператор присваивания} (not X1) and (not X2) and (not X3);
Y4:={оператор присваивания} X1 and (not X2) and X3;
F:={оператор присваивания}Y1 and Y2 and Y3 and Y4;
writeln(F){Оператор вывода};
end.{оператор окончания}
Правила минимизации с использованием карт Карно
1. В карте Карно группы единиц (для получения ДНФ) и группы нулей (для получения КНФ) необходимо обвести четырехугольными контурами. Внутри контура должны находиться только одноименные значения функции. Этот процесс соответствует операции склеивания или нахождения импликант данной функции.
2. Количество клеток внутри контура должно быть кратно степени двойки (1, 2, 4, 8, 16...).
3. При проведении контуров крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки, считаются соседними (для карт до 4-х переменных).
4. Каждый контур должен включать максимально возможное количество клеток. В этом случае он будет соответствовать простой импликанте (имплиценте). Число контуров должно быть минимальным.
5. Все единицы (нули) в карте (даже одиночные) должны быть охвачены контурами. Любая единица (нуль) может входить в контуры произвольное количество раз.
6. Число контуров должно быть минимальным. Множество контуров, покрывающих все 1 (0) функции образуют тупиковую ДНФ (КНФ). Целью минимизации является нахождение минимальной из множества тупиковых форм.
7. В элементарной конъюнкции (дизъюнкции), которая соответствует одному контуру, остаются только те переменные, значение которых не изменяется внутри обведенного контура. Переменные булевой функции входят в элементарную коньюнкцию (для значений функции 1) без инверсии, если их значение на соответствующих координатах равно 1 и с инверсией - если 0. Для значений булевой функции, равных 0, записываются элементарные дизьюнкции, куда переменные входят без инверсии, если их значение на соответствующих координатах равно 0 и с инверсией - если 1.
Рассмотрим пример на рис. 2.52.
Рисунок 2.52 – Карта Карно двух переменных
СДНФ: . Применяя для минимизации метод аналитических преобразований (закон склеивания и Блейка-Порецкого), получаем:
Можно пойти другим путем, применяя операцию неполного склеивания, получим дизъюнкцию импликант:
И - простые импликанты, поскольку к ним невозможно применить операцию склеивания, они образуют сокращенную ДНФ. Других вариантов нет, поэтому данная ДНФ является тупиковой, кратчайшей и минимальной.
По карте Карно получаем:
МКНФ: 
.
В кубической форме процесс минимизации будет выглядеть следующим образом:
где 01, 10, 11 – минтермы, Х1 и 1Х – импликанты, они же простые импликанты. Остается одна простая иплицента (она же макстерм) 00. С 1 = {1Х, Х1}, С 0 = {00}.
Рассмотрим пример на рис. 2.53.
Рисунок 2.53 – Карта Карно трех переменных
МДНФ: 
.
Рассмотрим пример на рис. 2.54.
Рисунок 2.54 – Карта Карно четырех переменных
Для частично (не полностью) определенных функций рассмотрим пример на рис. 2.55. Неизвестные значения, обозначаемые Х участвуют в склеивании
Рисунок 2.55 – Карта Карно четырех переменных частично определенной функции
МДНФ: 
.
МКНФ: 
.
КП={C 0 , C 1 },
.
Если рассматривать запись результатов минимизации в кубическом виде, то при минимизации булевой функции по единичным значениям каждой конъюнкции ранга R соответствует куб ранга R, где каждой переменной без инверсии соответствует 1 в кубе, переменной с инверсией - 0, а на месте отсутствующей переменной ставиться X. Полученное множество кубов образует единичное покрытие C 1 (соответствующее ДНФ).
При минимизации булевой функции по нулевым значениям и представлении результатов минимизации в кубическом виде, нулевое покрытие C 0 формируется на основе КНФ. Таким образом, каждой дизъюнкции ранга R (из КНФ) соответствует куб ранга R, где каждой переменной без инверсии соответствует 0 в кубе, переменной с инверсией - 1, а на месте отсутствующей переменной ставиться X. Полученное множество кубов образует нулевое покрытие C 0 (соответствующее КНФ).
Особенностью изображения карт Карно для числа переменных более 4-х является то, что «математически» соседние столбцы карты Карно пространственно оказываются разнесенными. Таким образом, карта Карно для 5 переменных представляет собой две карты 4-х переменных, зеркально отображенные относительно центральной вертикальной линии (выделенной жирным тоном на рис. 2.56).
Рисунок 2.56 – Карта Карно пяти переменных
При этом столбцы одного цвета в правой и левой частях карты фактически оказываются соседними по переменной x 3 (соседние столбцы также указываются стрелками в нижней части карты). При выполнении склеиваний следует учитывать «соседство» указанных столбцов, особенно розовых и зеленых, которые пространственно разделены.
2.2.3 Минимизация систем булевых функций
Существует два подхода в минимизации систем булевых функций:
Минимизация каждой функции в отдельности;
Совместная минимизация функций системы.
Рассмотрим первое направление. Если произвести минимизацию булевых функций, входящих в систему, независимо друг от друга, то общая схема будет состоять из изолированных подсхем. Ее можно иногда упростить за счет объединения участков подсхем, реализующих одинаковые члены, входящие в несколько булевых функций системы.
Пусть в результате минимизации функций получены следующие МДНФ:
На рис. 2.57 показана реализация системы функций без учета общих частей (термов). Аппаратурные затраты по критерию Квайна без учета инверсий для данной реализации составляют C b = 18.
На рис. 2.58 показана реализация системы функций с объединением общих частей . Аппаратурные затраты по критерию Квайна без учета инверсий для данной реализации составляют C b = 14.Очевидно, что данная реализация является более простой (экономичной).
Рисунок 2.57 – Реализация системы функций без учета общих частей
Рисунок 2.58 – Реализация система функций с объединением общих частей
Данный метод не всегда эффективен. Ниже это будет проиллюстрировано примером.
Рассмотрим второе направление. Существуют различные методы, в данном случае предлагается метод минимизации системы булевых функций. Алгоритм минимизации следующий. (Для КНФ алгоритм аналогичен).
1. Выписать все минтермы функций (можно в кубической форме), входящие в систему. Каждому минтерму присвоить признак, содержащий номера функций системы, в которые входит рассматриваемый минтерм, например, минтерм 0 (f 1 , f 3) 0000, минтерм 15 (f 1) 1111.
2. Выполнить склеивание. Если признаки склеиваемых элементарных произведений (минтермов и далее импликант) не содержат общих номеров, склеивание не выполняется, поскольку эти элементарные произведения не относятся к одной функции. Результату склеивания (импликантам) присваивать признак, состоящий из номеров функций, общих для двух склеиваемых минтермов или импликант. Не участвовавшие в склеивании импликанты и минтермы являются простыми импликантами и все они составляют сокращенную ДНФ системы, записываемой в виде функции .
3. Построить таблицу покрытий функции - для каждого минтерма выделяется столько столбцов, сколько различных номеров функций содержит его признак. Далее все аналогично, строится минимальная форма функции .
4. Произвести получение выражений МДНФ для каждой функции системы по функции .
Замечание. Если функция не полностью определена, наборы, на которых она не определена, должны участвовать в склеивании, но в таблицу покрытий не вносятся.
Рассмотрим пример. Пусть дана система булевых функций (табл. 2.8). Найдем МДНФ системы булевых функций.
Таблица 2.8 – Таблица истинности системы булевых функций
| 0 0 0 | 1 1 |
| 0 0 1 | 0 0 |
| 0 1 0 | 0 1 |
| 0 1 1 | 0 1 |
| 1 0 0 | 0 0 |
| 1 0 1 | 1 1 |
| 1 1 0 | 1 0 |
| 1 1 1 | 1 0 |
Выполняем склеивания.
В склеивании не участвовали все 1-кубы и два 0-куба 000 (f 1) и 101 (f 2). Это простые импликанты. Они составляют сокращенную ДНФ функции . Все они войдут в таблицу покрытий.
Строим таблицу покрытий (табл. 2.9)
Таблица 2.9 – Таблица покрытий
| Простые импликанты | Минтермы функции | ||||||||
| f 1 | f 2 | f 2 | f 2 | f 1 | f 2 | f 1 | f 1 | ||
| A | 0x0 (f 2) | v | v | ||||||
| B | 01x (f 2) | v | v | ||||||
| C | 1x1 (f 1) | v | v | ||||||
| D | 11x (f 1) | v | v | ||||||
| E | 000 (f 1 , f 2) | v | v | ||||||
| F | 101 (f 1 , f 2) | v | v |
Ядро функции составляют простые импликанты B, D, E, F. Остальные импликанты являются лишними и не будут входить в тупиковую и минимальную ДНФ. Т.е. МДНФ функции будет состоять только из ядра.
По МДНФ функции строим МДНФ и МДНФ .
Аппаратурные затраты по критерию Квайна без учета инверсий и с учетом объединения общих частей выражения (
) составляют C b =16.
Попробуем для минимизации рассмотренной системы воспользоваться первым подходом, предполагающим минимизацию каждой функции отдельно.
Карта Карно для функции представлена на рис. 2.59
Рисунок 2.59 – Карта Карно для функции
Карта Карно для функции представлена на рис. 2.60
Рисунок 2.60 – Карта Карно для функции
Общих частей у МДНФ функций нет, в результате аппаратурные затраты по критерию Квайна без учета инверсий составляют C b =20. По оценке аппаратурных затрат видно, что раздельная минимизация функций системы уступает совместной, хотя последняя является более трудоемкой.
2.3 Комбинационные компоненты средней степени интеграции
Сумматоры
Каким образом выполняется суммирование двух положительных чисел в двоичном коде? Например, 3+5=8:
Существует большое многообразие сумматоров в приведено 9 типов сумматоров, рассмотрим самые простые из них.
Таблица 2.12 – Таблица истинности для полного сумматора
| a | b | C in | S | C out |
.
Выполнив минимизацию C out по карте Карно, получим;
С in – перенос из предыдущего младшего разряда,
C out – перенос с следующий старший разряд.
На рис. 2.67 представлена схема одноразрядного полного сумматора.
Рисунок 2.67 – Схема одноразрядного полного сумматора
Для последовательного выполнения операции сложения (разряд за разрядом) используется один полный сумматор, общий для всех разрядов. Для выполнения операции операнды и перенос подаются на него последовательно, начиная с младших разрядов рис. (2.68).
Рисунок 2.68 – Схема последовательного сумматора
Последовательный сумматор имеет небольшие аппаратурные затраты, но требует большого времени выполнения операции. Более быстродействующим будет параллельный сумматор с последовательным переносом. Для примера рассмотрим четырехразрядный параллельный сумматор с последовательным переносом (рис. 2.69).
Рисунок 2.69 – Схема параллельного сумматора с последовательным переносом
Для каждого разряда в этой схеме используется отдельный одноразрядный полный сумматор. В младший разряд (a 0 , b 0 ) переноса нет, поэтому С in =0. На каждый последующий разряд подеется перенос из предыдущего. Хоть сумматор и называется параллельным, на самом деле все разряды обрабатываются не точно одновременно, а только после формирования переноса для данного разряда. Отсюда следует, что быстродействие устройства определяется суммой задержек передачи сигнала переноса с младшего разряда на выход сумматора старшего разряда.
Мультиплексоры
Мультиплексором (от английского слова multiplex - многократный) называется комбинационный узел, способный коммутировать (передавать) информацию с нескольких входов на один выход. С помощью мультиплексора осуществляется временное разделение информации, поступающей по разным каналам. На рисунке 2.70 приведен пример мультиплексора 2 в 1. Мультиплексоры имеют две группы входов и один, реже два - взаимодополняющих выхода F и . Входы являются информационными, вход А - управляющими (адресными). Набор сигналов на адресных входах определяет конкретный информационный вход, который будет соединен с выходным каналом. Условно мультиплексор обозначается MX или MUX.
Рисунок 2.70 – Условное обозначение мультиплексора MX 2 в 1
В таблице 2.13 приведены значения адресов для соответствующих входов.
Таблица 2.13 – Информационные входы и их адреса
| Информационные входы | А |
| D 0 | |
| D 1 |
На рис. 2.71 приведен механический аналог мультиплексора 2 в 1. Когда А =0, коммутируется D 0 и F , когда А =1, коммутируется D 1 и F.
Рисунок 2.71 – Механический аналог мультиплексора MX 2 в 1
В таблице 2.14 представлена таблица истинности MX 2 в 1.
Таблица 2.14 – Таблица истинности MX 2 в 1
| А | D 0 | D 1 | F |
Выполнив минимизацию по карте Карно функции F , получим выражение:
На рисунке 2.72 приведена структура мультиплексора 2 в 1.
Рисунок 2.72 – Структура мультиплексора MX 2 в 1
На рисунке 2.73 приведен пример мультиплексора 4 в 1.
Рисунок 2.73 – Условное обозначение стробируемого MUX 4 в 1
Входы являются информационными, входы - управляющими (адресными). Набор сигналов на адресных входах определяет конкретный информационный вход, который будет соединен с выходным каналом. В таблице 2.15 приведены значения адресов для соответствующих входов.
Таблица 2.15 – Информационные входы и их адреса в MUX 4 в 1
| Информационные входы | Адреса информационных входов А 1 А 2 |
| D 0 | 0 0 |
| D 1 | 0 1 |
| D 2 | 1 0 |
| D 3 | 1 1 |
Разрешающий (стробирующий) вход V управляет одновременно всеми информационными входами независимо от состояния адресных входов. Запрещающий сигнал на этом входе блокирует действие всего устройства. Наличие разрешающего входа V расширяет функциональные возможности мультиплексоров, позволяя синхронизировать его работу с работой других узлов.
На рисунке 2.74 приведен механический аналог мультиплексора MUX 4 в 1. Если V =0, то F =0, т.е. будет выполняться коммутация с нулем. Если V =1, то F будет коммутироваться с каналом в соответствии с поданным адресом на входы А 1 А 2 , т.е. мультиплексор будет выполнять свою основную функцию. .
Рисунок 2.74 – Механический аналог мультиплексора MUX 4 в 1
Разрешающий вход используется также при наращивании числа входных информационных каналов. Мультиплексор на рисунке 2.73 реализует функцию, представленную в табл. 2.16.
Таблица 2.16 – Таблица истинности MUX 4 в 1
| V | А 1 | А 2 | D 0 | D 1 | D 2 | D 3 | F |
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | |||||
| x | x | x | x | x | x |
Функция выхода мультиплексора MUX 4 в 1 будет иметь вид:
Демультиплексоры
Демультиплексоры (DMX) выполняют преобразования информации, обратное преобразованию информации в мультиплексоре. Демультиплексор выполняет коммутацию одного входного информационного канала с одним из нескольких выходных каналов. Число выходных каналов демультиплексора равно , где n - число адресных входов. В качестве демультиплексоров можно использовать дешифраторы. Демультиплексор из 1 в 2 представлен на рис. 2.76.
Рисунок 2.76 – Условное обозначение мультиплексора DMX 1 в 2
В таблице 2.17 приведены значения адресов для соответствующих выходов.
Таблица 2.17 – Выходы и их адреса в DMX 1 в 2
Запись 0/z означает, что на выходе может быть либо 0, либо z, 0 и z соответствуют различным таблицам истинности. Символ z означает состояния высокого импеданса или высокого сопротивления на выходе (обрыв связи).
Вне зависимости от того, что на выходе (0 либо z), функция реализуется уравнениями:
На рисунке 2.78 приведена структура демультиплексора 1 в 2.
Рисунок 2.78 – Структура демультиплексора DMX 1 в 2
Дешифраторы
Комбинационная логическая схема, преобразующая поступающий на её входы двоичный позиционный код в активный сигнал только на одном из выходов (унитарный код), называется дешифратором (от английского decoder). Если количество двоичных разрядов дешифрируемого кода обозначить через n, то число выходов дешифратора равно 2 n . На рисунке 2.79 изображен дешифратор из 2 в 4. Слева – входы 1, 2 – степени двойки, условно будем их обозначать D 1 , D 2 далее для удобства. V – стробирующий вход. Справа – выходы 0, 1, 2, 3 – десятичный эквивалент подаваемого на входы кода, для удобства будем далее их обозначать Q 0 , Q 1 , Q 2 , Q 3 .
Рисунок 2.79 – Условное обозначение дешифратора 2 в 4
Функции дешифратора представлены в таблице 2.19.
Таблица 2.19 – Таблица истинности DC 2 в 4
| D 2 , D 1 | Q 0 , Q 1 , Q 2 , Q 3 . |
| 2 1 | 0 1 2 3 |
| 0 0 | 1 0 0 0 |
| 0 1 | 0 1 0 0 |
| 1 0 | 0 0 1 0 |
| 1 1 | 0 0 0 1 |
С учетом стробирующего сигнала уравнения имеют следующий вид:
,
В ЭВМ с помощью дешифраторов осуществляется выборка необходимых ячеек ЗУ (запоминающих устройств), расшифровка кодов операций с выдачей соответствующих управляющих сигналов, реализация булевых функций.
Если элементы И в схеме дешифратора (рис. 2.80) заменить на элементы Шеффера (И-НЕ), то получим дешифратор с инверсными выходами, что показывается на выходах кружками. Так как дешифраторы реализуют булевы функции, являющиеся конституэнтами единицы, то любую булеву функцию можно реализовать на базе дешифратора c прямыми выходами и логических схем ИЛИ, а также на базе дешифратора c инверсными выходами и логических схем И-НЕ (рис 2.81).
Рисунок 2.81- Реализация булевой функции y на основе дешифратора с прямыми выходами (a) и инверсными выходами (б)
Дешифраторы можно использовать в качестве демультиплексоров, если V использовать как информационный вход, а D 1 , D 2 - как адресные.
Шифраторы
В условных обозначениях шифраторов используются буквы CD (от слова coder) (рис. 2.82).
Рисунок 2.82 – Условное обозначение шифратора 4 в 2
Таблицей, описывающей функционирование шифратора, является табл. 2,19, с той лишь разницей, что являются входными булевыми переменными, а - выходными булевыми функциями шифратора. Функция шифратора представлена в таблице 2.20.
Таблица 2.20 – Таблица истинности CD
Записав МДНФ для каждой функции выхода, получим следующие уравнения:
Структура шифратора представлена на рис. 2.83.
Рисунок 2.83 – Структура шифратора 4 в 2
Уровень представления схемы, в которой используются мультиплексоры, демультиплексоры, шифраторы, дешифраторы, сумматоры и т.п., называется функционально-блочным .
Уровень представления схемы, состоящей из логических элементов (вентилей), называется логическим .
3 Последовательностная логика
Особенность последовательностной схемы (в отличии от комбинационной) состоит в том, что значения на выходах схемы в текущий момент времени зависят не только от того, какие значения были поданы на входы, но и в каком состоянии находилась схема в предыдущий момент времени.
Представителями последовательностных схем являются триггеры. Триггер это элементарный автомат, содержащий элемент памяти (запоминающий элемент) и схему управления элементом памяти. На схему управления подают входные сигналы (информационные) и сигналы обратной связи с выхода элемента памяти (рис. 3.1). В некоторых простейших триггерах схема управления может отсутствовать.
Состояние выхода триггера определяется элементом памяти, сигналом на его прямом выходе Q . Обычно триггер имеет и инверсный выход , иногда он обозначается Q *.
Рисунок 3.1– Структурная схема триггера
ЗЭ – запоминающий элемент;
КС – комбинационная схема управления;
x 1, ..., x n – информационные входы триггера;
С 1 , С m – синхронизующие входы;
Q , – соответственно прямой и инверсный выходы триггера;
f 1 , f 2 – функции возбуждения ЗЭ.
На рис. 3.2 приведены примеры запоминающих элементов. Они состоят из вентилей И-НЕ или ИЛИ-НЕ с обратными связями.
Рисунок 3.2 – Примеры запоминающих элементов
Классификация триггеров проводится по закону логического функционирования (триггеры типа RS, R*S*, JK, J*K* и другие), по способу записи информации в триггер (асинхронные и синхронные), по способу восприятия триггером тактовых сигналов (управляемые уровнями и управляемые фронтами), по структуре (одноступенчатые и двухступенчатые).
3.1 Асинхронные триггеры
Асинхронные триггеры – триггеры, у которых переход в новое состояние вызывается изменениями информационных входных сигналов. Т.е. без тактирующих или синхронизирующих сигналов.
3.1.1 RS-триггер
Триггером типа RS называется триггер с двумя устойчивыми состояниями равновесия и двумя информационными входами (рис. 3.3). Вход S (Set) служит для установки триггера в «1», вход R (Rеsеt) для установки в «0». Одновременная подача двух активных сигналов на входы R и S запрещена, т.е. R S . Подача двух нулей на входы триггера сохраняет его внутреннее состояние. Активным значением сигнала на входе является уровень 1. Вход в этом случае считается прямым. Если активным значением сигнала на входе является нуль, то такой вход считается инверсным. Обычно инверсный вход обозначается символом звездочки (*). Триггеры с инверсными входами будут рассмотрены далее.
Рисунок 3.3 – Структура и условное обозначение асинхронного RS-триггера
Для полного описания триггера достаточно задать закон его функционирования.
Поскольку триггер является элементарным автоматом, то закон его функционирования задается полной таблицей переходов (ПТП) (таблица 3.1), с помощью которой можно построить сокращенную таблицу переходов (таблица 3.2). В таблице t
и t
Q
Q
в момент времени t
.
Таблица 3.1 – Полная таблица переходов RS -триггера
| t | t +1 | |||
| R | S | Q | Q | |
| X | ||||
| X |
Если разбить таблицу 3.1 по две строки сверху, видно, что значения R и S в парах строк одинаковые. Опустив значения столбца , получим сокращенную таблицу переходов (СТП).
Таблица 3.2 – Сокращенная таблица переходов RS -триггера
| R | S | Q (t +1) |
| Q (t ) | ||
| X |
В таблице 3.3 представлена дополнительная таблица переходов (ДТП). Ее легко получить из ПТП. В первом столбце ДТП записываются входы триггера, в остальных столбцах – все возможные переходы состояний триггера 
: «0-0», «0-1», «1-0», «1-1». В ПТП прослеживаются все эти переходы и помечаются (в нашем случае красной цифрой). Цифра обозначает номер перехода в ДТП. Затем в соответствии с расставленными метками из ПТП в столбцы ДТП записываются значения, подаваемые на входы R
и S
на данном переходе.
Таблица 3.3 – Дополнительная таблица переходов RS -триггера
Матрица переходов (МП) это фактически повернутая ДТП (таблица 3.4). Строки ДТП являются столбцами матрицы. Матрица переходов показывает, какие значения сигналов нужно подавать на входы триггера для осуществления указанного перехода состояний Q (t )-Q (t +1). Пары идентичных значений в ячейке ДТП заменяются одним значением в МП. Пары различных значений в ячейке ДТП заменяются одной буквой, например b 1, Так как на переходе «0-0» сигнал на входе R может быть равен или 0, или 1, то его обозначают через неопределенный коэффициент b 1 , . Аналогично для сигнала на входе S для перехода «1-1» ставится b 2 , В различных ячейках МП, где необходимо ставить буквы, должны быть либо различные буквы, либо одна и та же буква, но с различными индексами. Это удобно при синтезе триггеров, чтобы не возникало путаницы. Синтез будет рассмотрен позже.
Таблица 3.4 – Матрица переходов RS-триггера
| Q (t )-Q (t +1) | R | S |
| 0-0 | b 1 | |
| 0-1 | ||
| 1-0 | ||
| 1-1 | b 2 |
Еще одним способом описания триггеров является граф переходов (рис. 3.4). Вершинам соответствуют состояния триггеров, а дугам – переходы между состояниями. Состояние определяется значением выхода Q. Когда Q =0, считается, что триггер находится в состоянии а 0 , когда Q =1, считается, что триггер находится в состоянии а 1 . На дугах записываются условия того или иного переходов.
Рисунок 3.4 – Граф переходов RS -триггера
Для дуги, что выходит из а
0 и входит в а
0 (то есть петли) – для перехода «0-0»: 
;
для дуги из а 0 в а 1 – для перехода «0-1»: ;
для дуги из а 1 в а 0 – для перехода «1-0»: ;
для дуги из а
1 в а
1 – для перехода «1-1»: 
.
Функция переходов триггера в момент t+1 может быть задана с помощью карт Карно (рис. 3.5), которые строятся по полной таблице переходов триггера.
Рисунок 3.5 – Карта Карно для функции переходов RS-триггера
Используя карту Карно, можно найти минимальную КНФ булевой функции для описания функционирования RS -триггера (характеристическую функцию переходов) .
Данное выражение соответствует схеме RS -триггера, изображенного на рис. 3.3.
3.1.2 R *S *-триггер (RS -триггер с инверсными входами)
Триггером типа R *S *-называется триггер с двумя устойчивыми состояниями равновесия и двумя информационными входами (рис. 3.6). Вход S * (Set) служит для установки триггера в «1», вход R * (Rеsеt) для установки в «0». Активным значением сигнала на входе является уровень 0. Вход в этом случае считается инверсным. Инверсный вход обозначается символом звездочки (*). Одновременная подача двух активных сигналов на входы R * и S * запрещена, т.е. R * S * . Подача двух единиц на входы триггера сохраняет его внутреннее состояние.
Рисунок 3.6 – Структура и условное обозначение асинхронного R *S *-триггера
Полная таблица переходов (ПТП) (таблица 3.5), с помощью которой можно построить сокращенную таблицу переходов (таблица 3.6). В таблице t
и t
+1 – соседние моменты времени, в пределах которых рассматриваются переходы состояний триггера (переходы из состояния Q
в момент времени t в состояние Q
в момент времени t
+1). Обозначается такой переход условно .
Таблица 3.5 – Полная таблица переходов R*S* -триггера
Обратите внимание, что столбец Q (t +1) в сокращенной таблице переходов R*S* -триггера, перевернут относительно того же столбца RS -триггера. Это справедливо для всех одноименных триггеров с прямыми и инверсными входами. Зная СТП триггера с прямыми входами, можно легко получить СТП одноименного триггера с инверсными входами.
В таблице 3.7 представлена дополнительная таблица переходов (ДТП).
Таблица 3.7 – Дополнительная таблица переходов R*S* -триггера
Матрица переходов (МП) представлена в таблице 3.8).
Таблица 3.8 – Матрица переходов R*S*-триггера
| Q (t )-Q (t +1) | R* | S* |
| 0-0 | b 1 | |
| 0-1 | ||
| 1-0 | ||
| 1-1 | b 2 |
Граф переходов представлен на рис. 3.7.
Рисунок 3.7 – Граф переходов R*S* -триггера
Аналитические выражения для условий переходов получают по ДТП.
Для дуги, что выходит из а 0 и входит в а 0 (то есть петли) – для перехода «0-0»: ;
для дуги из а 0 в а 1 – для перехода «0-1»: ;
для дуги из а J (Jarк) служит для установки триггера в «1», вход K (Кill) для установки в «0». Активным значением сигнала на входе является уровень 1. Одновременная подача двух активных сигналов на входы K и J не запрещена, при этом на выходе появляется инверсное значение состояния триггера . Подача двух нулей на входы триггера сохраняет его внутреннее состояние.
Рисунок 3.9 – Условное обозначение асинхронного JK -триггера
Полная таблица переходов (ПТП) (таблица 3.9), с помощью которой можно построить сокращенную таблицу переходов (таблица 3.10).
Таблица 3.9 – Полная таблица переходов JK -триггера
В таблице 3.11 представлена дополнительная таблица переходов.
Таблица 3.11 – Дополнительная таблица переходов JK -триггера
Матрица переходов представлена в таблице 3.12.
Таблица 3.12 – Матрица переходов J K-триггера
3.1.4 J*K* -триггер
Триггером типа J*K* называется триггер с двумя устойчивыми состояниями равновесия и двумя информационными входами (рис. 3.12). Вход J* в «1», вход *K для установки в «0». Активным значением сигнала на входе является уровень 0. Одновременная подача двух активных сигналов на входы K* и J* не запрещена, при этом на выходе появляется инверсное значение состояния триггера . Подача двух единиц на входы триггера сохраняет его внутреннее состояние.
Рисунок 3.12 – Условное обозначение асинхронного J*K* -триггера
Полная таблица переходов (таблица 3.13), с помощью которой можно построить сокращенную таблицу переходов (таблица 3.14).
Таблица 3.13 – Полная таблица переходов J*K* -триггера
Матрица переходов представлена в таблице 3.15.
Таблица 3.15 – Матрица переходов J*K*-триггера
| Q (t )-Q (t +1) | K* | J* |
| 0-0 | b 1 | |
| 0-1 | b 2 | |
| 1-0 | b 3 | |
| 1-1 | b 4 |
3.1.5 D -триггер
Триггером типа D (Delay - задержка)называется триггер с двумя устойчивыми состояниями равновесия и одним информационным входом D (рис. 3.13). Значения, поступающие на вход D, записываются на выход Q, т.е. триггер работает как повторитель.
Поскольку логическую функцию, даже такую простую, как Исключающее ИЛИ, можно реализовать различными способами, часто бывает нужно найти для нее самое простое решение, или, возможно, наиболее удобное схемное решение. Над этой проблемой бились многие светлые умы и в настоящее время существует несколько способов ее разрешения, включая алгебраические методы, реализуемые с помощью ЭВМ. При числе входов, не превышающем четырех, наилучшим методом является составление карты Карно. Этот метод позволяет также найти логическое выражение (если оно заранее неизвестно) по таблице истинности. Проиллюстрируем этот метод с помощью примера. Предположим, что требуется построить схему для мажоритарного подсчета голосов при баллотировке. Будем считать, что имеются три входа, работающие в положительной логике (на любом из них может быть 1 или 0) и выход (0 или 1). Выход равен 1, если 1 присутствует не менее чем на двух входах.
Шаг 1. Составим таблицу истинности
Здесь должны быть представлены все возможные сочетания и соответствующие им состояния выхода (или выходов). В том случае, когда состояние входа не оказывает влияния на выход, ставится X (любое значение).
Рис. 8.27. Карта Карно.
Шаг 2. Составим карту Карно. Она представляет собой нечто очень близкое к таблице истинности, но содержит переменные, которые расположены по двум осям. Переменные должны быть расположены таким образом, чтобы при переходе от каждого квадрата к соседнему менялось бы состояние только одного входа (рис. 8.27).
Шаг 3. Отметим на карте группы, содержащие 1 (можно также использовать и группы, содержащие 0). Три овала на рис. 8.27 определяют логические выражения АВ, АС и ВС.
схемная реализация ее показана на рис. 8.28. Этот результат кажется очевидным, когда он уже получен. Можно было бы составить выражение для нулей и вместо этого получить
Это выражение может оказаться полезным для случая, когда в каких-либо точках схемы имеются дополнения А, В и С.
Некоторые комментарии к картам Карно.
1. Ищите группы, содержащие 2, 4, 8 и т.д. квадратов. Они имеют простые логические выражения.
2. Логика будет тем проще, чем крупнее блок вы опишете.
3. Состыкуйте края карты Карно. Например, карта на рис. 8.29 описывается выражением С.
4. Блок «единиц», содержащий один или два «нуля», лучше всего описывается с помощью группировки, показанной на рис. 8.30. Этому блоку соответствует логическое выражение .
6. Карта Карно может и не привести к лучшему решению. Иногда более сложное логическое выражение имеет более простую схемную реализацию, например в случае, когда некоторые члены выражения уже сформированы схемой в виде логических сигналов, которые можно использовать в качестве входных. Кроме того, реализации Исключающего ИЛИ не очевидны из карты Карно. Наконец, при выборе логической структуры схемы определенную роль играют ограничения, связанные с конструкцией ИМС (например, когда в одном корпусе содержатся четыре -входовых вентиля). Когда используются такие программируемые логические устройства как ПМЛ для конструирования логических функций, внутренняя структура (программируемые вентили И и фиксированные вентили ИЛИ) сдерживает реализацию, которая могла бы быть применена.
Логика работы цифрового устройства описывается таблицей истинности, в которой показывается, какие логические уровни будут присутствовать на выходе цифровой схемы при заданных логических уровнях на входе этой схемы. Для того чтобы синтезировать схему с заданной логикой работы необходимо составить булево уравнение (в случаи если у схемы предполагается один выход) или систему уравнений (в случаи если выходов у схемы больше одного). Рассмотрим два способа составления уравнений из таблицы истинности: прямым и методом карт Карно.
Способ первый: составление уравнений из таблицы истинности прямым способом.
При составлении булевых уравнений прямым способом нужно учитывать, что получившиеся уравнения могут быть не минимально возможными.
Выделим алгоритм составления уравнения по таблице истинности:
- 1. Выделим те строки, в которых функция принимает истинное значение;
- 2. Составим для этих строк минтермы операндов;
- 3. Соединим минтермы при помощи операции дизъюнкции.
Рассмотрим пример.
Составим уравнение для устройства, имеющего один выход y, три входа x 0 , x 1 , x 2 . Логика работы устройства описана в таблицы 8.
Таблица 8 - Описание работы устройства
Составим функцию для строки три. В этой строке x 0 и x 2 принимают ложные значения, x 1 принимает истинное значение. Соединим эти операнды при помощи конъюнкции (элемент И):
Такая функции (принимающая истинное значения), в которую входит конъюнкция переменных или их отрицания называется минтермом.
Составим минтерм для строки пять:
Так как имеется два минтерма, соединим их при помощи дизъюнкции (элемент ИЛИ):
Что и будет уравнением устройства описанной таблицей истинности 8.
Выделим алгоритм составления системы уравнений по таблице истинности:
- 1. Определим количество выходов, следовательно, и количество уравнений в системе;
- 2. Для каждого из выходов составим уравнение:
- 2.1 Выделяем те строки, в которых функция принимает истинное значение;
- 2.2 Составлим для этих строк минтермы операндов;
- 2.3 Если минтермов больше одного, то соединим минтермы при помощи операции дизъюнкции.
- 3. Объединим полученные уравнения в систему.
Рассмотрим пример.
Пусть заданно устройство, логика работы которого описана в таблице 10. У устройства имеется два входа x 0 и x 1 , и два выхода y 1 , y 0 . Так как задано два выхода уравнения для каждого из выходов будут составляться отдельно. Составим систему уравнений, состоящую из двух уравнений.
Таблица 10 - Описание работы устройства
Выделим строки, в которых y 0 принимает истинные значения. y 0 принимает истинное значение только в одной строке, а именно в четвертой строке. Составим уравнение для y 0:
Выделим строки, в которых y 1 принимает истинные значения. Здесь имеется две строки: вторая и пятая. Для второй строки минтерм будет иметь вид. Для пятой. Объединим их с помощью операции ИЛИ, тем самым составив уравнение для y 1:
Остается составить систему уравнений, описывающую заданное устройство:
Способ второй: составление уравнений из таблицы истинности методом карт Карно.
Карты Карно представляет собой видоизмененную таблицу истинности, который позволяет минимизировать булевы функции. Это значит, что по сравнению с составлением булевых уравнений из не видоизмененной таблицы истинности, уравнения, полученные методом минимизации карт Карно, будут содержать меньше операций над операндами. Отметим, что последние утверждение не всегда верно, так как булева функция, полученная напрямую из таблицы истинности, может иметь минимально возможную форму.
Здесь не будет приводиться подробный алгоритм составления карт Карно для разного числа операндов, ограничимся рассмотрением примеров составления уравнений посредствам карт Карно для таблиц истинности, содержащих два, три, четыре операнда.
Перед тем как привести примеры, отметим основные положения, которыми будем руководствоваться при объединении областей (групп):
- 1. Область, которая подвергается объединению, должна состоять из логических единиц, при этом объединению подлежат только прямоугольные области, содержащие число логических единиц 2 n (т.е. 2 клетки, 4 клетки и т.д.).
- 2. Клетки, находящиеся на границе карты, граничат между собой, и могут быть объединены.
- 3. Все единицы должны быть объединены в какую-либо область, причем количество областей должно быть минимальным.
- 4. Одна ячейка может быть включена в разные области.
Названные положения касаются только случая объединения областей, состоящих из логических единиц.
Уравнение составляется следующим образом: в конъюнкцию области входит только те операнды, которые не меняют свои состояния на противоположные в пределах области. В случае если областей больше одного, между конъюнкциями областей ставятся дизъюнкции.
Система уравнений строится по тем же принципам, но карты Карно должны быть построены для каждого из выходов по отдельности.
Пример 1. Составим уравнение содержащих два операнда (или их инверсию) по таблице истинности 11 посредствам карт Карно.
Таблица 11 - Карта Карно для двух операндов
Составим карту Карно, для этого преобразуем таблицу истинности к виду, показанному на рисунке 18.
Рис. 18.
Здесь, горизонтальная часть отводится операнду x 1 , которое принимает значение 0 и 1 (). Вертикальной части таблицы аналогично соответствует x 0 .
Выделим те строки таблицы истинности 11, где y принимает значение логической единицы: строки два и три. Заметим, что во второй строке x 0 и x 1 принимает значение 00 (), в третьей строке x 0 и x 1 принимает значение 10 ().
Проставим в карте Карно 18 на пересечениях x 0 x 1 единицы в тех местах, где и (рис. 19).
Рис. 19.
Выделим область согласно положениям объединения областей (Рис. 20).
Рис. 20.
Получена одна область, составим уравнение. Операнд меняет в области свое значение на инверсию. Неинвертированный операнд x 1 не входит в область. Единственный операнд, который не меняет своего значения в полученной области - . Тогда уравнение примет вид:
Заметим, что если составлять уравнение из таблицы 10 прямым способом, то получилось бы не минимизированное уравнение:
которое можно преобразовать к минимально возможной форме путем применения аксиом и свойств алгебры логики.
Пример 2. Составим уравнение содержащих три операнда (или их инверсию) по таблице истинности 12 посредствам карт Карно.
Таблица 12 - Карта Карно для трёх операндов
Составим карту Карно дл трех операндов (рис. 21).
Рис. 21.
Для трех операндов горизонтальная часть соответствует операндам x 1 x 2 , которые принимают значение 00, 01, 11, 10. Важно отметить, что порядок 00, 01, 11, 10 должен соблюдаться в точности, изменения его на другой порядок не допускается. Вертикальной части таблицы соответствует операнд x 0 , принимающей значение 1 и 0).
Заполним карту Карно. Аналогично предыдущему примеру: выделим строки в таблице истинности 12, где y принимает истинное значение (вторая, третья, четвертая, седьмая строки). Проставим единицы в те ячейки карты Карно, которые соответствуют значениям операндов в этих строках (рис. 22).
Рис. 22.
Выделим области согласно положениям объединения областей (Рис. 23).
Рис. 23.
Выделено две области. В первой области полностью находится операнды и, объединим их конъюнкцией. Во второй области не меняют своего значения операнды, объединим их в конъюнкцию. Так как есть две области, объединим конъюнкции областей операцией дизъюнкции, тем самым составив конечное уравнение:
Пример 4. Составим уравнение содержащих четыре операнда (или их инверсию) по таблице истинности 13 посредствам карт Карно.
Таблица 13 - Карта Карно для четырех операндов
Минимизация функций с использованием карты Карно
При минимизации функций f 1 и f 2 из табл. 3.2 нам приходилось искать наиболее активные способы преобразования исходных выражений. Например, далеко не очевидным было решение повторить терм на первом шаге минимизации функции f 2. - Для того чтобы как можно быстрее получить минимальное выражение, представляющее логическую функцию нескольких переменных, можно воспользоваться графическим представлением таблицы истинности, называемым картой Карно. Для функции трех переменных карта Карно представляет собой прямоугольник, составленный из восьми квадратов, расположенных в два ряда по четыре в каждом (рис. 3.14, а). Каждый квадрат соответствует конкретному набору значений входных переменных. Например, третий квадрат в верхнем ряду представляет значения (x 1 х 2 , х 3) = (1, 1, 0).
Поскольку в таблице истинности функции трех переменных содержится восемь строк, карта должна состоять из восьми квадратов. Значения внутри квадратов - это значения функции при соответствующих значениях переменных.
Главная идея карты Карно заключается в том, что расположенные рядом по горизонтали и по вертикали квадраты отличаются значениями только одной переменной. Если два смежных квадрата содержат единицы, это означает возможность алгебраического упрощения соответствующей пары термов. Например, на карте функции f 2 (рис. 3.14, а) единицы в двух крайних слева квадратах верхнего ряда соответствуют термам и х 2 . Эта пара термов упрощается следующим образом:
что мы и сделали в предыдущем разделе при минимизации алгебраического выражения для функции f 2 . Минимизированное произведение, соответствующее группе квадратов, - это произведение входных переменных, значения которых одинаковы для всех квадратов этой группы. Если значение входной переменной х i равно нулю для всех квадратов группы, тогда переменная х i входит в результирующее произведение. Квадраты с левого края карты считаются смежными с квадратами с ее правого края. Так, в карте функции f 2 имеется группа из четырех единиц, состоящая из крайнего слева столбца и крайнего справа столбца карты, Соответствующая группа термов упрощается до одного терма , содержащего единственную переменную, поскольку только переменная х 2 имеет одинаковые значения во всех квадратах группы.
Рис. 3.14. Минимизация функций с использованием карт Карно: карта для трех переменных (а); карта для четырех переменных (б);
Карты Карно могут использоваться и для минимизации функций более чем трех переменных. Карту для четырех переменных можно составить из двух карт для трех переменных. Два примера таких карт показаны на рис. 3.14, б, и под каждой из них приведено минимальное выражение для представляемой ею функции Если на карте для трех переменных квадраты можно группировать по два и по четыре, то на карте для четырех переменных их можно группировать еще и по восемь. Пример такой группировки показан на карте функции g 3 Обратите внимание, что четыре угловых квадрата можно объединить в одну группу, как на карте функции g 2 , где на их основе составлен терм . Как и в случае карты для трех переменных, терм, соответствующий группе квадратов, представляет собой произведение переменных, значения которых одинаковы для всех квадратов этой группы. Так, в группе из четырех квадратов в правом верхнем углу карты функции g 2 во всех квадратах х 1 = 1 и х 3 = 0, поэтому эту группу представляет терм х1 . Остальные две переменные, х 2 и x 4 имеют в квадратах этой группы разные значения. Карты Карно можно использовать и для функций пяти переменных. В этом случае для представления функции используются две карты для четырех переменных: одна из них соответствует значению 0 пятой переменной, а другая – ее значению 1.
Общая процедура формирования на карте Карно групп из двух, четырех, восьми и т. д. квадратов определяется просто. Две смежные пары квадратов, содержащих единицы, можно объединить в группу из четырех квадратов. Две смежные группы по четыре квадрата можно объединить в группу из восьми квадратов.
В общем случае количество квадратов в группе должно быть равным 2 k , где k - целое число.
Теперь давайте рассмотрим процедуру получения с помощью карты Карно минимальной суммы произведений. Как видно на рис. 3.14, большей группе квадратов соответствует произведение меньшего числа переменных. Поэтому для получения минимального выражения нужно объединить все квадраты на карте, содержащие единицы, в как можно меньшее количество групп, выбирая наибольшие из них, так чтобы при этом охватить все единицы. Для примера рассмотрим карту функции g2 приведенную на рис. 3.14, б.
