Табличный метод Куайна-Маккласки
В предыдущей главе мы обсудили метод 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 представления.
| Название группы | Минимальные сроки | 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 из соседних групп.
| Название группы | Минимальные сроки | 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.