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

а о

Рис. 1.18. Другая форма символов для операций НЕ-И и НЕ-ИЛИ.

а - операция НЕ-И; б - операция НЕ-ИЛИ. V .

ветствующая карта Карно. Сравнение с рис. 1.17 показывает, что такой вентиль полностью эквивалентен вентилю НЕ-И. На рис. 1.18,6 показан вентиль И с инвертированием входных величин. Из карты Карно вытекает эквивалентность этого вентиля НЕ-ИЛИ.

1.8. ОСНОВНЫЕ СООТНОШЕНИЯ

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

(а) УУ=У, y-f У=У.

Эти важные соотношения полезны при преобразовании функций.

(б) YZZY.

Порядок указания переменных для операции И не влияет на значения функции.

(в) Y+Z=Z+Y.

r+r=r

L J

YZ-IY 6

i-i 1 1 I

в

хчУг)=(х*УКХ*г}

Рис. 1.19. Иллюстрация основных правил.

X о 1

о 1

х-х = о

о 1

о 1

о 1

о 1

Рис. 1.19 (продолжение).

Х-Х и

к

О f

Для операции ИЛИ порядок задания входных величин также не существен.

(г) X(Y+Z) = (XY) + (XZ). Алгоритм представления произведения в виде суммы произведений позволяет переводить выражения из PS-формы в SP-форму.

(<3) X+(YZ) = (X-1-Y).(X+Z). Алгоритм представления суммы в виде произведения сумм позволяет переводить выражения из SP-формы в PS-форму.

(е) 0Х=0 и \Х=Х.

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

(ж) 0--Х=Л: и \+Х=\.

Максимальная комбинация переменной с тождественным нулем совпадает с переменной, а максимальная комбинация с единицей дает 1.

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

(з) ХХ=0 и Х+Х=1.

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

(и) 1=Х.

Левая из трех карт Карно на рис. 1.19, ы определяет исходную переменную X. Операция НЕ над переменной меняет местами О и 1 (средняя карта Карно). Повторное выполнение операции НЕ приводит к исходному положению О и 1 (правая карта Карно). Правила (з) и^ {и) описывают свойства операции НЕ. (к) ХУХ+У.

Для функции f=XY единица на карте Карно находится в правой нижней клетке. Операция отрицания над этой функцией порождает О в правой нижней клетке и 1 во всех остальных клетках карты (рис. 1.19,к). Такая карта идентична карте для функции X+Y. Это равенство уже отмечалось выше при сопоставлении карт на рис. 1.17, а и 1.18, а при рассмотрении операции НЕ-И. Обратите внимание, что последовательное применение операций И и НЕ эквивалентно операции ИЛИ, а ИЛИ и НЕ эквивалентно И.

Правило (к) в книгах по теории переключательных схем часто называют теоремой де Моргана.

Можно отметить, что в разд. 1.1-1.7 равенства представлены в стандартной форме. Правила же, приведенные в этом разделе.

(). Эти правила выражены в форме суждений исчисления высказываний и могут проверяться по правилам алгебры логики. Поскольку методы исчисления высказываний в данном случае полезны лишь для утверждения справедливости нескольких тождеств, эти приемы рассмотрения проиллюстрируем лишь на одном примере, а именно на формуле XY=X+Y (рис. 1.19, к). В табл. 1.5 первые два столбца соответствуют высказываниям относительно значений переменных X и У в терминах истина (7) и ложь (F), а не в цифровых обозначениях 1 и 0. Каждая строка столбца 3 {XY) - результат выполнения операции И над содержимым соответствующих строк столбцов 1 и 2. В столбцах 4 и 5 указаны результаты операции

НЕ над переменными X и У. В каждой строке столбца 6 (Х-Ь У) содержится результат операции И над содержимым соответствующих строк столбцов 4 и 5. Столбец 7 {X-Y) содержит результаты операции НЕ над содержимым столбца 3. Столбец 8 образован результатами проверки на тождество ( = ) содержимого столбцов 6 и 7.

1.9. КАРТЫ КАРНО КАК СРЕДСТВО ПРОЕКТИРОВАНИЯ

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

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

Таблица 1.5 имеют форму равенств меж-

Проверка истинности тождества Ду переменными и выраже-

ХУ=-Х+У ниями, полученными путем

применения определенных

, 23 456 7 8 операций к этим перемен-

X Y X Y + = НЫМ.

-- Знак равенства (=) в

ттт т т вышеприведенных правилах

iP FTT т т должен по существу пони-

ттт FFF F т маться как знак тождества

следней строк, а также клетки первого и последнего столбцов.

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

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

Рис. 1.20. Карта функции f(W, X, У, Z)-. = WXYZ.

На рис. 1.20 указаны значения функции для 16 различных возможных комбинаций значений четырех переменных W, X, Y и Z. Карта дает полное представление функции. Эту же функцию переменных W, X, Y и Z можно представить в следующей полиномиальной форме:

/ (W, X, Y, Z)={WXYZ)+{{MXYZ)+{mXYZ) -f

+ (mxYZ)+{mxYZ) -\- {mxYz)+{mxYZ) -f

+ (fiWXYZ) -f {mXYZ) -4- (1WXYZ) -f iSWXYZ)+

+{mxYZ) -f {mxYZ) -f {mxYz) -f -\-{mxYZ)+(mxYZ).

Однако можно пользоваться и простой формой записи этой функции:-

/=S(9)=1FXFZ.

В соответствии с этим запись

/=Е (9,13) = WXYZ-]- WXYZ указывает на наличие в функции двух минитермов. Пользуясь

Приведенным выше правилом (г), эту функцию можно представить в виде

f = WYZ(X+X). Поскольку из правила (з) следует

Х+Х = 1,

то запись функции f можно представить в сокращенной форме

/ = WYZ или 2 (9, 13) = WVZ.

Анализ рис. 1.21 показывает, что у функции f=2 (9, 13), представленной обведенными рамкой двумя соседними клетками, X принимает значение как О, так и 1. Следовательно, при

Рис. 1.21. Карта i=WYZ.

Pec. 1.22. Карта /=WZ.

изображении данной функции переменной X вообще можно пренебречь. На рис. 1.22 приведена карта с обведенными рамкой четырьмя соседними клетками. На основании предыдущего рассмотрения две клетки второй строки можно представить в виде

f = WYZ.

Аналогично две клетки третьей строки можно представить в виде

fWYZ.

В целом для данной карты

/ = WYZ+WYZ = WZ (Г+F) = WZ.

Этот результат может быть получен непосредственным анализом карты. Обведенные клетки позволяют провести упрощение по столбцам, сохраняя лишь W, поскольку X принимает значения как 1, так и О, и по строкам, сохраняя только Z, поскольку Y оказывается равным и О и 1.

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

Рис. 1.23. Карта t=-WX.

00 01

00 01 11 10

На рис. 1.24 показано, что смежными, подлежащими объединению можно считать элементы первого и последнего столбцов и первой и последней строк. На рис. 1.25 показано восемь смежных клеток. Единственной переменной, сохраняемой при записи функции, является W (со значением W), так как все остальные переменные X, Y v. Z принимают значения и 1, и 0. Такая груп-

Рис. 1.24. Карта /=Ж

Рис. 1.25. Карта f=PF.

пировка клеток, конечно, очевидна, поскольку полностью отвечает способу построения карты Карно.

Если смежные клетки образуют фигуру типа прямоугольника или квадрата либо располагаются вдоль строки или столбца, то их можно группировать при условии, что число объединяемых клеток равно 2 (т. е. 2, 4, 8, 16 и т. п.).

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

f = YZWY.

На рис. 1.27 показана группировка, когда две клетки принадлежат одновременно двум выделенным группам соседних клеток.

00 01

00 01 11 ю

00 01 11 10

Рис. 1.26. Карта f=yZ-l-W.

Рис. 1.27. Карта ]=WXXZ.

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

ш

00 01 11 10

00 01 11 10

Рис. 1.28. Карта f=WY+YZ+WX. Рис. 1.29. Карта f=WXY+WXZ,

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

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

Рис. 1.30. Карта f{V,W, X, Y, Z)==WXZ.

На рис. 1.30 с помощью карт изображена функция пяти переменных V, W, X, Y, Z. Когда переменных больше четырех, трудно отображать близость отдельных клеток друг к другу на плоских картах. Заметим, что клетка WXYZ на карте для значения V является смежной с клеткой WXYZ на карте для V. Аналогично две выделенные клетки на карте У являются смежными с двумя клетками, выделенными на карте V.

Рис. 1.31. Карта f=XYZ.

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

В некоторых случаях проще группировать пустые (содержащие 0) клетки. При группировке пустых клеток получают выра-