Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Мінімізація методом Квайна – Мак-Класкі





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Приклад 1.Мінімізувати перемикальну функцію, задану у вигляді досконалої диз'юнктивної нормальної форми, методом Квайна – Мак-Класкі:

Етап 1: виписати двійкове представлення наборів, що утворюють ДДНФ даної функції:

(0011, 0111, 1000, 1010, 1011, 1100, 1111)

Етап 2: розбити отримані двійкові коди на групи, що містять однакову кількість одиниць у коді. Для ФАЛ, що залежать від n змінних, таких груп може бути n+1 (ні однієї одиниці в коді, одна одиниця, дві одиниці, ... , n одиниць у коді). Розташувати групи за зростанням кількості одиниць (табл.7). Якщо кількість груп, що вийшли, менше n+1, то відсутні групи позначити як порожні.

 


Таблиця 7 – Розташування груп за зростанням кількості одиниць

- - - -

 

Етап 3: порівняти кожен код з однієї групи з кожним кодом із сусідніх груп. Якщо знайдені два коди, що відрізняються тільки в одному розряді (тобто вони можуть "склеюватися" між собою згідно операції склеювання , то позначити ці коди яким-небудь особливим символом, наприклад "*", і в нову групу помістити код, що зберігає значення в співпадаючих розрядах і який-небудь особливий символ, що має, наприклад "-", на місці незбіжного розряду. При цьому утвориться n-1 нова група кодів. Якщо код попадає в декілька "склейок", то він символом * може позначатися тільки один раз.

Ця процедура повторюється для знову утворених груп доти, поки можлива процедура "склеювання" елементів сусідніх груп. Максимально можливе число кроків на цьому етапі дорівнює n. На всіх кроках, починаючи з другого, необхідно стежити за тим, щоб два "склеювані" коди являли собою терми, що залежать від одних і тих же логічних змінних, тобто знаки "-" у них повинні знаходитися в одних і тих же позиціях. З появою в одній групі декількох однакових імплікант для подальшого аналізу варто залишити лише одну з них, виходячи зі співвідношення .

 

Рис.1. Процес отримання первинних імплікант

Результат виконання даного етапу – одержання всіх первинних імплікант вихідної перемикальної функції, тобто скороченої диз'юнктивної нормальної форми. Первинними імплікантами будуть всі імпліканти, отримані на останньому кроці цього етапу, а також всі імпліканти, отримані на всіх попередніх кроках, які не ввійшли в жодну з "склейок", тобто, не позначені символом "*".

Етап 4: скласти імплікантну матрицю, що представляє собою таблицю, де по стовпцях розташовані конституенти одиниці вихідної функції, а по рядках - первинні імпліканти.

В клітинку таблиці ставиться який-небудь відповідний символ, наприклад "+", якщо первинна імпліканта, що розташована в заголовку рядка, є власною частиною конституенти одиниці, що розташована в заголовку стовпця (табл.8). У протилежному випадку клітинка залишається порожньою.

 

Таблиця 8 –Заповнення імплікантної матриці

Первинні імпліканти Конституенти одиниці
 
--11 + +     +   +
10-0     + +      
1-00     +     +  
101-       + +    
-111   +         +

 

Найпростіший, але, звичайно, не повний, контроль правильності заповнення таблиці може бути проведений у такий спосіб. Якщо первинна імпліканта, що розташована в заголовку рядка, не містить символів "-", то в цьому рядку повинна бути рівно одна позначена клітинка. Рядок, що має в заголовку імпліканту з k символами "-", повинний містити рівно 2k позначених клітинок. Крім того, не повинно бути жодного стовпця, що не має хоча б однієї позначеної клітинки.

Етап 5: знайти суттєві імпліканти функції.

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

З подальшого розгляду виключаються стовпці, що містять позначки в рядках, які відповідають суттєвим імплікантам.

Для розглянутої функції суттєвими імплікантами будуть --11 і 1-00, тому що тільки первинна імпліканта --11 дозволяє покрити імпліканту 0011 вихідного набору, а первинна імпліканта 1-00 необхідна для покриття імпліканты 1100.

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

 

Таблиця 9 – Викреслювання рядків і стовпців з імплікантної матриці

Первинні імпліканти Конституенти одиниці
 
--11 + +     +   +
10-0     + +      
1-00     +     +  
101-       + +    
-111   +         +

 

Етап 6: знайти тупикові диз'юнктивні нормальні форми і вибрати з них мінімальні ДНФ.

Для одержання тупикових ДНФ необхідно відшукати мінімальну кількість первинних імплікант, які забезпечують покриття всіх стовпців таблиці, що залишилися.

Для аналізу після етапу 5 залишився тільки один стовпець. Його покриття може бути забезпечено включенням у тупикову форму або імпліканти 10-0, або 101-, що приводить до двох тупикових ДНФ. При наявності вибору в мінімальну форму включається імпліканта, що залежить від меншого числа змінних. Обидві отримані імпліканти залежать від трьох змінних, тому кожна з них може бути включена в мінімальну форму. При рівності рангів додатковим фактором для включення тієї чи іншої імпліканти в мінімальну форму іноді служить менше число змінних, які входять у імпліканту в інверсному вигляді, тому що це в ряді випадків дозволяє скоротити обсяг устаткування для апаратної реалізації отриманої функції. Ми у своєму розгляді даний параметр у критерій мінімальності включати не будемо.

Таким чином, розглянута функція має дві різні мінімальні диз'юнктивні форми:

з яких обирається одна.

Приклад 2. Мінімізувати ФАЛ, задану у вигляді досконалої кон’юнктивної нормальної форми, методом Квайна – Мак-Класкі:

Послідовність і зміст етапів, виконуваних при мінімізації заданої в ДКНФ логічної функції, еквівалентні аналогічним етапам, що виконувалися при мінімізації логічної функції, заданої в ДДНФ (див. попередній приклад).

Етап 1: записати двійкове представлення наборів, що утворюють ДКНФ даної функції:

(0000, 0111, 1010, 1011, 1101, 1110, 1111)

Етап 2: розбити отримані коди на групи, що містять однакову кількість нулів у коді. Для перемикальної функції, що залежать від n змінних, таких груп може бути n+1 (жодного нуля в коді, один нуль, два нулі, ... , n нулів у коді). Розташувати групи за зростанням кількості нулів (табл.10). Якщо кількість груп, що вийшли, менше n+1, то відсутні групи позначаються як порожні.

 

Таблиця 10 – Розташування груп за зростанням кількості нулів

- - - -

 

Етап 3: порівняти кожен код з однієї групи з кожним кодом із сусідніх груп. Якщо знайдені два коди, що відрізняються тільки в одному розряді (тобто вони можуть "склеюватися" між собою згідно , то позначити їх яким-небудь особливим символом, наприклад, "*", і в нову групу помістити код, що зберігає значення в співпадаючих розрядах і який-небудь особливий символ, що має, наприклад "-", на місці незбіжного розряду. При цьому утвориться n-1 нова група кодів.

Ця процедура повторюється для знову утворених груп доти, поки можлива процедура "склеювання " елементів сусідніх груп. Максимально можливе число кроків на цьому етапі дорівнює n. На всіх кроках, починаючи з другого, необхідно стежити за тим, щоб два "склеюваних" коди являли собою терми, що залежать одних і тих же логічних змінних, тобто знаки "-" у них повинні знаходитися в одних і тих же позиціях (рис.2). З появою в одній групі декількох однакових термів для подальшого аналізу варто залишити лише один з них, виходячи зі співвідношення .

 

Рис.2. Процес отримання первинних імпліцент

 

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

Етап 4: скласти імпліцентну матрицю, яка представляє собою таблицю, що в якості заголовків стовпців має всі конституенти нуля вихідної функції, а як заголовки рядків - первинні імпліценти.

В клітинку таблиці ставиться який-небудь відповідний символ, наприклад "+", якщо первинна імпліцента, що розташована в заголовку рядка, є власною частиною конституенти нуля, що розташована в заголовку стовпця. У протилежному випадку клітинка залишається порожньою:

 

Таблиця 11 – Викреслювання рядків і стовпців з імпліцентної матриці

Первинні імпліценти Конституенти нуля
 
1-1-     + +   + +
-111   +         +
11-1         +   +
0000 +            

 

Найпростіший контроль правильності заповнення таблиці може бути проведений аналогічно прикладу 1.

Етап 5: знайти суттєві імпліценти.

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

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

Для розглянутої функції всі мінтерми, що містяться в заголовках рядків, будуть суттєвими, тому що первинна імпліцента 1-1- необхідна для покриття макстермів 1010, 1011, 1110 і 111 вихідного набору, імпліцента -111 – для покриття макстерма 0111, імпліцента 11-1 – для покриття макстерма 1101, а імпліцента 0000 необхідна для покриття такого ж макстерму у вихідному наборі.

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

Отримана єдина мінімальна кон’юнктивна нормальна форма має наступний вигляд:

 

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.