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

Пример 4.6. Минимизировать ФАЛ                                                                       4. Согласно полученной таблице простыми импликантами являются 0-0- и -0-0, так
                                                                                                         как только первая покрывает 0-куб 0001 и только вторая покрывает 0-куб 0010.
                         z(x) = Σ(0, 1, 2, 4, 5, 7, 8, 10, 12, 14, 15).
                                                                                                     5. В оставшейся после вычеркивания существенных импликант и покрытых ими
Решение. Цена покрытия исходной ФАЛ ЦП= 44.                                                              конституент единицы таблице больше нет существенных импликант. Поэтому
1. Сформируем кубический комплекс K(z). Формирование кубического комплекса                               произведем сжатие по столбцам и строкам. Первоначальное сжатие по столбцам
   K(z) удобно выполнять при помощи разбиения конституент ФАЛ на группы,                                 не выполняется, так как в таблице отсутствуют столбцы входящие в любой из
   содержащие одинаковое количество единиц. При таком представлении кубы                                 оставшихся. Таблица сжимается по строкам, так как первая строка полностью
   более высокого ранга могут образовать только кубы, находящиеся в                                      входит во вторую, а четвертая строка полностью входит в пятую. Поэтому из
   расположенных рядом группах. В рассматриваемом примере для ФАЛ четырех                                таблицы вычеркиваем строки с номерами один и четыре.
   переменных можно выделить пять групп, представив их в виде таблицы.
                                                                                                            Простые                                  0-кубы ФАЛ
                                               Номер группы                                              импликанты         0111              1100                1110      1111
 Ранг куба
                   1                  2              3                      4               5            01-1                *
0-куб            0000               0001           0101                   0111            1111           -111                *                                               *
                                    0010           1010                   1110                           111-                                                      *         *
                                    0100           1100                                                  --00                                   *
                                    1000                                                                 1--0                                   *                  *
1-куб             000-              0-01              01-1                -111
                                                                                                        Оставшаяся таблица может быть сжата по столбцам, так как первый столбец
                  00-0              -010              1-10                111-
                                                                                                        полностью входит в четвертый, а второй столбец – в третий. На основании этого
                  0-00              010-              11-0
                                                                                                        из таблицы вычеркиваются третий и четвертый столбцы.
                  -000              -100
                                    10-0                                                                  Простые                                    0-кубы ФАЛ
                                    1-00                                                                 импликанты         0111              1100                1110      1111
2-куб             0-0-              1--0
                  0-0-              1--0                                                                 -111                *                                               *
                  --00                                                                                   111-                                                      *         *
                  0-0-                                                                                   1--0                                   *                  *
                  -0-0
                  --00                                                                                  Полученная таблица больше не может быть сжата ни по строкам, ни по столбцам.
                                                                                                        При этом импликанта 111- является лишней, так как она не покрывает ни одну из
    Для заполнения таблицы каждый из кубов левого столбца поочередно                                    оставшихся конституент единицы. Полученная после ее исключения таблица и
    сравнивается с кубами правого столбца. Если сравниваемая пара образовала куб                        является циклической.
    более высокого ранга, последний записывается в соответствующий столбец                           6. Просуммировав импликанты циклической таблицы и простые импликанты,
    таблицы.                                                                                            получим ФАЛ минимальной стоимости.
2. Кубы, не образовавшие куб более высокого ранга, являются простыми                                                      z ( x) = x3 x1 + x2 x0 + x2 x1 x0 + x3 x0 .
    импликантами и формируют покрытие ФАЛ
                                                                                                           Алгоритм сжатия по строкам и столбцам можно пояснить следующим
                    П(z) = (01-1; -111; 111-; 0-0-; --00; -0-0; 1--0).
                                                                                                     образом. Из множества импликант, полученных после исключения существенных,
3. С использованием П(z) построим таблицу покрытий Квайна.                                           необходимо найти такое их минимальное подмножество, которое обеспечит
                                                                                                     покрытие всех оставшихся в таблице конституент единицы. Поэтому, если
Прост.                                      0-кубы ФАЛ
                                                                                                     существует i-я импликанта, которая покрывает множество 0-кубов Vi, которое
импл.    0000   0001     0010    0100    0101 0111 1000            1010      1100    1110   1111
                                                                                                     включает множество Vj, покрываемое импликантой j, то импликанта j является
01-1                                      *      *
                                                                                                     лишней.
-111                                             *                                               *         Описанный алгоритм без каких-либо изменений позволяет минимизировать
111-                                                                                  *          *   ФАЛ любого числа переменных, в том числе и с применением ЭВМ.
0-0-      *      *                *        *
--00      *                       *                          *                   *
-0-0      *               *                                  *       *
1--0                                                         *       *           *    *

                                               39                                                                                            40