Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Менеджмент
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Захист інформації в комп’ютерних системах
Група:
МЕ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
МЕТОДИ АНАЛІЗУ ТА СИНТЕЗУ
КОМБІНАЦІЙНИХ СХЕМ.
КОМЬ\БІНАЦІЙНІ СХЕМИ З ОДНИМ ВИХОДОМ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 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.
Отже в нашому прикладі, після операції склеювання і перенумерування новоутворених кон’юнкцій, допоміжна функція Z набуде вигляду:
(16) 2) поглинання - всі кон’юнкції в (16) перевіряємо на предмет їх поглинання новоутвореними імплікантами - в даному прикладі імплікантою . Оскільки поглинання ми здійснюємо тільки при повному збігу ознак, приходимо до висновку, що жодна з кон’юнкцій виразу (16) новоутвореною імплікантою не поглинається. Тому, а також через те, що новоутворена імпліканта містить тільки одну змінну, вираз (16) є остаточним на етапі знаходження простих імплікант за Квайном. Тобто приходимо до висновку, що вираз (16) містить тільки прості імпліканти, які більше не склеюються між собою. Зауваження: взагалі кажучи, процес пошуку простих імплікант завершується за умови, якщо новоутворені імпліканти не склеюються між собою. Тобто не завжди при склеюванні можна дійти до імплікант з одною змінною.
Таблиця 2
Будуємо імплікантну таблицю функції Z (Таблиця 2). В таблиці відводимо по одному рядку на кожну просту імпліканту з (16). Кожен стовпець імплікантної таблиці відповідає одній одиниці з таблиці істинності (Таблиця 1). Тобто на кожен мінтерм з множини A в Таблиці 2 відводиться стовпець, який додатково розбивається на частини за кількістю різних номерів функцій, які містить ознака даного мінтерма.
Прості
Мінтерми функції Z
імпліканти
3
2
3
1
1
3
2
2
1
3
1
2
3
я
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
X
X
X
X
?
X
Імплікантну таблицю заповнюємо в такій послідовності:
відображаємо факт покриття простими імплікантами функції Z тих чи інших мінтермів системи. Для цього в кожному рядку таблиці ставимо позначки на перетині з стовпцями, що відповідають таким мінтермам, які імпліканта даного рядка здатна поглинути з врахуванням ознак. Наприклад, імпліканта здатна поглинути чотири з восьми мінтермів системи (а саме ті, в які змінна входить, як і в імпліканту, в прямому вигляді). Цим чотирьом мінтермам в Таблиці 2 відповідають вісім стовпців, але позначки ставимо тільки в тих стовпцях, які мають таку - ж ознаку, як і дана імпліканта - ознаку 1. Фізично факт покриття мінтерма простою імплікантою (тобто зміст позначки в імплікантній таблиці) означає наступне. Дана проста імпліканта, за умови включення її до виразу, на основі якого здійснено синтез комбінаційної схеми, здатна забезпечити на виході цієї схеми наявність тієї одиниці з таблиці істинності, якій відповідає даний стовпець імплікантної таблиці.
аналізуємо всі стовпці імплікантної таблиці - всі позначки, які є єдиними в стовпці, виділяємо (в Таблиці 2 обведено). Наявність єдиної позначки, що лежить на перетині певного стовпця з рядками імплікантної таблиці, означає, що тільки одна імпліканта з множини простих імплікант здатна забезпечити наявність тієї одиниці з таблиці істинності, якій відповідає даний стовпець.
аналізуємо всі рядки імплікантної таблиці - ті рядки, які містять хоча б одну виділену позначку, в свою чергу відмічаємо (в Таблиці 2 відмічено буквою я). Одночасно в останній (допоміжний) рядок виносимо всі позначки, які містяться у виділених рядках. Після цього визначаємо ті клітинки допоміжного рядка, в яких позначок немає (в Таблиці 2 такі клітинки позначено знаком ?).
На основі імплікантної таблиці записуємо мінімальну ДНФ (МДНФ) допоміжної функції Z. В МДНФ обов’язково входить ядро функції - диз’юнкція відмічених в імплікантній таблиці (буквою я) простих імплікант. Адже, як вже було сказано, кожна з таких імплікант є єдиним можливим «джерелом» формування одиничного значення функцій заданої системи при певному одному або кількох наборах значень аргументів.
В нашому прикладі до ядра функції Z входять: 1) імпліканта , яка єдина з простих імплікант системи здатна забезпечити одиничне значення функції при наборі значень вхідних змінних (мінтерм ); 2) імпліканта - вона і тільки вона може забезпечити формування одиничного значення функції при наборі значень вхідних логічних змінних (мінтерм ); 3) - тільки вона може забезпечити значення при наборі значень змінних (мінтерм ); 4) - гарантує , якщо (мінтерм ). Окрім тих мінтермів функції Z, по відношенню до яких вони є ядром, імпліканти ядра покривають також і інші мінтерми функції Z (в Таблиці 2 всі мінтерми, що покриваються імплікантами ядра, відмічено в допоміжному рядку). Ті мінтерми, які жодною з імплікант ядра не покриваються (в Таблиці 2 відмічено знаком ?) необхідно покрити за допомогою інших імплікант функції Z. Тобто у випадку, коли ядро не покриває всіх мінтермів системи, до МДНФ крім ядра необхідно обов’язково включити мінімальний набір імплікант системи, який в сукупності покриває ті мінтерми, що не були покриті ядром. В нашому прикладі (див. Таблицю 2) імплікантами ядра не покрито три мінтерми - 1) мінтерм в другій функції системи (його можна покрити імплікантою , або імплікантою - дві позначки у відповідному стовпці Таблиці 2); 2) мінтерм в третій функції системи (покривається або імплікантою , або імплікантою ); 3) мінтерм в другій функції системи (покривається або імплікантою , або імплікантою ). Оскільки кожен із згаданих мінтермів покривається різними імплікантами, аналізуємо можливість оптимального покриття кожного мінтерма зокрема. Для покриття першого із згаданих мінтермів вигідно взяти імпліканту - вона є меншою від імпліканти і має менше ознак. Для покриття другого мінтерму беремо імпліканту , яка має менше ознак, ніж імпліканта . Для покриття третього мінтерму беремо імпліканту - вона простіша і має менше ознак, ніж імпліканта . Отже остаточно МДНФ функції Z набуде вигляду:
(17) Далі на основі (17) записуємо скорочену ДНФ заданої системи логічних функцій, розрізняючи імпліканти за ознаками належності до тої чи іншої функції (тобто у вираз для першої функції системи записуємо диз’юнкцію тих імплікант виразу (17), які містять одиницю в своїй ознаці; у вираз для другої функції - ті, що містять в своїй ознаці двійку; для третьої функції - імпліканти, ознака яких містить номер 3):
(18) І нарешті останній крок мінімізації -поглинання в межах функцій системи - в нашому прикладі в першій функції системи (див. (18)) імпліканта поглинає імпліканту . В інших функціях системи (18) варіантів поглинання немає. Отже остаточно МДНФ заданої системи логічних функцій набуде вигляду:
Рис.1
(19) На основі (19) будуємо комбінаційну схему на елементах І, АБО, НЕ (Рис.1). При цьому необхідно враховувати, що для реалізації однакових імплікант в різних функціях системи (в даному прикладі таких немає) достатньо одного логічного елемента.
Найпоширенішим методом сумісної мінімізації другої групи є метод каскадів (або метод декомпозиції). В основу цього методу покладено теорему про розклад логічної функції n змінних на логічні функції меншої кількості змінних. Суть полягає в тому, що будь-яку функцію можна зобразити як композицію функцій меншого числа змінних. Наприклад, цю функцію можна розкласти на функції змінної наступним чином:
(20) де - виділена змінна; , - вирази для залишкових функцій – одержуються з виразу для функції підстановкою значень відповідно і .
Виділеною змінною може бути довільна змінна . Процес виділення більш простих складових функцій називається декомпозицією. Він може виконуватись щодо новоутворених складових стільки разів, скільки потрібно для одержання простих виразів мінімального рангу, які легко синтезувати.
Декомпозиція зі сторони виконується таким чином:
(21) Розглянемо цей спосіб мінімізації на прикладі.
Приклад 2. Виконати сумісну мінімізацію за методом декомпозиції системи логічних функцій, заданої таблицею істинності (Таблиця 1). Побудувати комбінаційну схему для реалізації мінімізованої системи,використовуючи логічні елементи І,АБО,НЕ.
Розв’язання.
Перший крок при реалізації даного методу мінімізації, як і в попередньому випадку - запис кожної з функцій системи в ДДНФ (система (1)). Далі необхідно розкласти кожну з функцій системи (1) на функції двох змінних, а функції двох змінних в свою чергу - на функції однієї змінної. Тобто потрібно скористатися залежностями (21). Тут слід вказати на велику кількість варіантів такого розкладу при мінімізації систем логічних функцій (особливо якщо змінних багато). Тому при великій кількості змінних вибір оптимального варіанту - процес достатньо тривалий. В нашому прикладі є три змінні і ми обмежимося трьома варіантами розкладу (при збільшенні кількості змінних кількість варіантів розкладу росте швидше, ніж кількість змінних).
1-ий варіант - вилучаємо з функцій системи (1) змінну (тобто виносимо за дужки пряме та інверсне значення цієї змінної):
(22) З функцій, що в дужках, знову вилучаємо якусь змінну (в даному випадку не має значення яку) і спрощуємо їх, застосовуючи закони алгебри логіки:
(23) Підставивши (23) у (22), розкривши дужки і (якщо це вигідно) знову вилучивши змінні, отримаємо:
(24) 2-ий варіант - вилучаємо з функцій системи (1) змінну :
(25) Спрощуємо залишкові функції, застосовуючи закони алгебри логіки:
(26) Підставляємо (26) в (25) і розкриваємо дужки:
(27) 3-ій варіант - вилучаємо з функцій системи (1) змінну :
(28) Спрощуємо залишкові функції, застосовуючи закони алгебри логіки. Після цього отримаємо:
(29) Підставивши (29) у (28), розкривши дужки і (якщо це вигідно) знову вилучивши змінні, отримаємо:
(30) Отже, отримали три варіанти мінімізованих систем - (24), (27), (30). Наступний крок - пошук оптимальної системи. Причому при такому пошуку потрібно розглядати не тільки три згадані системи, алей інші, отримані шляхом перестановок відповідних рівнянь між цими трьома системами. Як критерій оптимальності виберемо мінімальні апаратні затрати. Після аналізу систем (24), (27), (30), а також інших систем, отриманих шляхом підміни кожного рівняння відповідними рівняннями з систем (24), (27), (30), виявимо, що однаково простими будуть системи (24), (27), а також всі інші системи, в яких комбінуються варіанти рівнянь з систем (24), (27), (30) і не використовується рівняння для з системи (30). З вказаної множини систем виберемо для реалізації систему (27) і на її основі побудуємо комбінаційну схему, використовуючи логічні елементи І, АБО, НЕ (Рис.2).
Зауваження: при оцінці складності системи необхідно враховувати не тільки загальну кількість входження всіх змінних в цю систему, але й кількість однакових кон’юнкцій в системі. Чим більше однакових кон’юнкцій, тим простішою буде схема.
Рис.2
2. ЗАВДАННЯ
2.1. Теоретична частина (виконується при підготовці до лабораторного заняття)
Ознайомитися з основними відомостями.
Визначити свій варіант системи логічних функції.
Для цього необхідно номер варіанта (задає викладач) перевести в двійкову систему числення і підставити шість розрядів отриманого двійкового числа в Таблицю 3 (1 - молодший розряд).
Мінімізувати задану Таблицею 3 систему логічних функцій за допомогою імплікантної таблиці і методом декомпозиції.
На основі отриманих в п.3 виразів побудувати дві комбінаційні схеми для реалізації заданої системи логічних функцій, використовуючи елементи І, АБО, НЕ.
Побудувати комбінаційну схему для реалізації заданої системи логічних функцій на дешифраторі.
Порівняти за складністю комбінаційні схеми, отримані в п.4 і в п.5.
2.2. Експериментальна частина
Всі три синтезовані комбінаційні схеми реалізувати за допомогою схемного редактора САПР Foundation Series.
Проконтролювати правильність функціонування синтезованих схем за допомогою моделювальника САПР, визначивши значення вихідних сигналів для всіх наборів значень вхідних змінних.
Замалювати часові діаграми роботи схем.
Зміст звіту
Назва і мета роботи.
Всі матеріали, що стосуються синтезу комбінаційних схем у відповідності з теоретичною частиною завдання.
Часові діаграми роботи комбінаційних схем, що досліджувалися в лабораторії.
Короткі висновки за результатами роботи.
Література:
Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ. Теория и проектирование. - К.: Вища шк., 1989.
Б.Є.Рицар. Цифрова техніка. - К.: НМК ВО, 1991.
Таблиця 3
№ набору
0
0
0
0
0
0
1
0
0
1
0
1
2
0
1
0
1
0
3
0
1
1
0
4
1
0
0
1
0
5
1
0
1
1
6
1
1
0
0
0
7
1
1
1
1
1
1
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора