3.5. Задача мінімізації логічних функцій

Якщо в складі проектованої схеми повинні входити елементи И, АБО, НЕ то представлення функцій у довільній із розглянутих канонічних форм уже дає можливість побудови такої схеми. Легко підрахувати, яка кількість і яких елементів буде потрібно для реалізації конкретної логічної функції. На розглянутому вище прикладі очевидно, що використання ДДНФ дасть більш просту реалізацію.

Приймаючи до уваги подібні проблеми оптимізації пристрою, що проектується, можна підтверджувати, що в загальному випадку схема з меншою кількістю елементів обходиться дешевше і більш надійна в роботі. Отже, незалежно від застосовуваних при побудові логічних схем елементів, важливим етапом синтезу є пошук такого виду логічної функції, у якому є мінімальне число логічних операцій над мінімальним числом вхідних сигналів. Процес пошуку такого виду називається мінімізацією функції і грунтується на так називаних правилах склеювання:

у котрих А і В - змінні або логічні функції. Ці правила можна сформулювати в такий спосіб: диз'юнкція або кон'юнкція двох змінних, що відрізняються одне від іншого тільки знаком заперечення для однієї змінної, можуть бути замінені одним виразом без тієї змінної, по якій вони відрізняються. Наприклад:

Вирази, для котрих можливо склеювання, називають сусідніми виразами. Якщо в отриманих канонічних представленнях є сусідні вирази, то відповідні представлення можна спростити з метою одержання простої технічної реалізації

Вирази ДДНФ із вищенаведеного приклада можна спростити в такий спосіб

.

У випадку складних функцій від великого числа змінних пошук сусідніх виразів і їх склеювання групи зазначеним вище засобом стає скрутним. Метод матриць Карно (діаграм Вейча) полегшує процедуру склеювання завдяки тому, що сусідні члени ДДНФ або ДКНФ, для котрих можливо склеювання, розміщаються на площині по сусідству в географічному сенсі. Для функцій n змінних кожна складові канонічної форми може мати n сусідів. Приклади матриць Карно приведені на рис. 3.2 - 3.4.

X₂ X₂ X₃

0 1 00 01 11 10

X₁ X₁

0 0 1 0 0 1 3 2

1 2 3 1 4 5 7 6

Рис. 3.2 - Карти Карно для двох і трьох змінних

X₃ X₄

X₁ X₂ 00 01 11 10

00

0 1 3 2

01 4 5 7 6

11 12 13 15 14

8 9 11 10

10

Рис. 3.3 - Карта Карно для чотирьох змінних

X₃ X₄ X₅

X₁ X₂ 000 001 011 010 110 111 101 100

00 0 1 3 2 6 7 5 4

01 8 9 11 10 14 15 13 12

11 24 25 27 26 30 31 29 28

10 16 17 19 18 22 23 21 20

Рис. 3.4 - Карта Карно для п'ятьох змінних

Кожна клітина матриці відповідає одній комбінації значень вхідних змінних. Код цих комбінацій підібраний так, щоб сусідні клітини відрізнялися значенням тільки однієї змінної, тобто щоб їм відповідали сусідні вирази. Код із такою властивістю називається кодом Гріючи. У побудовану на основі такого коду таблицю вписуються символи, що відповідають значенням функції на визначених наборах вхідних змінних із таблиці істинності.

Якщо в двох сусідніх клітинах заповненої матриці Карно знаходяться однакові символи (0 або 1), то відповідні цим клітинам вирази можна склеювати, що рівнозначно усуненню змінної, яка у рамках групи, що склеюється, змінює значення. Сусідні клітини, що утворять пари, об'єднуються замкнутою лінією для позначення можливості склеювання. Можливі варіанти склеювання для функцій чотирьох змінних наведені на рис. 3.5.

Розглянемо приклад. Нехай із таблиці істинності отримана ДДНФ і вона мінімізується аналітичним методом за допомогою склеювання:

Матриця Карно для даного випадку буде мати вигляд, показаний на рис. 3.6.

Рис. 3.5 - Варіанти склеювання для логічної функції чотирьох перемінних.

00 01 11 10

00

1 0 0 1

01 0 0 0 0

11 0 0 0 0

1 0 0 1

10

Рис. 3.6 - Карта Карно для приклада

Методика мінімізації логічних функцій за допомогою карт Карно використовується при автоматизованому проектуванні вузлів сучасних ЕОМ і розробці логічних моделей об'єктів і процесів гірничо-металургійного виробництва.