DigitElectrLabsPart1 (Лабы), страница 8

Объясняется этовсе более широким использованием при проектировании электронных средств программируемых логических СБИС широкого применения и полузаказных СБИС на основебазовых матричных кристаллов. Эти СБИС и БИС, как правило, содержат отдельныенескоммутированные между собой элементарные ЛЭ, например Стрелка Пирса илиШтрих Шеффера (см.

таблицу 2.3), или просто наборы транзисторов, резисторов идиодов, которые могут быть соединены между собой в соответствии с заданным алгоритмом обработки логических сигналов. Поскольку число элементов в одной СБИСзадано из технологических соображений, то минимизация ФАЛ по критерию уменьшения числа используемых элементов позволяет на одном кристалле решать более сложные задачи логической обработки сигналов, т.е. в конечном счете уменьшать числотребуемых ИС и связей между ними. Это снижает стоимость и повышает надежность49электронной аппаратуры.Рассмотрим ряд методов, позволяющих провести минимизацию ФАЛ по критериюуменьшения числа элементарных ЛЭ.4.1Минимизация функций алгебры-логикипри помощи кубических представленийНаиболее просто и наглядно задача минимизации ФАЛ решается с использованиемее кубических представлений (см.

раздел 2.3.5). Ранее было показано, что любая логическая функция n-переменных характеризуется своим кубическим комплексом K(z),образованным кубическими комплексами K0 , K1 , . . . , Kn−1 . Из кубического комплексаK(z) всегда можно выделить множество кубов Π(z) таких, что каждый член комплексаK0 , т.е. вершина куба, будет включен по крайней мере в один куб из множества Π(z).Множество кубов Π(z) называется покрытием комплекса K(z), или покрытием логической функции.

Очевидно, что для любой ФАЛ существует несколько ее покрытий.В свою очередь, каждому покрытию Π(z), так же как и самому комплексу, соответствует своя дизъюнктивная нормальная форма, получаемая логическим суммированиемлогических произведений, соответствующих выделенным кубам ФАЛ.Сложность полученной таким образом ДНФ принято характеризовать понятием«цена покрытия» (ЦПP), которая равна сумме цен всех кубов, составляющих данноепокрытие Π(z): ЦП =ЦК .

В свою очередь, цена одного r-куба ФАЛ n-переменныхопределяется как разность полного числа входных переменных и ранга соответствующего куба, т.е. равна числу переменных в соответствующей дизъюнкции: ЦK = n − r.Так, для ФАЛ трех переменных цена 0-куба равна трем, а 2-куба - единице.В соответствии со сказанным, задача минимизации ФАЛ сводится к поиску покрытия Π(z) кубического комплекса K(z), имеющего минимальную цену.Покрытие Π(z) комплекса K(z), имеющее минимальную цену, называется покрытием Квайна, а соответствующая этому покрытию ДНФ — называется минимальнойдизъюктивной нормальной формой (МДНФ).Пример 4.1 Минимизировать ФАЛ, заданную в виде словесного описания в примере 2.1.

Составить структурную схему логического устройства.Решение. Как было показано в примере 2.3, СДНФ для данной ФАЛ запишется в видеz = x̄2 x1 x0 + x2 x̄1 x0 + x2 x1 x̄0 + x2 x1 x0 .Представим ФАЛ в виде трехмерного куба (рис. 4.1). Запишем кубический комплексK(z) = (011, 101, 110, 111, 11−, 1 − 1, −11). Нулевой кубический комплекс включает всевершины куба (зелёные точки на рис. 4.1):Π1 (z) = K0 = (011, 101, 110, 111).PНайдем цену покрытия: ЦП1 = ЦК0 = (3 − 0) + (3 − 0) + (3 − 0) + (3 − 0) = 12.Все вершины куба включаются так же в единичный кубический комплекс K1 (ребракуба, выделенные красным на рис.

4.1), поэтому и он образует покрытие ФАЛ:Π2 (z) = K1 = (11−, 1 − 1, −11).PНайдем цену покрытия: ЦП2 = ЦК1 = (2 − 1) + (2 − 1) + (2 − 1) = 3.Перебирая сочетания кубов различных рангов, можно получить и другие покрытияФАЛ, но здесь очевидно, что Π2 (z) для данной ФАЛ будет иметь минимальную цену,50Рис. 4.1. Геометрическое представление кубического комплекса для ФАЛт.

е. является покрытием Квайна. Соответствующая этому покрытию МДНФ запишетсяв виде:z2 (x2 , x1 , x0 ) = x2 x1 + x2 x0 + x1 x0 .(4.1)Анализируя получившееся выражение для ФАЛ, можно сказать, что для реализацииэтой функции в виде структурной схемы потребуются 3 логических элемента 2И и одинэлемент 3ИЛИ (рис.4.2) в отличие от структурной схемы, представленной на рис 3.1,не потребуется ЛЭ реализующих операцию НЕ.Рис. 4.2. Структурная схема логического устройства, реализующая МДНФ ФАЛТаким образом, полученная в результате минимизации функция и ее структурнаясхема проще.

Техническая реализация такой схемы будет дешевле и надежней.4.2Минимизация функций алгебры–логикис использованием карт ВейчаДанный метод базируется на табличном представлении ФАЛ. Он широко используется при ручной, без применения ЭВМ, минимизации ФАЛ, число переменных вкоторой обычно не превышает пяти.Карта Вейча — это прямоугольная таблица, число клеток в которой для ФАЛ nпеременных равно 2n , каждой из клеток поставлен в соответствие некоторый набор51входных переменных, причем рядом расположенным клеткам соответствуют соседниенаборы входных переменных (кодов), а в самих клетках записаны значения функций,определенные для этих кодов.Рассмотрим построение карт Вейча для функций двух, трех и четырех переменных.Карта Вейча функции двух переменных приведена в таблице 4.1.

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

Карта Вейча функции двух переменныхx0x̄0x1f (x1 , x0 )f (x1 , x̄0 )x̄1f (x̄1 , x0 )f (x̄1 , x̄0 )Карта Вейча функции трех переменных приведена в таблице 4.2. Она содержитвосемь клеток. Наборы входных переменных, соответствующие крайним левому и правому столбцам, являются соседними. Поэтому данную карту удобно представить какповерхность цилиндра и она, в отличие от карты двух переменных, является объемнойфигурой.Таблица 4.2. Карта Вейча функции трёх переменныхx0x̄0x1x1f (x̄2 , x1 , x0 ) f (x2 , x1 , x0 )f (x̄2 , x1 , x̄0 ) f (x2 , x1 , x̄0 )x̄2x2x̄1f (x2 , x̄1 , x0 )f (x2 , x̄1 , x̄0 )x2x̄1f (x̄2 , x̄1 , x0 )f (x̄2 , x̄1 , x̄0 )x̄2Карта Вейча функции четырех переменных приведена в таблице 4.3.

Она содержит16 клеток. Очевидно, что наборы входных переменных, соответствующие крайним левому и правому столбцам, как и в карте для трех переменных, являются соседними.Кроме этого соседние коды содержатся в нижней и верхней строках карты. Поэтомуданная карта тоже является объемной фигурой и может быть представлена как поверхность тора.Таблица 4.3. Карта Вейча функции четырёх переменныхx0x0x̄0x̄0x1f (x̄3 , x̄2 , x1 , x0 )f (x̄3 , x2 , x1 , x0 )f (x̄3 , x2 , x1 , x̄0 )f (x̄3 , x̄2 , x1 , x̄0 )x̄3x1f (x3 , x̄2 , x1 , x0 )f (x3 , x2 , x1 , x0 )f (x3 , x2 , x1 , x̄0 )f (x3 , x̄2 , x1 , x̄0 )x3x̄1f (x3 , x̄2 , x̄1 , x0 )f (x3 , x2 , x̄1 , x0 )f (x3 , x2 , x̄1 , x̄0 )f (x3 , x̄2 , x̄1 , x̄0 )x3x̄1f (x̄3 , x̄2 , x̄1 , x0 )f (x̄3 , x2 , x̄1 , x0 )f (x̄3 , x2 , x̄1 , x̄0 )f (x̄3 , x̄2 , x̄1 , x̄0 )x̄3x̄2x2x2x̄2Еще более сложную форму имеет карта Вейча функции пяти переменных.

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

Вобоих случаях получают равносильные выражения, которые, однако, могут отличатьсяпо числу членов (т. е. цене) и выполняемым логическим операциям.Алгоритм минимизации ФАЛ сводится к следующему.1. На карте Вейча ФАЛ n–переменных выделяют прямоугольные области, объединяющие выбранные значения функции (лог.

0 или лог. 1). Каждая область должнасодержать 2k клеток, где k – целое число. Выделенные области могут пересекаться, т. е. одна или несколько клеток могут включаться в различные области.2. Каждой из выделенных областей соответствует k-куб исходной ФАЛ, которыйпредставляется самостоятельным логическим произведением переменных, значения которых в рамках выделенной области остаются постоянными.

Каждое произведение содержит n − k переменных и носит название импликанты.3. Из полученного множества выбирают минимальное число максимально большихобластей, включающих все выбранные значения ФАЛ.4. Логически суммируют импликанты, соответствующие выбранным областям. Полученная сумма образует МДНФ, т.е. является покрытием ФАЛ минимальнойстоимости (покрытием Квайна).При объединении клеток с единичными значениями ФАЛ получают МДНФ самойфункции, а при объединении клеток с нулевыми значениями ФАЛ — МДНФ функции,инверсной заданной. Последнее легко объясняется при помощи тождеств, данных втаблице 2.2.Пример 4.2 Минимизировать ФАЛ, заданную в виде словесного описания в примере 2.1 при помощи карты Вейча. Получить МДНФ для самой функции и дляфункции, инверсной заданной. Сравнить цены покрытия.Решение.