Табличный метод Куайна-МакКласки

В предыдущей главе мы обсуждали метод K-map, который является удобным методом минимизации булевых функций до 5 переменных. Но с помощью этого метода сложно упростить булевы функции, имеющие более 5 переменных.

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

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

xy + xy ‘= x (y + y’) = x.1 = x

Процедура табличного метода Куайна-МакКласки

Выполните следующие шаги для упрощения булевых функций с помощью табличного метода Куайна-МакКлюки.

Шаг 1 — Расположите заданные минимальные слагаемые в порядке возрастания и создайте группы на основе числа элементов, присутствующих в их двоичных представлениях. Таким образом, будет не более «n + 1» групп, если в булевой функции есть «n» булевых переменных или «n» битов в двоичном эквиваленте min членов.

Шаг 2 — Сравните минимальные термины, присутствующие в последовательных группах . Если есть изменение только в однобитовой позиции, то возьмите пару из этих двух минимальных членов. Поместите этот символ ‘_’ в отличающуюся битовую позицию и оставьте оставшиеся биты как есть.

Шаг 3 — Повторите шаг 2 с вновь сформированными терминами, пока мы не получим все основные импликанты .

Шаг 4 — Сформулируйте таблицу основных импликантов . Он состоит из множества строк и столбцов. Основные импликанты могут быть размещены в строке, а минимальные — в столбце. Поместите «1» в ячейки, соответствующие минимальным терминам, которые охватываются каждым основным импликантом.

Шаг 5 — Найдите основные простые импликанты, наблюдая за каждым столбцом. Если минимальный член покрывается только одним основным импликантом, то он является существенным основным импликантом . Эти основные простые импликанты будут частью упрощенной булевой функции.

Шаг 6 — Сократите таблицу первичных импликантов, удалив строки каждого существенного первичного импликанта и столбцы, соответствующие минимальным терминам, которые охватываются этим существенным первичным импликантом. Повторите шаг 5 для таблицы Сокращенный главный импликант. Остановите этот процесс, когда все минимальные члены данной булевой функции закончатся.

пример

Упростим следующую булеву функцию $f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right)$, используя Табличный метод Куайна-МакКлюки.

Данная булева функция имеет вид суммы минимальных членов . Он имеет 4 переменные W, X, Y и Z. Заданные минимальные слагаемые равны 2, 6, 8, 9, 10, 11, 14 и 15. Порядок возрастания этих минимальных слагаемых основан на количестве присутствующих в их двоичный эквивалент равен 2, 8, 6, 9, 10, 11, 14 и 15. В следующей таблице приведены эти минимальные члены и их эквивалентные двоичные представления.

Заданные минимальные слагаемые разбиты на 4 группы в зависимости от количества единиц, присутствующих в их двоичных эквивалентах. В следующей таблице показано возможное объединение минимальных терминов из смежных групп.

Термины min, которые отличаются только однобитовой позицией от смежных групп, объединяются. Этот отличающийся бит представлен этим символом ‘-‘. В этом случае есть три группы, и каждая группа содержит комбинации двух минимальных членов. В следующей таблице показано возможное объединение пар минимальных членов из соседних групп.

Последовательные группы пар минимальных членов, которые отличаются только однобитовой позицией, объединяются. Этот отличающийся бит представлен этим символом ‘-‘. В этом случае есть две группы, и каждая группа содержит комбинации из четырех минимальных членов. Здесь эти комбинации 4-минутных терминов доступны в двух строках. Итак, мы можем удалить повторяющиеся строки. Сокращенная таблица после удаления лишних строк показана ниже.

Дальнейшее объединение комбинаций минимальных членов из смежных групп невозможно, так как они отличаются более чем одним битом. В приведенной выше таблице есть три строки. Итак, каждый ряд даст один главный импликант. Следовательно, основными импликантами являются YZ ‘, WX’ & WY.

Таблица основных значений показана ниже.

Основные импликанты располагаются в строке, а минимальные — в колонке. 1 помещаются в общие ячейки строк простого импликанта и соответствующие столбцы минимального члена.

Мин. Слагаемые 2 и 6 охватываются только одним главным импликантом YZ ‘ . Таким образом, это важный главный импликант . Это будет частью упрощенной логической функции. Теперь удалите эту строку главного импликанта и соответствующие столбцы минимального члена. Таблица приведенных основных значений приведена ниже.

Минимальные условия 8 и 9 охватываются только одним главным имплицитным WX ‘ . Таким образом, это важный главный импликант . Это будет частью упрощенной логической функции. Теперь удалите эту строку главного импликанта и соответствующие столбцы минимального члена. Таблица приведенных основных значений приведена ниже.

Минимальный срок 15 покрывается только одним главным имплицитным WY . Таким образом, это важный главный импликант . Это будет частью упрощенной логической функции.

В этом примере задачи у нас есть три основных импликанта, и все три имеют важное значение. Следовательно, упрощенная булева функция

f (W, X, Y, Z) = YZ ‘+ WX’ + WY.