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

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

 

1.1 Визначення значень БФ

 

Булева функція 5 змінних F(x1,x2,x3,x4,x5) задається своїми значеннями, які  визначаються 7-разрядовими двійковими еквівалентами чисел: по значенню чисел А (на наборах 0-6), В (на наборах 7-13), С (набори 14-20), по значенню (А+В+С) (набори 21-27) і на наборах 28-31 функції приймає невизначені значення.

А= 1011000;

В= X101000;

С= XXXXXXX;

(А+В+С) = XX11001;

Відповідно, значення функцій F(x1,x2,x3,x4,x5) на наборах від 0 до 31 буде мати вигляд:

Таблиця 1

Х1	Х2	Х3	Х4	Х5	F
0	0	0	0	0	1
0	0	0	0	1	0
0	0	0	1	0	1
0	0	0	1	1	1
0	0	1	0	0	0
0	0	1	0	1	0
0	0	1	1	0	0
0	0	1	1	1	X
0	1	0	0	0	1
0	1	0	0	1	0
0	1	0	1	0	1
0	1	0	1	1	0
0	1	1	0	0	0
0	1	1	0	1	0
0	1	1	1	0	X
0	1	1	1	1	X
1	0	0	0	0	X
1	0	0	0	1	X
1	0	0	1	0	X
1	0	0	1	1	X
1	0	1	0	0	X
1	0	1	0	1	X
1	0	1	1	0	X
1	0	1	1	1	1
1	1	0	0	0	1
1	1	0	0	1	0
1	1	0	1	0	0
1	1	0	1	1	1
1	1	1	0	0	X
1	1	1	0	1	Х
1	1	1	1	0	Х
1	1	1	1	1	Х

1.2 Мінімізація БФ (Карти Карно)

 

Отримуємо МДНФ і МКНФ булевой функції  за допомогою метода карт Карно. Схеми карт Карно приведені нижче:

 

Таблиця 2 – Карта Карно для МДНФ

	000	001	011	010	110	111	101	100
00	1		1	1		X
01	1			1	X	X
11	1		1		X	X	X	X
10	X	X	X	X	X	1	X	X

 

В результаті мінімізації, отримаємо: Y=|x3|x4|x5+x1x4x5+|x2|x3x4+|x1|x3x4|x5

 

Таблиця 3 – Карта Карно для МКНФ

	000	001	011	010	110	111	101	100
00		0			0	X	0	0
01		0	0		X	X	0	0
11		0		0	X	X	X	X
10	X	X	X	X	X		X	X

В результаті мінімізації, отримаємо: Y=(x4+|x5)(x1+|x3)(x1+|x2+|x5)(|x1+|)

 

1.3 Мінімізація БФ (Квайна-МакКласки)

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

 

Спочатку знайдемо МДНФ. Комплекси кубів та їх склеювання.

C₀:

00000 ü

00010 ü

00011 ü

00111 ü

01000 ü

01010 ü

01110 ü

01111 ü

10000 ü

10001 ü

10010 ü

10011 ü

10100 ü

10101 ü

10110 ü

10111 ü

11000 ü

11011 ü

11100 ü

11101 ü

11110 ü

11111 ü

C_1:

000X0 ü

0X000 ü

X0000 ü

0001X ü

0X010 ü

X0010 ü

010X0 ü

X1000 ü

1000X ü

100X0 ü

10X00 ü

1X000 ü

00X11 ü

X0011 ü

01X10

100X1 ü

10X01 ü

1001X ü

10X10 ü

1010X ü

101X0 ü

1X100 ü

11X00 ü

0X111 ü

X0111 ü

0111X ü

X1110 ü

10X11 ü

1X011 ü

101X1 ü

1X101 ü

1011X ü

1X110 ü

1110X ü

111X0 ü

X1111 ü

1X111 ü

11X11 ü

111X1 ü

1111X ü

 

C₂ :

0X0X0

X00X0

XX000

X001X

100XX ü

10XX0 ü

10X0X ü

1XX00

X0X11

10XX1 ü

10X1X ü

101XX ü

1X10X ü

1X1X0 ü

XX111

X111X

1XX11

1X1X1 ü

1X11X ü

111XX ü

 

C₃:

10XXX

1X1XXX

1X1X1

 

 

Складемо таблицю покривань:

 

Таблиця 4 – Покривання

	00000	00010	00011	01000	01010	10111	11000	11011
01X10					ü
0X0X0	ü	ü		ü	ü
X00X0	ü	ü
XX000	ü			ü			ü
X001X		ü	ü
1XX00							ü
X0X11			ü			ü		ü
XX111						ü
X111X
1XX11						ü
10XXX						ü
1X1XX						ü
1X1X1						ü

 

Ядро: X0X11

 

Будуємо скорочену таблицю покривань:

 

Таблиця 5 – Скорочена таблиця покривань

	00000	00010	00011	01000	01010	11000
01X10					ü
0X0X0	ü	ü		ü	ü
X00X0	ü	ü
XX000	ü			ü		ü
X001X		ü	ü
1XX00						ü

 

Найменша МДНФ: Y=x1x4x5+|x1x2x4|x5+|x1|x3|x5+|x3|x4|x5+|x2|x3|x5+|x2|x3x4+x1|x4|x5+|x2x4x5+x3x4x5

 

Тепер знайдемо МКНФ. Для цього  повторимо всі попередні дії  для ДНФ.

C₀:

00001 ü

00100 ü

10000 ü

00101 ü

00110 ü

01001 ü

01100 ü

10001 ü

10010 ü

10100 ü

00111 ü

01011 ü

01101 ü

01110 ü

10011 ü

10101 ü

10110 ü

11001 ü

11010 ü

11100 ü

01111 ü

11101 ü

11110 ü

11111 ü

 

C₁:

00X01 ü

0X001 ü

X0001 ü

0010X ü

001X0 ü

0X100 ü

1000X ü

100X0 ü

10X00 ü

001X1 ü

0X101 ü

X0101 ü

0011X ü

0X110 ü

X0110 ü

010X1 ü

01X01 ü

X1001 ü

0110X ü

011X0 ü

X1100 ü

100X1 ü

10X01 ü

1X001 ü

100X1 ü

10X10 ü

1X010 ü

1010X ü

101X0 ü

1X100 ü

0X111 ü

01X11 ü

X1101 ü

011X1 ü

X1110 ü

0111X ü

1X101 ü

1X110 ü

11X01 ü

11X10 ü

111X0 ü

1110X ü

X1111 ü

111X1 ü

1111X ü

C₂:

XXX01

0X1XX

XX10X

XX1X0

X11XX

Таблиця покривань приведена нижче:

Таблиця 6 – Покривання

	0001	00100	00101	00110	01001	01011	01100	01101	11001	11010
10X0X
10XX0										ü
01XX1					ü	ü		ü	ü
1XX10
XXX01	ü		ü		ü			ü
0X1XX		ü	ü	ü			ü	ü
XX10X		ü	ü				ü	ü
XX1X0		ü		ü			ü
X11XX							ü	ü

 

Ядро: XXX01

           01XX1

           1XX10

 

Будуємо скорочену таблицю покривань:

 

Таблиця 7 – Скорочена таблиця покривань

	0001	00100	00101
0X1XX	ü	ü	ü
XX10X	ü		ü
XX1X0	ü	ü	ü
X11XX			ü

 

Найменша МКНФ: Y=(x4+|x5)(x1+|x2+|x5)( |x1+x3)( |x3+x4)( |x3+x5) (|x2+|x3)

 

1.4 Опис мінімізації БФ заданими  методами

 

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

Такий підхід обумовлений тим, що:

- складність схеми  легко обчислюється по БФ, на  основі яких будується схема:  для ДНФ складність дорівнює  сумі кількості літер, (літері  зі знаком відповідає ціна 2), і  кількість знаків диз’юнкції, збільшеного на 1 для кожного диз’юнктивного виразу.

- усі класичні методи мінімізації БФ забезпечують мінімальність схемі саме у змісті ціни по Квайну.

Схема з мінімальною  ціною по Квайну часто реалізується з найменшим числом конструктивних елементів – корпусів інтегральних мікросхем.

Для даних функцій ми маємо:

С(МДНФ)=43

С(МКНФ)=21

Так як ціна МКНФ менше, то для реалізації схеми будемо використовувати МКНФ.

 

1.5 Приведення БФ до заданого  базису

 

Заданий базис: 3 АБО, так як це не повний функціональний базис, то ми використовуємо базис 3 АБО-НІ.

Y=|(|(Х1Х3))+|(|(|Х3|X5))+|(|(|X1|X2|X3))+|(|(|X2|X4|X5))+|(|(X2X4|X5))+ |(|(|X1X2|X4X5))

Для реалізації функції  по останньому виразу необхідно 15 елементів

3 АБО-НІ (Рис.1). Ранг даної схеми дорівнює 5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1 – Комбінаційна схема

 

 

1.6 Аналіз комбінаційної схеми  методом П-алгоритму

 

Для аналізу методом  П-алгоритму ми пронумерували кожен вихід елемента схеми.

Нульове покриття С₀:

 

                                 10XX0

                                 1XX10

                                 XXX01

                                 0X1XX

 

2 Проектування керуючих автоматів Мілі та Мура