Проектирование комбинационных схем

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

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

Булева алгебра

Булева алгебра основана Джорджем Булем (1815-1864 гг) и является с середины 30-х годов прошлого столетия основой для анализа цифровых логических схем. Булевой алгеброй называется непустое множество A с двумя бинарными операциями логического умножения  (конъюнкция) и логического сложения  (дизъюнкция), унарной операцией  (отрицание) и двумя выделенными элементами: 0 (Ложь) и 1 (Истина). Основные равносильности Булевой алгебры представлены в табл.2.1. Использование следствий законов алгебры логики позволяет сократить (минимизировать) логические выражения.

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

 

 

Таблица 2.1

Сводная таблица равносильностей Булевой алгебры

	коммутативность, переместительность
	ассоциативность, сочетательность
конъюнкция относительно дизъюнкции дизъюнкция относительно конъюнкции	дистрибутивность, распределительность
	комплементность, дополнительность (свойства отрицаний)
	законы де Моргана
	законы поглощения (склеивания)
	Блейка-Порецкого
	идемпотентность
	инволютивность отрицания, закон снятия двойного отрицания
	свойства констант
дополнение 0 есть 1 дополнение 1 есть 0
	склеивание

 

2.2 И спользование таблиц истинности
для описания работы комбинационных логических схем

Таблицы истинности могут быть однозначно сопоставлены вербальным алгоритмам и приводившимся выше диаграммам. Если принадлежность произвольной точки прямоугольника множеству Y (или Z) считать «истиной» (с обозначением Т или 1), а противоположный случай – «ложью» (F или 0), то таблица истинности для операции И (конъюнкция) может быть изображена в виде табл. 2.2. Таблица истинности для операции ИЛИ (дизъюнкция) приведена в табл. 2.3.

 

                             Таблица 2.2                                                              Таблица 2.3

Таблица истинности для операции И                   Таблица истинности для операции ИЛИ

Y	Z	Ù		Y	Z	Ú
0	0	0		0	0	0
0	1	0		0	1	1
1	0	0		1	0	1
1	1	1		1	1	1

 

В этих таблицах представлены четыре различные комбинации случаев принадлежности (или непринадлежности) точки множествам Y и Z.

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

Для дальнейшего анализа и синтеза логической схемы необходимо преобразовать информацию в форме таблицы истинности в Булево выражение. Для записи в дизъюнктивно нормальной форме выделяются те комбинации переменных строки, которые дают логическую «1» на выходе. Аналогичным образом можно построить таблицу истинности по Булеву выражению.

Таблица истинности и Булево выражение по разному описывают принцип действия одной и той же логической схемы. Например, если имеется три датчика А, В и С, а включение электродвигателя или другого исполнительного устройства происходит при срабатывании датчиков В и С или датчика А, то формальное описание данного вербального условия работы можно представить в виде таблицы истинности для трех переменных (рис. 2.1), которому соответствует Булево выражение в нормально-дизъюнктивной форме

Рис.2.1. Таблица истинности для Булева выражения

 

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

 

Рис.2.2. Таблица истинности для Булева выражения

 

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

Рис.2.3. Формальное описание работы схемы по вербальному описанию
в виде таблицы истинности

 

Формальное описание в виде исходного Булева выражения в нормально-дизъюнктивной форме . Логическая схема для реализации вербального алгоритма в соответствии с исходным Булевым выражением будет иметь вид (рис.2.4).

Рис.2.4. Исходная логическая схема для реализации вербального алгоритма

 

Используя равносильности Булевой алгебры можно минимизировать исходную функцию Y _исх ,

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

Рис.2.5. Минимизированная логическая схема для реализации вербального алгоритма

Если пронумеровать строки таблицы истинности в соответствии с десятичным значением соответствующих двоичных кодов, то можно записать условие работы схемы в виде набора номеров строк, где выходная функция принимает значение 1. Например, функция, записанная в виде Y=∑ (3, 5, 6, 9, 10, 12), может быть представлена соответствующей таблицей истинности (рис.2.6).

 

Рис.2.6. Таблица истинности

 

Формальное описание в виде исходного Булева выражения в нормально-дизъюнктивной форме будет иметь вид:

.

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

 

2.3 Преобразование входных величин с помощью карт Карно

Несмотря на то, что Булевы выражения и таблицы истинности используются для описания функционирования интегральных схем, ни один из этих способов изображения нельзя признать плодотворным при освоении современных методов логического конструирования. Карта Карно́ - графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного Булева куба. Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Другими словами в картах Карно при смещении на одну строку по вертикали или на один столбец по горизонтали изменяется лишь одна входная переменная за один шаг. Это исключает так называемые «гонки» или состязания, наблюдаемые при одновременном изменении двух и более входных переменных (рис.2.7).

 

 

Рис.2.7. Соответствие номеров строк таблицы истинности и клеток Карты Карно

 

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

Рис.2.8. Матрица Карно

 

Шесть единиц нанесены на карту в соответствии шести членам в исходном Булевом выражении. Рядом стоящие единицы объединены в группы из 2^х и 4^х единиц. Члены, дополняющие друг друга внутри контура, исключаются. Объединив оставшиеся члены функцией ИЛИ, получим минимизированное выражение в дизъюнктивной нормальной форме (ДНФ) (сумма произведений). Количество групп, объединенных контурами определяет число членов минимизированного Булева выражения:

Таблица истинности (рис.2.9) для обоих вариантов одинаковая.

 Рис.2.9. Таблица истинности для булева выражения

 

Логические схемы, составленные в соответствии с исходным и упрощенным выражением будут выполнять одинаковые логические функции, однако, количество элементов меньше, соответственно меньше стоимость, вес, объем, выше надежность.

Чем больше размеры объединяющих контуров, тем больше переменных можно опустить. Карту Карно можно как бы «свернуть» в цилиндр с вертикальной осью или с горизонтальной осью или образовать шар, объединяя угловые единицы. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности.

Карта Карно рассматривается как поверхность фигуры под названием тор. Единичному значению функции соответствуют p-клетки карты Карно. Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x₄, следовательно, они дают импликанту Х₁, Х₂, `Х₃. Две соседние импликанты первого ранга образуют импликанту второго ранга.

На карте Карно (рис.2.10) соседние клетки образуют две импликанты первого ранга и одну импликанту второго ранга. Минимизированное Булево выражение будет иметь вид

Y = Х₁, Х₂, `Х<sub>3</sub> + `Х₁, Х₂, Х₃+ `Х<sub>1</sub>, `Х₄

Рис.2.10.Карта Карно для четырех переменных

                                                                                               

Если функция имеет 5 переменных, то рисуются две карты Карно: для x₅=0 и для x₅=1. Если 6 переменных - 4 карты так, чтобы в соседних картах соседние клетки имели одинаковые координаты (Рис.2.11).

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

 

Рис.2.11. Варианты карт Карно

 

Если на картах Карно выделить все компактные группы наибольшей размерности, то получим минимизированное Булево выражение в дизъюнктивно-нормальной форме (ДНФ).

Минимизировать исходное Булево выражение и логическую схему (рис 2.4) гораздо удобнее с помощью карты Карно (Рис.2.12).

Рис.2.12. Карта Карно по таблице истинности (рис.2.3)

 

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

В качестве примера рассмотрим минимизацию функции 4-х переменных методом карт Карно, где две компактные группы размера 4 и одна компактная группа размера 2 (рис.2.13).

 

`

Рис.2.13. Пример карты Карно

 

Минимизированное Булево выражение в данном случае будет иметь вид

Y = `Х<sub>1</sub> Ù`Х₃ Ù`Х₄ Ú Х₁Ù Х₂ Ú Х₁, Ù Х₃

 

Логические элементы

 

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

На рис. 2.14  показаны ключи 1 и 0, управляемые клавишами 1 и 0 соответственно, и вспомогательные устройства в виде гальванической батареи 5 В с внутренним сопротивлением 100 Ом и лампы накаливания на 6 B с мощностью 300 мВт, которые позволяют судить о состоянии ключа: если он находится в положении 1, лама горит (рис. 2.9, а), или не горит, если он находится в положении 0 (рис. 2.14 б).

Возможно другое расположение ключей по отношению к вспомогательным устройствам, показанное на рис. 2.15. В этих схемах состояние индикаторов нуля или единицы противоположно показанному на рис. 2.14. При нажатии на клавишу 1 индикатор фиксирует состояние 0 (рис. 2.14, а) и наоборот (рис. 2.14, б). Следовательно: схемы на рис. 2.15 по выходному сигналу (состоянию индикаторных лампочек) обратны (инверсны) по отношению к схемам на рис. 2.14. Поэтому такие ключи называют инверторами.

 

       а)                                                          б)

Рис. 2.14. Схемы электромеханических имитаторов

логической единицы (а) и нуля (б)

 

        а)                                                           б)

Рис. 2.15. Электромеханические имитаторы логической единицы (а) и нуля (б) в инверсном режиме

 

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

     а)                                                                  б)

Рис. 2.16. Электромеханические имитаторы

логической "1" (а) и "0" (б) в инверсном режиме

 с индикаторами выходного напряжения

 

На рис.2.16 сопротивление 490 Ом имитирует внутреннее сопротивление нагрузки ключа (аналог коллекторного сопротивления в транзисторном ключе), сопротивление 10 Ом — сопротивление замкнутого электронного ключа, сопротивление 500 0м — сопротивление разомкнутого ключа с учетом внешней нагрузки. Как видно из рис. 2.16, наличие на выходе логического нуля (инверсия 1) индицируется напряжением 100 мВ (в практических конструкциях может быть и больше), а наличие логической единицы — напряжением 2,55 В (нормируется на уровне 2,4 В). Электронные ключи проектируются таким образом, чтобы при наихудших сочетаниях входных и выходных параметров ключи могли различать сигналы логической единицы и нуля.

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

                                  а)       б)       в)      г)

Рис. 2.17. Графические обозначения буферного логического

 элемента (а), элементов И (AND) (б), ИЛИ (OR) (в),

исключающее ИЛИ (XOR) (г) и их инверсные варианты

 в нижнем ряду (NOT, NAND, NOR, XNOR соответственно)

 

Электромеханические аналоги двухвходовых элементов И, И-НЕ показаны на рис. 2.18.

      а)                                                                б)

Рис. 2.18. Электромеханические имитаторы
двухвходовых элементов

 

Исследования логических схем целесообразно проводить с помощью имеющегося в программе EWB логического преобразователя. В качестве примера на рис. 2.19 приведена схема для исследования элемента Исключающее ИЛИ. Подключение исследуемого элемента к логическому преобразователю показано на рисунке. Очевидно, что при наличии двух входов возможны только четыре комбинации входных сигналов, что отображается на экране преобразователя в виде таблицы истинности, которая генерируется после нажатия клавиши Кл1.

 

Рис. 2.19.  Исследование логического элемента Исключающее ИЛИ

с помощью логического преобразователя

 

Для получения Булева выражения исследуемого элемента необходимо нажать клавишу Кл2. Это выражение приводится на дополнительном дисплее, расположенном в нижней части лицевой панели, в виде двух слагаемых, соответствующих выходному сигналу ИСТИНА (сигнал логической единицы на выходе OUT). Сопоставление полученного выражения с таблицей истинности убеждает нас в том, что таких комбинаций действительно две, если учесть, что в полученном выражении приняты следующие обозначения: А'=0 – инверсия А=1, В'=0 — инверсия В=1, знак + соответствует логической операции ИЛИ.

С помощью логического преобразователя можно проводить не только анализ логических устройств, но и их синтез. Допустим, что нам требуется составить схему и Булево выражение для логического элемента, у которого выходная комбинация в таблице истинности не 0110, как на рис. 2.19, а 1101. Для внесения необходимых изменений отмечаем курсором в столбце OUT подлежащий изменению символ, изменяем его с помощью клавиатуры и затем, перемещаясь по столбцу клавишами управления курсором, изменяем по необходимости символы в других строках. После внесения всех изменений последовательно нажимаем на клавиши Кл2, Кл3, Кл4 (рис.2.19) и получаем результат, представленный на рис. 2.15. Синтезированное логическое устройство показано в верхнем левом углу рис. 2.20, а его Булево выражение — на дополнительном дисплее.

Рис. 2.20. Результат синтеза логического устройства

 по заданной таблице истинности

 

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

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

 

Рис.2.21. Окно установки количества входов

 логического элемента