Прикладна теорія цифрових автоматів

Міністерство освіти і науки України ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ Кафедра комп’ютерних інтелектуальних систем та мереж

Курсове проектування

з дисципліни

„Прикладна теорія цифрових автоматів”

Виконав: студент гр.

Одеса 2002

1.ВИБІР ВАРІАНТА ЗАВДАННЯ

Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами:

- блок "Е" – схема під номером (А) mod 5 = 27 mod 5 = 2;

- блок "F" – схема під номером (В) mod 5 = 6 mod 5 = 1;

- блок "G" – схема під номером (С) mod 5 = 13 mod 5 = 3;

- блок "H" – схема під номером (А+В+С) mod 5 = 46 mod 5 = 1.

Блоки E, F, G, H з’єднуються між собою згідно зі структурною схемою графа, яка показана на рис. 10 у методичних вказівках.

Розташування обирається з використанням номера групи. Тип тригера знаходимо по таблиці на підставі числа (А) mod 3 = 27 mod 3 = 0.

(A) mod 3	ТИП ТРИГЕРА
0	Т	D
1	D	JK
2	JK	T
автомат	Мілі	Мура

Табл.1

З табл.1 отримуємо T-тригер для автомата Мілі та D-тригер для Мура.

Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів для мого варіанта завдання – КР1533.

Після відповідної розмітки будуємо граф-схему для обоіх автоматів:

2. ОСНОВНА ЧАСТИНА

 

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

 

2.1.1. Кодування станів

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

1.          Кожному стану автомата а_m (m = 1,2,...,M) ставиться у відповідність ціле число N_m, рівне числу переходів у стан а_m (N_m дорівнює числу появ а_m у поле таблиці ).

2.          Числа N₁, N₂, ..., N_m упорядковуються по убуванні.

3.          Стан а_s з найбільшим N_s кодується кодом: де R-кількість елементів пам'яті.

4.          Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.

5.          Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім із трьома і так далі поки не будуть закодовані всі стани.

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

Статистика:

a1 2стана

a2 1стан

a3 2стана

a4 1стан

a5 2стана

a6 1стан

a7 1стан

a8 2стана

a9 2стана

a10 1стан

a11 2стана

a12 1стан

a13 1стан

a14 2стана

a15 2стана

a16 2стана

a17 2стана

a18 2стана

a19 1стан

a20 2стана

a21 2стана

a22 2стана

a23 1стан

a24 2стана

a25 3стана

Результати кодування:

a1 00011

a2 10011

a3 00110

a4 10101

a5 00101

a6 11001

a7 01011

a8 01100

a9 01010

a10 01101

a11 01001

a12 00111

a13 01110

a14 11000

a15 10100

a16 10010

a17 10001

a18 10000

a19 10110

a20 01000

a21 00100

a22 00010

a23 11010

a24 00001

a25 00000

Табл.2. Таблиця переходів D-тригера

Am Kam As(y) X Kas D1D2D3D4D5	a13	a17 a1(-) 1	1     00011 D4D5	D4D5	a1 a2(y2y4) 1 10011 D1 D4D5
a2	a18 a3(y7) 1	X5 00110 D3D4	D3D4	a3 a4(y1y9) NX1 10101 D1 D3  D5	a4
a14 a5(y1y8) 1	X2 00101 D3 D5	D3 D5	a5 a6(y4) X4 11001 D1D2 D5	a6 a7(y4y5) 1 01011 D2  D4D5	a7
a15 a8(y2y4) 1	1 01100 D2D3	D2D3	a8	a22 a9(y7) 1	X5 01010 D2 D4
D2 D4	a9 a10(y1y9) NX1 01101 D2D3 D5	a10	a16 a11(y1y8) 1	X2 01001	D2 D5
D2 D5	a11 a12(y4) X4 00111 D3D4D5	a12 a13(y4y5) 1 01110 D2D3D4	a3	a18 a14(y8) X1	NX5NX6 11000 D1D2
D1D2	a5	a20 a15(y3y10) NX4NX3	X4NX3 10100	D1 D3	D1 D3
a9	a22 a16(y8) X1	NX5NX6 10010 D1 D4	D1 D4	a11	a24 a17(y3y10) NX4NX3
X4NX3 10001 D1 D5	D1 D5	a21	a20 a18(y3y6) 1	NX4NX1 10000 D1	D1
a18 a19(y3) NX5X6 10110 D1 D3D4	a19	a14 a20(y5y9) 1	NX2 01000 D2	D2	a20
a20 a21(y6) X4X3	NX4X1 00100 D3	D3	a25	a24 a22(y3y6) 1	NX4NX1 00010 D4
D4	a22 a23(y3) NX5X6 11010 D1D2 D4	a23	a16 a24(y5y9) 1	NX2 00001 D5	D5
a24	a24	a11 a25(y6) X4X3	NX4X1	NX4 X3 00000