Конспекты лекций по цифровой электронике. Насыров И.А. - 15 стр.

числа внешних соединений даже за счет увеличения числа элементов и внутренних      Решение.   Как было показано в примере 2.3, СДНФ для данной ФАЛ запишется в
соединений. Эти требования диктуются требованиями повышения надежности                        виде   y ( x2 , x1 , x0 ) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0 . Запишем ее
электронных средств.
                                                                                               кубический комплекс (рис. 3.1): K(y) = (011, 101, 110, 111, 11-, 1-1, -11).
       Однако при проектировании аппаратуры с применением БИС и СБИС
требование уменьшения числа корпусов ИС и количества их соединений между
собой по-прежнему остается весьма важным.
       Требование уменьшения числа элементарных ЛЭ, входящих в
разрабатываемое устройство, в настоящее время также не потеряло своей
актуальности. Объясняется это все более широким использованием при
проектировании электронных средств программируемых логических СБИС широкого
применения и полузаказных СБИС на основе базовых матричных кристаллов. Эти
СБИС и БИС, как правило, содержат отдельные нескоммутированные между собой
элементарные ЛЭ, например 2И-НЕ или 2ИЛИ-НЕ, или просто наборы транзисторов,
резисторов и диодов, которые могут быть соединены между собой в соответствии с     Рис. 4.1. Геометрическое представление          Рис. 4.2. Структурная схема логического
заданным алгоритмом обработки логических сигналов. Поскольку число элементов в               кубического комплекса для ФАЛ                   устройства, реализующая
одной СБИС задано из технологических соображений, то минимизация ФАЛ по                      из примера 3.1                                  МДНФ ФАЛ
критерию уменьшения числа используемых элементов позволяет на одном кристалле
                                                                                   Нулевой кубический комплекс включает все вершины куба (рис. 4.1), поэтому
решать более сложные задачи логической обработки сигналов, т.е. в конечном счете
                                                                                   образует покрытие функции:
уменьшать число требуемых ИС и связей между ними. Это снижает стоимость и
                                                                                             П1(y) = K0=(011; 101; 110; 111), найдем цену покрытия Ц П = 12.
повышает надежность электронной аппаратуры.                                                                                                                  1

       Рассмотрим ряд методов, позволяющих провести минимизацию ФАЛ по             Все вершины куба включаются также в единичный кубический комплекс K1, поэтому
критерию уменьшения числа элементарных ЛЭ.                                         и он образует покрытие ФАЛ:
       Наиболее просто и наглядно задача минимизации ФАЛ решается с                               П2(y) = K1= (11-; 1-1; -11), цена покрытия будет Ц П = 3.
                                                                                                                                                         2
использованием ее кубических представлений. Ранее было показано, что любая
                                                                                         Перебирая сочетания кубов различных рангов, можно получить и другие
логическая функция n-переменных характеризуется своим кубическим комплексом
                                                                                   покрытия ФАЛ, но здесь очевидно, что П2(y) для данной ФАЛ будет иметь
K(y), образованным кубическими комплексами K0, K1, …, Kn-1. Из кубического
                                                                                   минимальную цену, т.е. является покрытием Квайна. Соответствующая этому
комплекса K(y) всегда можно выделить множество кубов П(y) таких, что каждый член
комплекса K0, т.е. вершина куба, будет включен по крайней мере в один куб из       покрытию МДНФ запишется в виде: y2 ( x2 , x1 , x0 ) = x2 x1 + x2 x0 + x1 x0 .
множества П(y). Множество кубов П(y) называется покрытием комплекса K(y), или             Анализируя получившееся алгебраическое выражение для ФАЛ, можно
покрытием логической функции. Вполне очевидно, что для любой ФАЛ существует        сказать, что для реализации этой функции в виде структурной схемы потребуется 3
несколько ее покрытий. В свою очередь, каждому покрытию П(y), так же как и         логических элемента 2И и один элемент 3ИЛИ (рис. 4.2), в отличие от структурной
самому комплексу, соответствует своя дизъюнктивная нормальная форма,               схемы представленной на рис 3.1, не потребуется ЛЭ реализующих операцию НЕ.
получаемая логическим суммированием логических произведений, соответствующих              Таким образом, полученная в результате минимизации функция и ее
выделенным кубам ФАЛ.                                                              структурная схема проще. Техническая реализация такой схемы будет дешевле и
       Сложность полученной таким образом ДНФ принято характеризовать              надежней.
понятием «цена покрытия» (ЦП), которая равна сумме цен всех кубов, составляющих
                                                                                   4.2. Минимизация функций алгебры-логики с использованием карт Вейча
данное покрытие П(y): Ц П = ∑   Ц K . В свою очередь, цена одного r-куба ФАЛ n-    Данный метод базируется на табличном представлении ФАЛ. Он широко
переменных определяется как разность полного числа входных переменных и ранга      используется при ручной, без применения ЭВМ, минимизации ФАЛ, число
соответствующего куба, т.е. равна числу переменных в соответствующей               переменных в которой обычно не превышает пяти.
дизъюнкции: ЦK = n-r. Так, для ФАЛ трех переменных цена 0-куба равна трем, а 2-           Карта Вейча – это прямоугольная таблица, число клеток в которой для ФАЛ
куба — единице.                                                                    n-переменных равно 2n, каждой из клеток поставлен в соответствие некоторый набор
       В соответствии со сказанным, задача минимизации ФАЛ сводится к поиску       входных переменных, причем рядом расположенным клеткам соответствуют
покрытия П(y) кубического комплекса K(y), имеющего минимальную цену.               соседние наборы входных переменных (кодов), а в самих клетках записаны значения
       Покрытие П(y) комплекса K(y), имеющее минимальную цену, называется          функций, определенные для этих кодов.
покрытием Квайна, а соответствующая этому покрытию ДНФ — называется                       Рассмотрим построение карт Вейча для функций двух, трех и четырех
минимальной ДНФ (МДНФ).                                                            переменных.
Пример 4.1. Минимизировать ФАЛ заданную в виде словесного описания в примере              Карта Вейча функции двух переменных приведена на рис. 4.3. Она содержит
             2.1. Составить структурную схему логического устройства.              четыре клетки и является плоской фигурой. Для удобства использования по краям
                                       29                                                                                     30