Мінімізація функції методами Квайна–Мак–Класки та діаграм Вейча

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

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

1. Вступ

Дана курсова робота виконана по номеру технічного завдання 830018510 = 111,1110,1010,0110,1001,10012 і складається з двох головних частин: синтез комбінаційних схем та синтез автомата.

2. Синтез комбінаційних схем

2.1 Представлення функції f4 в канонічних формах алгебр Буля, Пірса, Шефера та Жегалкіна

Запишемо доконану диз'юнктивну нормальну форму (ДДНФ) та доконану кон'юктивну нормальну форму (ДКНФ) для функції f4 = Y:

Ці форми водночас є канонічними формами алгебри Буля, відповідно І/АБО та АБО/І.

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

Отримаємо форму АБО-НЕ/АБО-НЕ:

Замінивши АБО-НЕ “стрілкою Пірса”, отримаємо остаточно:



Канонічну форму алгебри Шефера отримаємо з ДДНФ шляхом подвійного заперечення та розкриттям нижнього з них за правилом Де-Моргана. Отримаємо форму І-НЕ/І-НЕ:

Замінивши І-НЕ на знак “/”, отримаємо:

Y = ((X4/X4)/(X3/X3)(X2/X2)/X1)/((X4/X4)/(X3/X3)/X2/X1)/

((X4/X4)/X3/(X2/X2)/X1)/(X4/(X3/X3)/(X2/X2)/X1)/ (X4/(X3/X3)/X2/(X1/X1))/(X4/X3/(X2/X2)/(X1/X1))/(X4/X3/X2/(X1/X1))/

(X4/X3/X2/X1)

Канонічну форму алгебри Жегалкіна можна отримати із ДДНФ наступним чином: зовнішню операцію АБО замінюємо на виключне АБО, аргументи із запереченням замінюємо на суму з одиницею, розкриваємо дужки та викреслюємо попарно однакові члени. Маємо:



2.2 Приналежність функції f4 п'ятьом передповним класам

Визначимо приналежність функції f4 п'ятьом передповним класам. Вона належить до класу функцій, зберігаючих нуль: f4 (0, 0, 0, 0) = 0. Аналогічно, вона входить до класу функцій, зберігаючих одиницю: f4 (1, 1, 1, 1) = 1.

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

F4	K0	K1	Kc	Км	Кл
	+	+	-	-	-

2.3 Мінімізація функції f4 методом Квайна

Складемо таблицю покриття (табл. 2.1).

Табл. 2.1

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

		+	+
				+		+

Отже мінімізована функція має вигляд:

YМДНФ =

б)Мінімізація заперечення функції f4 методом Квайна - Мак-Класки:

0000 00X0 1ХХ1

0010 0X00

1000 X000

0100 0X10

0110 01X0

0111 011X

1011

1101

Складемо таблицю покриття( таблиця 2.2)

Табл.2.2

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

	1011	1101	Х000	011Х	0ХХ0
0000					+
0010
0100
1000
0110					+
0111
1011
1101

YМКНФ =

2.4 Мінімізація функції f4 методом діаграм Вейча:

Запишемо значення функції f4 у діаграму Вейча (таблиця 2.3) та об'єднаємо одиниці в прямокутники по 2n клітинок.



Отже, ми отримали таку ж саму форму, як і при мінімізації першим методом: YМДНФ =

Логічна схема функції Y мднф, зображена на риснку 2.1.

Рис.2.1 Логічна схема

Складність схеми за Квайном становить: К=64.

2.6 Мінімізація заперечення функції f4 методом діаграм Вейча

Запишемо значення функції f4 у діаграму Вейча (таблиця 2.6) та об'єднаємо одиниці в прямокутники по 2n клітинок:



Отже, ми отримали таку ж саму форму, як і при мінімізації першим методом:

YМКНФ =

Логічна схема що реалізує функцію Умднф, зображена на рисунку 2.2.

Рис. 2.2 - Логічна схема

Складність схеми за Квайном: К=36.

2.7 Спільна мінімізація функцій f1, f2, f3 методом Квайна - Мак- Класки:

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

0000(1,2,3) X000(1,2) X1X0(3)

0001(1,2) X100(1,3) X11X(3)

0010(1,2,3) X110(3) 0XX0(1,3)

0100(1,3) X111(1,2,3)

1000(1,2) 0X00(1,3)

0110(1,2,3) 0X10(1,2,3)

1001(3) 1X00(1,2)

1100(1,2,3) 1X11(1)

0111(1,2,3) 00X0(1,2,3)

1011(1) 01X0(1,3)

1101(2) 11X1(2)

1110(3) 000X(1,2)

1111(1,2,3) 011X(1,2,3)

110X(2)

111X(3)

Будуємо таблицю покриття для трьох функцій (таблиця 2.7), визначаємо ядро функції (імпліканти, без яких мінімальна форма неможлива):

Табл. 2.7

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

Отже шукана МДНФ системи функцій:

2.8 Спільна мінімізація системи функцій f1,f2,f3 методом Квайна-Мак-Класки по нулям

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

0001(3) X100(2)

0100(1,2) X011(2,3)

1000(3) X101(1,3)

0011(1,2,3) 0X01(3)

0101(1,2,3) 0X11(1,2)

0110(2,3) 1X10(1,2)

1001(1,2) 00X1(3)

1010(1,2,3) 10X0(3)

1100(2) 01X1(1,2)

0111(1,2) 11X0(2)

1011(2,3) 010X(1,2)

1101(1,3) 101X(2,3)

1110(1,2)

Будуємо таблицю покриття для трьох функцій (таблиця 2.7), визначаємо ядро функції (імпліканти, без яких мінімальна форма неможлива)

Табл.2.7

Таблиця покриття трьох функцій

Отже шукана МКНФ системи функцій:

2.9 Вісім нормальних форм системи функцій:

Перші чотири форми отримаємо з ДДНФ функцій:

(І/АБО)

(І-НЕ/І-НЕ)

(АБО/І-НЕ)

(АБО-НЕ/АБО)

Наступні чотири форми отримаємо з ДКНФ функцій:

(АБО/І)

(І/АБО-НЕ )

2.10 Комбінаційні схеми системи перемикальних функцій

Будуємо схеми системи перемикальних функцій, які показані на рисунку 2.3 та рисунку 2.4.



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

Складність схеми за Квайном: К=40.



Рис. 2.4 - Комбінаційна схема системи перемикальних функцій в базисі АБО/І-НЕ

Складність схеми за Квайном: К=40.

3. Синтез автомата

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

3.1 Спрощена операційна схема

Операційна схема буде складатися з двох регістрів суматора та лічильника СТ. При реалізації функції збільшується розрядність регістрів RG1, RG2 і суматора SM. Описана операційна схема зображена на рисунку 3.1.

Операційна схема автомата

Рис. 3.1 - Операційна схема автомата

3.2 Змістовний мікроалгогритм

В мікроалгоритмі вкажемо початкові умови: У вихідному стані в регістрах RG1 і RG2 та лічильнику СТ знаходяться відповідно операнди А,С та В.Для реалізації операнду С на два необхідно виконати мікрооперацію зсуву вмісту регістру RG2 вліво. До СТ додаємо одиницю. RG2 залишаємо без зміни. На етапі обчислення функції у циклі до RG2 додається вміст регістру RG1. Після чого зменшується на одиницю вміст лічильника СТ. Результат обчислення функції формується в регістрі RG2. Змістовний мікроалгоритм зображений у вигляді блок-схеми на рисунку 3.2.

Блок-схема змістовного мікроалгоритму

Рис. 3.2. Блок-схема змістовного мікроалгоритму

3.3 Цифрова діаграма стану регістрів

Нехай в початковому стані (ПС) А=110=0001, В=410=0011, а С =110=0001. В першому стані значення RG1 зсуваємо вліво на один розряд, а до значення СТ залишаємо без зміни. З кожним наступним станом до числа з RG2 додаємо число з RG1 і зменшуємо на 1 значення СТ. Повторюємо дані операції поки СТ<>0.

Результат всіх операцій заносимо в таблицю 3.1.

Табл. 3.1

Цифрова діаграма стану регістрів

№ такту
ПС	0001	0001	0011
Зсув, збільшення CT на одиницю	0010	0001	0011+0001=0100
1	0010	0001 +0010 0011	0100
2	0010	0011 +0010 0101	0011
3	0010	0101 +0010 0111	0010
4	0010	1111 +0010 1001	0001

Перевірка: D=1+ 2*1*(3+1)= 9

1001(2)=10+01+02+23=1+8=9

3.4 Функціональна схема

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



Рис. 3.3 - Функціональна схема

3.5 Розробка закодованого мікроалгоритму

Змінимо блок-схему, вказавши керуючі сигнали зобразимо це на рисунку 3.4.

Рис. 3.4 - Змістовний мікроалгоритм

Кодування мікрооперацій та логічних умов занесемо відповідно до до таблиці 3.2 та таблиці 3.3.

Табл. 3.2

Таблиця кодування мікрооперацій

Табл.3.3

Таблиця кодування логічних умов

функція мікроалгоритм алгебра пірс

Виконаємо розмітку станів мікроалгоритму автомата Мілі.,

.

Рис. 3.5 - Закодована графічна схема та розмітка станів автомата

3.6 Складання графа автомата

Щоб зобразити переходи з одного стану автомата в інший використовують, т.з. граф автомата. Кожен стан кодується своїм кодом. Граф автомата зображений на рисунку 3.6.

Рис.3.6 - Граф автомата

3.7 Структурна таблиця автомата

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

Табл. 3.4

Таблиця станів автомата Мілі

Одержання МДНФ функцій збудження тригерів і керуючих сигналів

Мінімізуємо вихідні сигнали та функції тригерів методом діаграм Вейча:



В результаті мінімізації отримали такі функції:

3.8 Побудова електричної функціональної схеми автомата

Електрична функціональна схема автомату наведена в розділі “Керуючий автомат. Схема електрична функціональна”.

4.Висновок

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

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

Перемикальні функції f1, f2, f3 були спільно мінімізовані з використанням диз'юнктивної та кон'юнктивної нормальних форм Квайна - Мак - Класки. На основі чого були побудовані комбінаційні схеми з найменшою складністю і з врахуванням відповідної елементарної бази.

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

5. Список використаної літератури

1. Жабін В. І., Клименко І. А., Ткаченко В. В. “Прикладна теорія цифрових автоматів. Методичні вказівки до виконання курсової роботи для студентів спеціальності 8.091501 “Комп'ютерні системи та мережі””, -- К.: НАУ, 2004.

2. Жабін В. І., Ткаченко В. В. “Цифрові автомати. Практикум”,-- К.: ВЕК +, 2004.

3. Жабін В.І., Жуков І.А., Клименко І.А., Ткаченко В.В. “Прикладна теорія цифрових автоматів: Навч. посібник. ”,-- К.: НАУ, 2007.

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