3.3. Комбинации логических элементов

Цифровые системы строятся на основе комбинаций логических элементов. Такие комбинации могут быть описаны таблицей истинности, булевой функцией или логической схемой (табл. 3.2).

Таблица 3.2

Получение булевой функции из таблицы истинности

Входы	Выход	Входы	Выход
D С В А	Y	D С В А	Y
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1	0 0 0 0 0 0 0 0	1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	0 0 1 0 0 0 0 0

Эта таблица описывает все возможные комбинации четырех входов (А, В, С, D). Заметим, что только комбинация 1010 даст 1 или Н-сигнал на выходе. Эквивалентная этой таблице истинности булева функция приведена в заголовке табл. 3.2. Входы подчинены операции И, что дает булеву функцию (читается как D и НЕ-С и В и НЕ -A дают на выходе Y).

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

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

Рис. 3.5. Построение логических схем:

а — на основании булевой функции; б — упрощенный вариант

инверсии, которые могут рассматриваться как LOW- активные входы. Другими словами, чтобы активизировать элемент И, на рис. 3.5, б входы А к С должны быть LOW, a входы В и D - HIGH. Так как входы D и В должны быть HIGH для активизации элемента И, их называют HIGH-активными входами.

Рассмотрим другую таблицу истинности (табл. 3.3). Здесь две комбинации входов вызовут 1 или HIGH на выходе. Булевой функцией, соответствующей этой таблице истинности, становится тогда такая: = = Y (читается: D и НЕ-С и НЕ-В и НЕ-А или D и С и НЕ-В и А равно Y на выходе).

Рис. 3.6. Построение логической схемы по булевой функции

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

Рассмотрим схему, которая состоит из двух вентилей И и одного вентиля ИЛИ (рис. 3.7. а). Она может быть представлена выражением

f = •х2 + х1•

Схема составления таблицы истинности для этого выражения показана на рис. 3.10, б. Сначала для каждого входного значения определяются значения термов И, затем, с помощью операции ИЛИ, — результирующие значения функции f./ Таблица истинности функции f идентична таблице истинности функции Исключающее ИЛИ, так что схема с тремя вентилями, показанная на рис. 3.7, а, реализует функцию Исключающее ИЛИ с помощью вентилей И, ИЛИ и НЕ.

Таблица 3.3

Таблица истинности, соответствующая эквивалентному выражению = = Y

Входы	Выход	Входы	Выход
D С В А	Y	D С В А	Y
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1	0 0 0 0 0 0 0 0	1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	1 0 0 0 0 1 0 0

Рис. 3.7. Реализация функции Исключающее ИЛИ с использованием вентилей И, ИЛИ и НЕ: схема для функции Исключающее ИЛИ (а);

таблица истинности для выражения •х2 + х1• (б)

Логическое выражение •х2 + х1• называется суммой произведений, поскольку операцию ИЛИ иногда называют суммой, а операцию И — произведением. Следует отметить, что правильнее было бы записать это выражение так: f = ((•х2) + (х1•())

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

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

Таблица 3.4

Функции трех переменных

х1	х2	х3	f1	f2
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 1 0 1 0 0 0 1	1 1 1 0 1 1 0 0

Предположим, мы хотим составить схему функции f1 на основе вентилей И, ИЛИ и НЕ. Для каждой строки таблицы, в которой f1 = 1, в формулу суммы произведений включается терм И со всеми тремя входными переменными. К одной, двум или трем из этих переменных по отдельности нужно применить оператор — НЕ таким образом, чтобы терм был равен 1 только в том случае, когда значения переменных соответствуют данной строке таблицы истинности. Это означает, что если в этой строке хi = 0, в произведение включается элемент , а если хi = 1 -элемент хi. Например, в четвертой строке таблицы истинности значение функции 1 соответствует входным значениям (x1 х2 х3) - (0, 1, 1)

Данной строке соответствует терм х2х3. Составив аналогичные термы для всех строк таблицы истинности, в которых функция f1 имеет значение 1, мы получим вот такую сумму произведений:

f1 = + х3 + х2х3 + x1х2х3

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

а) б)

Рис. 3.8. Логическая схема для функции f₁ (а) и соответствующая ей минимальная схема реализации (б)

3.3.1. Минимизация логических выражений

Теперь вы знаете, как формируется сумма произведений для произвольной таблицы истинности. Фактически для каждой таблицы истинности существует множество эквивалентных выражений и логических схем. Два логических выражения или две логические схемы считаются эквивалентными, если у них одинаковые таблицы истинности. Сформированной нами в предыдущем разделе сумма произведений для функции f1 эквивалентно, в частности, такое выражение: + .

Чтобы это доказать, достаточно составить таблицу истинности данного выражения и сравнить ее с таблицей 3.1. Процесс создания таблицы истинности выражения + х2х3, приведенной в табл. 3.5, можно разбить на три этапа. Сначала для каждого набора входных значений вычисляется произведение , затем — произведение х2х3, после чего оба результата складываются для получения окончательного значения. Как видите, наша таблица истинности идентична таблице истинности функции f1, приведенной в табл. 3.1.

Для упрощения логических выражений выполняется ряд алгебраических операций. Они основаны на двух логических законах, о которых мы еще не упоминали: дистрибутивном w(y+z)=wy+wz и законе исключенного третьего w+=1.

Таблица 3.5

Вычисление выражения + х2х3

x1 x2 x3		х2х3	+ х2х3 = f1
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 1 0 0 0 0 0 0	0 0 0 1 0 0 0 1	1 1 0 1 0 0 0 1

В табл. 3.6. приведено доказательство истинности дистрибутивного закона.

Таблица 3.6

Использование таблиц истинности для доказательства

эквивалентности выражений.

w у z	y + z	Значение w(y + z)	wy	wz	Значение wy + wz
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 1 1 1 0 1 1 1	0 0 0 0 0 1 1 1	0 0 0 0 0 0 1 1	0 0 0 0 0 1 0 1	0 0 0 0 0 1 1 1

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

Вот еще одна форма дистрибутивного закона, которую мы приводим для полноты изложения материала, хотя она нам и не потребуется:

w +yz = (w+y)(w + z)

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

Обычно при оценке стоимости выражения учитывается общее количество вентилей и их входных значений (входных линий), необходимых для реализации выражения в форме, показанной на рис. 3.8. Например, стоимость большей схемы на этом рисунке равна 21: 5 вентилей плюс 16 входных значений. Инверсия входных значений при подсчете игнорируется. Стоимость более простого выражения равна 9:3 вентиля плюс 6 входных значений. Теперь можно определить и критерий минимизации. Сумма произведений считается минимальной, если не существует эквивалентного ей выражения меньшей стоимости. В простых примерах, которые мы будем рассматривать в этой книге, минимальный размер выражений будет очевидным. Поэтому мы не считаем нужным приводить строгие доказательства их минимальности.

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

f1 = + х3 + х2х3 + x1х2х3 = (+ х3) + (+x1) х2х3 = 1 + 1 х2х3 = + х2х3

Это выражение минимально. Соответствующая ему логическая схема приведена на уже упоминаемом нами рис. 3.8.

Сгруппировать термы попарно, с тем чтобы упростить исходное выражение, не всегда так просто, как в примере с функцией f1. В случае затруднений помогает такое правило: w + w = w.

Это правило позволяет повторять термы-произведения при необходимости объединить некоторый терм более чем с одним другим термом. Для примера рассмотрим функцию f2 из табл. 3.4. Исходная сума произведений, формируемая на основе таблицы истинности этой функции, такова:

f2 = + х3 + х2 + x1 + x1 х3

Повторив первый терм и изменив порядок следования термов (на основе коммутативного закона), мы получим:

f2 = + х3 + x1 + x1 х3 + + х2

Сгруппировав термы попарно и вынеся одинаковые произведения за скобки, сможем записать следующее выражение:

f2 = (+ х3) + x1(+ х3) + (+ х2) = + x1+

Первую пару термов можно упростить еще раз, и тогда получится минимальное выражение: f2 = +

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

Таблица 3.7

Законы двоичной логики

Название закона Алгебраическое тождество

Коммутативный w + у = у + w wу = yw Ассоциативный (w + у) + z = у + (w + z) (wy)z = w(yz) Дистрибутивный w + yz = (w + y)(w + z) w(y + z) = wy + wz Идемпотентности w + w = w ww= w Возведение в степень = w Дополнения (закон исключенного третьего) w + = 1 w = 0 Закон де Моргана () = wy = + 1+w = l 0•w = 0 0 + w = w 1•w = w

3.3.2. Минимизация функций с использованием карты Карно

При минимизации функций f1 и f2 из табл. 3.4 нам приходилось искать наиболее активные способы преобразования исходных выражений. Например, далеко не очевидным было решение повторить терм на первом шаге минимизации функции f2.- Для того чтобы как можно быстрее получить минимальное выражение, представляющее логическую функцию нескольких переменных, можно воспользоваться графическим представлением таблицы истинности, называемым картой Карно. Для функции трех переменных карта Карно представляет собой прямоугольник, составленный из восьми квадратов, расположенных в два ряда по четыре в каждом (рис. 3.9, а). Каждый квадрат соответствует конкретному набору

Рис. 3.9. Минимизация функций с использованием карт Карно: карта для трех переменных (а); карта для четырех переменных (б);

значений входных переменных. Например, третий квадрат в верхнем ряду представляет значения (x1 х2, х3) = (1, 1, 0).

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

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

верхнего ряда соответствуют термам и х2. Эта пара термов упрощается следующим образом:

+ х2.= .

что мы и сделали в предыдущем разделе при минимизации алгебраического выражения для функции f2. Минимизированное произведение, соответствующее группе квадратов, — это произведение входных переменных, значения которых одинаковы для всех квадратов этой группы. Если значение входной переменной хi равно нулю для всех квадратов группы, тогда переменная хi входит

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

Карты Карно могут использоваться и для минимизации функций более чем трех переменных. Карту для четырех переменных можно составить из двух карт для трех переменных. Два примера таких карт показаны на рис. 3.9, б, и под каждой из них приведено минимальное выражение для представляемой ею функции Если на карте для трех переменных квадраты можно группировать по два и по четыре, то на карте для четырех переменных их можно группировать еще и по восемь. Пример такой группировки показан на карте функции g3 Обратите внимание, что четыре угловых квадрата можно объединить в одну группу, как на карте функции g2, где на их основе составлен терм . Как и в случае карты для трех переменных, терм, соответствующий группе квадратов, представляет собой произведение переменных, значения которых одинаковы для всех квадратов этой группы. Так, в группе из четырех квадратов в правом верхнем углу карты функции g2 во всех квадратах х1 = 1 и х3 = 0, поэтому эту группу представляет терм х1. Остальные две переменные, х2 и x4 имеют в квадратах этой группы разные значения. Карты Карно можно использовать и для функций пяти переменных. В этом случае для представления функции используются две карты для четырех переменных: одна из них соответствует значению 0 пятой переменной, а другая – ее значению 1.

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

В общем случае количество квадратов в группе должно быть равным 2k, где k — целое число.

Теперь давайте рассмотрим процедуру получения с помощью карты Карно минимальной суммы произведений. Как видно на рис. 3.9, большей группе квадратов соответствует произведение меньшего числа переменных. Поэтому для получения минимального выражения нужно объединить все квадраты на карте, содержащие единицы, в как можно меньшее количество групп, выбирая наибольшие из них, так чтобы при этом охватить все единицы. Для примера рассмотрим карту функции g2 приведенную на рис. 3.9, б.

Как вы уже знаете, единицы по ее углам составляют группу из четырех квадратов, представляемую термом . Еще одна группа из четырех квадратов располагается в правом верхнем углу и представлена термом х1. Эти две группы охватывают все единицы на карте, за исключением одной единицы в квадрате (х1, х2, х3, х4) = (0,1,0,1). Наибольшая группа единиц, включающая этот квадрат, — это группа из двух квадратов, представленная термом х2х4. Таким образом, минимальное выражение для функции g2 должно быть следующим:

g2 = + х1 + х2х4

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

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

3.3.3. Безразличные значения

В некоторых случаях определенные наборы входных значений цифровых схем никогда не используются. Для примера рассмотрим двоично-десятичное представление числа (Binary-Coded Decimal, BCD). Десятичные цифры от 0 до 9 можно представить с помощью четырех двоичных переменных, b3 b2, b1 и b0 (рис. 3.10). Эти четыре переменные могут составить 16 разных наборов значений, из которых для представления десятичных цифр используются только 10. Оставшиеся значения не используются. Следовательно, логическая схема, обрабатывающая данные в формате BCD, никогда не получит в качестве входных данных ни один из шести оставшихся наборов значений.

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

Такие значения называются безразличными (don't care) и в таблице истинности они обозначаются буквой «d». При реализации функции им можно присвоить либо

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

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

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

3.3.4. Синтез вентилей И-НЕ и ИЛИ-НЕ

А сейчас нам предстоит рассмотреть еще два базовых логических вентиля, называемых И-НЕ и ИЛИ-НЕ. Эти вентили очень широко применяются в логических схемах, что объясняется простотой их реализации. Таблицы истинности вентилей И-НЕ и ИЛИ-НЕ приведены на рис. 3.11.

Рис. 3.11. Вентили: И-НЕ (а); ИЛИ-НЕ (б)

Они представляют собой функции И и ИЛИ, к результату которых применена функция НЕ. Если мы обозначим операторы И-НЕ и ИЛИ-НЕ символами «» и «», то, используя закон де Моргана (см. табл. 3.5), сможем представить их следующим образом:

х1  х2 = = +; х1  х2 = = 

Вентили И-НЕ и ИЛИ-НЕ могут использоваться и с более чем двумя входными переменными, и действуют они в соответствии с очевидным обобщением закона де Моргана:

х1х2…xn==++…+ и х1 х2 … xn = = …

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

(х1  х2)  (х3  x4) == = х1х2 + х3x4

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

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

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

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

Рис. 3.12. Эквивалентные схемы на основе вентилей И-НЕ и вентилей И и ИЛИ

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

Рис. 3.17. Реализация логических функций с тремя входными переменными на основе вентилей с двумя входами: И и ИЛИ (а); И-НЕ (б)

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

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

Еще раз хотим обратить внимание читателя на тот факт, что для каждой логической функции существует множество вариантов реализации. Для практического воплощения функции важно выбрать вариант с наименьшей стоимостью. Кроме того, часто бывает необходимым минимизировать задержку распространения сигнала в логической схеме. С идеей минимизации схем мы познакомили вас в предыдущих разделах, чтобы объяснить суть процесса логического синтеза и показать, счет чего может быть достигнуто снижение стоимости реальных логических схем. Для этой цели можно применить карты Карно, которые подскажут, какие не алгебраические операции приведут к оптимальному решению. Оптимизацию схем не обязательно выполнять вручную. К услугам конструкторов имеется сложное и достаточно мощное программное обеспечение для автоматизированного проектирования (Computer Aided Design, CAD). Пользуясь такой программой, конструктор задает исходную функцию, и программа сама генерирует наиболее эффективную и простую схему для ее реализации.