Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Черкаський державний технологічний університет

Кафедра комп'ютерних систем

КУРСОВА РОБОТА

з дисципліни „Комп'ютерна логіка”

на тему „ Аналіз та синтез комбінаційних схем”

Студента 2 курсу CП-126 групи

напряму підготовки комп'ютерна інженерія

спеціальності системне програмування

Паливоди Євгенія Вікторовича

Керівник Шувалова Л.А

м. Черкаси 2013

Вступ

Тема: Мінімізація перемикальних функцій різними методами та синтез комбінаційних схем.

Мета роботи: Метою курсової роботи є одержання навичок побудови комбінаційних схем в програмі AFDK, що реалізують перемикальні функції в заданому елементному базисі, та реалізацію перемикальних функції з мінімальною складністю.



1. Завдання 1

Короткі теоретичні відомості:

Вихідною формою подання перемикальної функції для виконання мінімізації за методом Квайна є ДДНФ.

Метод Квайна базується на використанні співвідношення неповного склеювання

(A1-2.1)

і співвідношення поглинання

(А1-2.2)

де А,В,С - довільні кон'юнктивні терми;

х - змінна.

Завдання мінімізації методом Квайна складається з находженням СДНФ з використанням співвідношень неповного склеювання і поглинання. Далі за допомогою таблиці покриття, яка дозволяє позбавитися надлишкових простих імплікант, отримують ядро функції (якщо воно є), потім знаходять ТДНФ і обирають з них МДНФ.

Під ядром функції розуміють сукупність імплікант, які неможливо вилучити із СДНФ. Такі імпліканти покривають деякі конституанти тільки самостійно.

Виконання мінімізації перемикальної функції здійснюється за такими етапами.

1. Записати перемикальну функцію у вихідній формі, якою є ДДНФ.

2. Застосувати співвідношення неповного склеювання (А1-2.1) послідовно до конституент одиниці, потім до імплікант (n - 1)-го рангу, (n - 2)-го рангу і так далі, поки формування нових імплікант можливе.

3. Виконати всі можливі поглинання, використовуючи співвідношення (А1-2.2), в результаті чого визначаються всі прості імпліканти, які складають СДНФ.

4. Побудувати таблицю покриття (імплікантну матрицю) для подальшого спрощення запису функції.

5. Визначити ядро перемикальної функції та всі ТДНФ. З числа отриманих ТДНФ вибрати МДНФ.

Виконання завдання:

Реалізувати перемикальну функцію у в базисі елементів І-НЕ з мінімальною складністю за Квайном.

0)

Х3	Х2	Х1	F1
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Виконаємо склеювання:

=

=



Виконуємо поглинання:

Таблиця покриття:

				X
	X	X
		X	X
		X			X

Всі чотири імпліканти самостійно покривають всі конституанти, тобто вони є ядром функції.

Тому МДНФ :

Реалізувати перемикальну функцію у в базисі елементів І-НЕ:

Комбінаційна схема, дивись додаток А.



2. Завдання 2

Короткі теоретичні відомості:

Алгебра Буля

Алгебра визначена на n ? 2 змінних. Для перетворення аргументів в алгебрі Буля використовуються функції І, АБО та НЕ. Система перемикальних функцій відповідно має вигляд

Аксіоми алгебри Буля:

Алгебра Шефера

Алгебра Шефера визначена на n ? 2 елементах і містить тільки одну функцію І-НЕ (функцію Шефера), яку в n-містному варіанті можна записати у вигляді



Аксіоми алгебри Шефера

Алгебра Пірса

Алгебра Пірса визначена на п? 2 елементах і містить тільки одну функцію АБО-НЕ (функцію Пірса або Веба)_; яку в n-містному варіанті можна записати у вигляді

Основні аксіоми алгебри Пірса:

Виконання завдання:

Подати в нормальних формах алгебр Пірса, Шеффера перемикальну функцію, що задана ДДНФ

0)

Х3	Х2	Х1	F1
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Алгебра Буля:

Алгебра Шефера:

Алгебра Пірса:

3. Завдання 3

Короткі теоретичні відомості:

Діаграми Вейча і карти Карно для перемикальної функції двох, трьох і чотирьох аргументів відповідно зображені на рис. А1-2.2, а,б. Усередині клітинок вказані номери наборів.

Графічні методи призначені для ручної мінімізації. Наочність цих методів зберігається за невеликої кількості аргументів. При цьому відшукання імплікант не формалізоване, і успіх мінімізації цілком визначається кваліфікацією оператора.

Кожна клітинка відповідає конституенті. Прямокутник, що містить 2^K клітинок , відповідає імпліканти. Прямокутник максимального розміру відповідає простій імплікант.

Обґрунтуванням графічного методу мінімізації є той факт, що розташовані поруч клітинки відповідають сусіднім наборам аргументів, що відрізняються значенням однієї змінної і, таким чином, можуть бути склеєні за методом Квайна (А1-2.1). За n перемінних кожна клітинка має n сусідніх клітинок.

Чим більше клітинок містить прямокутник, тим менше букв входить у записні імпліканти. Імпліканта містить тільки ті змінні, котрі приймають однакові значення для всіх клітинок прямокутника.

Наведемо етапи мінімізації перемикальних функцій графічним методом.

1. Заповнити діаграму Вейча або карти Карно. Значення функцій записують у клітинки, що відповідають номерам наборів.

2. Виконати об'єднання одиниць в прямокутники з максимально можливої кількістю клітинок (число клітинок, що можуть поєднуватися, має дорівнювати ). При цьому кожна одиниця повинна входити як мінімум в один прямокутник. Прямокутник може містити й одну клітинку.

3. Визначити МДНФ. Сукупності простих імплікант, що входять у МДНФ, відповідає мінімальна множина прямокутників, що покривають усі одиниці.

Виконання завдання:

За допомогою діаграм Вейча отримати МДНФ функції, що задана ДДНФ

0)

х4	х3	х2	х1	F1
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1



Мінімізована перемикальна функція:

Комбінаційна схема, дивись додаток Б.

4. Завдання 4

За допомогою діаграм Вейча отримати заперечення МДНФ функції, що задана ДДНФ

0)

х4	х3	х2	х1	F1
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Комбінаційна схема, дивись додаток В.

5. Завдання 5

Короткі теоретичні відомості:

У формі ДДНФ і ДКНФ задана перемикальна функція має відповідно вигляд:



Виходячи із ДДНФ з урахуванням аксіоми =х (див. розділ А1-1.4) та правила де Моргана (А 1-1.2) одержимо перші чотири нормальні форми:

На базі ДКНФ аналогічним чином отримаємо ще чотири нормальні форми:

Останні чотири форми можна аналогічно одержати виходячи із заперечення перемикальної функції, що відповідає формі І/АБО-НЕ.

Виконання завдання:

Отримати операторні форми для реалізації перемикальної функції, поданої у ДДНФ, у заданому елементному базисі з мінімальною складністю



0)

Реалізувати перемикальну функцію у заданому елементному базисі

0) 2АБО-НЕ.

х4	х3	х2	х1	F1
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1



Отримання нормальних форм з заперечення МДНФ:

Операторні форми для реалізації функції в базисі 2АБО-НЕ:

Комбінаційна схема, дивись додаток Г.

6. Завдання 6

Короткі теоретичні відомості:

Метод Петрика використовується для знаходження можливих покриттів перемикальної функції з таблиці покриття, яка одержана будь-яким методом знаходження СДНФ. Метод Петрика дозволяє формалізувати процес знаходження мінімального покриття функції.

Сутність методу полягає в такому. Таблицю покриття функції подають у вигляді логічного виразу, спрощення якого приводить до визначення всіх можливих множин імплікант, що покривають функцію.

Будемо вважати, що, наприклад, за допомогою метода Квайна, одержана таблиця покриття, заголовками рядків якої є прості імплікант, а заголовками стовпців - конституанти одиниці заданої функції.

Можна запропонувати такі етапи реалізації методу.

1. Для зручності перетворення логічних виразів усі прості імпліканти, що входять у СДНФ, позначаються довільними символами (зазвичай прописними латинськими літерами).

2.Для кожного і-го стовпця таблиці покриття будується умова покриття відповідної конституаенти у вигляді диз'юнкції всіх імплікант, що покривають цю конституенту.

3. Записується умова покриття всієї функції, яка представляє собою кон'юнкцію одержаних в п.2 диз'юнкцію всіх імплікант, що покривають цю конституенту.

4. Одержаний логічний вираз приводиться до бездужкової форми. Після спрощення виразу та виконання всіх можливих поглинань формується диз'юнкція кон'юнкцій. Кожна кон'юнкція в одержаній формі відповідає множині простих імплікант, що покривають функцію, тобто ТДНФ. Виході з одержаних тупікових форм обирають МДНФ функції.

Виконання завдання:

Методом Петрика отримати МДНФ перемикальної функції , якщо СДНФ заданої функції містить імпліканти (імпліканти задані номерами наборів термів, що склеювались):

0) 13, 23, 26, 15, 45, 46

Х3	Х2	Х1	F1
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Склеюємо конституенти:



A		X		X
B			X	X
C			X				X
D		X				X
I					X	X
E					X		X

=

Можливі покриття функції:



Мінімізована функція:

7. Завдання 7

перемикальний функція операторний елементний

Короткі теоретичні відомості:

За спільної системи мінімізації декількох перемикальних функцій необхідно враховувати можливе дублювання однакових елементів з однаковими логічними сигналами на входах під час побудови комбінаційної схеми, що приводить до її ускладнення.

Розглянемо мінімізацію систем функцій у диз'юнктивних нормальних формах булевої алгебри. Для усунення повторення однакових елементів у схемі на етапі мінімізації системи функцій необхідно виявити однакові імпліканти у запису різних функцій.

Для мінімізації можуть бути використані різні методи, зокрема, методи Квайна і Квайна - Мак-Класкі.

Вихідною формою для мінімізації системи функцій методом Квайна та Квайна - Мак-Класкі є ДДНФ системи перемикальних функцій, для отримання якої необхідно подати в ДДНФ кожну функцію. При цьому кожній конституенті одиниці приписується множина міток, що визначають іі приналежність до певної функцій.

Наведемо етапи мінімізації системи перемикальних функцій:

1. Записати ДДНФ системи перемикальних функцій.

2. Виконати склеювання термів.

3. Виконати всі можливі поглинання.

4. Скласти таблицю покриття.

5. Вибрати покриття для кожної функції.

Відмінності мінімізація систем перемикальних функцій від мінімізації окремих функцій полягають у такому.

Склеювання здійснюються тільки для тих термів, що мають хоча б одну однакову мітку. Отриманому в результаті склеювання терму присвоюється множина міток, що є перетинами множин міток термів, які склеювались.

Поглинання одного терму іншим здійснюється тільки в тому випадку, коли множині міток двох термів цілком збігаються.

Під час вибору остаточної форми подання перемикальної функції з використанням таблиці покриттів необхідно прагнути до того, щоб загальне число букв у покритті було мінімальним.

Виконання завдання:

Виконати спільну мінімізацію системи перемикальних функцій

Метод мінімізації обрати самостійно.

0)

Х3	Х2	Х1	F1	F2	F3
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	1	0	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	1	1	1



F1

F2

F3

010

011

100

101

111

000

010

100

101

111

000

010

011

100

101

111

0X0{2,3}

X

X

X

X

X00{2,3}

X

X

X

X

01X{1,3}

X

X

X

X

X11{1,3}

X

X

X

X

10X{1,2,3}

X

X

X

X

X

X

1X1{1,2,3}

X

X

X

X

X

X

Комбінаційна схема, дивись додаток Д.



Висновок

Виконавши курсову роботу я виконав всі поставленні завдання згідно з варіантом.

Опрацювавши теоретичний матеріал і розібравшись з поняттями, я узагальнив знання, які зв'язані з знаходженням доконаних форм, пошуком мінімальних форм перемикальних функцій та їх реалізації в певному базисі. Також я закріпив навички по роботі з програмою AFDK, яка моделює процес роботи схеми використовуючи логічні елементи, та побудовою комбінаційних схем в даній програмі використовуючи елементи які знаходяться в стандартній бібліотеці. Основною проблемою при виконанні курсової роботи було побудова комбінаційних схем мінімізованої функції яка реалізована на чотирьох змінних, тому що після мінімізації функція була реалізована на двох змінних і це викликало проблему з створенням таблиці істинності на чотири змінних в програмі AFDK. Курсова робота була виконана у повному обсязі.



Додатки

Додаток А

Складність за Квайном K=16



Додаток Б

Складність за Квайном K=16



Додаток В

Складність за Квайном K=8



Додаток Г

Складність за Квайном K=8



Додаток Д

Складність за Квайном K=26



Використанна література

1. Самофалов К. Г., Романкевич А. М., Валуйский В. Н. и др. // Прикладная теория цифровых автоматов. - Киев: Вища школа, 1987. - 370с.

2. Грей П. Логика, алгебра и базы даннях // Пер.с англ. Х. И. Килова, Г. Е. Минца. -М. : Машиностроение, 1989. - 368 с.

3. Клини С. К. Математическая логика // М. : Мир, 1973. - 480 с.

4. Мендельсон Є. Введение в математическую логику // Пер. с англ. Ф. А. Кабакова. - 2-е изд., испр. - М. : Мир, 1985. - 307 с.

5. Новиков П. С. Элементы математической логики // М. : Наука, 1973. - 399 с.

6. Курейчик В. М. Математическое обеспечение конструкторського и технологического проектирования с применением САПР // М. : Радио и связь, 1990. - 352 с.

7. Акимов О. Е. Дискретная математика // Логика, группы, графы. - 2-е изд., доп.. - М. : Лаборатория Базових Знаний, 2001. - 376 с.

8. Луцький Г. М., Кривий С.Л., Печурін М.К. Основи дискретної математики // Навч. посібник. - К. : ІСДО, 1995, - 252 с.

Размещено на Allbest.ru

...