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

Пример 4.5. Минимизировать структуру устройства, алгоритм работы которого задан         элемент, что, в конечном счете, приводит к упрощению ее технической реализации.
следующей таблицей истинности:                                                                 Таким образом, выделение при минимизации системы ФАЛ общих областей
     x2              x1              x0                  z2        z1      z0           на картах Вейча позволят получить наиболее простую ее техническую реализацию.
                                                                                        При этом следует иметь ввиду, что общие области могут выделятся не на всех картах,
     0               0               0                   0         0       0
                                                                                        а лишь на части из них. Как правило, это приводит к упрощению технической
     0               0               1                   0         0       0            реализации.
     0               1               0                   1         1       1
     0               1               1                   1         0       0            3.3. Минимизация функций алгебры-логики на ЭВМ методом Квайна и Мак-Класски
     1               0               0                   1         1       1            На практике рассмотренные ранее методы минимизации ФАЛ с использованием карт
     1               0               1                   0         0       1            Вейча ограничивается числом переменных не более пяти. Это объясняется двумя
                                                                                        основными причинами:
     1               1               0                   1         1       1
                                                                                        • при увеличении числа переменных метод теряет свою наглядность, что снижает
     1               1               1                   0         1       0
                                                                                            эффективность его применения;
Решение. Нарисуем карты Вейча для каждой ФАЛ, входящей в заданную систему.              • так как выбор покрытий производится по большей части интуитивно, то
         Минимизируем данную систему ФАЛ по каждому выходу отдельно по                      конечный результат минимизации сильно зависит от индивидуального опыта
         известному алгоритму, как это показано на рис. 4.6.                                разработчика, что препятствует применению для минимизации ФАЛ ЭВМ.
                                                                                                При увеличении числа переменных для минимизации ФАЛ используются
                                                                                        методы, обладающие однозначностью алгоритма, что является предпосылкой
                                                                                        применения ЭВМ. К таким методам относится метод Квайна и Мак-Класки.
                                                                                                Алгоритм отыскания МДНФ этим методом сводится к следующему.
                                                                                        1. Находят покрытие П(z) заданной функции. Для этого формируют кубический
                                                                                            комплекс ФАЛ и в каждом i-ом кубическом комплексе отмечают кубы
                                                                                            (импликанты), не образовавшие i+1-й кубический комплекс. Отмеченные
               Рис. 4.6. Карты Вейча для системы ФАЛ, пример 4.5                            импликанты, называемые простыми, образуют покрытие заданной ФАЛ.
                                                                                        2. Строят таблицу покрытий матрицы Квайна. Строки указанной таблицы
Используя приведенные на рис. 3.6 карты Вейча, для заданной таблице истинности
                                                                                            соответствуют простым импликантам, а столбцы – 0-кубам (конституентам
можно записать следующую систему минимальных ФАЛ:
                                                                                            единицы) ФАЛ. На пересечении i-й строки и j-го столбца ставится метка, если
                                  z0 = x1 x0 + x2 x1 ,                                      импликанта i покрывает конституенту j. Отметим, что импликанта i покрывает
                                  z1 = x1 x0 + x2 x0 + x2 x1 ,                              конституенту j в случае, если она отличается от нее независимыми аргументами.
                                                                                        3. Определяю покрытие минимальной стоимости, для этого:
                                  z2 = x2 x1 + x2 x0 .                                    а) выделяют ядро Квайна. Если 0-куб заданной ФАЛ покрывается только одной
Техническая реализация данной системы потребует семь элементов 2И, два элемента               простой импликантой, то последняя является существенной и входит в ядро
2ИЛИ и один элемент 3ИЛИ, т.е. всего десять элементов.                                        Квайна и, следовательно, в покрытие минимальной стоимости;
          Нетрудно заметить, что полученные выражения содержат общие члены      x1 x0     б) из таблицы вычеркивают столбцы и строки, покрытые импликантами ядра
                                                                                              Квайна. Если в полученной после вычеркивания таблице содержатся простые
и   x2 x0 .   Поэтому техническую реализацию устройства можно упростить. При                  импликанты, они также включаются в ядро Квайна с последующим
использовании общих для нескольких элементов выходов для реализации                           вычеркиванием соответствующих строк и столбцов;
потребуется: пять элементов 2И, два элемента 2ИЛИ и один элемент 3ИЛИ, т.е. всего         в) сжимают таблицу по столбцам, для чего из нее вычеркивают столбцы, в которые
восемь элементов.                                                                             полностью входит любой из оставшихся столбцов;
       Анализ приведенных карт Вейча показывает, что на входных кодах 010, 100 и          г) сжимают таблицу по строкам, для чего из нее вычеркивают строки, которые
110 все три функции принимают единичное значение. Поэтому можно записать:                     полностью включаются в любую из оставшихся строк.
                   z0 = x1 x0 + x2 x0 + x2 x1 = x0 (x2 + x1 ) + x2 x1 ,
                                                                                                Последовательно сжимая таблицу по строкам и столбцам, получают
                                                                                        циклическую таблицу, импликанты которой должны входить в покрытие ФАЛ
                   z1 = x1 x0 + x2 x0 + x2 x1 = x0 ( x2 + x1 ) + x2 x1 ,                минимальной стоимости. На пересечении i-х строк циклической таблицы и
                                                                                        импликант, образующих ядро Квайна, получают МДНФ заданной функции.
                   z2 = x1 x0 + x2 x0 + x2 x1 = x0 (x2 + x1 ) + x2 x1.                          Проиллюстрируем применение описанного алгоритма на примере.
      Реализация этой схемы потребует четыре элемента 2И и четыре элемента
2ИЛИ, т.е. всего также восемь элементов. Однако из схемы исключен трехвходной

                                              37                                                                               38