ня аналітичного вигляду функції застосовується алгебра Буля:
(
Для приведення системи перемикальних функцій, заданих таблично, до аналітичної формі використовувалися розкладання Шеннона: граничне розкладання Шеннона - СДНФ і двоїсте граничне розкладання Шеннона - СКНФ:
(
МІНІМІЗАЦІЯ булевих функцій
Основні визначення в теорії мінімізації функцій
При розробці схем на основі конкретної елементної бази кількість обладнання зазвичай вимірюється числом корпусів (модулів) інтегральних мікросхем, використовуваних у схемі. У теоретичних розробках орієнтуються на довільну елементну базу.
Оцінкою витрат обладнання на побудова схеми називається ціною схеми по Квайну, що представляє собою сумарну кількість входів до усіх логічні вентилі. При такій оцінці одиницею складності є один вхід логічного елемента. Ціна інверсного входу звичайно приймається рівної двом. Такий підхід до оцінки складності виправданий з наступних причин:
Складність схеми легко обчислюється по логічним функцій, на основі яких будується схема: для ДНФ або КНФ складність схеми дорівнює сумі кількості букв (букві зі знаком заперечення відповідає ціна 2) і кількості знаків диз'юнкції (кон'юнкції), збільшеного на 1 для кожного диз'юнктивного (кон'юнктивний) вираження;
Всі класичні методи мінімізації логічних функцій забезпечують мінімальність схеми в сенсі ціни по Квайну.
Мінімізація функцій проводиться в класі ДНФ або КНФ. В основу покладені два закони:
Закон склеювання:
(
Закон поглинання:
(
Мінімізація булевих функцій геометричним методом.
Суть геометричного методу полягає в зображенні області визначення булевої функції n змінних у вигляді вершин n-мірного куба. Елементам куба можна поставити під взаємо-однозначна відповідність кон'юнкції різного рангу: вершин куба - кон'юнкції третього рангу, ребрам - другого, гранях - перший. Кожен геометричний еквівалент меншої розмірності покривається всіма геометричними еквівалентами більшої розмірності. Кон'юнкції більшого рангу покриваються кон'юнкції меншого рангу (рис. 1.1.).
Рис. 1.1. Геометричний метод мінімізації перемикальної функції трьох змінних
Висновок: даний метод незручний для мінімізації функцій з кількістю вхідних сигналів, що перевищує трьох, тому виникає необхідність розглядати n-мірні куби (n gt; 3) в результаті чого метод втрачає наочність і значно збільшується час роботи, що обмежує його область застосування в задачах синтезу КЦУ.
Мінімізація булевих функцій методом діаграм Вейча
Куб Карно (метод діаграм Вейча) - графічний спосіб мінімізації перемикальних функцій, що забезпечує відносну простоту роботи з великими виразами. Являє собою операції попарного неповного склеювання lt;http://ru.wikipedia/wiki/%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B8gt; і елементарного поглинання lt;http://ru.wikipedia/wiki/%D0%91%D1%83%D0%BB%D0%B5%D0%B2%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0gt;. Діаграми Вейча можна розглядати як певну плоску розгортку n-мірного булева куба lt; https: //ru.wikipedia/wiki/%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0% BA% D1% 83% D0% B1 gt; (рис. 1.2.).
Рис. 1.2. Діаграма Вейча як плоска розгортка 3-мірного куба
Висновок: метод діаграм Вейча зручний для інженерних завдань, позбавлений громіздкість та характеризується хорошою наочністю. Виділено та проаналізовано ряд істотних недоліків розглянутого методу:
Суворе обмеження щодо кількості вхідних сигналів (максимум шести);
Відсутність алгоритму, що забезпечує знаходження оптимального контуру.
Мінімізація булевих функцій методом Квайна
Метод Квайна для мінімізації функції включає в себе кілька етапів (рис. 1.3.).
Рис. 1.3. Діаграмні зображення етапів алгоритму Квайна
етап. Знаходження первинних импликант.
Перехід від канонічної форми до скороченої базується на теоремі Блейка, згідно з якою для отримання скороченої форми слід виконати всілякі узагальнені склеювання суміжних минтермов, а потім всілякі поглинання минтермов. В основу першого етапу входить реалізація алгоритму Блейка-Порецкого:
побудова списку векторів, що представляють минтермов нормальної форми. Видалити зі списку всі вектори, що поглинаються іншими. Якщо залишається єдиний вектор, перейти до кроку 6. Інакше позначити другий з залишилися векторів через?;
знайти для вектора...
