Методичні вказівки до практичних занять з дисципліни «Схемотехніка»

2
Мінімізація логічних функцій методом карт Карно. Синтез комбінаційної схеми з
одним виходом
Синтез комбінаційної схеми можна поділити на три етапи.
Перший етап:
- Складають таблицю істинності, в якій фіксується склад і значення вхідних та вихідних логічних змінних і яка відображає задану логіку роботи комбінаційної схеми: - в такій таблиці для кожного можливого набору значень (далі просто набору) вхідних логічних змінних вказують значення логічної функції: «1», «0», або «*» (в останньому випадку значення функції невизначене). Можна також задати логічну функцію в іншій формі, наприклад в аналітичній у вигляді досконалої диз’юнктивної нормальної форми
(ДДНФ).
- На основі таблиці істинності, застосовуючи ті чи інші методи мінімізації логічних функцій, знаходять логічне рівняння в мінімальній диз’юнктивній нормальній формі
(МДНФ). При цьому якщо логічна функція визначена не на всіх наборах вхідних змінних, здійснюють її оптимальне довизначення (таке довизначення, при якому функція буде мати простішу МДНФ).
Другий етап:
Отримане на першому етапі логічне рівняння заданої функції (у МДНФ) записують в операторній формі, тобто у вигляді суперпозиції операторів логічних елементів
(оператором логічного елемента називають функцію, яку реалізує цей елемент). Якщо обмежитися операторами І, АБО, НЕ, І-НЕ, АБО-НЕ і припустити, що число входів відповідних логічних елементів є достатньо великим, то операторний запис функції зводиться до її подання в одній із восьми стандартних канонічних нормальних форм (див.
Приклад 1). Нормальні форми дозволяють будувати комбінаційні схеми з двома рівнями
(каскадами) логічних елементів.
Якщо число входів p логічних елементів менше, ніж вимагається для реалізації рівняння в нормальній формі, то змінні об’єднуються в групи (не більше p змінних в кожній). Причому число таких груп також не повинне перевищувати p, інакше така сукупність груп в свою чергу розбивається на групи по p елементів і так далі. Такі перетворення дозволяють подати задану функцію в операторній формі з врахуванням числа входів елементів. Але в цьому випадку операторна форма не буде нормальною, бо за рахунок додаткового каскадування елементів комбінаційна схема буде мати більше ніж два рівні.
Третій етап:
На основі операторного представлення логічної функції будують комбінаційну схему. При цьому враховують задану систему логічних елементів. Якщо задана система логічних елементів дозволяє реалізувати (або взяти за основу при реалізації з врахуванням числа входів елементів) декілька нормальних операторних форм, всі можливі варіанти реалізації комбінаційної схеми порівнюють за заданими параметрами і вибирають оптимальний варіант реалізації. Найчастіше такими параметрами є складність і швидкодія схеми. Розглянемо зміст етапів синтезу схеми на прикладі.

3
Приклад 1:нехай потрібно побудувати комбінаційну схему, яка реалізує логічну функцію y. Причому y  1
, якщо мають місце дві з чотирьох можливих подій. Якщо ж одночасно мають місце три події, логічна функція y може мати будь-яке значення. В
інших випадках y  0
Перший етап:
Позначимо згадані в умові задачі чотири події як вхідні логічні змінні x x x x
1 2
3 4
,
,
,
Домовимося, що коли деяка i-та подія має місце, то x i
 1. Інакше x i
 0.
За словесним описом заданої логічної функції складаємо таблицю істинності (Таблиця
1). В першому стовпчику таблиці вказуємо номер
набору вхідних логічних змінних. В наступних чотирьох стовпчиках - власне набір значень вхідних логічних змінних. Іншими словами в рядках Таблиці 1 (в межах стовпчиків x x x x
1 2
3 4
,
,
,
) перебираємо поєднання можливих подій: - починаючи від випадку коли не має місця жодна з подій і закінчуючи випадком коли одразу всі чотири події мають місце. Останній стовпчик таблиці (значення логічної функції y) заповнюємо у відповідності з заданим словесним описом цієї функції. Тобто значення функції будь-яке (*) в тих рядках таблиці, в яких є три одиниці в межах стовпчиків x
1
- x
4
(набори 7, 11, 13, 14). Значення функції дорівнює одиниці в тих рядках таблиці, в яких є дві одиниці в межах стовпчиків x
1
- x
4
(набори 3, 5, 6, 9, 10, 12). Для інших наборів значення функції дорівнює нулю.
Далі мінімізуємо логічну функцію, задану
Таблицею 1, методом карт Карно. Причому використовуємо карту Карно для чотирьох змінних (Рис.1). У відповідності з таблицею
істинності наносимо одиничні і невизначені значення логічної функції на карту Карно (Рис.1)
і здійснюємо їх накриття мінімальним числом контурів склеювання максимальної площі. При цьому невизначені значення функції довизначаємо так, щоб отримана внаслідок мінімізації МДНФ була якомога простішою (в нашому прикладі невизначені значення функції, які відповідають наборам 7,11,13 ми визначаємо як одиничні, а значення функції, яке відповідає
14-ому набору довизначаємо як нульове).
Кожному контуру склеювання в МДНФ функції відповідає одна кон’юнкція. Причому в цю
Таблиця 1
№ набору
x
1
x
2
x
3
x
4
y
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 1
*
1 1
*
*
1
*
1
Рис.1 1
1 1
1
*
*
1
*
1
*
Рис.2
x
1
x
4
x
2
x
3
x
1
x
4
x
2
x
3

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

5

 
 
 
 

y
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x















2 3
4 1
2 4
2 3
4 1
2 3
1 3
4
(форма АБО/І)
Інвертуючи форму АБО/І два рази і застосувавши до одної інверсії правило де
Моргана, отримаємо восьму нормальну форму - АБО-НЕ/АБО-НЕ:

 
 
 
 

y
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
















2 3
4 1
2 4
2 3
4 1
2 3
1 3
4

 
 
 
 
















x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2 3
4 1
2 4
2 3
4 1
2 3
1 3
4
(форма АБО-НЕ/АБО-НЕ)
Третій етап:
За операторними представленнями функції, з врахуванням наявних логічних елементів, будують комбінаційну схему.
Наприклад, якщо в нашому розпорядженні є логічні елементи І та АБО, ми можемо побудувати дворівневі комбінаційні схеми тільки на основі форм І/АБО, АБО/І.
Порівнюючи ці дві схеми, приходимо до висновку, що схема за формою АБО/І буде простішою, бо вимагає менше тривходових елементів на першому рівні і елемента з меншою кількістю входів на другому рівні.
Комбінаційну схему, побудовану за формою
АБО/І у відповідності з Прикладом 1, подано на Рис.3.
Мінімізація логічних функцій методом Квайна.
Метод Квайна мінімізації логічних функцій може бути коротко описаний наступним
алгоритмом:
1. Записати задану логічну функцію n змінних в досконалій диз’юнктивній нормальній формі (ДДНФ), тобто як диз’юнкцію мінтермів (елементарних кон’юнкцій n – ого рангу), які відповідають всім одиничним значенням заданої функції.
2. Здійснити всі можливі склеювання мінтермів ДДНФ заданої функції. Результатами склеювання будуть кон’юнкції-імпліканти (n-1) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію імплікант і тих мінтермів, які не мали пари для склеювання.
3. Здійснити всі можливі склеювання імплікант (n-1) -ого рангу. Результатами склеювання будуть кон’юнкції-імпліканти (n-2) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію отриманих імплікант (n-2) -ого рангу, мінтермів і імплікант
(n-1) -ого рангу, які не мали пари для склеювання. Повторювати пункт 3, поки у функції Z будуть існувати імпліканти, які можна склеїти.
4. Всі імпліканти функції Z, отриманої в пункті 3, є простими, тобто не мають пари для склеювання. Для такої функції Z – скороченої форми заданої логічної функції -
1 1
1 1
1
&
x
2
x
3
x
4
x
1
x
2
x
4
x
3
y
Рис.3

6 побудувати імплікантну таблицю Квайна. Стовпці таблиці відповідають мінтермам заданої логічної функції, а рядки – простим імплікантам функції Z.
5. За допомогою імплікантної таблиці Квайна визначити тупикові і мінімальні форми заданої логічної функції.
Розглянемо реалізацію описаного алгоритму на прикладі.
Приклад. Виконати мінімізацію методом
Квайна логічної функції, заданої таблицею
істинності
(Таблиця
1).
Побудувати комбінаційну схему для реалізації мінімізованої функції, використовуючи елементи І, АБО, НЕ.
Розв’язання.
1. Перший крок при реалізації даного методу мінімізації - запис заданої функції в
ДДНФ, тобто у вигляді диз’юнкції мінтермів, що відповідають одиничним значенням логічної функції. Отже, спираючись на Таблицю 1, записуємо ДДНФ заданої логічної функції. При цьому мінтерми ДДНФ нумеруємо:
8 4
3 2
1 7
4 3
2 1
6 4
3 2
1 5
4 3
2 1
4 4
3 2
1 3
4 3
2 1
2 4
3 2
1 1
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Z









(1)
Далі переходимо до знаходження простих імплікант за Квайном.
Знаходження простих імплікант за Квайном зводиться до пошуку пар мінтермів та
імплікант, що склеюються між собою.
Для нашого прикладу цей процес буде
виглядати так:
1-ий етап: на цьому етапі здійснюємо всі можливі склеювання мінтермів функції
(1). Для цього перебираємо всі можливі пари мінтермів у функції (1):



 2 1
не склеюються



 3 1
не склеюються,



 4 1
4 3
1 4
4 3
2 1
1 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x


:
:



 4 2
4 2
1 4
4 3
2 1
2 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x





 4 3
3 2
1 4
4 3
2 1
3 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x


Таблиця 1
№ набору
x
1
x
2
x
3
x
4
z
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 1
8 1
0 0
0 0
9 1
0 0
1 1
10 1
0 1
0 1
11 1
0 1
1 0
12 1
1 0
0 1
13 1
1 0
1 0
14 1
1 1
0 1
15 1
1 1
1 0

7



 8 3
4 3
2 8
4 3
2 1
3 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x





 8 6
4 3
1 8
4 3
2 1
6 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x





 8 7
4 2
1 8
4 3
2 1
7 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x


Отже, ми виконали всі можливі склеювання мінтермів. Аналізуючи результати склеювання робимо висновок, що з восьми мінтермів функції (1) тільки п’ятий не мав пари для склеювання. На основі результатів склеювання записуємо новий варіант функції
Z. Для цього спочатку записуємо диз’юнкцію імплікант, отриманих при склеюванні (в даному випадку імпліканти - це кон’юнкції трьох змінних). При цьому не допускаємо
повторення однакових імплікант. Далі дописуємо диз’юнкцію мінтермів, що не мали пари для склеювання (в даному прикладі – п’ятий мінтерм функції (1)). Імпліканти нумеруємо. Отримаємо вираз (2).
4 3
2 1
7 4
2 1
6 4
3 1
4 4
3 2
3 3
2 1
2 4
2 1
1 4
3 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Z







(2)
Далі перевіряємо всі імпліканти 3-го рангу з виразу (2) на можливість склеювання.
В даному прикладі жодна імпліканта з (2) не має пари для склеювання. Тобто всі кон’юнкції виразу (2) є простими імплікантами. Тому переходимо до складання
імплікантної таблиці Квайна.
2-ий етап:
Будуємо імплікантну таблицю функції