4.6 Аналіз і синтез комбінаційних схем
В розділі 4.2 було показано, що в системах керування інформацію, зображену фізичними сигналами, оброблюють керуючі автомати, які поділяють на два класи – комбінаційні схеми (автомати без пам’яті) та цифрові автомати з пам’яттю.
Нагадуємо, що логічну схему називають комбінаційною, коли сукупність вихідних сигналів Y у будь-який момент часу однозначно визначають сигнали X, що надходять на її входи.
Комбінаційну схему (КС) можна задати абстрактною чи структурною моделлю. Абстрактною моделлю КС є або таблиця істинності, або логічні вирази, які пов’язують залежністю вихідні сигнали з вхідними. Структурну модель КС використовують для побудови її з конкретних логічних елементів. Табл. 4.5, логічні вирази (4.45), (4.46) і рис 4.20 являють собою зразки зазначених моделей для опису закону додавання однорозрядних двійкових чисел (півсуматор).
Таблиця 4.5 – Таблиця істинності для півсуматора
| x1 | x1 | y1=S | y2 = C |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Сума:
(4.45)перенесення:
. (4.46) 
Рисунок 4.20 – Структурна модель однорозрядного півсуматора (функціональна схема)
У ході розробки комбінаційних схем доводиться вирішувати завдання аналізу та синтезу.
Завдання аналізу полягає у визначенні статичних і динамічних властивостей комбінаційної схеми. У статиці визначаються булеві функції, реалізовані комбінаційної схемою за відомою її структурою. У динаміці розглядається здатність надійного функціонування схеми в перехідних процесах при зміні значень змінних на входах схеми, тобто визначається наявність на виходах схеми можливих небажаних імпульсних сигналів, які не випливають безпосередньо з виразів для булевих функцій, реалізованих схемою.
Завдання синтезу полягає в побудові із заданого набору логічних елементів комбінаційної схеми, що реалізує задану систему булевих функцій. Звичайно на етапі проектування закон функціонування КС спочатку задають у вигляді таблиці істинності. За нею потім складають логічний вираз, згідно з яким будують структуру КС.
4.6.1 Канонічний метод синтезу комбінаційних схем
4.6.1.1 Основні етапи канонічного синтезу комбінаційних схем
Як зазначалося вище, комбінаційна схема (КС) може мати кілька виходів. При канонічному методі передбачається, що кожна вихідна функція реалізується своєю схемою, сукупність яких і дає необхідну КС. Тому синтез складної КС з n виходами замінюється синтезом n схем з одним виходом.
Згідно з канонічним методом синтез КС включає в себе ряд етапів.
1. Вербальний опис функціонування комбінаційної схеми перетворюється в абстрактну модель, представлену спочатку таблицею істинності, а потім логічною функцією (або системою логічних функцій).
2. Логічні функції, що підлягають схемній реалізації представляються у вигляді досконалої диз’юнктивної нормальної форми (ДДНФ).
3. З використанням методів мінімізації визначається мінімальна ДНФ ( МДНФ ) або мінімальна кон’юнктивна нормальна форма ( МКНФ ). З отриманих двох мінімальних форм вибирається більш проста.
4. Булеву функцію в мінімальній формі представляють в заданому (або обраному розробником ) базисі.
5. За поданням функції в заданому базисі будують комбінаційну схему.
Розглянемо методику синтезу комбінаційних схем поетапно на прикладі мажоритарної схеми.
Приклад 4.21. Спроектувати логічну схему на три входи і один вихід, яка виробляє вихідний сигнал тільки в тому випадку, коли “1” з’являється більш ніж на одному вході, тобто схема повинна видавати сигнал на виході при появі сигналів на будь-яких двох входах або на всіх трьох. В цьому і проявляється “мажоритарність”, наприклад, для чотиривходової і п’ятивходової мажоритарних схем вихідний сигнал повинен з’являтися при кількості “1” більш ніж на двох входах, для шестивходової – більш ніж на трьох і т.д.
Наведений в прикладі 4.21 опис задачі і є вербальним описом закону функціонування комбінаційної схеми.
Виконуємо етап №1 – переходимо від вербального опису спочатку до таблиці істинності, а потім до логічної функції. Як було показано в розділі 2, кількість стрічок в такій таблиці дорівнює кількості різних наборів значень аргументів логічної функції (вхідних сигналів комбінаційної схеми), тобто z =2n , де n – кількість аргументів (входів). Для нашого випадку n=3, і z =23=8. Тоді таблиця істинності для мажоритарної схеми на три входи має вигляд табл.4.6:
Таблиця 4.6
-
№
набору
Входи
Вихід
F(x)
x3
x2
x1
0
0
0
0
0
1
0
0
1
0
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
Таким чином, 1-й етап синтезу заданої КС виконано.
Для виконання 2-го етапу потрібно перейти від представлення комбінаційної схеми у вигляді таблиці істинності до її представлення логічними функціями, для цього використовують канонічні форми представлення логічних функцій. Розглянемо способи здійснення такого переходу за допомогою досконалої диз’юнктивної нормальної форми (ДДНФ) та досконалої кон’юктивної форми (ДКНФ).
4.6.1.2 Представлення заданої логічної функції канонічною формою
Здебільшого логічну функцію під час синтезу комбінаційної схеми представляють у вигляді ДДНФ.
Нагадуємо, що згідно з означенням 2.20 розділу 2, досконалою диз’юнктивною нормальною формою бульової функції називають диз’юнкцію конституент одиниці:
; (4.47)де
,
, … ,
- функції, названі конституентами одиниці (або мінтермами).Згідно з виразом (4.47) ДДНФ записують за її таблицею істинності відповідно до такого правила: для кожного набору змінних, на якому бульова функція набуває одиничного значення, записують конституенту одиниці і всі ці конституенти одиниці об’єднують диз’юнктивно.
З таблиці істинності логічної функції, що представляє в прикладі 4.21 мажоритарну схему на три входи (табл. 4.6), бачимо, що ця функція перетворюється в одиницю на 3, 5, 6 та 7-му наборах значень змінних (нумерація наборів починається з 0). Конституенти одиниці для таких наборів можна записати відповідно у вигляді
, 
, 
і 
. Звичайно, щоб наведені кон’юнкції мали одиничні значення, змінні, які мають на вказаних наборах нульове значення, беруть із запереченням.
Таким чином, ДДНФ для логічної функції з табл. 4.6 запишемо у вигляді:
3 5 6 7 
. (4.48)У виразі (4.48) зверху над конституентами одиниці записані номери наборів таблиці істинності, яким вони відповідають.
Виконаємо третій етап синтезу комбінаційної схеми – етап мінімізації логічних функцій.
4.6.1.3 Мінімізація заданої логічної функції
У розділі 2 було показано, що при наявності потрібного набору логічних елементів будь-яку логічну функцію, зображену бульовим виразом, можна реалізувати у вигляді електронної цифрової схеми. Наприклад, з виразу
бачимо, що для реалізації його у вигляді фізичної схеми треба мати три логічних елементи I, два інвертори і один елемент АБО з трьома входами (рис. 4.21,а). 
Рисунок 4.21 - Структурні схеми електронних пристроїв, які реалізують логічні функції:
а) -
; б) - 
.Схема, що реалізує логічну функцію
, скла-дається лише з одного логічного елемента АБО (рис. 4.21, б). Аналіз обох цих схем свідчить про те, що вони мають один і той самий закон функціонування (табл. 4.7).Таблиця 4.7
| Входи | Виходи | ||
 |  |  | |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Таким чином, один і той самий процес перетворення цифрових сигналів можуть виконувати схеми, що мають різну складність, а отже, і вартість. Як умовний критерій вартості логічної схеми використовують її складність, що залежить від сумарної кількості входів логічних елементів.
Приклад 4.22. Визначити складність схем, представлених на рис. 4.21, а) і на рис. 4.21, б).
Розв’язування: З урахуванням того, що схема на рис.4.21,а) містить 2 одновходових логічних елементи НЕ, 3 двохвходових логічних елементи І та один тривходовий логічний елемент АБО, вираховуємо:
Су1 = 2 ·1 + 3 · 2 + 1 · 3=2+6+3=11.
Аналогічно для схеми на рис.4.21,б) маємо:
Су2 = 1·2 = 2.
Відповідь: Су1 =11, Су2 = 2.
Оскільки існує однозначна відповідність між бульовою функцією та логічною схемою, що її реалізує, то складність схеми можна зменшити шляхом мінімізації бульової функції, під якою розуміють процедуру знаходженням найпростішого виразу для неї, еквівалентного початковому.
Найчастіше мінімізують логічну функцію, подану в ДДНФ, щоб одержати мінімальну диз’юнктивну нормальну форму (МДНФ).
Мінімальною називають ДНФ логічної функції, вираз якої складається з найменшої сумарної кількості змінних та їх заперечень в усіх диз’юнктивних членах порівняно з усіма іншими еквівалентними ДНФ цієї функції.
Найпоширеніші методи мінімізації – з допомогою діаграм Вейча - Карно і метод Квайна - Мак-Класкі.
Застосуємо метод діаграм Вейча - Карно для мінімізації заданої логічної функції, представленої таблицею істинності табл. 4.6, що описує мажоритарну схему прикладу 4.21.
| Входи | В  ихідF(x) | ||
| x3 | x2 | x1 | |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Рисунок 4.22 – Побудова діаграми Вейча-Карно для мажоритарної логічної функції прикладу 4.21
Діаграми Вейча–Карно зручно застосовувати для мінімізації логічних функцій, що містять не більш як чотири-шість змінних. Діаграми Вейча-Карно являють собою спеціально організовані таблиці істинності. Спеціальна організація полягає в тому, щоб на таких таблицях істинності можна було формально виконувати закон склеювання.
Будуємо діаграму Вейча – Карно для функції трьох аргументів, заповнюючи одиницями її клітинки так, як зображено на рис. 4.22. З одиниць у першій стрічці діаграми, згідно правил проведення контурів (див. розділ 2), утворюємо 1-й і 2-й контури. Один вертикальний рядок одиниць у другому стовпчику діаграми дає третій контур.
Оскільки маємо три контури, то МДНФ буде містити три кон’юнкції. Визначимо їх склад. Оскільки перший контур перетинає один раз змінні x1 і x2без заперечення, то вони не вилучаються з конституенти одиниці і їх кон’юнкція утворює імпліканту x1x2. Змінна x3 цей контур перетинає двічі – як з запереченням, так і без нього, тому вона вилучається з кон’юнкції. Другий контур перетинає один раз змінні x1 і x3без заперечення, тому вони не вилучаються і утворюють імпліканту x1x3.Змінна x2 цей контур перетинає двічі – як з запереченням, так і без нього, тому вона вилучається з кон’юнкції. Аналогічно, третій контур перетинає один раз змінні x2 і x3без заперечення, тому вони не вилучаються і утворюють імпліканту x2x3. Змінна x1 цей контур перетинає двічі – як з запереченням, так і без нього, тому вона вилучається з кон’юнкції. Об’єднавши отримані три кон’юнкції диз’юнктивно, отримаємо потрібний вираз.
Отримана мінімальна ДНФ даної логічної функції має вигляд
FМДНФ= x1x2+x1x3+x2x3 . (4.48)
Необхідно відзначити, що логічна функція, яка підлягає реалізації F( x1, x2, ... , xm) може бути задана не на всіх можливих наборах аргументів, в такому випадку вона називається частково визначеною. На тих наборах, де функція невизначена, її довизначають таким чином, щоб у результаті мінімізації отримати більш просту МДНФ або МКНФ. При цьому спроститься і сама КС. Крім того, досить часто з метою отримання ще більш простого представлення функції МДНФ, отримана на третьому етапі, представляється в так званій дужковій формі, тобто виносяться за дужки загальні частини імплікант МДНФ.
Після того, як в процесі синтезу отримано МДНФ (чи МКНФ) логічної функції, виконують четвертий етап - перехід до заданого логічного базису.
Під час проектування інтегральних схем, які реалізують складні логічні функції, з погляду технологічності їх виготовлення дуже важливо забезпечити однотипність використовуваних логічних елементів. Для цього прагнуть застосовувати елементи одного й того самого базису. Тому треба навчитися зводити логічні вирази від одного базису до іншого. Наприклад, щоб звести до базису І-НЕ отриману логічну функцію (4.48), потрібно з допомогою законів алгебри логіки (в цьому випадку застосовують закон подвійного заперечення і правило де Моргана) перетворити її до потрібного вигляду:
FМДНФ= x1x2+x1x3+x2x3=
.На п’ятому етапі на основі отриманого виразу логічної функції складають її функціональну схему з логічних елементів заданого базису. В нашому випадку такими є логічні елементи І-НЕ. Згідно отриманого виразу, схема складається з трьох двох-входових і одного тривходового вентилів І-НЕ (рис.4.23).
У випадку, коли логічна функція має більш як п’ять аргументів, то діаграми Вейча-Карно робляться невкладистими. Тому в цьому разі мінімізувати логічні функції, зображені в ДДНФ, зручніше методом Квайна - Мак-Класкі, який передбачає виконання двох основних етапів. На першому з них переходять від ДДНФ до скороченої ДНФ логічної функції. На другому етапі переходять від скороченої ДНФ до глухих ДНФ і вибирають з-поміж них МДНФ [1,7]].
Рисунок 4.24 – Функціональна схема синтезованої КС для прикладу 4.21
1 2 3