ПРИНЦИП ГРАФІЧНОЇ МІНІМІЗАЦІЇ

В основі методу мінімізації лежить правило склеювання АВ v АВ = А (В v В) = А (3.17) і поняття "сусідня клітина". Сусідніми клітинами називають дві клітини, номери яких в двійковій системі числення відрізняються лише цифрою в одному розряді. Для всіх карт Карно, наведених на рис. 3.7, сусідніми є клітини, розташовані в одному стовпці або рядку, включаючи дві протилежні крайні клітини.

Пояснимо принцип мінімізації на конкретному прикладі, вважаючи, що початкова функція Y залежить від 4 змінних і задана одиничними наборами з номерами: 1, 2, 3, 5, 7, 10 і 12. Заповнена одиницями карта Карно для М = 4 зображена на рис. 3.8. На карті виділено такі області (групи) клітин:

  • • 1 - область з однієї клітини з номером 1100 (12);
  • • 2 - область з двох сусідніх клітин з номерами 0010 (2) і 1010 (10), розташованих на протилежних кінцях стовпчика;
  • • 3 - квадрат з чотирьох клітин з номерами 0001 (1), ООН (3), 0101 (5) і 0111 (7).

Для мінімізації Y скористаємося правилом складання структурних формул і формулою склеювання. єдину

Структура карт Карно для різного числа М вхідних сигналів

Мал. 3.7. Структура карт Карно для різного числа М вхідних сигналів

Номери одиничних наборів: 1, 2, 3, 5, 7, 10, 12

Приклад мінімізації повністю певної логічної функції

Мал. 3.8. Приклад мінімізації повністю певної логічної функції

клітку представимо як минтерм , область 2 - як суму двох минтермов

і область 3 - як суму чотирьох минтермов

Представивши Y як суму всіх минтермов, отримаємо наступне минимизированное вираз:

Розглянутий приклад показує, що група з двох сусідніх клітин замість суми двох минтермов дозволяє отримати один кон'юнктивний член, в якому на одну змінну менше, ніж в минтермов; група з чотирьох сусідніх клітин дозволяє отримати один кон'юнктивний член, в якому на дві змінні менше, ніж в минтермов, і т.д.

Таким чином, процедура мінімізації виконується в два етапи.

  • 1. Розмітка карти Карно полягає у виділенні груп одиничних клітин. Групу можуть становити 2, 4, 8, 16 клітин. Об'єднані в групу клітини обводятся на карті Карно лінією. Об'єднанню підлягають тільки ті заповнені одиницями клітини, які підпорядковані правилом склеювання. До них відносяться:
    • • дві сусідні клітини;
    • • клітини, складові повні стовпці або рядки;
    • • клітини, складові квадрати;
    • • дві групи клітин, розташовані симетрично щодо центральних вертикальних або горизонтальних осей карти і осей, розділення тексту на стовпчики та рядки карти з номерами 001 і 011, 111 і 101 (для М = 5 і 6).

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

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

Для спрощення зчитування інформації з карти Карно можна виписати номери клітин в двійковій системі числення і зберегти тільки ті змінні, які мають однакове значення для всієї виділеної області клітин. Якщо в номері клітини значення змінної Хi. = 1, то вона увійде в кон'юнктивний член в прямій формі, якщо X. = 0, то - в инверсной. На рис. 3.8 темним кольором виділені ті змінні, які не входять до коньюнктівний член, так як в даній області приймають значення і 0, і 1.

Такий же результат, отриманий шляхом перебору, наведено в табл. 3.5, де прочерк (-) свідчить про те, що змінна входить в групу як в прямому, так і в інверсному вигляді, тобто приймає значення 0 і 1. Для спрощення цієї процедури по периметру карти Карно (див. рис. 3.7 і 3.8) за допомогою товстих ліній виділені зони (у вигляді одного або декількох стовпців або рядків), в яких та чи інша змінна Х0, .. ., Х м, дорівнює одиниці. Для іншої частини карти значення змінних дорівнюють нулю. Наприклад, на рис. 3.8 для області 3 змінні Х 2, X, мають значення і 0, і 1, змінна Х 3 має значення тільки 0, змінна X " - тільки 1. Тому область 3 зчитується як кон'юнктивний член Х 3 Х 0.

Таблиця 3.5

№ групи

Х 3

Х 2

X,

х 0

кон'юнктивний член

1

1

1

0

0

2

-

0

1

0

3

0

-

1

У розглянутому прикладі початкова функція У визначена для всіх можливих наборів логічних змінних. Така функція називається повністю визначеною. Розглянемо особливості мінімізації для інших характерних випадків.

 
< Попер   ЗМІСТ   Наст >