Мінімізація булевих функційВажливим етапом проектування цифрових пристроїв є мінімізація булевих функцій, тобто знаходження їхніх виражень з мінімальним числом букв. Мінімізація забезпечує побудову економічних схем цифрових автоматів. Для мінімізації функцій із числом букв застосовують карти Карно. Їх будують у вигляді таблиць з кліток з розміткою рядків і стовпчиків змінними. Карти Карно для функцій трьох змінних .
Мінтерми в сусідніх клітинках карти Карно в рядку (з врахуванням верхніх і нижніх) або в стовпчику (з врахуванням крайніх) розрізняються значеннями однієї змінної, що дозволяє виконувати операцію склеювання по цій змінній. Загальні правила мінімізації. 1. Зображають карту Карно для змінних і роблять розмітку її рядків і стовпчиків. У клітинки таблиці, які відповідають мінтермам (одиничним наборам) функції, яка мінімізується, записують одиницю. 2. Склеюванню підлягають прямокутні конфігурації, які заповнені одиницями і містять 2, 4, або 8 клітинок. Верхні й нижні рядки, крайні ліві і праві стовпчики карти ніби склеюються, створюючи поверхню циліндра. 3. Множина прямокутників, які покривають усі одиниці, називають покриттям. Чим менше прямокутників і чим більше клітинок у прямокутниках, тим краще покриття. З декількох варіантів вибирають той, у якого менший коефіцієнт покриття. , де – загальне число прямокутників, – їхня сумарна площа в клітинках. 4. Форми отримані в результаті мінімізації, містять елементарних кон’юнкцій (за числом прямокутників у покритті). Кожна кон’юнкція містить тільки ті змінні, які не змінюють свого значення в наборах, що склеюються у відповідному прямокутнику. Число змінних у кон’юнкції називається її рангом. При склеюванні двох сусідніх клітинок одержують ранг кон’юнкції , чотирьох клітинок , восьми клітинок і т. д.
Розмітка карт Карно для функцій чотирьох змінних.
Для мінімізації булевих функцій використовують також діаграми Вейча, які аналогічні картам Карно і відрізняються від них способом розмітки замість символів 0 і 1 використовують булеві аргументи – , , та інші. Діаграми Вейча для 2, 3 та 4 - х змінних мають вигляд. Діаграма Вейча для 2- х змінних.
Діаграма Вейча для 3- х змінних.
Діаграма Вейча для 4- х змінних.
Приклад. Спростити логічний вираз з використанням діаграм Вейча.
Діаграма Вейча згідно заданого виразу буде мати вигляд:
Спрощений вираз має вигляд:
.
Контрольні запитання 1. Для чого призначені методи мінімізації. 2. Назвіть методи мінімізації логічних виразів. 3. Назвіть графічні методи мінімізації. 4. Мінімізуйте задані логічні вирази.
|