Мінімізація булевих функцій

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

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

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

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

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

Будь-яка логічна функція може записуватися різними аналітичними виразами різного рівня складності. Серед них є такі, які містять мінімальну кількість логічних змінних і операцій над ними. Задача знаходження таких аналітичних виразів називається мінімізацією логічних функцій.

Для мінімізації функції з числом змінних до п’яти-шести найбільш зручними є два методи: метод Квайна і метод карт Карно.

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

Аналітичний спосіб мінімізації. Для зменшення складності логічних функцій найчастіше використовують операції склеювання:

та поглинання:

Як приклад розглянемо процедуру спрощення такої функції:

Одержана функція має мінімальну складність.

Метод Квайна

Для знаходження логічної функції за таблицею істинності використовують метод Квайна. Цей метод представлено у вигляді послідовності таких дій:

1. У таблиці істинності виділяють рядки, в яких вихідна змінна має значення 1.

2. Для кожного рядка, де Y=1 складають кон'юнкцію всіх вхідних змінних цього рядка, причому записують співмножник Х _i, якщо змінна приймає значення 1, інакше записують . Таким чином, встановлюється стільки складових функції, скільки є рядків з Y=1.

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

Приклад 1. Скласти комбінаційну схему для наступної умови. Є два вимикачі. При включенні одного з них спалахує лампа (світлодіод). Складемо табл.:

У відповідність з таблицею знайдемо функцію . Комбінаційна схема має вигляд:

Рис. 2.4. Схема для реалізації логічної функцїі .

Функції реалізовані на суматорі за модулем два, через що і сам логічний елемент і логічна операція мають назву «Виключальне АБО» .

Ускладнимо приклад. Припустимо, що таблиця має вигляд:

Для другого рядка складаємо кон'юнкцію ; для третього – ; для шостого – ; для сьомого – ,

де К – кон'юнкція відповідного рядка. Отримана функція:

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

Використовуючи тотожність булевої алгебри, отримаємо: . Аналогічно об'єднаємо третій і четвертий доданки. Отриманий вираз перетворюємо до кінцевого результату

Схемна реалізація шуканої функції представляється у вигляді рис. 2.3.

Якщо таблиця істинності в стовпці вихідної змінної Y має більше одиниць, то роблять таким чином:

· розглядають не Y а , тобто інвертовану вихідну змінну;

· обчислюють для Y її логічну функцію і спрощюють її;

· інвертують знайдену функцію і отримують рішення для Y, оскільки .

Метод карт Карно

Карта Карно – це графічний засіб для спрощення логічних рівнянь або перетворення таблиць істинності у відповідну логічну схему простим і впорядкованим шляхом.

Як і таблиця істинності, карта Карно є засобом, що показує співвідношення між логічними входами і необхідним виходом.

Особливість карти Карно полягає в тому, що по горизонталі та по вертикалі задаються координати клітин, якими виступають аргументи логічної функції. Тому кожна клітина має свою координату – 00, 01, 11, 10, яка може бути представлена відповідною двійковою або десятковою цифрою. Значення функції записується в відповідних клітинах нулями та одиницями. Наприклад, для двох змінних карта Карно має вигляд:

умова Х ₁ = 0, Х ₂ = 0 відповідає лівому верхньому кутку, а Х ₁ = 1, Х ₂ = 1 – правому нижньому кутку.

Для трьох вхідних змінних карта Карно має вигляд:

При переході від однієї комірки до сусідньої змінюється лише одна змінна (00, 01, 11, 10).

Для чотирьох вхідних змінних карта має вигляд:

Наприклад, задана таблиця 2.8 чотирьох змінних.

Таблиця 2.8

Спосіб мінімізації логічних виразів спрощується тим, що клітинки, які відрізняються тільки по одній змінній, можна об'єднати. Наприклад, в двох членах тільки змінна X₃ міняє свій стан з прямого на інверсний, а X ₁та X ₂залишаються незмінними. Ці два члени можуть бути згруповані (суміщені) таким чином, що в результаті змінну Х ₃можна скоротити, оскільки вона з'являється як у нормальному стані, так і в інверсному.

Відповідно до табл. 2.8 складаємо карту Карно наступним чином, при цьому X ₂ X ₁ – визначає стовпчик, X ₄ X ₃ – визначає рядок. Відповідно одиницю ставимо у верхній крайній куток.

Складемо логічні вирази всіх вхідних змінних для кожної комірки, де знаходиться одиниця. У групі А отримаємо кон'юнкцію:

Для групи В отримаємо кон'юнкцію:

У одну групу також зв'язують ті комірки, які знаходяться в лівому і правому краях одного рядка або у верхній і нижній частинах одного стовпчика. Так карти Карно дозволяють проводити мінімізацію не виконуючи перетворення, а шляхом записування однакових символів Х для всієї групи. Для групи С отримаємо кон'юнкцію:

У логічній сумі всіх отриманих виразів маємо:

.

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