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

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

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 Мінімізація БФ (Квайна-МакКласки)

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

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

C0:

00000

00010

00011

00111

01000

01010

01110

01111

10000

10001

10010

10011

10100

10101

10110

10111

11000

11011

11100

11101

11110

11111

C1:

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

C2 :

0X0X0

X00X0

XX000

X001X

100XX

10XX0

10X0X

1XX00

X0X11

10XX1

10X1X

101XX

1X10X

1X1X0

XX111

X111X

1XX11

1X1X1

1X11X

111XX

C3:

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

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

C0:

00001

00100

10000

00101

00110

01001

01100

10001

10010

10100

00111

01011

01101

01110

10011

10101

10110

11001

11010

11100

01111

11101

11110

11111

C1:

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

C2:

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.

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

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

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

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

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

10XX0

1XX10

XXX01

0X1XX

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

2.1 Вибір вихідних даних

Граф схема складається з чотирьох блоків E,F,G,H і вершин BEGIN та END.

Вони обираються наступним чином:

- блок E 17 mod 5 = 2;

- блок F 7 mod 5 = 2;

- блок G 1 mod 5 = 1;

- блок H 25 mod 5 = 0.

Блоки E, F, G, H з'єднуються між собою схемою яка має вигляд :

Рисунок 2 - Алгоритм

Граф-схема алгоритму показана в додатку 1.

Тип тригера обирається за формулою: 17mod4=1.

Отже для автомата Мілі використовуємо D тригер, а для Мура - JK. Серія інтегральних мікросхем для побудови принципових мікросхем КР 555.

2.2 Структурний синтез автомата Мілі

2.2.1 Розмітка ГСА для автомата Мілі

Для автомата Мілі розмітка ГСА позначається буквою bi. Відмічаються входи в вершини, які слідують за операторними. Виходячи з цього ми отримуємо для автомата Мілі 21 стан.

2.2.2 Кодування станів

Оскільки ми використовуємо D тригер, а його особливістю є те, що вихід тригера такий же як стан у момент часу (t+1), то для оптимального кодування будуємо таблицю переключення автомата, тобто записуємо скільки разів автомат переключається у певний стан.

Таблиця 8 - Переключення автомата

Стан	Кількість переключень
b0	6
b1	1
b2	2
b3	1
b4	2
b5	2
b6	1
b7	2
b8	1
b9	2
b10	2
b11	2
b12	2
b13	1
b14	1
b15	2
b16	2
b17	2
b18	2
b19	2
b20	1

Оптимальне кодування станів буде таким:

Таблиця 9 - Оптимальне кодування станів

Стан	Кількість переключень	Кодування
b0	6		00000
b2	2		00001
b4	2		00010
b5	2		00100
b7	2		01000
b9	2		10000
b10	2		00011
b11	2		00110
b12	2		01100
b15	2		11000
b16	2		10001
b17	2		10010
b18	2		10100
b19	2		01010
b1	1		01011
b3	1		01001
b6	1		00101
b8	1		00111
b13	1		01110
b14	1		11100
b20	1		10110

2.2.3 Таблиця переходів автомата Мілі

На основі ГСА і закодованих стані будуємо таблицю 10 переходів автомата.

Останній стовбець таблиці 10 заповнюється за допомогою оберненої таблиці переходів D- тригера .

булевий мінімізація комбінаційний керуючий автомат

Таблиця 10 - Переходи автомата

b(t)	K(b(t))	b(t+1)	K(b(t+1))	x	y	ФЗ
b0	00000	b1	01011	1	y2y4	D2D4D5
b1	01011	b2	00001	1	y7	D5
b2	00001	b3	01001	|x1	y1y9	D2D5
		b9	10000	x1	y8	D1
b3	01001	b4	00010	1	y2y4	D4
b4	00010	b5	00100	1	y7	D3
b5	00100	b6	00101	|x1	y1y9	D3D5
		b11	00110	x1	y8	D3D4
b6	00101	b7	01000	1	y3y6	D2
b7	01000	b2	00001	x5	y7	D5
		b8	00111	|x5x6	y3	D3D4D5
		b9	10000	|x5|x6	y8	D1
b8	00111	b10	00011	1	y3y6	D4D5
b9	10000	b4	00010	x2	y2y4	D4
		b10	00011	|x2	y3y6	D4D5
b10	00011	b5	00100	x5	y7	D3
		b11	00110	|x5|x6	y8	D3D4
		b12	01100	|x5x6	y1y8	D2D3
b11	00110	b7	01000	x2	y3y6	D2
		b12	01100	|x2	y1y8	D2D3
b12	01100	b13	01110	x4	y4	D2D3D4
		b16	10001	|x3	y3y10	D1D5
b13	01110	b14	11100	1	y4y5	D1D2D3
b14	11100	b15	11000	1	y1y2	D1D2
b15	11000	b0	00000	|x4x2	y4y5	-
		b20	10110	x4	y3	D1D3D4
		b18	10100	|x1|x2|x4	y5y9	D1D3
		b0	00000	x1|x2|x4	-	-
b16	10001	b15	11000	1	y1y2	D1D2
b17	10010	b0	00000	|x3	y2y6	-
		b19	01010	x3	y7	D2D4
b18	10100	b16	10001	x4|x3	y3y10	D1D5
		b17	10010	x3x4	y6	D1D4
		b17	10010	|x4x1	y6	D1D4
		b0	00000	x1|x3|x4	y2y6	-
		b19	01010	x1|x3x4	y7	D2D4
b19	01010	b0	00000	x1	-	-
		b18	10100	|x1	y5y9	D1D3
b20	10110	b0	00000	1	y2y6	-

Побудуємо на основі останньої колонки Таблиці 13 функції збудження і приведемо їх до базису І-НІ:

D1=| (| (b2x1) | (b7|x5|x6) |(b12|x3) |b13|b14|(b15x4) |(b15|x1|x2|x4) |b16|(b18|x3x4) | (b18x3x4) |(b18|x4x1) |(b19|x1))

D2=|(|b0|(b2|x1) |b6|(b10|x5x6) |(b11x2) |b11|(b12x4) |b13|b14|b16|(b17x3) |(b18|x1x3|x4))

D3=|(|b4|b5|(b7|x5x6) | (b10x5) |(b10|x5|x6) |(b10Vx5x6) |(b11|x2) |(b12x4) |b13|(b15x4) |(b15|x1|x2) |(b19|x1))

D5=|(|b0|b1|(b2|x1) |(b5|x1) |b5x7) |(b7|x5x6) |b8|(b9|x2) |(b12|x3) |(b18|3x4))

На основі передостанньої колонки Таблиці 10 будуємо функції виходу:

Y1=|(|(b2|x1) | (b5|x1) | (b10|x5x6) | (b11x2) |b14|b16)

Y2=|(|b0|b3| (b9x2) |b14|b16|(b17|x3) |(b18|x1|x3|x4) |b20)

Y3=|(|b|(b7|x5x6) |b8| (b9|x2) |(b11x2) |(b12|x3) |(b15x4) |(b18|x3x4))

Y4=|(|b0|b3|(b9x2) |(b12x4) |b13|(b15|x4x2))

Y5=|(|b13|(b15x2|x4) |(b15|x1|x2|x4) |b19)

Y6=|(|b6|b8|(b9|x2) |(b11x2) |(b16|x3) |(b18x3x4)(b18x1|x4) |(b18|x1|x3|x4) |b20)

Y7=|(|b1|b4|(b7x5) |(b10x5) |(b17x3) |(b18|x1x3|x4))

Y8=|(| (b2|x1) |(b5x1) |b7|x5|x6) |(b10|x5|x6) |(b11|x2))

Y9=|(|(b2|x1) |(b5|x1) |(b15|x1|x2|x4) |(b19|x1))

Y10=|(|(b12|x3) |(b18x4|x3))

За отриманими функціями збудження та виходу будуємо схему автомата Мілі. Вона представлена у додатку 2.

2.3 Структурний синтез автомата Мура

2.3.1 Розмітка ГСА для автомата Мура

Для автомата Мура розмітка ГСА позначається буквою аi (Додаток 1).

Відмічаються всі операторні вершини, вершина початку та кінця позначається а0. Таким чином для автомата Мура ми отримали 23 стани.

2.3.2 Кодування станів

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

Матриця Т:

i	j	P(i,j)
1	2	2
2	3	1
3	5	1
3	6	1
4	3	1
4	6	4
4	7	2
4	8	1
6	8	1
5	9	1
7	9	1
8	10	1
9	11	1
9	12	1
9	13	1
10	11	1
10	12	2
11	4	1
12	4	1
12	13	1
13	15	1
13	17	1
13	18	2
14	17	1
14	18	1
14	22	1
14	23	1
15	16	1
16	19	1
17	19	2
18	22	1
18	23	1
19	21	1
19	20	1
19	1	1
19	14	1
20	1	2
21	22	1
22	1	1
23	14	1
23	1	1

Оптимальне кодування станів буде таким:

Таблиця 11 - Оптимальне кодування станів

a0	00011
a1	00111
a2	01111
a3	11111
a4	01101
a5	01011
a6	11100
a7	11011
a8	11101
a9	10011
a10	11001
a11	10111
a12	10101
a13	00000
a14	10001
a15	10010
a16	10000
a17	00101
a18	00010
a19	01010
a20	00110
a21	00100
a22	00001

2.3.3 Таблиця переходів автомата Мура

На основі ГСА і закодованих стані будуємо таблицю13 переходів автомата.

Останній стовбець таблиці 12 заповнюється за допомогою оберненої таблиці переходів JK- тригера ( таблиця 12 ).

Таблиця 12 - Обернена таблиці переходів JK- тригера

Q(t)	Q(t+1)	J	K
0	0	X	0
0	1	1	X
1	0	X	1
1	1	0	X

Таблиця 13 - Переходи автомата

а(t)/y	K(a(t))	a(t+1)	K(a(t+1))	x	ФЗ
a0	00011	a1	00111	1	J3
a1/y2y4	00111	a2	01111	1	J2J3
a2/y7	01111	a4	01101	|x1	K4
		a5	01011	x1	K3
a3/y3y6	11111	a2	01111	x5	K1
		a5	01011	|x5|x6	K1K3
		a6	11100	|x5x6	K4K5
a4/y1y9	01101	a7	11011	1	J1K3J4
a5/y8	01011	a7	11011	x2	J1
		a8	11101	|x2	J1J3K4
a6/y3	11100	a8	11101	1	J5
a7/y2y4	11011	a9	10011	1	K2
a8/y3y6		a9	10011	x5	K2K3J4
		a11	10111	|x5|x6	K2J4
	11101	a12	10101	|x5x6	K2
a9/y7	10011	a10	11001	|x1	J2K4
		a11	10111	x1	J3
a10/y1y9	11001	a3	11111	1	J3J4
a11/y8	10111	a3	11111	x2	J2
		a12	10101	|x2	K4
a12/y1y8	10101	a14	10001	x4	K3
		a16	10000	|x3|x4	K3K5
		a17	00101	x3|x4	J1
a13/y5y9	00000	a16	10000	|x3x4	J1
		a17	00101	x3x4	J3J5
		a17	00101	x1|x4	J3J5
		a21	00100	|x1|x3|x4	J3
		a22	00001	|x1|x3|x4	J5
a14/y4	10001	a15	10010	1	J4K5
a15/y4y5	10010	a18	00010	1	K1
a16/y3y10	10000	a18	00010	1	K1J4
a17/y6	00101	a21	00100	|x3	K5
		a22	00001	x3	K3
a18/y1y2	00010	a0	00011	x1|x2|x4	J5
		a19	01010	x2|x4	J2
		a20	00110	x4	J3
		a13	00000	|x1|x2|x4	K4
a19/y4y5	01010	a0	00011	1	K2J5
a20/y3	00110	a21	00100	1	K4
a21/y2y6	00100	a0	00011	1	K3J4J5
a22/y7	00001	a0	00011	x1	J4
		a13	00000	|x1	K5

Побудуємо на основі останнього cтовпця функції збудження і переведемо ці функції у зручний базис (і-ні).

J1=|(|a4|a5|(a12|x3x4) |(a13|x3x4))

J2=|(|a1|(a9|x1) |(a11x2) |(a18x2|x4))

J3=|(|a0|a1|(a5|x2)|(a9x1) |a10|(a13x3x4) |(a13x1|x4) |(a13|x1|x3|x4) |(a18x4))

J4=|(|a4|(a8x5) |(a8|x5|x6) |a10|a14|a16|a21|(a22x1))

J5=|(|a6|(a13x3x4) |(a13x1|x4) |(a13|x1x3|x4) |(a18x1|x2|x4) |a19|a21)

K1=|(|(a3x5) |(a3|x5|x6) |a15|a16)

K2=|(|a7|(a8x5) |(a8|x5|x6) |(a8|x5x6) |a19)

K3=|(|a2x1) |(a3|x5|x6) |a4|(a8x5) |(a12x4) |(a12|x3|x4) |(a17x3) |a21)

K4=|(|a2|x1) |(a3|x5x6) |(a5x2) |(a9|x1) |(a11|x2) |(a18|x1|x2|x4) |a20)

K5=|(|(a3|x5x6) |a12|x3|x4) |(a17|x3) |(a22|x1))

Y1=a4+a10+a12+a18

Y2=a1+a7+a18+a21

Y3=a3+a6+a8+a16+a20

Y4=a1+a7+a14+a15+a19

Y5=a13+a15+a19

Y6=a3+a8+a17+a21

Y7=a2+a9+a22

Y8=a5+a11+a12

Y9=a4+a10+a13

Y10=a16

За отриманими функціями збудження та виходу будуємо схему автомата Мура. Вона представлена у додатку 3.

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