Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

Метод Куайна — Мак-Класки


Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.

Алгоритм минимизации

  • Термы (конъюнктивные в случае СДНФ и дизъюнктивные в случае СКНФ), на которых определена ФАЛ записываются в виде их двоичных эквивалентов;
  • Эти эквиваленты разбиваются на группы, в каждую группу входят эквиваленты с равным количеством единиц (нулей);
  • Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов;
  • Составляется таблица, заголовком строк в которой являются исходные термы, а заголовком столбцов — термы низких рангов;
  • Расставляются метки, отражающие поглощение термов высших рангов (исходных термов) и далее минимизация производится по методу Куайна.
  • Особенности

    Специфика метода Куайна — Мак-Класки по сравнению с методом Куайна в сокращении количества попарных сравнений на предмет их склеивания. Сокращение достигается за счет исходного разбиения термов на группы с равным количеством единиц (нулей). Это позволяет исключить сравнения, заведомо не дающие склеивания.

    Несмотря на большую возможность практического применения чем у карт Карно когда речь идёт о более чем четыре переменных, метод Куайна—Мак-Класки тоже имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. Можно показать, что для функции от n переменных верхняя граница количества основных импликант 3n/n. Если n = 32 их может быть больше чем 6.5 * 1015. См. также Трансвычислительная задача.

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

    Пример

    Шаг 1: находим основные импликанты

    Пусть функция задана с помощью следующей таблицы истинности:

    Можно легко записать СДНФ, просто просуммировав минтермы (не обращая внимание на неполностью определённые термы), где функция принимает значение 1.

    f = x ¯ y z ¯ t ¯ + x y ¯ z ¯ t ¯ + x y ¯ z t ¯ + x y ¯ z t + x y z ¯ t ¯ + x y z t . {displaystyle f={ar {x}}y{ar {z}}{ar {t}}+x{ar {y}}{ar {z}}{ar {t}}+x{ar {y}}z{ar {t}}+x{ar {y}}zt+xy{ar {z}}{ar {t}}+xyzt.}

    Для оптимизации запишем минтермы, включая те, которые соответствуют равнодушным состояниям, в следующую таблицу:

    Теперь можно начинать комбинировать между собой минтермы, то есть проводить операцию склеивания. Если два минтерма отличаются лишь символом, который стоит в одной и той же позиции в обоих, заменяем этот символ на «-», это означает, что данный символ для нас не имеет значения. Термы, не поддающиеся дальнейшему комбинированию, обозначаются «*». При переходе к импликантам второго ранга, трактуем «-» как третье значение. Например: −110 и −100 или −11- могут быть скомбинированы, но не −110 и 011-. (Подсказка: Сначала сравнивай «-».)

    Количество "1" Минтермы | Импликанты 1-го уровня | Импликанты 2-го уровня ------------------------------|-----------------------|---------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* ------------------------------| m(8,10) 10-0 |---------------------- 2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-----------------------| m12 1100 | m(9,11) 10-1 | ------------------------------| m(10,11) 101- | 3 m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ------------------------------|-----------------------| 4 m15 1111 | m(11,15) 1-11 | | m(14,15) 111- |

    Шаг 2: таблица простых импликант

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

    Принцип выбора импликант такой же как и в методе Куайна. Простые импликанты, которые является ядрами выделены жирным шрифтом. В этом примере, ядра не перекрывают все минтермы, в таком случае может быть выполнена дополнительная процедура упрощения таблицы (см. Метод Петрика). Есть два варианта:

    f x , y , z , t = y z ¯ t ¯ + x y ¯ + x z   {displaystyle f_{x,y,z,t}=y{ar {z}}{ar {t}}+x{ar {y}}+xz } f x , y , z , t = y z ¯ t ¯ + x t ¯ + x z .   {displaystyle f_{x,y,z,t}=y{ar {z}}{ar {t}}+x{ar {t}}+xz. }
    (голосов:0)

    Пожожие новости
    Комментарии

    Ваше Имя:   

    Ваш E-Mail: