Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Захисту інформації
Кафедра:
Не вказано
Інформація про роботу
Рік:
2015
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Схемотехніка
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОДИ АНАЛІЗУ ТА СИНТЕЗУ КОМБІНАЦІЙНИХ СХЕМ.
МІНІМІЗАЦІЯ МЕТОДОМ КВАЙНА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 3
з курсу «Схемотехніка пристроїв технічного захисту інформації»
для студентів базового напряму 6.170102 «Системи технічного захисту інформації»
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № 12 від 07.05.2015р.
Львів – 2015
Мета роботи: вивчення методу Квайна мінімізації логічних функцій.
1. ОСНОВНІ ВІДОМОСТІ
Метод Квайна мінімізації логічних функцій [1] може бути коротко описаний наступним алгоритмом:
Записати задану логічну функцію n змінних в досконалій диз’юнктивній нормальній формі (ДДНФ), тобто як диз’юнкцію мінтермів (елементарних кон’юнкцій n – ого рангу), які відповідають всім одиничним значенням заданої функції.
Здійснити всі можливі склеювання мінтермів ДДНФ заданої функції. Результатами склеювання будуть кон’юнкції-імпліканти (n-1) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію імплікант і тих мінтермів, які не мали пари для склеювання.
Здійснити всі можливі склеювання імплікант (n-1) -ого рангу. Результатами склеювання будуть кон’юнкції-імпліканти (n-2) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію отриманих імплікант (n-2) -ого рангу, мінтермів і імплікант (n-1) -ого рангу, які не мали пари для склеювання. Повторювати пункт 3, поки у функції Z будуть існувати імпліканти, які можна склеїти.
Всі імпліканти функції Z, отриманої в пункті 3, є простими, тобто не мають пари для склеювання. Для такої функції Z – скороченої форми заданої логічної функції - побудувати імплікантну таблицю Квайна. Стовпці таблиці відповідають мінтермам заданої логічної функції, а рядки – простим імплікантам функції Z.
Таблиця 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
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
За допомогою імплікантної таблиці Квайна визначити тупикові і мінімальні форми заданої логічної функції.
Розглянемо реалізацію описаного алгоритму на прикладі.
Приклад. Виконати мінімізацію методом Квайна логічної функції, заданої таблицею істинності (Таблиця 1). Побудувати комбінаційну схему для реалізації мінімізованої функції, використовуючи елементи І, АБО, НЕ.
Розв’язання.
1. Перший крок при реалізації даного методу мінімізації - запис заданої функції в ДДНФ, тобто у вигляді диз’юнкції мінтермів, що відповідають одиничним значенням логічної функції. Отже, спираючись на Таблицю 1, записуємо ДДНФ заданої логічної функції. При цьому мінтерми ДДНФ нумеруємо:
(1) Далі переходимо до знаходження простих імплікант за Квайном.
Знаходження простих імплікант за Квайном зводиться до пошуку пар мінтермів та імплікант, що склеюються між собою. Для нашого прикладу цей процес буде виглядати так:
1-ий етап: на цьому етапі здійснюємо всі можливі склеювання мінтермів функції (1). Для цього перебираємо всі можливі пари мінтермів у функції (1):
не склеюються
не склеюються,
: :
Отже, ми виконали всі можливі склеювання мінтермів. Аналізуючи результати склеювання робимо висновок, що з восьми мінтермів функції (1) тільки п’ятий не мав пари для склеювання. На основі результатів склеювання записуємо новий варіант функції Z. Для цього спочатку записуємо диз’юнкцію імплікант, отриманих при склеюванні (в даному випадку імпліканти - це кон’юнкції трьох змінних). При цьому не допускаємо повторення однакових імплікант. Далі дописуємо диз’юнкцію мінтермів, що не мали пари для склеювання (в даному прикладі – п’ятий мінтерм функції (1)). Імпліканти нумеруємо. Отримаємо вираз (2).
(2)
Далі перевіряємо всі імпліканти 3-го рангу з виразу (2) на можливість склеювання. В даному прикладі жодна імпліканта з (2) не має пари для склеювання. Тобто всі кон’юнкції виразу (2) є простими імплікантами. Тому переходимо до складання імплікантної таблиці Квайна.
2-ий етап:
Будуємо імплікантну таблицю функції Z (Таблиця 2). В таблиці відводимо по одному рядку на кожну просту імпліканту з (2). Кожен стовпець імплікантної таблиці відповідає мінтерму з ДДНФ (1).
Таблиця 2
Прості
Мінтерми функції Z
імпліканти
я
X
X
я
X
X
X
X
X
X
я
X
X
я
X
X
я
X
X
X
?
X
X
X
X
X
Імплікантну таблицю заповнюємо в такій послідовності:
відображаємо факт покриття простими імплікантами функції Z тих чи інших мінтермів. Для цього в кожному рядку таблиці ставимо позначки на перетині з стовпцями, що відповідають таким мінтермам, які імпліканта даного рядка здатна поглинути. Наприклад, імпліканта здатна поглинути два з восьми мінтермів (а саме і ).
аналізуємо всі стовпці імплікантної таблиці - всі позначки, які є єдиними в стовпці, виділяємо (в Таблиці 2 виділено контурною позначкою). Наявність єдиної позначки в стовпці означає, що тільки одна імпліканта з множини простих імплікант здатна забезпечити наявність тієї одиниці з таблиці істинності, якій відповідає даний стовпець (мінтерм).
аналізуємо всі рядки імплікантної таблиці - ті рядки, які містять хоча б одну виділену позначку, в свою чергу виділяємо (в Таблиці 2 виділено буквою я). Одночасно в останній (допоміжний) рядок виносимо всі позначки, які містяться у виділених рядках. Після цього визначаємо ті клітинки допоміжного рядка, в яких позначок немає (в Таблиці 2 єдину таку клітинку позначено знаком ?).
На основі імплікантної таблиці записуємо мінімальну ДНФ (МДНФ) функції Z. В МДНФ обов’язково входить ядро функції - диз’юнкція відмічених в імплікантній таблиці (буквою я) простих імплікант. Адже, як вже було сказано, кожна з таких імплікант є єдиним можливим «джерелом» формування одиничного значення заданої функцій при певному одному або кількох наборах значень аргументів.
В нашому прикладі імпліканти ядра функції Z покривають всі мінтерми крім одного - . В цьому випадку, а загалом у всіх випадках, коли ядро не покриває всіх мінтермів функції до МДНФ крім ядра необхідно обов’язково включити мінімальний набір імплікант системи, який в сукупності покриває ті мінтерми, що не були покриті ядром. В нашому прикладі (див. Таблицю 2) для покриття мінтерму можна вибрати будь-яку з двох простих імплікант - або . Отже остаточно МДНФ функції Z набуде вигляду:
(3) На основі (3) будуємо комбінаційну схему на елементах І, АБО, НЕ (Рис.1).
Рис.1.
2. ЗАВДАННЯ
2.1. Теоретична частина (виконується при підготовці до лабораторного заняття)
Ознайомитися з основними відомостями.
Визначити свій варіант логічної функції.
Для цього необхідно номер варіанта (задає викладач) перевести в двійкову систему числення і підставити шість розрядів отриманого двійкового числа в Таблицю 3 (1 - молодший розряд).
Мінімізувати задану Таблицею 3 логічну функцію методом Квайна.
На основі МДНФ заданої логічної функції побудувати комбінаційну схему на елементах І, АБО, НЕ.
Таблиця 3
№ набору
0
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
0
3
0
0
1
1
1
4
0
1
0
0
5
0
1
0
1
1
6
0
1
1
0
0
7
0
1
1
1
8
1
0
0
0
0
9
1
0
0
1
10
1
0
1
0
1
11
1
0
1
1
1
12
1
1
0
0
13
1
1
0
1
1
14
1
1
1
0
15
1
1
1
1
0
2.2. Експериментальна частина
Синтезовану в пункті 2.1 комбінаційну схему реалізувати за допомогою схемного редактора САПР Foundation Series.
Проконтролювати правильність функціонування синтезованої схеми за допомогою моделювальника САПР, визначивши значення вихідного сигналу для всіх наборів значень вхідних змінних.
Замалювати часові діаграми роботи схем.
Зміст звіту
Назва і мета роботи.
Всі матеріали, що стосуються синтезу комбінаційної схеми у відповідності з теоретичною частиною завдання.
Часові діаграми роботи комбінаційної схеми, що досліджувалися в лабораторії.
Короткі висновки за результатами роботи.
Література:
Максимович В.М. Електроніка та мікросхемотехніка. Конспект лекцій.
Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ. Теория и проектирование. - К.: Вища шк., 1989.
Б.Є.Рицар. Цифрова техніка. - К.: НМК ВО, 1991.
04.12.2018 14:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора