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

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

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

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

ху + ху '= х (у + у') = х.1 = х

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

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

Step 1 - Упорядочить указанные минимальные сроки в ascending orderи сделайте группы на основе количества единиц, присутствующих в их двоичных представлениях. Итак, будетat most ‘n+1’ groups если есть n логических переменных в булевой функции или n битов в двоичном эквиваленте минимальных условий.

Step 2 - Сравните минимальные термины, представленные в successive groups. Если есть изменение только в одной битовой позиции, тогда возьмите пару этих двух минимальных членов. Поместите этот символ '_' в другую битовую позицию и оставьте оставшиеся биты как есть.

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

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

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

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

пример

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

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

GA3
Название группы Минимальные сроки W Икс Y Z
GA1 2 0 0 1 0
8 1 0 0 0
GA2 6 0 1 1 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
14 1 1 1 0
GA4 15 1 1 1 1

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

GB3
Название группы Минимальные сроки W Икс Y Z
GB1 2,6 0 - 1 0
2,10 - 0 1 0
8,9 1 0 0 -
8,10 1 0 - 0
GB2 6,14 - 1 1 0
9,11 1 0 - 1
10,11 1 0 1 -
10,14 1 - 1 0
11,15 1 - 1 1
14,15 1 1 1 -

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

Название группы Минимальные сроки W Икс Y Z
GB1 2,6,10,14 - - 1 0
2,10,6,14 - - 1 0
8,9,10,11 1 0 - -
8,10,9,11 1 0 - -
GB2 10,11,14,15 1 - 1 -
10,14,11,15 1 - 1 -

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

Название группы Минимальные сроки W Икс Y Z
GC1 2,6,10,14 - - 1 0
8,9,10,11 1 0 - -
GC2 10,11,14,15 1 - 1 -

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

В prime implicant table показано ниже.

Минимальные сроки / основные импликанты 2 6 8 9 10 11 14 15
YZ’ 1 1 1 1
WX’ 1 1 1 1
WY 1 1 1 1

Первичные импликанты располагаются по строкам, а минимальные термины - по столбцам. Единицы помещаются в общие ячейки простых импликантных строк и соответствующих столбцов с минимальным термином.

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

Минимальные сроки / основные импликанты 8 9 11 15
WX’ 1 1 1
WY 1 1

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

Минимальные сроки / основные импликанты 15
WY 1

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

В этом примере задачи у нас есть три основных импликанты, и все они существенны. Следовательноsimplified Boolean function является

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