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

Згідно канонічного методу синтез КС включає ряд етапів:

1. Підлягаюча реалізації булева функція (або її заперечення) представляється у вигляді СДНФ (скороченої диз’юнктивної нормальної форми).

2. З використанням методів мінімізації визначається мінімальна ДНФ (МДНФ) або мінімальна КНФ (МКНФ). З одержаних двох мінімальних форм вибирається простіша.

3. Булеву функцію в мінімальній формі згідно п.2 представляють в заданому (або вибраному розробником) базисі .

4. За уявленням функції в заданому базисі будують комбінаційну схему.

Необхідно відзначити, що булева функція F(X1,X2,...,Xm), яка підлягає реалізації може бути задана не на всіх можливих наборах аргументів X1, X2, ..., Xm. На тих наборах, де функція невизначена, її довизначають так, щоб в результаті мінімізації одержати простішу МДНФ або МКНФ. При цьому спроститься і сама КС. Крім того, досить часто з метою отримання ще простішого представлення функції МДНФ, одержана в п.2, представляється в так званій дужковій формі, тобто виносяться за дужки загальні частини імплікант МДНФ.

Доведено, що будь-яку функцію (крім тотожного нуля) можна представити у вигляді СДНФ. На практиці часто буває зручно одержати (замість СДНФ) як можна більш «коротку» ДНФ. Словам «коротка ДНФ» можна додати різний зміст, а саме: ДНФ називається мінімальною, якщо вона містить найменше число букв (зрозуміло, серед всіх ДНФ їй рівносильних); ДНФ називається найкоротшою, якщо вона містить мінімальне число знаків диз'юнкції; тупиковою, якщо знищення однієї або декількох букв у ній приведе до нерівної ДНФ і скороченою ДНФ, якщо її спрощення проведене за допомогою правила Блейка.

На практиці найбільш важливим є знаходження мінімальної ДНФ, але алгоритм її знаходження власне кажучи є варіантом перебору всіх рівносильних ДНФ. Алгоритмічно найпростіше знаходити скорочену ДНФ. Якщо функція п змінних задана своєю таблицею істинності, то правило Блейка має простий геометричний зміст. Саме, якщо всі можливі набори змінних уявити собі як вершини п-мірного куба зі стороною рівної 1 (усього вершин буде 2п) у декартовой системі координат, то треба відзначити ті вершини, на яких значення функції дорівнює 1, і якщо якась із цих одиниць лежать на «прямій», «площині» або «гіперплощині» у n-мірному просторі, то в скорочену ДНФ будуть входити «рівняння» цих прямих або гіперплощин по відомому правилу: якщо в це рівняння входило складовою частиною х = 0, то в скорочену ДНФ входить , якщо х = 1, те просто . Зрозуміло, геометрично все це зобразити можна тільки при п = 2, 3.

Карти Карно дозволяють ці геометричні засади використати при п = 3, 4, 5, для функцій, заданих своєю таблицею істинності. При більших п карти Карно практично не використовуються. Розглянемо окремо (і більш докладно) випадки п = 3, 4.

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

Оператором логічного елемента називають функцію, що реалізує цей елемент. Якщо число входів у елементів достатнє, то одержання операторного запису функції зводиться до її представлення в одній з нормальних форм. У базисі елементів І, АБО, НЕ, І-НЕ, АБО-НЕ таких форм вісім.

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

Метод мінімізації Квайна-МакКласки є модифікацією методу Квайна. Він ґрунтується на співвідношеннях неповного склеювання і поглинання, як і метод Квайна. Особливістю методу є використання цифрової форми запису перемикальних функцій. В цьому випадку зменшується число символів для представлення термів і число операцій в процесі мінімізації робить метод зручним при що програмній реалізації. Якщо використовувати геометричну інтерпретацію представлення перемикальних функцій, то кожен набір аргументів є n-мірним вектором (n – число аргументів) і визначає точку n-мірного простору. Сукупність усіх наборів представляє n-мірний куб. Конституентам відповідають вершини куба, а імплікантам – ребра і грані. Кожній конкретній функції відповідає певне представлення.

Наприклад, для функції 3-х змінних конституентам відповідають вершини 3-мірного куба, а імплікантам – ребра і грані. Терми n-рангу називають 0-кубами, терми (n-1)-го рангу – 1-кубами, (n-2)-рангу – 2-кубами і т.д.

Етапи мінімізації:

1. Для функції виписують комплекс 0-кубів (K0). Набори упорядковуються за кількістю одиниць. Одержують групи без одиниць, з однією одиницею, із двома і т.д. В цьому випадку склеювання можливе тільки між сусідніми групами кубів.

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

3. Шляхом поглинання формується покриття Z, що відповідає скороченій ДНФ.

4. Будується матриця покриття, з якої визначають усі ТДНФ.

5. Серед ТДНФ відшукується МДНФ.

1.2 Структурний синтез цифрових автоматів

Цифровий автомат - пристрій, що характеризується набором внутрішніх станів, в які він переходить під впливом команд