Мінімізація за допомогою К-карт

К-карти ― різновидність мінімізуючих карт, в основу побудови яких покладено перехід від карти для (n -1)-ї змінної до карти для n змінних за допомогою принципу дзеркального відображення. На рис. 3.13 – 3.17 подано К-карти для однієї, двох,..., п’яти змінних, одержаних за допомогою наступних правил.

Карта для однієї змінної складається з клітин (рис.3.13), для двох змінних (рис. 3.14) карта складається з =4 клітин, для трьох змінних (рис. 3.15) – із клітин і т. д. Карта для n змінних містить у два рази більше клітин, ніж карта для (n -1) змінної. При цьому подвоєння кількості клітин здійснюється у відповідністю з діаграмою:

1¯ 2®3 ¯ 4 ®5 ¯ 6®7 ¯ 8®9 ¯ 10®11 ¯ 12®...,

де цифрами позначають кількість змінних, а стрілки – напрямок подво­єння карти. Зокрема, для одержання карти для функції від двох змінних, кар­ту для функції від однієї змінної подвоюємо вертикально вниз за допомо­гою дзеркального відображення та додавання до відображених значень числа . Для одержання карти для функції від трьох змінних, карту для функ­ції від двох змінних подвоюємо горизонтально вправо за допомо­гою дзеркального відображення та додавання до відображених значень числа , при переході до карти для функції від чотирьох змін­них, карту для функції від трьох змінних подвоюємо вертикально вниз і т. д.

Особливо просто здійснюється така побудова у двійковій або шістьнадцятковій системах числення. У цьому випадку перехід від карти (n -1)-го порядку до карти n -го порядку здійснюється за допомогою дзеркального відображення вертикально вниз (для парних n) або горизонтально вправо (для непарних n) і приписування зліва всім значенням “старих” клітин карти цифри 0 і цифри 1 – всім значенням “нових” клітин. Це означає, що всім “старим” кліткам ставиться у відповідність заперечення чергової змінної, а “новим” – змінна без заперечення.

На рис. 3.13 – 3.15 показано утворення К-карт для n =1, 2 і 3, нумерація їх клітин у десятковій і двійковій системах числення, а також мінтерми, які відповідають номерам клітин.

Þ Û

Рис. 3.13

Þ Û Û

Рис. 3.14

	1+22 0+22     3+22 3+22

Þ Û

Û Û

Рис. 3.15

На рис. 3.16 показано утворення К-карти для n = 4, нумерація її клітин у десятковій, шістьнадцятковій та двійковій системах числення, а також мінтерми, які відповідають номерам клітин.

	2+23 3+23 7+23 6+23 0+23 1+23 5+23 4+23
				A B F E     D C

Þ Û Û Û

Û Û

Рис. 3.16

В основу мінімізації за допомогою К-карт покладено операцію склеювання вмісту сусідніх або відповідних клітин.

Сусідніми називаються клітини, які геометрично сусідні (тобто ма­ють спільну сторону). До сусідніх відносяться і клітки крайніх лівого і пра­вого стовпців, а також крайніх нижнього і верхнього рядків будь-якої К-карти для n £ 4 або будь-якого блоку 4´4 клітин ­– для n > 4 (вони стають сусідніми при згортанні К-карти або блоку в горизонталь­ний або вертикальний циліндр).

Сусідніми є також клітини, які займають відповідні місця в блоках 4´4, оскільки при “перегині” К-карти вздовж ліній, які розділяють блоки, ці клітини накладаються.

Кожна клітина має n сусідніх клітин.

Запис К-карт у двійковій або шістьнадцятковій системах числення полег­шує виконувати операцію склеювання вмісту сусідніх клі­тин.

На рис. 3.17 показано К-карту для n =5, нумерацію її клітин у шістьнадцятковій та двійковій системах числення, а також мінтерми, які відповідають номерам клітин.

	00 01 05 04 14 15 11 10 02 03 07 06 16 17 13 12 0A 0B 0F 0E 1E 1F 1B 1A 08 09 0D 0C 1C 1D 19 18

ß

ß

Рис. 3.17

Приклад 3.12. Знайти мінімальну КНФ для функції від чотирьох змінних

, заданої множиною одиничних наборів.

Розв’язання. За даною логічною функ­цією складемо К-карту (рис. 3.26), в якій відоб­ражено двійкові набори, на яких функція приймає одиничні значення. Така форма подання функції є зручною для одержання склейок двійкових наборів (конституент одиниці), які входять в прямокутні області сусідні клітин. Склеювання можна проводити у тих стовпчиках двійкових наборів, в яких кількість нулів і одиничок однакова. Склейки відмічено символом ²*².

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

Відповідна мінімальна форма має вигляд

,

яку, скориставшись законом комута­ти­в­ності для кон’юнкції, можна записати у більш зручній формі

.

Звернемо увагу: якби ми записали функцію у вигляді ДДНФ, то для її реалізації потрібно би 21 інвертор, 33 кон’юнктори та 10 диз’юнкторів. Після мінімізації потрібно лише 5 інверторів, 5 кон’юнкторів і 3 диз’юнктори.

Не нашли, что искали? Воспользуйтесь поиском: