Карти Карно та Вейча. Синтез комбінаційних схем
Методи мінімізації логічних функцій. Перетворення і спрощення форми.
Процес спрощення зводиться до застосування загальних властивостей (табл.7) для зменшення загальної кількості входження у формулу змінних із символів логічних операцій.
Зазвичай перетворення виконують у диз’юнктивній нормальній формі (сума мінтермів), а використовують властивості склеювання, поглинання і виявлення.
Склеювання 
дозволяє замінити два мінтерми, які відрізняються однією змінною (з інверсією і без) одним мінтермом меншого рівня. Поглинання 
дозволяє виключити всі мінтерми, в яких в якості співмножника входить деякий інший мінтерм меншого рангу. Процедура склеювання не забезпечує отримання мінімальних форм, а призводить до скороченої форми, мінтерми якої називають простими імплікантами. Серед простих імплікант можуть бути такі, які покривають ся сукупністю інших імплікант, тобто є надлишковими. Після видалення надлишкових імплікант отримують тупикові форми, серед яких знаходяться і мінімальні.
Отже, пошук мінімальних форм серед нормальних форм конкретної функції є однією з головних задач синтезу логічних схем.
Для мінімізації булєвих форм розроблено ряд методів, серед яких найбільш відомі алгоритм Квайн-МакКласкі, графічні методи, які базуються на картах Карно і Вейч.
Карти Карно
Карти Карно представляють собою спеціально організовані таблиці відповідності, на яких зручно виконувати операції склеювання при мінімізації. Рядки і стовбці таблиці відповідають всім можливим наборам значень змінних, причому кожні сусідні набори відрізняються однією змінною. Крайні таблиці комірки також вважаються сусідніми і мають ці властивість.
На рис. показано карти Карно для двох, трьох і чотирьох змінних:
Правила:
1. Кожному набору значень змінних по рядках і стовбцях відповідає своя комірка, яка знаходиться на їхньому перетині.
2. Комірка заповнюється одиницею якщо на відповідному наборі функція приймає одиничне значення (нулі зазвичай не вписують).
3. Отже відмічені комірки відповідають мінтермам, а невідмічені – макстермам канонічних форм.
4. Операції склеювання двох мінтермів n-го рангу початкової форми відповідає по карті Карно об’єднанню двох сусідніх комірок, відмічених одиницями. Ця об’єднана пара являє собою мінтерм (n-1)-го рангу.
5. Аналогічне склеювання двох мінтермів (n-1)-го рангу у мінтерм (n-1)-го рангу являє собою об’єднання відповідних пар комірок у прямокутну групу з чотирьох сусідніх комірок і т.д.
Повна кількість комірок у будь-якій групі завжди подається цілим ступенем двійки:
,
де a,b – відповідно цілі числа пар комірок по горизонталі і вертикалі, причому кожна група відображає мінтерм (n-a-b)-го рангу і покриває 2a+b мінтермів n-го рангу початкової канонічної форми.
Зчитування мінтермів з карти Карно виконується шляхом послідовного розгляду груп комірок.
У мінтерм входять тільки ті змінні, які зберігають свої значення у даній групі, причому значенням “1” відповідає сама змінна, а значенню “0” – її інверсія. Змінні, які приймають у даній групі різні значення (“0” і “1”), є вільними і у даному мінтермі відсутні.
Найпростішій формі відповідає мінімальне покриття, кількість груп в якому менша, а самі групи крупніші, ніж в аналогічних покриттях. Чим менше груп у покритті, тим менше мінтермів у формулі, чим більше розмір групи, тим нижче ранг мінтерма, тобто менша кількість змінних у мінтермі.
Знаходження мінімального покриття на карті Карно
1. Вибирається відмічена комірка, яка входить у таку найбільшу групу, яка покриває будь-які можливі групи цієї комірки.
2. За цією ж ознакою вибирається інша, ще не покрита комірка, і формується її найбільша група.
3. Цей процес продовжується до тих пір, поки всі відмічені комірки не увійдуть до груп.
4. З можливих варіантів вибирають ті, що приводять до мінімальних покриттів.
Переваги карт Карно: наочність, простота.
Недолік: метод обмежується функціями чотирьох змінних.
При п’яти змінних використовуються 2 карти для 4х змінних, одна з яких відповідає інверсії п’ятої змінної без інверсії. При цьому вони або розмічаються однаково і порівнюються накладанням, або симетрично, і порівнюються відносно вісі симетрії.
Карти Вейча
Відрізняються від карт Карно способом розмітки змінних. На рис показано карти Вейча.
Графічні методи придатні для мінімізації відносно простих функцій. Машинні методи аналізу і проектування логічних схем базуються на формальному алгоритмі Квейна-МакКласкі та його різновидах.
Синтез комбінаційних схем
Комбінаційною схемою називають таку цифрову схему, функціонування якої може бути описане системою перемикальних функцій. Комбінаційні схеми будують з елементарних комбінаційних схем, які ще наз логічними елементами (І, АБО, НІ).
Задача синтезу та її етапи
1. Перемикальна функція подається у вигляді ДДНФ.
2. Знаходиться мін ДНФ функції.
3. Мін ДНФ функції подають у вигляді суперпозиції елементних логічних операторів.
4. За операторним поданням перемикольної функції складається комбінаційна схема.