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

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







0
0
0
0
0
0
1

1
0
0
1
0
1
1

2
0
1
0
1
0
0

3
0
1
1
1
0
1

4
1
0
0
0
1
0

5
1
0
1
0
1
0

6
1
1
0
1
0
1

7
1
1
1
1
1
1

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

З отриманої множини мінтермів А будуємо ДДНФ допоміжної функції Z (вказуємо при цьому ознаки):
(2) 2. Далі приступаємо до знаходження простих імплікант за Квайном. Перед цим для зручності пронумеруємо кожний мінтерм функції Z (див. (2)).
Знаходження простих імплікант за Квайном зводиться до пошуку пар мінтермів та імплікант, що склеюються між собою. При цьому слід розрізняти (і не склеювати між собою) мінтерми, що входять до різних функцій, тобто такі мінтерми, ознаки яких не містять однакових номерів функцій.
Зауваження: процес пошуку простих імплікант є багатоетапним, причому максимальна кількість цих етапів на одиницю менша за кількість логічних змінних, від яких залежать функції системи. На першому етапі здійснюють всі можливі склеювання мінтермів функції Z. На другому етапі здійснюють склеювання імплікант, що утворилися як результат виконання першого етапу, тобто склеюють кон’юнкції, кількість змінних в яких на одиницю менша, ніж в мінтермах. І так далі, аж поки на останньому етапі не розглянуть можливість склеювання імплікант, що містять тільки дві змінні. Для нашого прикладу цей процес має два етапи (три логічні змінні), і поетапно буде виглядати так:
1-ий етап: на цьому етапі здійснюємо склеювання мінтермів функції Z. Етап можна умовно поділити на два кроки:
1) склеювання - в (2) відшукуємо всі пари мінтермів, що склеюються (мінтерми таких пар крім звичайних властивостей повинні мати в ознаці хоча б один спільний номер функції). При склеюванні результат записуємо як диз’юнкцію імпліканти і (не завжди) мінтермів, що склеювалися. Імпліканті присвоюємо ознаку, яка містить номери функцій, спільні для ознак обох мінтермів пари. Мінтерм, що брав участь в склеюванні, входить до результату склеювання, якщо його ознака не збігається повністю з ознакою імпліканти. Мінтерм, ознака якого повністю збігається з ознакою імпліканти, до результату склеювання не входить (він поглинається імплікантою). У відповідності з викладеним для нашого прикладу отримаємо (зліва в дужках вказано номери мінтермів, що склеюються):
(3) не склеюються, бо не містять спільних ознак
не склеюються
: :
(4) (5) (6) (7) (8) (9) (10) (11) Отже, ми виконали всі можливі склеювання мінтермів. Інші пари мінтермів не склеюються. На основі результатів склеювання (3) - (11) записуємо новий варіант допоміжної функції Z. Для цього спочатку записуємо диз’юнкцію імплікант, отриманих при склеюванні (в даному випадку імпліканти - це кон’юнкції двох змінних); далі дописуємо диз’юнкцію мінтермів, що фігурують в результатах склеювання (3) - (11). При цьому не допускаємо повторення однакових (включно з ознаками) )імплікант і мінтермів. Далі до отриманого результату необхідно обов’язково дописати диз’юнкцію тих мінтермів, які взагалі не були задіяні при склеюванні (аналіз на наявність таких мінтермів проводиться обов’язково!!!) - в нашому прикладі таких мінтермів немає.
Діючи в описаній послідовності, для нашого прикладу отримаємо (як і в (2), всі кон’юнкції в (12)нумеруємо:
(12) Наступним кроком є процедура поглинання.
2) поглинання - кожен мінтерм з (12) перевіряємо на предмет його поглинання одною з новоутворених імплікант. Причому поглинання можливе тільки за умови повного збігу ознак імпліканти і мінтерма. Поглинуті мінтерми викреслюємо з допоміжної функції Z. Так, в нашому прикладі мінтерм 11 поглинається імплікантою 6, а мінтерм 12 - імплікантою 9 (див. (12)). Викресливши згадані мінтерми з (12) і перенумерувавши заново кон’юнкції, отримаємо остаточно на першому етапі пошуку простих імплікант:
(13) 2-ий етап: - на цьому етапі здійснюємо склеювання імплікант, отриманих при виконанні попереднього етапу (в даному прикладі це кон’юнкції двох змінних). При цьому діємо аналогічно до 1-го етапу:
1) склеювання - здійснюємо на основі (13) по відношенню до кон’юнкцій двох змінних:
(14) (15)Інші пари кон’юнкцій двох змінних в (13) не склеюються. До нового варіанту допоміжної функції Z увійде: 1) - новоутворена імпліканта (вона однакова (повторяється) в результатах склеювання (14), (15)); 2) кон’юнкції 6, 9 з (13), які брали участь в склеюванні і не були відразу (за умови повного збігу ознак) поглинуті новоутвореними імплікантами; 3) кон’юнкції з (13), що не брали участь в склеюванні на цьому етапі, а саме (див. (13)): 1, 2, 3, 7, 8, 10, 11.
Отже в нашому прикладі, після операції склеювання і перенумерування новоутворених кон’юнкцій, допоміжна фу