МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»

МЕТОДИ АНАЛІЗУ ТА СИНТЕЗУ
КОМБІНАЦІЙНИХ СХЕМ.
КОМБІНАЦІЙНІ СХЕМИ З ОДНИМ ВИХОДОМ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 2
з курсу «Обчислювальна техніка»
для студентів спеціальностей
7.160102 “Захист інформації з обмеженим доступом та автоматизація її обробки”
7.160103 “Системи захисту від несанкціонованого доступу”
7.160104 “Адміністративний менеджмент в сфері захисту інформації з обмеженим доступом”
7.160105“Захист інформації і комп'ютерних системах і мережах”
Львів 2008
Мета роботи: - вивчення методів аналізу і синтезу комбінаційних логічних схем з одним виходом, оцінки їх апаратурної складності та швидкодії.
1. ОСНОВНІ ВІДОМОСТІ
Логічний елемент - це електронний пристрій, який реалізує певну логічну (перемикальну) функцію. Сукупність логічних елементів і зв’язків між ними, призначену для перетворення двійкових змінних, називають логічною схемою. Логічні схеми поділяють на послідовнісні і комбінаційні.
Комбінаційною називають схему, m вихідних сигналів якої в кожний момент часу повністю визначаються сукупністю n її вхідних сигналів в цей самий момент часу. Тобто вихідні сигнали комбінаційної схеми в даний момент часу не залежать від вхідних сигналів, які діяли в попередні моменти часу (схема не має пам’яті). Кажуть, що така схема має один стан.
Поведінка комбінаційної схеми описується системою логічних функцій. Виділяють задачі аналізу та синтезу комбінаційних схем.
Задача аналізу комбінаційної схеми полягає в знаходженні системи логічних функцій, що відображають логіку роботи такої схеми. В процесі аналізу з схеми вилучають елементи, що не впливають на логіку її роботи (формувачі, елементи узгодження і т.д.), після чого визначають згадану систему логічних функцій.
Задача синтезу є оберненою до задачі аналізу.
1.1. Синтез комбінаційної схеми з одним виходом
Синтез комбінаційної схеми можна поділити на три етапи.
Перший етап:
- Складають таблицю істинності, в якій фіксується склад і значення вхідних та вихідних логічних змінних і яка відображає задану логіку роботи комбінаційної схеми: - в такій таблиці для кожного можливого набору значень (далі просто набору) вхідних логічних змінних вказують значення логічної функції: «1», «0», або «*» (в останньому випадку значення функції невизначене). Можна також задати логічну функцію в іншій формі, наприклад в досконалій диз’юнктивній нормальній формі (ДДНФ).
- На основі таблиці істинності, застосовуючи ті чи інші методи мінімізації логічних функцій, знаходять логічне рівняння в мінімальній диз’юнктивній нормальній формі (МДНФ). При цьому якщо логічна функція визначена не на всіх наборах вхідних змінних, здійснюють її оптимальне довизначення (таке довизначення, при якому функція буде мати простішу МДНФ).
Другий етап:
Отримане на першому етапі логічне рівняння заданої функції (у МДНФ) записують в операторній формі, тобто у вигляді суперпозиції операторів логічних елементів (оператором логічного елемента називають функцію, яку реалізує цей елемент). Якщо обмежитися операторами І, АБО, І-НЕ, АБО-НЕ і припустити, що число входів відповідних логічних елементів є достатньо великим, то операторний запис функції зводиться до її подання в одній із восьми стандартних канонічних нормальних форм (див. Приклад 1). Нормальні форми дозволяють будувати комбінаційні схеми з двома рівнями (каскадами) логічних елементів.
Якщо число входів p логічних елементів менше, ніж вимагається для реалізації рівняння в нормальній формі, то змінні об’єднуються в групи (не більше p змінних в кожній). Причому число таких груп також не повинне перевищувати p, інакше така сукупність груп в свою чергу розбивається на групи по p елементів і так далі. Такі перетворення дозволяють подати задану функцію в операторній формі з врахуванням числа входів елементів. Але в цьому випадку операторна форма не буде нормальною, бо за рахунок додаткового каскадування елементів комбінаційна схема буде мати більше ніж два рівні.
Третій етап:
На основі операторного представлення логічної функції будують комбінаційну схему. При цьому враховують задану систему логічних елементів. Якщо задана система логічних елементів дозволяє реалізувати (або взяти за основу при реалізації з врахуванням числа входів елементів) декілька нормальних операторних форм, всі можливі варіанти реалізації комбінаційної схеми порівнюють за заданими параметрами і вибирають оптимальний варіант реалізації. Найчастіше такими параметрами є складність і швидкодія схеми. Розглянемо зміст етапів синтезу схеми на прикладі.
Таблиця 1
№ набору






0
0
0
0
0
0

1
0
0
0
1
0

2
0
0
1
0
0

3
0
0
1
1
1

4
0
1
0
0
0

5
0
1
0
1
1

6
0
1
1
0
1

7
0
1
1
1
*

8
1
0
0
0
0

9
1
0
0
1
1

10
1
0
1
0
1

11
1
0
1
1
*

12
1
1
0
0
1

13
1
1
0
1
*

14
1
1
1
0
*

15
1
1
1
1
0

Приклад 1: нехай потрібно побудувати комбінаційну схему, яка реалізує логічну функцію y. Причому , якщо мають місце дві з чотирьох можливих подій. Якщо ж одночасно мають місце три події, логічна функція y може мати будь-яке значення. В інших випадках .
Перший етап:
Позначимо згадані в умові задачі чотири події як вхідні логічні змінні . Домовимося, що коли деяка i-та подія має місце, то . Інакше .
За словесним описом заданої логічної функції складаємо таблицю істинності (Таблиця 1). В першому стовпчику таблиці вказуємо номер набору вхідних логічних змінних. В наступних чотирьох стовпчиках - власне набір вхідних логічних змінних. Іншими словами в рядках Таблиці 1 (в межах стовпчиків ) перебираємо поєднання можливих подій: - починаючи від випадку коли не має місця жодна з подій і закінчуючи випадком коли одразу всі чотири події мають місце. Останній стовпчик таблиці (значення логічної функції y) заповнюємо у відповідності з заданим словесним описом цієї функції. Тобто значення функції будь-яке (*) в тих рядках таблиці, в яких є три одиниці в межах стовпчиків - (набори 7, 11, 13, 14). Значення функції дорівнює одиниці в тих рядках таблиці, в яких є дві одиниці в межах стовпчиків - (набори 3, 5, 6, 9, 10, 12). Для інших наборів значення функції дорівнює нулю.


1



1
*
1

1
*

*


1
*
1


Рис.1

1
1

1

1

*



*
1
*

1

*



Рис.2
Далі мінімізуємо логічну функцію, задану Таблицею 1, методом карт Карно. Причому використовуємо карту Карно для чотирьох змінних (Рис.1). У відповідності з таблицею істинності наносимо одиничні і невизначені значення логічної функції на карту Карно (Рис.1) і здійснюємо їх накриття мінімальним числом правильних прямокутників (контурів склеювання) максимальної площі. При цьому невизначені значення функції довизначаємо так, щоб отримана внаслідок мінімізації МДНФ була якомога простішою (в нашому прикладі невизначені значення функції, які відповідають наборам 7,11,13 ми визначаємо як одиничні, а значення функції, яке відповідає 14-ому набору довизначаємо як нульове). Кожному контуру склеювання в МДНФ функції відповідає одна кон’юнкція. Причому в цю кон’юнкцію входять ті змінні, які в однаковій формі (прямій або інверсній) входять в ті мінтерми, чиї клітинки охоплені даним контуром. Наприклад, значення функції, охоплені крайнім лівим контуром на Рис.1, будуть представлені в МДНФ кон’юнкцією , оскільки клітинкам карти Карно, охопленим даним контуром, відповідають мінтерми і , які відрізняються тільки формою входження в них змінної .
Аналогічно мінімізуємо заперечення функції y ( - Рис.2). При заповненні цієї карти (порівняно з Рис.1) невизначені значення функції так і залишаються невизначеними, одиниці заміняються нулями, а нулі - одиницями.
Результатом мінімізації є МДНФ функції та її заперечення :
(1) (2) Другий етап:
Знаходимо представлення логічної функції y у восьми стандартних канонічних нормальних формах. Позначаються нормальні форми вказівкою на внутрішні та зовнішні функції розкладу. Наприклад, для МДНФ (1) внутрішньою логічною функцією є функція І (тобто кон’юнкції, що відповідають контурам склеювання). Зовнішньою функцією розкладу є функція АБО. Отже МДНФ (1) логічної функції y є формою І/АБО:
(форма І/АБО) Наступну форму знаходимо, два рази проінвертувавши форму І/АБО і застосувавши один раз правило де Моргана:

(форма І-НЕ/І-НЕ) Застосувавши правило де Моргана до кожної з внутрішніх функцій розкладу форми І-НЕ/І-НЕ, отримують форму АБО/І-НЕ:

(форма АБО/І-НЕ) Нарешті, застосувавши пр