double arrow

Мінімізація булевих функцій. Логічні елементи. Логічні схеми

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

Нехай задано систему повністю визначених булевих функцій, які подані в ДНФ:

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

Сума рангів (число букв) елементарних кон’юнкцій множини А є зручним критерієм для оцінювання складності заданої системи.

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

Алгоритм мінімізації систем булевих функцій

1. Побудувати повну множину А елементарних кон’юнкцій системи, яку мінімізуємо, враховуючи, що спочатку кожна з функцій системи подана в ДДНФ. Кожній конституенті одиниці множини А присвоїти ознаку, що містить номери функцій системи, в яку входить розглядувана конституента.

2. Виконати мінімізацію ДДНФ функції , конституентами якої є всі елементи множини А. При цьому:

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

б) якщо ознаки не мають спільних номерів, то склеювання не відбувається;

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

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

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

Областю визначення логічної функції F (Х1, Х2, …, Хn) є cкінченна множина різних двійкових наборів довжиною n, на кожному з яких указується значення функції нуль або одиниця. Кількість різних двійкових наборів дорівнює множині n -розрядних двійкових чисел m = 2n.

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

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

Розроблено універсальні (канонічні) форми представлення булевих функцій, які дають можливість одержати аналітичну форму довільної функції безпосередньо з таблиці істинності. Ця форма надалі може бути мінімізована або спрощена. Оскільки між множиною аналітичних представлень і множиною схем, які реалізують цю функцію, існує взаємно однозначна відповідність, то пошук канонічної форми запису є початковим етапом синтезу логічних схем. Найбільше поширення одержали ДДНФ і ДКНФ. Для одержання цих форм вводяться поняття мінтермів (конституєнта 1) і макстермів (конституєнта 0).

Мінтерм – це функція n змінних, яка дорівнює одиниці тільки на одному наборі. Мінтерм одержують як кон’юнкцію n змінних, що входять до нього у прямому виді, якщо значення даної змінної в наборі Xi = 1, і – із запереченням, якщо Xi = 0.

Макстерм – це функція n змінних, яка дорівнює нулю тільки на одному наборі. Макстерм одержують як диз’юнкцію усіх змінних, що входять до нього у прямому вигляді, коли значення Xi = 0, або в інверсному вигляді, якщо значення Xi = 1.

Важливим етапом проектування комп'ютерних схем є мінімізація булевих функцій, тобто знаходження їх виражень з мінімальною кількістю букв. Мінімізація забезпечує побудову економічних схем комп'ютерів. Для мінімізації функцій із кількістю букв n <= 6 застосовують карти Карно. Їх будують у вигляді таблиць з 2n клітинок з розміткою рядків і стовпчиків змінними. Кожна клітинка карти Карно однозначно відповідає одному наборові таблиці істинності для функції п змінних або мінтермам цієї функції. Клітинки карти Карно часто нумерують десятковими цифрами – номерами наборів.

При мінімізації для кожного мінтерму, який входить у ДДНФ функції, ставиться одиниця, а інші клітинки не заповнюються.

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

Наведемо загальні правила мінімізації.

  1. Зображають карту Карно для n змінних і розмічають її рядки та стовпчики. У клітинки таблиці, які відповідають мінтермам (одиничним наборам) функції, що мінімізується, записують одиницю.
  2. Склеюванню підлягають прямокутні конфігурації, які заповнені одиницями і містять 1, 2, 4 або 8 клітинок. Верхні й нижні рядки, крайні ліві і праві стовпчики карти ніби склеюються, створюючи поверхню циліндра.
  3. Множина прямокутників, які покривають усі одиниці, називається покриттям. Чим менше прямокутників і чим більше клітинок у прямокутниках, тим краще покриття. З декількох варіантів вибирають той, у якого менший коефіцієнт покриття z = r / s, де r – загальна кількість прямокутників; s – їх сумарна площа в клітинках.
  4. Формули, отримані в результаті мінімізації, містять r елементарних кон’юнкцій (за кількістю прямокутників у покритті). Кожна кон’юнкція містить тільки ті змінні, які не змінюють свого значення в наборах, що склеюються у відповідному прямокутнику. Кількість змінних у кон’юнкції називають її рангом. Склеюючи дві сусідні клітинки, одержують ранг кон’юнкції n – 1, чотири клітинки – n – 2, вісім клітинок – n – 3 і т. д.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: