eng
Содержание
Оглавление.
Предисловие к четвертому изданию
Список принятых сокращений
Глава 1 Основы теории проектирования микроэлектронных устройств на цифровых микросхемах.
1.1
Основы алгебры логики.
1.1.1
Основные аксиомы и тождества алгебры логики .
1.1.2
Аналитическая форма представлений булевых функций.
1.1.3
Упрощение (минимизация) булевых функций.
1.2
Основные положения и определения теории конечных автоматов.
Глава 2 Логические элементы интегральных микросхем.
2.1
Система параметров.
2.2
Интегральные элементы одноступенчатой логики.
2.2.1
Резистивно-транзисторные ИМС (RTL).
2.2.2
Диодно-транзисторные ИМС (DTL).
2.2.3
Интегральные микросхемы с эмиттерными связями (ECL).
2.2.4
Интегральные элементы инжекционной логики (И2Л).
2.3
Интегральные элементы двухступенчатой логики.
2.3.1
Диодно-транзисторные ИМС (DTL-2).
2.3.2
Транзисторно-транзисторные ИМС (TTL).
2.3.3
Транзистор - транзисторно-транзисторные ИМС (T-TTL).
2.4
Логические элементы на полевых транзисторах.
2.4.1
Логические элементы на одноканальных МДП – структурах.
2.4.2
Логические элементы на дополняющих МДП-транзисторах.
2.4.3
Логические элементы с нагрузочным КМДП-транзистором.
2.5
Логические элементы с вентильным и блокирующим КМДП – транзисторами.
2.6
Динамические элементы на МДП-транзисторах.
2.7
Схемы согласования логических элементов (преобразователи уровней).
2.7.1
Преобразователи логических сигналов TTL, T-TTL-элементов в сигналы МДП-элементов.
2.7.2
Преобразователи логических сигналов TTL-элементов в сигналы ECL-элементов, сигналов ECL-элементов в сигналы TTL-элементов.
2.7.3
Преобразователи логических сигналов TTL-элементов в сигналы (И2Л)- элементов, сигналов (И2Л)- элементов в сигналы TTL-элементов.
2.7.4
Логические элементы с тремя состояниями.
2.8
Схемотехнические особенности логических элементов, реализуемых в составе БИС.
Глава 3 Триггерные устройства цифровых систем.
3.1
Классификация триггерных устройств.
3.2
Требования и параметры, характеризующие триггерные устройства.
3.3
Статические триггеры.
3.3.1
Триггеры с управлением записью вида L, .
3.3.2
Триггеры с управлением записью вида [F].
3.3.3
Триггеры, в которых прием и фиксация информации разнесены во времени.
3.4
Импульсно- статические триггеры.
3.4.1
Триггеры видов Fi, i.
3.5
Триггеры на МДП и КМДП-элементах.
3.5.1
Статические триггеры.
3.5.2
Динамические триггеры.
3.6
Квазистатические триггеры.
3.7
Логические методы синтеза триггерных структур.
Глава 4 Регистры.
4.1
Параллельные регистры.
4.1.1
Однофазные параллельные регистры двухтактного действия.
4.1.2
Однофазные параллельные регистры однотактного действия.
4.1.3
Парафазные параллельные регистры.
4.2
Сдвигающие (последовательные) регистры и их классификация.
4.3
Сдвигающие регистры многотактного действия.
4.4
Сдвигающие регистры однотактного действия.
4.4.1
Сдвигающие регистры на триггерах вида LF.
4.4.2
Сдвигающие регистры на триггерах вида L .
4.4.3
Сдвигающие регистры на триггерах вида F, Fi.
4.4.4
Сдвигающие регистры на многотактных триггерах.
4.5
"Протяженные" сдвигающие регистры однотактного действия.
4.6
Однотактные ПСР на основе многотактных триггеров.
Глава 5 Счетчики.
5.1
Классификация счетчиков.
5.2
Счетчики на основе триггерных устройств.
5.3
Счетчики с переносом.
5.3.1
Счетчики с последовательным (сквозным) переносом.
5.3.2
Счетчики с параллельным переносом.
5.3.3
Счетчики с параллельно- последовательным переносом.
5.3.4
Счетчики на триггерах F, Fi, типов.
5.3.5
Вычитающие счётчики.
5.3.6
Работа счетчика, фиксирующего информацию по фронту , в режиме фиксации по фронту F.
5.4
Реверсивные счетчики.
5.5
Счетчики с произвольным коэффициентом счета.
5.5.1
Счетчики с естественным порядком счета.
5.5.1.1
Счетчики с Ксч≠2n , использующие R входы.
5.5.2
Счетчики с произвольным порядком счета.
5.5.3
Счетчики с принудительным насчетом.
5.5.4
Счетчики с начальной установкой кода.
5.5.5
Адресные счетчики.
5.6
Логические методы синтеза счетчиков.
5.7
Безвентильные счетчики.
5.8
Сдвигающие счетчики.
5.8.1
Счетчики на кольцевых сдвигающих регистрах.
5.8.2
Счетчики с постоянно взвешенными кодами.
5.8.3
Счетчики на регистрах с перекрестными связями.
5.8.4
Сдвигающие счетчики на совмещенных схемах.
5.8.5
Полиномиальные счетчики.
5.9
Счетчики, построенные по схеме регистр-сумматор.
5.10
Сдвигающие счетчики на основе специальных кольцевых схем.
Глава 6 Счетчики на основе многостабильных пересчетных схем.
6.1
Многостабильные схемы.
6.2
Многостабильные триггеры.
6.2.1
Однофазные многостабильные триггеры.
6.2.2
Многофазные многостабильные триггеры.
6.3
Многоустойчивые пересчетные схемы.
6.4
Многостабильные пересчетные схемы, постоенные по способу M-S.
6.5
Многостабильные пересчетные схемы, построенные по способу MТ и коммутирующих триггеров.
6.6
Многостабильные пересчетные схемы, построенные по способу MТ и запоминающего регистра.
6.7
Многостабильные пересчетные схемы, построенные на полусчетных кольцах.
6.8
Реверсивные многостабильные пересчетные схемы.
6.9
Многоразрядные счетчики на основе многостабильных пересчетных схемах.
6.10
Реверсивные счетчики на многостабильных пересчетных схемах.
6.11
Синтез счетчиков без избыточных кодовых комбинаций на основе многостабильных пересчетных схем.
Глава 7 Дешифраторы, коммутаторы, преобразователи кода и схемы сравнения.
7.1
Линейные дешифраторы.
7.2
Прямоугольные или матричные дешифраторы.
7.3
Пирамидальные дешифраторы.
7.4
Логические коммутаторы (мультиплексоры).
7.5
Преобразователи (шифраторы) кода.
7.6
Устройства сравнения и контроля нечетности.
Глава 8 Сумматоры.
8.1
Одноразрядные сумматоры.
8.2
Последовательные сумматоры.
8.3
Параллельные сумматоры.
8.3.1
Параллельные сумматоры с последовательным переносом.
8.3.2
Сумматоры с параллельным переносом.
8.3.3
Сумматоры с групповым переносом.
8.4
Накапливающие сумматоры.
8.5
Двоично-десятичные сумматоры.
Глава 9 Распределители сигналов.
9.1
Параметры и классификация распределителей сигналов.
9.2
Распределители, построенные по схеме счётчик-дешифратор.
9.2.1
Распределители на регистрах с перекрестными связями.
9.2.2
Распределители на двоичных счётчиках с дешифратором.
9.2.3
Распределители на многостабильных пересчетных схемах.
9.3
Бездешифраторные распределители сигналов.
9.3.1
Распределители на кольцевых схемах.
9.3.2
Бездешифраторные распределители сигналов на основе счётчика Джонсона.
9.3.3
Бездешифраторные распределители сигналов на основе многостабильных триггеров и пересчетных схем.
9.4
Сравнительная оценка экономичности различных вариантов распределителей сигналов.
Глава 10 Импульсные устройства.
10.1
Устройства выделения одиночного импульса из серии.
10.2
Устройства выделения фронтов.
10.3
"Укорачивающие " цепи.
10.4
Устройства расширения импульсов.
10.5
Устройства увеличения крутизны фронтов.
10.6
Устройства задержки сигналов.
10.7
Устройства формирования одиночных импульсов при замыкании контактов.
10.8
Устройства обнуления при включении питания .
10.9
Устройства формирования пакета импульсов.
10.10
Одновибраторы.
10.11
Импульсные генераторы.
10.11.1
Общие сведения, показатели качества, схемы RC, LC генераторов.
10.11.2
Кварцевые генераторы: общие сведения, расчетные формулы, схемы.
10.11.3
Генератор трехфазного напряжения со сдвигом фаз на 120°.
10.11.4
Устройства контроля работы генераторов.
10.12
Регулируемая линия задержки.
10.13
Деление частоты на числа Nд=n+0,5.
10.14
Получение меандра при делении на числа 2n+1.
10.15
Формирование "привязанных" тактовых импульсов.
10.16
Приём цифровой информации.
10.17
Схема привязки синхроимпульсов к сигналам "ПУСК".
10.18
Выделение фронтов F и цифровым методом.
10.19
Увеличение крутизны фронтов триггером Шмитта.
10.20
Схема обнуления на триггере Шмитта.
10.21
Расширение импульсов триггером Шмитта.
10.22
ШИМ для управления силовыми ключами преобразователя.
10.23
Каскады управления силовыми ключами ВИП.
10.24
Восстановление длительности импульсов в последовательности передаваемых сигналов.
10.25
Удвоение частоты.
Глава 11 Вторичные источники питания.
11.1
Общие сведения, блок схема ВИП.
11.2
Функциональное назначение узлов ВИП.
11.3
Работа блок схемы ВИП.
11.4
Функциольные узлы ВИП, схемная реализация, описание.
11.5
Преобразователь напряжения.
11.6
Транзистор и особенности его работы в различных стадиях.
11.6.1
Транзистор в стадии включён.
11.6.2
Транзистор в стадии выключен.
11.6.2.1
Запирание транзистора подачей на базу отрицательного напряжения Uбэ<0.
11.6.2.2
Запирание транзистора отключением базового вывода (режим "плавающей", оборванной базы).
11.6.2.3
Запирание транзистора соединением базы с эмиттером.
11.6.2.4
Запирание транзистора включением резистора между базой и эмиттером.
11.6.3
Транзистор в активном режиме.
11.6.4
Транзистор в переходном режиме выключен-включён.
11.6.5
Транзистор в переходном режиме включён-выключен.
11.6.6
Выбор транзистора.
11.7
Работа преобразователя.
11.8
Трансформатор.
11.8.1
Общие сведения, основные уравнения, эквивалентная схема.
11.8.2
Требования к трансформатору, процессы в магнитопроводе, потери в трансформаторе, переходные процессы, К.П.Д. трансформатора.
11.9
Расчёт трансформатора.
11.10
Сглаживающий фильтр.
11.10.1
Общие сведения.
11.10.2
Схемы фильтров.
11.10.3
Реактивное сопротивление, физический смысл.
11.10.4
Показатели качества.
11.10.5
Работа с сигналами прямоугольной формы.
11.10.6
Выбор элементов фильтра, расчёт дросселя фильтра,краткие выводы.
11.11
Схемы вторичных источников питания.
11.11.1
ВИП без обратной связи.
11.11.2
Регулировка ВИП.
11.11.3
Схемы ВИП с обратной связью.
11.11.4
Регулировка ВИП с обратной связью.
11.12
Сервисные схемы ВИП
11.12.1.
Защита ВИП от повышенного входного напряжения.
11.12.2.
Защита ВИП от пониженного входного напряжения.
11.12.3.
Защита от повышенного напряжения на выходе ВИП.
11.12.4.
Ограничение тока включения.
11.12.5.
Последовательность включения и выключения вторичных номиналов ВИП.
11.12.6
Защита ВИП от перегрузок по току и короткого замыкания.
11.12.7
Управлением включением и отключением ВИП.
11.12.8
Защита ВИП при плавном (медленном) нарастании первичного напряжения.
11.12.9.
Экономичный по числу интегральных схем ВИП с дополнительными функциями.
Глава 12 Передача и прием информации по проводным линиям связи.
12.1
Блок схема канала связи.
12.1.1
Линия связи.
12.2
Схемная реализация длинной линии на основе Э.В.П.
12.2.1
Защита линии связи от помех.
12.3
Кодирование информации.
12.3.1
Передача и приём информации в импульсном (типа F) униполярном коде.
12.3.2
Кодирование информации импульсами F и .
12.4
Передача и приём информации в коде Манчестер-II фронтами F, .
12.4.1
Приёмное устройство (декодер).
12.5
Передача и приём информации и синхрочастоты по одной Л.С. способом раздельного кодирования нулей и единиц.
Глава 13 Разработка схемы цифрового устройства и выбор элементной базы.
13.1
Основные параметры элементной базы ИС.
13.2
Разработка электрической схемы цифрового устройства
Предисловие.
Нарастающий интерес к микроэлектронике, вновь появившийся за последние 5 лет, побудил авторов к переизданию книги "Микроэлектронные схемы цифровых устройств", которая, по отзывам читателей, представляет практический интерес для разработчиков цифровой аппаратуры.
Основной материал книги не претерпел изменений за исключением нескольких параграфов.
Заново переписан параграф 3.4 "Импульсно-статические триггеры", как наиболее экономичные по числу ИС.
В главу 5 "Счётчики" введены параграфы:
параграф 5.3.4 "Счётчики на триггерах F,Fi, LF типов",
параграф 5.3.5 "Вычитающие счётчики",
параграф 5.5.11 "Счётчики с Ксч≠2n, использующие R входы".
Существенно расширена глава 10 "Импульсные устройства" за счет введения в её состав целого ряда новых схем по обработке информации (14схем).
Заново переписан и значительно расширен параграф 10.11. "Импульсные генераторы".
Опыт работы авторов в области разработки цифровой аппаратуры показал, что разработчик такой аппаратуры постоянно сталкивается с вопросами связанными с передачей информации между блоками и со вторичными источниками питания, знание которых расширяет кругозор разработчика и существенно помогает при проектировании цифровых комплексов.
Поэтому авторы решили отразить эти вопросы в новом издании книги.
В состав книги введены две новые главы:
глава - 11 Вторичные источники питания (ВИП).
глава - 12 Передача и прием информации по проводным линиям связи.
В главе 11 приводится описание узлов ВИП, описание и расчет трансформатора, дросселя фильтра, а также рассмотрены особенности работы транзистора в составе преобразователя.
Схемная часть представленных материалов отражает опыт авторов в данных областях, публикуется впервые и будет полезна инженерам и студентам соответствующих специальностей.
Главы 1,2,7 и 8 написаны И.Н. Букреевым, Б.М. Мансуровым и В.И. Горячевым совместно, гл. 3-5 и 9 В.И. Горячевым и Б.М. Мансуровым совместно, гл 6,10,11,12 – В.И. Горячевым
Глава 1
Основы теории проектирования микроэлектронных устройств на цифровых микросхемах
1.1. Основы алгебры логики
Как известно, алгебра логики (булева алгебра), в отличие от обычной алгебры, оперирует всего двумя переменными, причем эти переменные могут принимать только два значения типа да-нет, включено-выключено и т. п. При этом для удобства математического описания эти переменные принято обозначать 1 и 0.
Булева алгебра наиболее эффективна для описания функционирования различных электронных устройств, которые в силу специфики работы могут находиться в состоянии либо «включено», либо «выключено». Основным понятием булевой алгебры является понятие переключательной функции. Переключательной (булевой, двоичной) функцией называют функцию вида f(X1, ..., Xn)1, которая, как и ее переменные (аргументы) Х1 ..., Хп, может принимать два значения: 0 или 1. Как и всякая функция, булева функция имеет область определения. Поскольку аргументы переключательной функции могут принимать только два значения, то область определения булевой функции выражается совокупностью комбинаций этих переменных и, следовательно, она всегда конечна. В свою очередь, каждую совокупность комбинаций аргументов называют набором. В итоге для любой переключательной функции от п переменных существует 2п различных наборов. Наборы аргументов нумеруют двоичными числами, разрядами которых являются сами аргументы переключательных функций. В качестве примера в табл. 1.1 и 1.2 представлены всевозможные наборы переключательных функций от одного и двух переменных.
Таблица 1.1
Номер набора Аргумент
X1
0 0
1 1
Таблица 1.2
Номер набора Аргумент
X1 X2
0 0 0
1 0 1
2 1 0
3 1 1
Поскольку любая булева функция определена на 2n наборах и сама принимает только два значения (0 или 1), то число булевых функций от п переменных равно . Например, при n = 1 (т. е. для булевой функции от одной переменной) существует 22 = 4 различных булевых функций, каждая из которых определена на 21 наборах (см. табл. 1.1).
Булевы функции от одной переменной (сингулярные функции), а также их условное обозначение и название приведены в табл. 1.3. Действительно, как следует из табл. 1.3, существует всего четыре сингулярные функции от одной переменной X: константа 0, переменная X, инверсия X, константа 1. Функции константа 0 и константа 1 названы так по той причине, что любому из двух ее наборов аргументов Х = 0 и Х = 1 ставится в соответствие постоянное значение функции, равное 0 для функции константа 0 и 1 для функции константа 1.
Таблица 1.3
Функция X Условное обозначение Название функции
0 1
f0(X) 0 0 0 Константа 0
f1(X) 0 1 X Переменная X
f2(X) 1 0 X Инверсия X
f3(X) 1 1 1 Константа 1
Функция f1(X) — переменная X на одном наборе Х = 0 равна 0, а на другом наборе Х = 0 равна 1, т. е. повторяет переменную X. Функция f2(X) принимает значение 1 на наборе Х = 0 и значение 0 на наборе Х = 1. Функция, выполняющая такую операцию над аргументом, носит название отрицания или инверсии и является одной из основных функций булевой алгебры. При п = 2, т. е. для булевых функций от двух переменных X1 и Х2 (бинарные функции), существует 24 = 16 различных функций, каждая из которых определена на четырех наборах (см. табл. 1.2). Булевы функции двух переменных, их условное обозначение и название даются в табл. 1.4. Заметим, что среди этих 16 функций фактически бинарными являются 10, а остальные зависят от двух переменных формально и являются либо константами (f0 и f15), либо сингулярными, т. е. повторениями переменных (f3 и f5) и их отрицаниями (f12 и f10). К наиболее часто встречающимся булевым функциям от двух переменных относятся функции f1 (конъюнкция), f1 (дизъюнкция) и f6 (логическая неравнозначность, Исключающее ИЛИ, сложение по модулю 2).
Таблица 1.4
Функция Наборы Обозначение функции Название функции
X1 0 0 1 1
X2 0 1 0 1
f0(X1, X2) 0 0 0 0 0 Константа 0
f1(X1, X2) 0 0 0 1 X1 X2, X1 X2 Конъюнкция (логическая операция И)
f2(X1, X2) 0 0 1 0 X1 X2 Запрет по Х2 (отрицание импликации)
f3(X1, X2) 0 0 1 1 X1 Переменная Х1
f4(X1, X2) 0 1 0 0 X2 X1 Запрет по X1
f5(X1, X2) 0 1 0 1 X2 Переменная Х2
f6(X1, X2) 0 1 1 0 X1 Z X2 Сумма по модулю 2
f7(X1, X2) 0 1 1 1 X1 + X2, X1 X2 Дизъюнкция (логическая операция ИЛИ)
f8(X1, X2) 1 0 0 0 X1 X2 Стрелка Пирса (отрицание дизъюнкции)
f9(X1, X2) 1 0 0 1 X1 X2 Эквивалентность
f10(X1, X2) 1 0 1 0
Отрицание Х2 (функция НЕ)
f11(X1, X2) 1 0 1 1 X2 X1 Импликация от Х2 к X1
f12(X1, X2) 1 0 1 1
Отрицание Х1 (функция НЕ)
f13(X1, X2) 1 1 0 1 X1 X2 Импликация от X1 к Х2
f14(X1, X2) 1 1 1 0 X1/X2 Штрих Шеффера (отрицание конъюнкции)
f15(X1, X2) 1 1 1 1 1 Константа 1
Из табл. 1.4 следует, что, например, функция f1 принимает значение 1 только на одном из четырех возможных наборов переменных, а именно на наборе X1 = 1 и Х2 = 1. На всех остальных наборах ее значение равно 0. Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X1 и Х2), появится только тогда, когда сигнал 1 будет одновременно присутствовать на двух входах. Элемент, реализующий эту функцию, носит название схемы И (логическое умножение).
Функция f7 принимает значение 1 на всех наборах переменных, кроме одного Х1 + 0 и Х2 + 0. Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X1 и Х2), появится только тогда, когда сигнал 1 будет присутствовать хотя бы на одном из входов. Элемент, реализующий эту функцию, носит название схемы ИЛИ (логическое сложение).
Из остальных функций табл. 1.4 выделим функцию f12. Элемент, реализующей ее, носит название схемы НЕ. Применительно к преобразованию сигналов данная функция означает, что сигнал на выходе устройства, имеющего один вход X1 (или X2 для f10), появится только в том случае, если сигнал 1 на входе отсутствует. При наличии сигнала 1 на входе, на выходе схемы НЕ будет действовать сигнал 0.
Некоторые из приведенных в табл. 1.4 функций могут быть распространены и на большее число независимых переменных. К таким функциям можно отнести, например, f1, f7, f8, f10, и др.; их можно записать в виде2
f1 = Х1 Х2...Хп = Х1 Х2...Хп;
f7 = Х1 + Х2 + ... + Хп = Х1 Х2 ... Хп;
Применительно к преобразованию сигналов, например, функция f1 от п переменных означает, что сигнал 1 на выходе устройства (в данном случае уже имеющего п входов) появится только при его присутствии одновременно на всех входах. Физическая реализация этой функции, как и функции f1 от двух переменных, носит название схемы И. Обращаясь к табл. 1.4, замечаем, что некоторые из приведенных функций получаются посредством декомпозиции или перенумерации аргументов булевых функций. Так, функция f13 может быть получена из функции f11, если поменять местами аргументы Х1 и Х2. Функция f14 (штрих Шеффера) может быть получена из функции f12 посредством замены значений аргумента Х1 значениями функции f1. В общем случае операция замены аргументов одной функции другими функциями носит название суперпозиции. Например, если
f = f(Y1, Y2), a Y1 = Y1(X1, X2) и Y2 = Y2(X3, X4),
то очевидно, что
f = f(X1, X2, X3, X4)
Последнее показывает, что многократное применение метода суперпозиции позволяет получить более сложные булевы функции. При этом возникает вопрос, возможен ли набор таких простых булевых функций, на основе которых можно получить любую сколь угодно сложную функцию. Этот вопрос связан с одним из основных понятий булевой алгебры — понятием функциональной полноты системы булевых функций. Система булевых функций будет называться полной, если на ее основе можно получить любую функцию, используя лишь операцию суперпозиции. Можно привести несколько систем булевых функций, обладающих функциональной полнотой. Одной из таких систем является система А. Эта система состоит из трех булевых функций и носит название основного функционально полного набора (ОФПН):
В общем случае одна из приведенных в этой системе функций, а именно дизъюнкция или конъюнкция, является лишней, поскольку ее исключение не приводит к нарушению функциональной полноты системы. Действительно, кроме этой системы, функциональной полнотой будут обладать системы булевых функций вида В и С, включающие всего две функции:
Системы В и С будут функционально полными в силу того, что операцию конъюнкции, отсутствующую в системе В, и операцию дизъюнкции, отсутствующую в системе С, можно получить на основе имеющихся двух функций в соответствии с правилами алгебры логики. Наконец, можно привести несколько систем, состоящих всего из одной функции, которые также обладают функциональной полнотой. Примером такой функции являются функция (отрицание конъюнкции) и функция (отрицание дизъюнкции). Недостающие функции дизъюнкции, конъюнкции и отрицания для этих систем можно получить на основе известных правил алгебры логики. Можно привести и другие функционально полные системы, например систему, состоящую из функций запрета и константы единицы, запрета и инверсии и т. п.
1.1.1. Основные аксиомы и тождества алгебры логики
Булева алгебра позволяет не только математически описывать переключательные функции, но и преобразовывать их, давая возможность реализовывать эти функции на различных функционально полных системах. Поскольку переключательные функции в конечном счете отражают определенные логические связи между различными узлами цифровых устройств, то тем самым булева алгебра позволяет преобразовывать эти связи и, следовательно, она является аппаратом, позволяющим разработчику осуществлять выбор оптимального варианта. В настоящее время наиболее полно разработаны методы преобразования выражений, которые содержат переключательные функции ОФПН. Применительно к такому набору булева алгебра располагает рядом законов, основные из которых приводятся ниже.
Законы дизъюнкции:
• 0 + 0 = 0;
• 1 + 0 = 1;
• 1 + 1 = 1;
• 0 + Х = Х — закон сложения с 0;
• 1 + Х = Х — закон сложения с 1;
• Х + Х = Х — закон тождества для сложения;
• Х + Х + ... + Х = Х;
• — закон исключенного третьего;
• X + Y = Y + X — переместительный (коммутативный) закон для сложения;
• X + Y + Z = (X + Y) + Z = X + (Y + Z) — сочетательный (ассоциативный) закон для сложения.
Законы конъюнкции:
• 0 0 = 0;
• 1 0 = 0;
• 1 1 = 1;
• 0 Х = 0 — закон умножения на 0;
• 1 Х = Х — закон умножения на 1;
• — законы тождества для умножения;
• — закон противоречия;
• X Y = Y X — переместительный (коммутативный) закон для умножения;
• X Y Z = X (Y Z) = (X Y) Z — сочетательный (ассоциативный) закон для умножения.
Законы инверсии:
•
• — закон двойного отрицания.
Законы преобразования выражений, содержащих операции конъюнкции, дизъюнкции и отрицания:
1. Законы поглощения:
• X + X Y = X;
• X (X + Y) = X.
2. Законы склеивания:
•
•
3. Операции обобщенного склеивания:
•
•
4.
5. Законы двойственности (формулы де Моргана):
•
•
Законы двойственности можно записать и в более общем виде:
•
•
6. Закон действия со скобками:
• X1 X2 + X1 X3 = X1 (X2 + X3).
Перечисленные формулы приводятся без доказательств, но читатель может легко убедиться в их справедливости, подставив в правые и левые части равенств значения переменных 0 и 1. Эти формулы далеко не исчерпывают возможных булевых равенств, однако, они являются основными, и их знание необходимо для овладения техникой преобразования булевых функций.
1.1.2. Аналитическая форма представления булевых функций
При решении конкретных технических задач булевы функции, отражающие логические связи, наиболее часто задаются в табличной форме. Однако такая форма задания функции, при всей ее наглядности, не позволяет ответить на вопрос, каким же образом реализовать и если можно, то упростить данную функцию? Для реализации и последующего упрощения булеву функцию следует представить в аналитической форме в одном из функционально полных наборов. Поскольку в настоящее время методы представления и минимизации функций наиболее полно разработаны в базисе ОФПН, то именно этот базис в дальнейшем и будет рассматриваться.
Допустим, что в ходе решения задачи требуется реализовать переключательную функцию, заданную табл. 1.5. Как видно из таблицы, функция должна принимать значение 1 только на 3-м, 6-м и 7-м наборах. На всех остальных наборах ее значение равно 0. Возникает вопрос, каким образом записать эту функцию аналитически, т. е. представить в виде формулы. Применительно к основному базису, содержащему элементы дизъюнкции, конъюнкции и отрицания, доказано, что любая переключательная функция, предварительно заданная в табличной форме, может быть записана аналитически в двух формах, получивших название канонических (нормальных): в дизъюнктивной совершенной нормальной форме (ДСНФ) и в конъюнктивной совершенной нормальной форме (КСНФ). Аналитическая запись функций в виде ДСНФ и КСНФ предполагает представление этих функций посредством суперпозиции специально вводимых вспомогательных функций: минтермов и макстермов. Минтермы часто называют конституентами единицы, а макстермы — конституентами нуля. Минтермом называют булево произведение (конъюнкцию) от п переменных, в котором каждая переменная входит один раз в прямой или инверсной форме. Макстермом называют булеву сумму от п переменных, в которой каждая переменная входит один раз в прямой или инверсной форме. Из сказанного следует, что переключательная функция от п переменных имеет число минтермов и макстермов, равное числу наборов, на которых она определена, т. е. 2п минтермов и макстермов. В качестве примера в табл. 1.6 и 1.7 даются минтермы и макстермы двух переменных X1 и Х2.
Таблица 1.5
Номер набора Аргументы Значение функции на i-ом наборе (fi) Номер набора Аргументы Значение функции на i-ом наборе (fi)
X1 X2 X3 X1 X2 X3
0 0 0 0 0 4 1 0 0 0
1 0 0 1 0 5 1 0 1 0
2 0 1 0 0 6 1 1 0 1
3 0 1 1 1 7 1 1 1 1
Таблица 1.6
Аргументы Минтермы
X1 X2 m0 m1 m2 m3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 1
1 1 0 0 0 1
Таблица 1.7
Аргументы Макстермы
X1 X2 M0 M1 M2 M3
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
Согласно приведенным определениям минтермы и макстермы двух аргументов выражаются формулами:
Запись переключательной функции в виде ДСНФ означает, что любая переключательная функция, заданная табличным способом, может быть представлена в виде логической суммы конъюнктивных членов. При этом каждый из этих членов представляет собой произведение значения функции на i-м наборе на i-й минтерм. Поскольку переключательная функция имеет 2п минтермов, то аналитическая запись функции в ДСНФ имеет вид
Таким образом, функция, заданная таблицей состояний (см. табл. 1.5), запишется аналитически следующим образом:
Из сказанного становятся понятны отдельные термины сокращенного представления функции в виде ДСНФ. В частности, термин «дизъюнкция» указывает на то, что внешней функцией разложения является дизъюнкция, а внутренней — конъюнкция. Термин «совершенная» указывает на то, что дизъюнктивные члены формируются из всех аргументов X1 ... Xn, т. е. на основе минтермов. Термин «нормальная» указывает на то, что форма записи является двухуровневой, т. е. дизъюнкция конъюнкций. Аналитическая запись функции в виде КСНФ означает, что переключательная функция, заданная табличным способом, может быть представлена в виде логического произведения (конъюнкцией) дизъюнктивных членов. При этом каждый из этих членов представляет собой сумму значений функции на i-м наборе и i-гo макстерма. Поскольку от п аргументов существует 2п макстермов, то аналитическая запись функции в КСНФ имеет вид
В итоге, для рассматриваемого примера (см. табл. 1.5)
или
Сопоставление двух форм записи одной и той же переключательной функции показывает, что запись функции в виде КСНФ более громоздкая, так как содержит большее число членов. Последнее объясняется тем, что число наборов, на которых переключательная функция равна 0, значительно больше числа наборов, на которых она равна 1. Для случая, когда число наборов, на которых функция равна 0, было бы меньше числа наборов, на которых функция равна 1, более предпочтительным оказывается представление функции в виде КСНФ. Из сказанного следует, что обе формы представления функций фактически эквивалентны. Однако при минимизации функций более удобной оказывается запись их в виде ДСНФ. Поэтому в дальнейшем будут рассматриваться только такие формы.
1.1.3. Упрощение (минимизация) булевых функций
Как было показано выше, аналитическая запись рассматриваемой функции, представленной в ДСНФ, имеет вид
(1,1)
Для реализации этой функции (рис. 1.1) потребуются три элемента И, один элемент ИЛИ и два элемента НЕ. Возникает вопрос, можно ли эту функцию, предварительно заданную в ДСНФ, представить в более компактном виде, чтобы выполнялась та же функция, но при ее реализации требовалось бы меньшее число элементов. Процесс нахождения выражений, выполняющих ту же логическую функцию, что и первоначально заданная, но для реализации которых требуется меньшее число элементов, и составляет сущность процесса минимизации. Попытаемся это сделать для приведенной выше функции (1.1). Приняв во внимание равенство Х + Х = Х, добавим к этому выражению еще один конъюнктивный член X1 X2 X3:
Теперь преобразуем полученное выражение, используя приведенные выше формулы:
(1.2)
Реализация уже этой функции потребует значительно меньшего числа элементов (рис. 1.2, а, б), что подчеркивает неэкономичность реализации функций алгебры логики, представленных в виде ДСНФ.
Как видно из рис. 1.1 и 1.2, одна и та же функция реализуется далеко неоднозначно по аппаратурным затратам. Это говорит о том, что, по-видимому, существует такая форма представления функции, которая выполняется с наименьшими аппаратурными затратами. Применительно к рассматриваемой функции такой формой является представление ее в виде скобочной формулы f = X2 (X1 + X3).
В наиболее общем виде задачей минимизации является получение схем минимальной стоимости. Однако в такой постановке задача чрезвычайно сложна, и в настоящее время общие методы ее решения отсутствуют [2]. Последнее в значительной степени объясняется тем, что при решении такой задачи необходимо иметь в виду, что всякая логическая операция реализуется на логических элементах (ЛЭ), параметры которых имеют определенные ограничения по числу входов, нагрузочной способности, быстродействию, потребляемой мощности и т. п. Поэтому наиболее часто процесс минимизации рассматривается в более упрощенной постановке, а именно в отыскании дизъюнктивных форм функций, содержащих по возможности меньшее число букв. В настоящее время известно достаточно большое число методов минимизации [4, 5]. Все они базируются на тождественных преобразованиях логических выражений и подразделяются на систематические и несистематические методы минимизации.
Примером несистематического метода минимизации является метод расчленения и проб. В соответствии с этим методом функции упрощают до минимальной только на основании аксиом и тождеств алгебры логики. Этот метод преобразования функций по существу аналогичен преобразованию выражений в традиционной алгебре и требует от разработчика знания не только возможно большего числа тождеств и аксиом алгебры логики, но и значительной изобретательности (эвристичности) и опыта. Основным недостатком такого метода является то, что зачастую трудно определить, является ли полученное выражение минимальным или имеются пути его дальнейшего упрощения. В силу указанных причин данный метод не получил широкого распространения и его полностью вытеснили систематические методы. Достоинством таких методов является то, что они описываются строгими алгоритмами, т. е. являются формализованными, и, следовательно, здесь имеется возможность применения ЭВМ, что особенно важно при минимизации функций с большим числом переменных.
К наиболее широко распространенным систематизированным методам следует отнести метод Квайна-Маккласки. Этот метод достаточно подробно рассмотрен в ряде источников [2, 5, 8], поэтому здесь мы остановимся на рассмотрении нескольких основных его этапах и определениях, которые потребуются в дальнейшем при рассмотрении других методов. Нахождение минимальной формы по этому методу осуществляется в три этапа. На первом этапе исследуется вид задания функции. И если она задана произвольной формой в булевой алгебре, например:
(1.3)
то с помощью тождественных соотношений, рассмотренных выше, она должна быть развернута в виде ДСНФ. В частности, применив к выражению (1.3) правило де Моргана, получим
(1.4)
Полученное в результате преобразований выражение представляет собой запись функции в дизъюнктивной нормальной форме ДНФ. Для записи функции в виде ДСНФ, т. е. суммы минтермов, необходимо провести операцию развертывания, которая заключается в умножении на выражение членов функции, не являющихся минтермами. Поскольку в выражении (1.4) ни один из членов не является минтермом, то для записи функции в виде ДСНФ необходимо умножить первый член на выражение , второй на , а третий и четвертый на :
Второй этап заключается в нахождении сокращенной ДНФ (СДНФ). Проиллюстрируем его конкретным примером. Найдем СДНФ функции:
Функция уже задана в виде ДСНФ, т. е. необходимость выполнения первого этапа отпадает. Далее осуществляются операции склеивания и поглощения. Проведем операцию склеивания в следующей последовательности:
выполним всевозможные склеивания 1-го члена X1 X2 X3 с остальными;
выполним всевозможные склеивания 2-го члена с остальными, кроме первого;
выполним всевозможные склеивания третьего члена с остальными, кроме первого и второго. Напомним, что операция склеивания осуществляется по формуле
Результат склеивания запишем в виде
Как видно из этих выражений, склеиваются всегда два минтерма, отличающиеся друг от друга только одним аргументом, и только таким, который обязательно в один минтерм входит в прямой, а в другой — в инверсной форме. Такие минтермы принято называть смежными, а конъюнкции, получаемые от их склеивания, — импликантами.
После операции склеивания проводится операция поглощения, которая выполняется с помощью формулы
Х1 Х2 + Х2 = Х2.
Для проведения операции поглощения необходимо заданную функцию представить в виде
где первые три члена получены от проведения операции склеивания. В этом выражении произведение X1 X3 поглощает члены и , произведение поглощает члены и и произведение поглощает члены и . Таким образом, в результате операции поглощения все минтермы функции оказались поглощены импликантами, что позволяет записать исходную функцию теперь уже в виде
(1.5)
К полученной формуле повторно применяют операции склеивания и последующего поглощения, и эта процедура выполняется до получения простых импликант. В рассматриваемом примере ни одно из произведений-импликант не склеивается между собой. Такие импликанты называют простыми, а функцию (1.5), состоящую из дизъюнкции простых импликант, — сокращенной ДНФ (СДНФ).
Однако СДНФ еще не минимальная форма записи функции. Поэтому дальнейший этап минимизации связан с упрощением СДНФ и заключается в устранении избыточных простых импликант из СДНФ. Функции, полученные в результате устранения из сокращенной ДНФ избыточных импликант, принято называть тупиковыми ДНФ. Наиболее распространенным методом получения тупиковых форм является метод импликантных матриц [1, 8]. Импликантная матрица представляет собой таблицу, включающую в себя все минтермы, расположенные горизонтально, и все простые импликанты, расположенные вертикально. Для рассматриваемого примера такая матрица показана в табл. 1.8. Для каждой импликанты находят минтермы, которые ими поглощаются, и против каждого поглощенного минтерма ставят знак . Например, импликанта X1 X3 поглощает минтермы X1 X2 X3 и , и против каждого из них ставят знак V. Чтобы найти тупиковые формулы, необходимо в импликантной матрице найти минимальное число импликант, которые поглощают знаком все минтермы.
Таблица 1.8
Простые импликанты Минтермы
X1 X2 X3
X1 X3
Для матрицы (см. табл. 1.8) такими импликантами будут произведения X1 X3 и , причем первое из них поглощает минтермы X1 X2 X3 и , а второе — остальные два минтерма и . В результате, тупиковая форма рассматриваемой функции запишется в виде
Поскольку в нашем примере имеется всего одна тупиковая форма, то она и будет минимальной. В общем случае переключательная функция может иметь не одну, а несколько тупиковых форм, и тогда искомой минимальной ДНФ будет та, которая содержит наименьшее число букв.
Следует отметить, что рассмотренный метод наиболее эффективен при числе переменных больше шести. Для функций с числом переменных до шести (такие функции являются наиболее распространенными) минимизация обычно осуществляется по табличному методу Вейча-Карно. Этот метод, первоначально предложенный Вейчем и затем усовершенствованный Карно, в отличие от рассмотренного выше, не требует первоначального представления функции в виде ДСНФ. Особенностью этого метода является также то, что в его основу положена табличная запись членов минимизируемого выражения, представляемого в виде ДНФ. Карты Карно представляют собой прямоугольные таблицы, составленные из ячеек, число которых равно числу минтермов минимизируемого выражения. Хотя метод Вейча-Карно и является табличным, однако, и здесь упрощение осуществляется за счет все тех же операций склеивания и поглощения. Правда, в данном случае это достигается благодаря такой записи минтермов в ячейки таблицы, когда каждую ячейку со всех сторон окружают ячейки со смежными минтермами.
Один из способов записи минтермов по методу Вейча-Карно показан на рис. 1.3. В качестве примера здесь показана карта Карно для функций от четырех аргументов: X1, X2, X3, X4. Нетрудно видеть, что любой из 16 минтермов находится как бы в окружении со всех четырех его сторон смежными минтермами, расположенными в соседних (смежных) ячейках. Например, смежными ячейками (клетками) для минтерма т8 будут клетки т12, т9, т0, и т10, так как каждый из минтермов, записанных в этих клетках, отличается от минтерма т8 формой вхождения только одного аргумента (под формой вхождения понимают запись аргумента в прямом или инверсном виде).
Процесс минимизации по картам Вейча-Карно фактически состоит из двух этапов: нанесения функции на карту Карно и считывания упрощенных форм. Рассмотрим этап нанесения на карту Вейча-Карно функции4 :
Каждый минтерм заданной функции на карте Вейча-Карно обозначается 1, помещенной в клетку соответствующего минтерма, В рассматриваемом примере имеется лишь один минтерм, а именно минтерм , обозначенный цифрой 1. Таким образом, для нанесения его на карту достаточно записать 1 в клетку, в которую входят все символы минтерма (рис. 1.4).
Чтобы нанести на карту выражение X1 X3 X4, обозначенное цифрой 2, которое не является минтермом, следует вписать единицы в клетки карты, относящиеся к символам X1 X3 X4. Как видно из рисунка 1.4, таких единиц, удовлетворяющих выражению X1 X3 X4 можно поставить две. На рис. 1.4 эти единицы отмечены цифрой 2 в кружке.
Чтобы нанести на карту выражение , отмеченное цифрой 3, необходимо поставить 1 теперь уже в четыре ячейки карты (см. рис. 1.4), причем одна 1 попадет в ячейку, в которой уже была записана 1 от выражения 2 (эти клетки на рис. 1.4 обозначены цифрой 3) в кружке. Однако независимо от того, сколько единиц окажется в одной клетке (две или более), считается, что клетка отмечена только один раз, т. е. всегда ставится одна единица. Очевидно, что для нанесения выражения на карту Карно необходимо вписать уже восемь единиц (см. рис. 1.4), часть из которых попадет в ранее отмеченные ячейки. Из рассмотренного примера становится понятно отсутствие необходимости первоначального представления функции в виде ДСНФ, поскольку карта Карно, по существу, автоматически обеспечивает развертывание выражения, записанного в ДНФ, в форму ДСНФ.
Кроме рассмотренного широко применяется еще один способ маркировки расположения минтермов на карте Карно. В соответствии с этим способом аргументы разбиваются на две группы. Например, для функции четырех переменных такими являются группы X1 X2 и X3 X4, для трех переменных X1 и X2 X3 или X1 X2 и X3. Наборы аргументов каждой группы используются для обозначения столбцов и строк карты Карно. При этом порядок чередования этих наборов при переходе от одного столбца к другому или от одной строки к следующей соответствует перестановке двоичных цифр в циклическом коде. На рис. 1.5 и 1.6 приведены примеры записи функций от четырех и пяти аргументов соответственно. Порядок нанесения функции на карты Карно практически не отличается от ранее рассмотренного. В качестве примера на рис. 1.5 показана запись на карту функции
а на рис. 1.6 функции
После нанесения выражения на карту начинается этап считывания упрощенных форм.
Здесь следует отметить, что этот этап не отличается однозначностью, поскольку выражение с карты Карно можно прочитать различным образом. Считывание упрощенных форм достигается путем склеивания минтермов, отмеченных на карте 1. При этом склеиваемые минтермы охватываются замкнутыми контурами, если они находятся не в крайних ячейках, и незамкнутыми, как в последнем случае. Поскольку одна и та же функция считывается неоднозначно, то поиск минимальных форм происходит путем переборов различных вариантов и их последующего сравнения по числу букв. Считается, что тупиковой ДНФ соответствуют такие склеивания, когда каждый минтерм не содержит лишних покрытий, а минимальной ДНФ — склеивания с таким распределением поглощений, когда склеивается наибольшее число минтермов. Получаемая в результате функция реализуется с наименьшими аппаратурными затратами.
Этап считывания упрощенных форм с карт Карно рассмотрим на рис. 1.7, где представлена функция от трех переменных со скобочной формой маркирования минтермов. Здесь наглядно иллюстрируется неоднозначность считываемых упрощенных форм. Считывание с рис. 1.7, а—в приводит к тупиковым формам, содержащим по четыре импликанты:
При считывании на рис. 1.7, г, д поглощения минтермов осуществляются наиболее удачно, поскольку они приводят к минимальным формам, содержащим по три импликанты:
Примеры считывания с карт Карно с формой маркирования минтермов, приведенной на рис. 1.5 и 1.6, показаны на рис. 1.8, а, б соответственно. Сопоставляя методы Квайна и Карно, можно видеть, что последний особенно эффективен при минимизации переключательных функций с числом аргументов не более шести. Однако в отличие от метода Квайна, метод Карно не является систематическим. При числе аргументов более шести минимизация, как правило, ведется с применением вычислительных машин, и здесь систематические методы минимизации по существу являются единственно возможными.
1.2. Основные положения и определения теории конечных автоматов
Цифровыми (конечными) автоматами называют устройства, предназначенные для обработки информации, заданной цифровыми кодами.
Применительно к ЭВМ (в зависимости от способа обработки цифровой информации) различают два класса цифровых автоматов: комбинационные и последовательностные. Здесь под способом обработки понимается преобразование входной информации по определенному закону и выдача этой информации в требуемом виде. Комбинационными автоматами (или комбинационными схемами) называют такие устройства, в которых значения выходных сигналов в дискретный момент времени определяются значениями входных сигналов. Простейшим примером комбинационных автоматов (КА) могут служить логические элементы, выполняющие функции И, И-НЕ, ИЛИ-НЕ и др. К более сложным комбинационным автоматам можно отнести, например, комбинационные сумматоры и дешифраторы. В отличие от комбинационных, в последовательностных автоматах значения выходных сигналов в данный момент времени зависят не только от значений входных сигналов в этот же момент времени, но и от значений входных сигналов в предыдущие моменты времени. Из этого следует, что последовательностные автоматы выполняют преобразование информации не между отдельными значениями входных переменных, а между их последовательностями, т. е. их работа должна рассматриваться во времени. Однако чтобы значения выходных сигналов зависели не только от текущих значений входных сигналов, но и от их предыдущих значений, последовательностному автомату необходима память, в которой должна храниться информация от предыдущих воздействий.
Один из вариантов структурной схемы последовательностного автомата показан на рис. 1.9. Автомат имеет п входов, на которые поступают сигналы Х1 ... Хn, k выходов, с которых снимаются сигналы Х1 ... Хh, и тa элементов памяти. Выходные состояния являются внутренними состояниями автомата и обозначаются Q1 ... Qm. Для задания цифрового автомата необходимо знать число входных переменных, число выходных переменных и число внутренних состояний, т. е. объем памяти автомата. Последний, в случае применения традиционных триггеров, определяем из выражения
тa = [1og2Ma]t,
где Ma — число внутренних состояний автомата.
Для п-входных и k-выходных переменных соответственно может быть 2п состояний входа и 2n состояний выхода при условии, что входные, внутренние и выходные сигналы автомата являются двоичными сигналами. Так как множество входных, внутренних и выходных состояний конечно, то цифровые последовательностные автоматы часто называют конечными автоматами. Кроме множества входных, выходных и внутренних состояний для формального задания автомата необходимо задать функции переходов и выходов, определенные на этих множествах. В свою очередь, для задания функций переходов необходимо указать зависимости, существующие между внутренними переменными т моменты времени i + 1 со значениями входных и выходных переменных в момент времени t. Аналитически эта зависимость записывается в виде
(1.6)
где i — выход i-го элемента памяти.
Для задания функций выхода необходимо задать формулировку связи выходных переменных в момент времени t(Yt) со значениями входных Хt и внутренних Qt переменных в тот же момент времени. Аналитически эта зависимость имеет вид
(1.7)
Кроме аналитической записи функции переходов и выходов могут задаваться в виде таблиц, которые носят название таблиц выходов и переходов. Если функции переходов и выходов заданы на всем множестве комбинаций значений аргументов X и Q, то такие автоматы называют полностью определенными или полными. В том случае, когда значения функций переходов и выходов на некоторых комбинациях переменных не заданы, то такие автоматы называют недоопределенными или неполными. Если автомат работает таким образом, что его выходной сигнал зависит не только от внутреннего состояния, в котором он находится, но и от сигнала на его входах, то такой автомат называют автоматом Мили. Поведение автомата Мили описывается уравнениями (1.6) и (17). Кроме автомата Мили на практике широкое применение находят так называемые автоматы Мура. Отличительной особенностью таких автоматов является то, что выходной сигнал в момент дискретного времени зависит только от внутреннего состояния автомата в этот момент и не зависит от входного сигнала. Поведение автомата Мура описывается уравнениями вида
(1.8)
Из уравнений (1.8) следует, что выходными сигналами автомата Мура являются внутренние состояния, т. е. сигналы с выходов элементов памяти. Такие автоматы называют автоматами без выхода, и для них не требуется задание функции выходов. Примерами подобных автоматов являются триггеры (или элементарные автоматы), счетчики, накапливающие сумматоры, регистры и др.
Процесс логического проектирования цифровых автоматов принято подразделять на два этапа: абстрактного и структурного синтеза. В ходе абстрактного синтеза на основе словесного описания условий работы устанавливается число входных, выходных переменных, тип автомата, число внутренних переменных, а также производится задание функций переходов и выходов либо в аналитической, либо в табличной форме. Здесь же производится кодирование внутренних состояний. Следует отметить, что от этого этапа в значительной степени зависит сложность построенного в результате синтеза автомата. В процессе структурного синтеза осуществляется выбор функционально полной системы элементов и типов элементов памяти. Основной задачей этого этапа является синтез КА, реализующих функции переходов и выходов с учетом выбранных элементов памяти, и минимизация схемного решения комбинационного автомата (схемы). Этап структурного синтеза заканчивается построением функциональной схемы автомата, выполненного на выбранном базисе логических элементов.
Перечисленные выше автоматы без выхода находят самое широкое применение в устройствах ЭВМ, и именно им будет уделено основное внимание в последующих главах.
Нарастающий интерес к микроэлектронике, вновь появившийся за последние 5 лет, побудил авторов к переизданию книги "Микроэлектронные схемы цифровых устройств", которая, по отзывам читателей, представляет практический интерес для разработчиков цифровой аппаратуры.
Основной материал книги не претерпел изменений за исключением нескольких параграфов.
Заново переписан параграф 3.4 "Импульсно-статические триггеры", как наиболее экономичные по числу ИС.
В главу 5 "Счётчики" введены параграфы:
параграф 5.3.4 "Счётчики на триггерах F,Fi, LF типов",
параграф 5.3.5 "Вычитающие счётчики",
параграф 5.5.11 "Счётчики с Ксч≠2n, использующие R входы".
Существенно расширена глава 10 "Импульсные устройства" за счет введения в её состав целого ряда новых схем по обработке информации (14схем).
Заново переписан и значительно расширен параграф 10.11. "Импульсные генераторы".
Опыт работы авторов в области разработки цифровой аппаратуры показал, что разработчик такой аппаратуры постоянно сталкивается с вопросами связанными с передачей информации между блоками и со вторичными источниками питания, знание которых расширяет кругозор разработчика и существенно помогает при проектировании цифровых комплексов.
Поэтому авторы решили отразить эти вопросы в новом издании книги.
В состав книги введены две новые главы:
глава - 11 Вторичные источники питания (ВИП).
глава - 12 Передача и прием информации по проводным линиям связи.
В главе 11 приводится описание узлов ВИП, описание и расчет трансформатора, дросселя фильтра, а также рассмотрены особенности работы транзистора в составе преобразователя.
Схемная часть представленных материалов отражает опыт авторов в данных областях, публикуется впервые и будет полезна инженерам и студентам соответствующих специальностей.
Главы 1,2,7 и 8 написаны И.Н. Букреевым, Б.М. Мансуровым и В.И. Горячевым совместно, гл. 3-5 и 9 В.И. Горячевым и Б.М. Мансуровым совместно, гл 6,10,11,12 – В.И. Горячевым
Глава 1
Основы теории проектирования микроэлектронных устройств на цифровых микросхемах
1.1. Основы алгебры логики
Как известно, алгебра логики (булева алгебра), в отличие от обычной алгебры, оперирует всего двумя переменными, причем эти переменные могут принимать только два значения типа да-нет, включено-выключено и т. п. При этом для удобства математического описания эти переменные принято обозначать 1 и 0.
Булева алгебра наиболее эффективна для описания функционирования различных электронных устройств, которые в силу специфики работы могут находиться в состоянии либо «включено», либо «выключено». Основным понятием булевой алгебры является понятие переключательной функции. Переключательной (булевой, двоичной) функцией называют функцию вида f(X1, ..., Xn)1, которая, как и ее переменные (аргументы) Х1 ..., Хп, может принимать два значения: 0 или 1. Как и всякая функция, булева функция имеет область определения. Поскольку аргументы переключательной функции могут принимать только два значения, то область определения булевой функции выражается совокупностью комбинаций этих переменных и, следовательно, она всегда конечна. В свою очередь, каждую совокупность комбинаций аргументов называют набором. В итоге для любой переключательной функции от п переменных существует 2п различных наборов. Наборы аргументов нумеруют двоичными числами, разрядами которых являются сами аргументы переключательных функций. В качестве примера в табл. 1.1 и 1.2 представлены всевозможные наборы переключательных функций от одного и двух переменных.
Таблица 1.1
Номер набора Аргумент
X1
0 0
1 1
Таблица 1.2
Номер набора Аргумент
X1 X2
0 0 0
1 0 1
2 1 0
3 1 1
Поскольку любая булева функция определена на 2n наборах и сама принимает только два значения (0 или 1), то число булевых функций от п переменных равно . Например, при n = 1 (т. е. для булевой функции от одной переменной) существует 22 = 4 различных булевых функций, каждая из которых определена на 21 наборах (см. табл. 1.1).
Булевы функции от одной переменной (сингулярные функции), а также их условное обозначение и название приведены в табл. 1.3. Действительно, как следует из табл. 1.3, существует всего четыре сингулярные функции от одной переменной X: константа 0, переменная X, инверсия X, константа 1. Функции константа 0 и константа 1 названы так по той причине, что любому из двух ее наборов аргументов Х = 0 и Х = 1 ставится в соответствие постоянное значение функции, равное 0 для функции константа 0 и 1 для функции константа 1.
Таблица 1.3
Функция X Условное обозначение Название функции
0 1
f0(X) 0 0 0 Константа 0
f1(X) 0 1 X Переменная X
f2(X) 1 0 X Инверсия X
f3(X) 1 1 1 Константа 1
Функция f1(X) — переменная X на одном наборе Х = 0 равна 0, а на другом наборе Х = 0 равна 1, т. е. повторяет переменную X. Функция f2(X) принимает значение 1 на наборе Х = 0 и значение 0 на наборе Х = 1. Функция, выполняющая такую операцию над аргументом, носит название отрицания или инверсии и является одной из основных функций булевой алгебры. При п = 2, т. е. для булевых функций от двух переменных X1 и Х2 (бинарные функции), существует 24 = 16 различных функций, каждая из которых определена на четырех наборах (см. табл. 1.2). Булевы функции двух переменных, их условное обозначение и название даются в табл. 1.4. Заметим, что среди этих 16 функций фактически бинарными являются 10, а остальные зависят от двух переменных формально и являются либо константами (f0 и f15), либо сингулярными, т. е. повторениями переменных (f3 и f5) и их отрицаниями (f12 и f10). К наиболее часто встречающимся булевым функциям от двух переменных относятся функции f1 (конъюнкция), f1 (дизъюнкция) и f6 (логическая неравнозначность, Исключающее ИЛИ, сложение по модулю 2).
Таблица 1.4
Функция Наборы Обозначение функции Название функции
X1 0 0 1 1
X2 0 1 0 1
f0(X1, X2) 0 0 0 0 0 Константа 0
f1(X1, X2) 0 0 0 1 X1 X2, X1 X2 Конъюнкция (логическая операция И)
f2(X1, X2) 0 0 1 0 X1 X2 Запрет по Х2 (отрицание импликации)
f3(X1, X2) 0 0 1 1 X1 Переменная Х1
f4(X1, X2) 0 1 0 0 X2 X1 Запрет по X1
f5(X1, X2) 0 1 0 1 X2 Переменная Х2
f6(X1, X2) 0 1 1 0 X1 Z X2 Сумма по модулю 2
f7(X1, X2) 0 1 1 1 X1 + X2, X1 X2 Дизъюнкция (логическая операция ИЛИ)
f8(X1, X2) 1 0 0 0 X1 X2 Стрелка Пирса (отрицание дизъюнкции)
f9(X1, X2) 1 0 0 1 X1 X2 Эквивалентность
f10(X1, X2) 1 0 1 0
Отрицание Х2 (функция НЕ)
f11(X1, X2) 1 0 1 1 X2 X1 Импликация от Х2 к X1
f12(X1, X2) 1 0 1 1
Отрицание Х1 (функция НЕ)
f13(X1, X2) 1 1 0 1 X1 X2 Импликация от X1 к Х2
f14(X1, X2) 1 1 1 0 X1/X2 Штрих Шеффера (отрицание конъюнкции)
f15(X1, X2) 1 1 1 1 1 Константа 1
Из табл. 1.4 следует, что, например, функция f1 принимает значение 1 только на одном из четырех возможных наборов переменных, а именно на наборе X1 = 1 и Х2 = 1. На всех остальных наборах ее значение равно 0. Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X1 и Х2), появится только тогда, когда сигнал 1 будет одновременно присутствовать на двух входах. Элемент, реализующий эту функцию, носит название схемы И (логическое умножение).
Функция f7 принимает значение 1 на всех наборах переменных, кроме одного Х1 + 0 и Х2 + 0. Применительно к преобразованию сигналов это означает, что сигнал на выходе устройства, имеющего два входа (X1 и Х2), появится только тогда, когда сигнал 1 будет присутствовать хотя бы на одном из входов. Элемент, реализующий эту функцию, носит название схемы ИЛИ (логическое сложение).
Из остальных функций табл. 1.4 выделим функцию f12. Элемент, реализующей ее, носит название схемы НЕ. Применительно к преобразованию сигналов данная функция означает, что сигнал на выходе устройства, имеющего один вход X1 (или X2 для f10), появится только в том случае, если сигнал 1 на входе отсутствует. При наличии сигнала 1 на входе, на выходе схемы НЕ будет действовать сигнал 0.
Некоторые из приведенных в табл. 1.4 функций могут быть распространены и на большее число независимых переменных. К таким функциям можно отнести, например, f1, f7, f8, f10, и др.; их можно записать в виде2
f1 = Х1 Х2...Хп = Х1 Х2...Хп;
f7 = Х1 + Х2 + ... + Хп = Х1 Х2 ... Хп;
Применительно к преобразованию сигналов, например, функция f1 от п переменных означает, что сигнал 1 на выходе устройства (в данном случае уже имеющего п входов) появится только при его присутствии одновременно на всех входах. Физическая реализация этой функции, как и функции f1 от двух переменных, носит название схемы И. Обращаясь к табл. 1.4, замечаем, что некоторые из приведенных функций получаются посредством декомпозиции или перенумерации аргументов булевых функций. Так, функция f13 может быть получена из функции f11, если поменять местами аргументы Х1 и Х2. Функция f14 (штрих Шеффера) может быть получена из функции f12 посредством замены значений аргумента Х1 значениями функции f1. В общем случае операция замены аргументов одной функции другими функциями носит название суперпозиции. Например, если
f = f(Y1, Y2), a Y1 = Y1(X1, X2) и Y2 = Y2(X3, X4),
то очевидно, что
f = f(X1, X2, X3, X4)
Последнее показывает, что многократное применение метода суперпозиции позволяет получить более сложные булевы функции. При этом возникает вопрос, возможен ли набор таких простых булевых функций, на основе которых можно получить любую сколь угодно сложную функцию. Этот вопрос связан с одним из основных понятий булевой алгебры — понятием функциональной полноты системы булевых функций. Система булевых функций будет называться полной, если на ее основе можно получить любую функцию, используя лишь операцию суперпозиции. Можно привести несколько систем булевых функций, обладающих функциональной полнотой. Одной из таких систем является система А. Эта система состоит из трех булевых функций и носит название основного функционально полного набора (ОФПН):
В общем случае одна из приведенных в этой системе функций, а именно дизъюнкция или конъюнкция, является лишней, поскольку ее исключение не приводит к нарушению функциональной полноты системы. Действительно, кроме этой системы, функциональной полнотой будут обладать системы булевых функций вида В и С, включающие всего две функции:
Системы В и С будут функционально полными в силу того, что операцию конъюнкции, отсутствующую в системе В, и операцию дизъюнкции, отсутствующую в системе С, можно получить на основе имеющихся двух функций в соответствии с правилами алгебры логики. Наконец, можно привести несколько систем, состоящих всего из одной функции, которые также обладают функциональной полнотой. Примером такой функции являются функция (отрицание конъюнкции) и функция (отрицание дизъюнкции). Недостающие функции дизъюнкции, конъюнкции и отрицания для этих систем можно получить на основе известных правил алгебры логики. Можно привести и другие функционально полные системы, например систему, состоящую из функций запрета и константы единицы, запрета и инверсии и т. п.
1.1.1. Основные аксиомы и тождества алгебры логики
Булева алгебра позволяет не только математически описывать переключательные функции, но и преобразовывать их, давая возможность реализовывать эти функции на различных функционально полных системах. Поскольку переключательные функции в конечном счете отражают определенные логические связи между различными узлами цифровых устройств, то тем самым булева алгебра позволяет преобразовывать эти связи и, следовательно, она является аппаратом, позволяющим разработчику осуществлять выбор оптимального варианта. В настоящее время наиболее полно разработаны методы преобразования выражений, которые содержат переключательные функции ОФПН. Применительно к такому набору булева алгебра располагает рядом законов, основные из которых приводятся ниже.
Законы дизъюнкции:
• 0 + 0 = 0;
• 1 + 0 = 1;
• 1 + 1 = 1;
• 0 + Х = Х — закон сложения с 0;
• 1 + Х = Х — закон сложения с 1;
• Х + Х = Х — закон тождества для сложения;
• Х + Х + ... + Х = Х;
• — закон исключенного третьего;
• X + Y = Y + X — переместительный (коммутативный) закон для сложения;
• X + Y + Z = (X + Y) + Z = X + (Y + Z) — сочетательный (ассоциативный) закон для сложения.
Законы конъюнкции:
• 0 0 = 0;
• 1 0 = 0;
• 1 1 = 1;
• 0 Х = 0 — закон умножения на 0;
• 1 Х = Х — закон умножения на 1;
• — законы тождества для умножения;
• — закон противоречия;
• X Y = Y X — переместительный (коммутативный) закон для умножения;
• X Y Z = X (Y Z) = (X Y) Z — сочетательный (ассоциативный) закон для умножения.
Законы инверсии:
•
• — закон двойного отрицания.
Законы преобразования выражений, содержащих операции конъюнкции, дизъюнкции и отрицания:
1. Законы поглощения:
• X + X Y = X;
• X (X + Y) = X.
2. Законы склеивания:
•
•
3. Операции обобщенного склеивания:
•
•
4.
5. Законы двойственности (формулы де Моргана):
•
•
Законы двойственности можно записать и в более общем виде:
•
•
6. Закон действия со скобками:
• X1 X2 + X1 X3 = X1 (X2 + X3).
Перечисленные формулы приводятся без доказательств, но читатель может легко убедиться в их справедливости, подставив в правые и левые части равенств значения переменных 0 и 1. Эти формулы далеко не исчерпывают возможных булевых равенств, однако, они являются основными, и их знание необходимо для овладения техникой преобразования булевых функций.
1.1.2. Аналитическая форма представления булевых функций
При решении конкретных технических задач булевы функции, отражающие логические связи, наиболее часто задаются в табличной форме. Однако такая форма задания функции, при всей ее наглядности, не позволяет ответить на вопрос, каким же образом реализовать и если можно, то упростить данную функцию? Для реализации и последующего упрощения булеву функцию следует представить в аналитической форме в одном из функционально полных наборов. Поскольку в настоящее время методы представления и минимизации функций наиболее полно разработаны в базисе ОФПН, то именно этот базис в дальнейшем и будет рассматриваться.
Допустим, что в ходе решения задачи требуется реализовать переключательную функцию, заданную табл. 1.5. Как видно из таблицы, функция должна принимать значение 1 только на 3-м, 6-м и 7-м наборах. На всех остальных наборах ее значение равно 0. Возникает вопрос, каким образом записать эту функцию аналитически, т. е. представить в виде формулы. Применительно к основному базису, содержащему элементы дизъюнкции, конъюнкции и отрицания, доказано, что любая переключательная функция, предварительно заданная в табличной форме, может быть записана аналитически в двух формах, получивших название канонических (нормальных): в дизъюнктивной совершенной нормальной форме (ДСНФ) и в конъюнктивной совершенной нормальной форме (КСНФ). Аналитическая запись функций в виде ДСНФ и КСНФ предполагает представление этих функций посредством суперпозиции специально вводимых вспомогательных функций: минтермов и макстермов. Минтермы часто называют конституентами единицы, а макстермы — конституентами нуля. Минтермом называют булево произведение (конъюнкцию) от п переменных, в котором каждая переменная входит один раз в прямой или инверсной форме. Макстермом называют булеву сумму от п переменных, в которой каждая переменная входит один раз в прямой или инверсной форме. Из сказанного следует, что переключательная функция от п переменных имеет число минтермов и макстермов, равное числу наборов, на которых она определена, т. е. 2п минтермов и макстермов. В качестве примера в табл. 1.6 и 1.7 даются минтермы и макстермы двух переменных X1 и Х2.
Таблица 1.5
Номер набора Аргументы Значение функции на i-ом наборе (fi) Номер набора Аргументы Значение функции на i-ом наборе (fi)
X1 X2 X3 X1 X2 X3
0 0 0 0 0 4 1 0 0 0
1 0 0 1 0 5 1 0 1 0
2 0 1 0 0 6 1 1 0 1
3 0 1 1 1 7 1 1 1 1
Таблица 1.6
Аргументы Минтермы
X1 X2 m0 m1 m2 m3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 1
1 1 0 0 0 1
Таблица 1.7
Аргументы Макстермы
X1 X2 M0 M1 M2 M3
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
Согласно приведенным определениям минтермы и макстермы двух аргументов выражаются формулами:
Запись переключательной функции в виде ДСНФ означает, что любая переключательная функция, заданная табличным способом, может быть представлена в виде логической суммы конъюнктивных членов. При этом каждый из этих членов представляет собой произведение значения функции на i-м наборе на i-й минтерм. Поскольку переключательная функция имеет 2п минтермов, то аналитическая запись функции в ДСНФ имеет вид
Таким образом, функция, заданная таблицей состояний (см. табл. 1.5), запишется аналитически следующим образом:
Из сказанного становятся понятны отдельные термины сокращенного представления функции в виде ДСНФ. В частности, термин «дизъюнкция» указывает на то, что внешней функцией разложения является дизъюнкция, а внутренней — конъюнкция. Термин «совершенная» указывает на то, что дизъюнктивные члены формируются из всех аргументов X1 ... Xn, т. е. на основе минтермов. Термин «нормальная» указывает на то, что форма записи является двухуровневой, т. е. дизъюнкция конъюнкций. Аналитическая запись функции в виде КСНФ означает, что переключательная функция, заданная табличным способом, может быть представлена в виде логического произведения (конъюнкцией) дизъюнктивных членов. При этом каждый из этих членов представляет собой сумму значений функции на i-м наборе и i-гo макстерма. Поскольку от п аргументов существует 2п макстермов, то аналитическая запись функции в КСНФ имеет вид
В итоге, для рассматриваемого примера (см. табл. 1.5)
или
Сопоставление двух форм записи одной и той же переключательной функции показывает, что запись функции в виде КСНФ более громоздкая, так как содержит большее число членов. Последнее объясняется тем, что число наборов, на которых переключательная функция равна 0, значительно больше числа наборов, на которых она равна 1. Для случая, когда число наборов, на которых функция равна 0, было бы меньше числа наборов, на которых функция равна 1, более предпочтительным оказывается представление функции в виде КСНФ. Из сказанного следует, что обе формы представления функций фактически эквивалентны. Однако при минимизации функций более удобной оказывается запись их в виде ДСНФ. Поэтому в дальнейшем будут рассматриваться только такие формы.
1.1.3. Упрощение (минимизация) булевых функций
Как было показано выше, аналитическая запись рассматриваемой функции, представленной в ДСНФ, имеет вид
(1,1)
Для реализации этой функции (рис. 1.1) потребуются три элемента И, один элемент ИЛИ и два элемента НЕ. Возникает вопрос, можно ли эту функцию, предварительно заданную в ДСНФ, представить в более компактном виде, чтобы выполнялась та же функция, но при ее реализации требовалось бы меньшее число элементов. Процесс нахождения выражений, выполняющих ту же логическую функцию, что и первоначально заданная, но для реализации которых требуется меньшее число элементов, и составляет сущность процесса минимизации. Попытаемся это сделать для приведенной выше функции (1.1). Приняв во внимание равенство Х + Х = Х, добавим к этому выражению еще один конъюнктивный член X1 X2 X3:
Теперь преобразуем полученное выражение, используя приведенные выше формулы:
(1.2)
Реализация уже этой функции потребует значительно меньшего числа элементов (рис. 1.2, а, б), что подчеркивает неэкономичность реализации функций алгебры логики, представленных в виде ДСНФ.
Как видно из рис. 1.1 и 1.2, одна и та же функция реализуется далеко неоднозначно по аппаратурным затратам. Это говорит о том, что, по-видимому, существует такая форма представления функции, которая выполняется с наименьшими аппаратурными затратами. Применительно к рассматриваемой функции такой формой является представление ее в виде скобочной формулы f = X2 (X1 + X3).
В наиболее общем виде задачей минимизации является получение схем минимальной стоимости. Однако в такой постановке задача чрезвычайно сложна, и в настоящее время общие методы ее решения отсутствуют [2]. Последнее в значительной степени объясняется тем, что при решении такой задачи необходимо иметь в виду, что всякая логическая операция реализуется на логических элементах (ЛЭ), параметры которых имеют определенные ограничения по числу входов, нагрузочной способности, быстродействию, потребляемой мощности и т. п. Поэтому наиболее часто процесс минимизации рассматривается в более упрощенной постановке, а именно в отыскании дизъюнктивных форм функций, содержащих по возможности меньшее число букв. В настоящее время известно достаточно большое число методов минимизации [4, 5]. Все они базируются на тождественных преобразованиях логических выражений и подразделяются на систематические и несистематические методы минимизации.
Примером несистематического метода минимизации является метод расчленения и проб. В соответствии с этим методом функции упрощают до минимальной только на основании аксиом и тождеств алгебры логики. Этот метод преобразования функций по существу аналогичен преобразованию выражений в традиционной алгебре и требует от разработчика знания не только возможно большего числа тождеств и аксиом алгебры логики, но и значительной изобретательности (эвристичности) и опыта. Основным недостатком такого метода является то, что зачастую трудно определить, является ли полученное выражение минимальным или имеются пути его дальнейшего упрощения. В силу указанных причин данный метод не получил широкого распространения и его полностью вытеснили систематические методы. Достоинством таких методов является то, что они описываются строгими алгоритмами, т. е. являются формализованными, и, следовательно, здесь имеется возможность применения ЭВМ, что особенно важно при минимизации функций с большим числом переменных.
К наиболее широко распространенным систематизированным методам следует отнести метод Квайна-Маккласки. Этот метод достаточно подробно рассмотрен в ряде источников [2, 5, 8], поэтому здесь мы остановимся на рассмотрении нескольких основных его этапах и определениях, которые потребуются в дальнейшем при рассмотрении других методов. Нахождение минимальной формы по этому методу осуществляется в три этапа. На первом этапе исследуется вид задания функции. И если она задана произвольной формой в булевой алгебре, например:
(1.3)
то с помощью тождественных соотношений, рассмотренных выше, она должна быть развернута в виде ДСНФ. В частности, применив к выражению (1.3) правило де Моргана, получим
(1.4)
Полученное в результате преобразований выражение представляет собой запись функции в дизъюнктивной нормальной форме ДНФ. Для записи функции в виде ДСНФ, т. е. суммы минтермов, необходимо провести операцию развертывания, которая заключается в умножении на выражение членов функции, не являющихся минтермами. Поскольку в выражении (1.4) ни один из членов не является минтермом, то для записи функции в виде ДСНФ необходимо умножить первый член на выражение , второй на , а третий и четвертый на :
Второй этап заключается в нахождении сокращенной ДНФ (СДНФ). Проиллюстрируем его конкретным примером. Найдем СДНФ функции:
Функция уже задана в виде ДСНФ, т. е. необходимость выполнения первого этапа отпадает. Далее осуществляются операции склеивания и поглощения. Проведем операцию склеивания в следующей последовательности:
выполним всевозможные склеивания 1-го члена X1 X2 X3 с остальными;
выполним всевозможные склеивания 2-го члена с остальными, кроме первого;
выполним всевозможные склеивания третьего члена с остальными, кроме первого и второго. Напомним, что операция склеивания осуществляется по формуле
Результат склеивания запишем в виде
Как видно из этих выражений, склеиваются всегда два минтерма, отличающиеся друг от друга только одним аргументом, и только таким, который обязательно в один минтерм входит в прямой, а в другой — в инверсной форме. Такие минтермы принято называть смежными, а конъюнкции, получаемые от их склеивания, — импликантами.
После операции склеивания проводится операция поглощения, которая выполняется с помощью формулы
Х1 Х2 + Х2 = Х2.
Для проведения операции поглощения необходимо заданную функцию представить в виде
где первые три члена получены от проведения операции склеивания. В этом выражении произведение X1 X3 поглощает члены и , произведение поглощает члены и и произведение поглощает члены и . Таким образом, в результате операции поглощения все минтермы функции оказались поглощены импликантами, что позволяет записать исходную функцию теперь уже в виде
(1.5)
К полученной формуле повторно применяют операции склеивания и последующего поглощения, и эта процедура выполняется до получения простых импликант. В рассматриваемом примере ни одно из произведений-импликант не склеивается между собой. Такие импликанты называют простыми, а функцию (1.5), состоящую из дизъюнкции простых импликант, — сокращенной ДНФ (СДНФ).
Однако СДНФ еще не минимальная форма записи функции. Поэтому дальнейший этап минимизации связан с упрощением СДНФ и заключается в устранении избыточных простых импликант из СДНФ. Функции, полученные в результате устранения из сокращенной ДНФ избыточных импликант, принято называть тупиковыми ДНФ. Наиболее распространенным методом получения тупиковых форм является метод импликантных матриц [1, 8]. Импликантная матрица представляет собой таблицу, включающую в себя все минтермы, расположенные горизонтально, и все простые импликанты, расположенные вертикально. Для рассматриваемого примера такая матрица показана в табл. 1.8. Для каждой импликанты находят минтермы, которые ими поглощаются, и против каждого поглощенного минтерма ставят знак . Например, импликанта X1 X3 поглощает минтермы X1 X2 X3 и , и против каждого из них ставят знак V. Чтобы найти тупиковые формулы, необходимо в импликантной матрице найти минимальное число импликант, которые поглощают знаком все минтермы.
Таблица 1.8
Простые импликанты Минтермы
X1 X2 X3
X1 X3
Для матрицы (см. табл. 1.8) такими импликантами будут произведения X1 X3 и , причем первое из них поглощает минтермы X1 X2 X3 и , а второе — остальные два минтерма и . В результате, тупиковая форма рассматриваемой функции запишется в виде
Поскольку в нашем примере имеется всего одна тупиковая форма, то она и будет минимальной. В общем случае переключательная функция может иметь не одну, а несколько тупиковых форм, и тогда искомой минимальной ДНФ будет та, которая содержит наименьшее число букв.
Следует отметить, что рассмотренный метод наиболее эффективен при числе переменных больше шести. Для функций с числом переменных до шести (такие функции являются наиболее распространенными) минимизация обычно осуществляется по табличному методу Вейча-Карно. Этот метод, первоначально предложенный Вейчем и затем усовершенствованный Карно, в отличие от рассмотренного выше, не требует первоначального представления функции в виде ДСНФ. Особенностью этого метода является также то, что в его основу положена табличная запись членов минимизируемого выражения, представляемого в виде ДНФ. Карты Карно представляют собой прямоугольные таблицы, составленные из ячеек, число которых равно числу минтермов минимизируемого выражения. Хотя метод Вейча-Карно и является табличным, однако, и здесь упрощение осуществляется за счет все тех же операций склеивания и поглощения. Правда, в данном случае это достигается благодаря такой записи минтермов в ячейки таблицы, когда каждую ячейку со всех сторон окружают ячейки со смежными минтермами.
Один из способов записи минтермов по методу Вейча-Карно показан на рис. 1.3. В качестве примера здесь показана карта Карно для функций от четырех аргументов: X1, X2, X3, X4. Нетрудно видеть, что любой из 16 минтермов находится как бы в окружении со всех четырех его сторон смежными минтермами, расположенными в соседних (смежных) ячейках. Например, смежными ячейками (клетками) для минтерма т8 будут клетки т12, т9, т0, и т10, так как каждый из минтермов, записанных в этих клетках, отличается от минтерма т8 формой вхождения только одного аргумента (под формой вхождения понимают запись аргумента в прямом или инверсном виде).
Процесс минимизации по картам Вейча-Карно фактически состоит из двух этапов: нанесения функции на карту Карно и считывания упрощенных форм. Рассмотрим этап нанесения на карту Вейча-Карно функции4 :
Каждый минтерм заданной функции на карте Вейча-Карно обозначается 1, помещенной в клетку соответствующего минтерма, В рассматриваемом примере имеется лишь один минтерм, а именно минтерм , обозначенный цифрой 1. Таким образом, для нанесения его на карту достаточно записать 1 в клетку, в которую входят все символы минтерма (рис. 1.4).
Чтобы нанести на карту выражение X1 X3 X4, обозначенное цифрой 2, которое не является минтермом, следует вписать единицы в клетки карты, относящиеся к символам X1 X3 X4. Как видно из рисунка 1.4, таких единиц, удовлетворяющих выражению X1 X3 X4 можно поставить две. На рис. 1.4 эти единицы отмечены цифрой 2 в кружке.
Чтобы нанести на карту выражение , отмеченное цифрой 3, необходимо поставить 1 теперь уже в четыре ячейки карты (см. рис. 1.4), причем одна 1 попадет в ячейку, в которой уже была записана 1 от выражения 2 (эти клетки на рис. 1.4 обозначены цифрой 3) в кружке. Однако независимо от того, сколько единиц окажется в одной клетке (две или более), считается, что клетка отмечена только один раз, т. е. всегда ставится одна единица. Очевидно, что для нанесения выражения на карту Карно необходимо вписать уже восемь единиц (см. рис. 1.4), часть из которых попадет в ранее отмеченные ячейки. Из рассмотренного примера становится понятно отсутствие необходимости первоначального представления функции в виде ДСНФ, поскольку карта Карно, по существу, автоматически обеспечивает развертывание выражения, записанного в ДНФ, в форму ДСНФ.
Кроме рассмотренного широко применяется еще один способ маркировки расположения минтермов на карте Карно. В соответствии с этим способом аргументы разбиваются на две группы. Например, для функции четырех переменных такими являются группы X1 X2 и X3 X4, для трех переменных X1 и X2 X3 или X1 X2 и X3. Наборы аргументов каждой группы используются для обозначения столбцов и строк карты Карно. При этом порядок чередования этих наборов при переходе от одного столбца к другому или от одной строки к следующей соответствует перестановке двоичных цифр в циклическом коде. На рис. 1.5 и 1.6 приведены примеры записи функций от четырех и пяти аргументов соответственно. Порядок нанесения функции на карты Карно практически не отличается от ранее рассмотренного. В качестве примера на рис. 1.5 показана запись на карту функции
а на рис. 1.6 функции
После нанесения выражения на карту начинается этап считывания упрощенных форм.
Здесь следует отметить, что этот этап не отличается однозначностью, поскольку выражение с карты Карно можно прочитать различным образом. Считывание упрощенных форм достигается путем склеивания минтермов, отмеченных на карте 1. При этом склеиваемые минтермы охватываются замкнутыми контурами, если они находятся не в крайних ячейках, и незамкнутыми, как в последнем случае. Поскольку одна и та же функция считывается неоднозначно, то поиск минимальных форм происходит путем переборов различных вариантов и их последующего сравнения по числу букв. Считается, что тупиковой ДНФ соответствуют такие склеивания, когда каждый минтерм не содержит лишних покрытий, а минимальной ДНФ — склеивания с таким распределением поглощений, когда склеивается наибольшее число минтермов. Получаемая в результате функция реализуется с наименьшими аппаратурными затратами.
Этап считывания упрощенных форм с карт Карно рассмотрим на рис. 1.7, где представлена функция от трех переменных со скобочной формой маркирования минтермов. Здесь наглядно иллюстрируется неоднозначность считываемых упрощенных форм. Считывание с рис. 1.7, а—в приводит к тупиковым формам, содержащим по четыре импликанты:
При считывании на рис. 1.7, г, д поглощения минтермов осуществляются наиболее удачно, поскольку они приводят к минимальным формам, содержащим по три импликанты:
Примеры считывания с карт Карно с формой маркирования минтермов, приведенной на рис. 1.5 и 1.6, показаны на рис. 1.8, а, б соответственно. Сопоставляя методы Квайна и Карно, можно видеть, что последний особенно эффективен при минимизации переключательных функций с числом аргументов не более шести. Однако в отличие от метода Квайна, метод Карно не является систематическим. При числе аргументов более шести минимизация, как правило, ведется с применением вычислительных машин, и здесь систематические методы минимизации по существу являются единственно возможными.
1.2. Основные положения и определения теории конечных автоматов
Цифровыми (конечными) автоматами называют устройства, предназначенные для обработки информации, заданной цифровыми кодами.
Применительно к ЭВМ (в зависимости от способа обработки цифровой информации) различают два класса цифровых автоматов: комбинационные и последовательностные. Здесь под способом обработки понимается преобразование входной информации по определенному закону и выдача этой информации в требуемом виде. Комбинационными автоматами (или комбинационными схемами) называют такие устройства, в которых значения выходных сигналов в дискретный момент времени определяются значениями входных сигналов. Простейшим примером комбинационных автоматов (КА) могут служить логические элементы, выполняющие функции И, И-НЕ, ИЛИ-НЕ и др. К более сложным комбинационным автоматам можно отнести, например, комбинационные сумматоры и дешифраторы. В отличие от комбинационных, в последовательностных автоматах значения выходных сигналов в данный момент времени зависят не только от значений входных сигналов в этот же момент времени, но и от значений входных сигналов в предыдущие моменты времени. Из этого следует, что последовательностные автоматы выполняют преобразование информации не между отдельными значениями входных переменных, а между их последовательностями, т. е. их работа должна рассматриваться во времени. Однако чтобы значения выходных сигналов зависели не только от текущих значений входных сигналов, но и от их предыдущих значений, последовательностному автомату необходима память, в которой должна храниться информация от предыдущих воздействий.
Один из вариантов структурной схемы последовательностного автомата показан на рис. 1.9. Автомат имеет п входов, на которые поступают сигналы Х1 ... Хn, k выходов, с которых снимаются сигналы Х1 ... Хh, и тa элементов памяти. Выходные состояния являются внутренними состояниями автомата и обозначаются Q1 ... Qm. Для задания цифрового автомата необходимо знать число входных переменных, число выходных переменных и число внутренних состояний, т. е. объем памяти автомата. Последний, в случае применения традиционных триггеров, определяем из выражения
тa = [1og2Ma]t,
где Ma — число внутренних состояний автомата.
Для п-входных и k-выходных переменных соответственно может быть 2п состояний входа и 2n состояний выхода при условии, что входные, внутренние и выходные сигналы автомата являются двоичными сигналами. Так как множество входных, внутренних и выходных состояний конечно, то цифровые последовательностные автоматы часто называют конечными автоматами. Кроме множества входных, выходных и внутренних состояний для формального задания автомата необходимо задать функции переходов и выходов, определенные на этих множествах. В свою очередь, для задания функций переходов необходимо указать зависимости, существующие между внутренними переменными т моменты времени i + 1 со значениями входных и выходных переменных в момент времени t. Аналитически эта зависимость записывается в виде
(1.6)
где i — выход i-го элемента памяти.
Для задания функций выхода необходимо задать формулировку связи выходных переменных в момент времени t(Yt) со значениями входных Хt и внутренних Qt переменных в тот же момент времени. Аналитически эта зависимость имеет вид
(1.7)
Кроме аналитической записи функции переходов и выходов могут задаваться в виде таблиц, которые носят название таблиц выходов и переходов. Если функции переходов и выходов заданы на всем множестве комбинаций значений аргументов X и Q, то такие автоматы называют полностью определенными или полными. В том случае, когда значения функций переходов и выходов на некоторых комбинациях переменных не заданы, то такие автоматы называют недоопределенными или неполными. Если автомат работает таким образом, что его выходной сигнал зависит не только от внутреннего состояния, в котором он находится, но и от сигнала на его входах, то такой автомат называют автоматом Мили. Поведение автомата Мили описывается уравнениями (1.6) и (17). Кроме автомата Мили на практике широкое применение находят так называемые автоматы Мура. Отличительной особенностью таких автоматов является то, что выходной сигнал в момент дискретного времени зависит только от внутреннего состояния автомата в этот момент и не зависит от входного сигнала. Поведение автомата Мура описывается уравнениями вида
(1.8)
Из уравнений (1.8) следует, что выходными сигналами автомата Мура являются внутренние состояния, т. е. сигналы с выходов элементов памяти. Такие автоматы называют автоматами без выхода, и для них не требуется задание функции выходов. Примерами подобных автоматов являются триггеры (или элементарные автоматы), счетчики, накапливающие сумматоры, регистры и др.
Процесс логического проектирования цифровых автоматов принято подразделять на два этапа: абстрактного и структурного синтеза. В ходе абстрактного синтеза на основе словесного описания условий работы устанавливается число входных, выходных переменных, тип автомата, число внутренних переменных, а также производится задание функций переходов и выходов либо в аналитической, либо в табличной форме. Здесь же производится кодирование внутренних состояний. Следует отметить, что от этого этапа в значительной степени зависит сложность построенного в результате синтеза автомата. В процессе структурного синтеза осуществляется выбор функционально полной системы элементов и типов элементов памяти. Основной задачей этого этапа является синтез КА, реализующих функции переходов и выходов с учетом выбранных элементов памяти, и минимизация схемного решения комбинационного автомата (схемы). Этап структурного синтеза заканчивается построением функциональной схемы автомата, выполненного на выбранном базисе логических элементов.
Перечисленные выше автоматы без выхода находят самое широкое применение в устройствах ЭВМ, и именно им будет уделено основное внимание в последующих главах.