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

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

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Кафедра комп'ютерних інтелектуальних систем та мереж

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

з дисципліни

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

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

Одеса 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.

Табл.1

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

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

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

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

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

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

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

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

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

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

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

Для станів, що залишилися, знову в порядку списку п. 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 11

a2 10 011

a3 110

a4 10 101

a5 101

a6 11 001

a7 1 011

a8 1 100

a9 1 010

a10 1 101

a11 1 001

a12 111

a13 1 110

a14 11 000

a15 10 100

a16 10 010

a17 10 001

a18 10 000

a19 10 110

a20 1 000

a21 100

a22 10

a23 11 010

a24 1

a25 0

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

2.1.2. Функції збудження тригерів та вихідних сигналів

Введемо слідуючі позначення:

Б= a20NХ4NХ1 Х=a3X1

В= a14NХ2 Ц=a18NX5NX6

Г= a20Х4Х3 Ч=a5NX4NX3

Д=a20NХ4Х1 Ш=a20X4NX3

Е=a18X5 Э=a9X1

Ж=a3NX1 Ю=a22NX5NX6

З= a24NХ4NХ1 Я=a11NX4NX3

И=a14X2 Щ=a24X4NX3

К=a5X4 Ь=a18NX5X6

Л= a16NХ2 Ы=a22NX5X6

П=a22X5

Р=a9NX1

Т=a16X2

У=a11X4

Виписуємо з таблиці вирази для тригерів:

D1=a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь

D2=К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы

D3=a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь

D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы

D5=a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л Формуємо функції виходів автомата:

Y1=a4+a5+a10+a11

Y2=a2+a8

Y3=a15+a17+a18+a19+a22+a23

Y4=a2+a6+a7+a8+a12+a13

Y5=a7+a13+a20+a24

Y6=a18+a21+a22+a25

Y7=a3+a9

Y8=a5+a11+a14+a16

Y9=a4+a10+a20+a24

Y10=a15+a17

2.1.3. Переведеня у базис:

D1= a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь=

=Na1•NЖ•NК•NЫ•NХ•NЦ•NЧ•NШ+NЭ•NЮ•NЯ•NЩ•Na21•NБ•NЬ

D2= К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы=

=NК•Na6•Na7•Na15•Na8•NП•NР•Na10+NТ•NХ•NЦ•Nа12•Na19•NВ•NЫ

D3= a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь=

=Na2•NЕ•NЖ•Na4•NИ•Na7•Na15•NР+NУ•Na12•NЧ•NШ•NГ•NД•NЬ

D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы

=Na13•Na17•Na1•Na2•NЕ•Na6•Na8•NП+NУ•Na12•NЭ•NЮ•NЬ•Na25•NЗ•NЫ

D5= a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л=

=Na13•Na17•Na1•NЖ•Na4•NИ•NК•Na6+NР•Na10•NТ•NУ•NЯ•NЩ•Na23•NЛ

Y1=a4+a5+a10+a11=Na4•Na5•Na10•Na11

Y2=a2+a8= Na2•Na8

Y3=a15+a17+a18+a19+a22+a23= Na15•Na17•Na18•Na19•Na22•Na23

Y4=a2+a6+a7+a8+a12+a13= Na2•Na6•Na7•Na8•Na12•Na13

Y5=a7+a13+a20+a24= Na7•Na13•Na20•Na24

Y6=a18+a21+a22+a25= Na18•Na21•Na22•Na25

Y7=a3+a9= Na3•Na9

Y8=a5+a11+a14+a16= Na5•Na11•Na14•Na16

Y9=a4+a10+a20+a24= Na4•Na10•Na20•Na24

Y10=a15+a17= Na15•Na17

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

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

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

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

Мы повинні кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що у мене Т-тригер.

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

Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P (i, j)? 0, i? j. Для кожної пари вказуємо її вагу.

¦T¦ =

i ¦ j ¦ P (i, j)

1 ¦ 2 ¦ 1

1 ¦ 11 ¦ 1

1 ¦ 12 ¦ 1

1 ¦ 21 ¦ 1

2 ¦ 3 ¦ 1

3 ¦ 4 ¦ 1

3 ¦ 13 ¦ 1

3 ¦ 15 ¦ 1

4 ¦ 5 ¦ 1

5 ¦ 6 ¦ 1

5 ¦ 7 ¦ 1

5 ¦ 13 ¦ 1

5 ¦ 18 ¦ 1

6 ¦ 7 ¦ 1

7 ¦ 8 ¦ 1

7 ¦ 17 ¦ 1

8 ¦ 9 ¦ 1

9 ¦ 10 ¦ 1

9 ¦ 14 ¦ 1

9 ¦ 19 ¦ 1

10 ¦ 11 ¦ 1

11 ¦ 12 ¦ 1

11 ¦ 14 ¦ 1

11 ¦ 22 ¦ 1

13 ¦ 15 ¦ 1

13 ¦ 17 ¦ 1

14 ¦ 19 ¦ 1

14 ¦ 21 ¦ 1

15 ¦ 16 ¦ 1

15 ¦ 17 ¦ 1

15 ¦ 18 ¦ 1

16 ¦ 17 ¦ 1

17 ¦ 18 ¦ 2

19 ¦ 20 ¦ 1

19 ¦ 21 ¦ 1

19 ¦ 22 ¦ 1

20 ¦ 21 ¦ 1

21 ¦ 22 ¦ 2

Підраховуємо вагу всіх компонентів всіх пар

P (1) = 4

P (2) = 2

P (3) = 4

P (4) = 2

P (5) = 5

P (6) = 2

P (7) = 4

P (8) = 2

P (9) = 4

P (10) = 2

P (11) = 5

P (12) = 2

P (13) = 4

P (14) = 4

P (15) = 5

P (16) = 2

P (17) = 5

P (18) = 3

P (19) = 5

P (20) = 2

P (21) = 5

P (22) = 3

Далі згідно правил алгоритму будуємо матрицю М

i ¦ j ¦ P (i, j)

17 ¦ 18 ¦ 2

15 ¦ 17 ¦ 1

3 ¦ 15 ¦ 1

7 ¦ 17 ¦ 1

5 ¦ 7 ¦ 1

5 ¦ 13 ¦ 1

13 ¦ 15 ¦ 1

13 ¦ 17 ¦ 1

3 ¦ 13 ¦ 1

5 ¦ 18 ¦ 1

15 ¦ 18 ¦ 1

4 ¦ 5 ¦ 1

5 ¦ 6 ¦ 1

15 ¦ 16 ¦ 1

16 ¦ 17 ¦ 1

2 ¦ 3 ¦ 1

1 ¦ 2 ¦ 1

1 ¦ 11 ¦ 1

1 ¦ 21 ¦ 1

21 ¦ 22 ¦ 2

19 ¦ 21 ¦ 1

9 ¦ 19 ¦ 1

11 ¦ 14 ¦ 1

14 ¦ 19 ¦ 1

14 ¦ 21 ¦ 1

9 ¦ 14 ¦ 1

11 ¦ 22 ¦ 1

19 ¦ 22 ¦ 1

10 ¦ 11 ¦ 1

11 ¦ 12 ¦ 1

19 ¦ 20 ¦ 1

20 ¦ 21 ¦ 1

1 ¦ 12 ¦ 1

3 ¦ 4 ¦ 1

6 ¦ 7 ¦ 1

7 ¦ 8 ¦ 1

8 ¦ 9 ¦ 1

9 ¦ 10 ¦ 1

Визначемо розрядність кода для кодування станів автомата

R = ] log2 N [ = ] log2 22 [ = 5

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

b1 1 011

b2 1 111

b3 111

b4 1 101

b5 101

b6 1 100

b7 100

b8 10 100

b9 10 000

b10 11 000

b11 11 010

b12 1 010

b13 110

b14 11 001

b15 11

b16 10

b17 0

b18 1

b19 10 001

b20 10 101

b21 10 011

b22 10 010

Підрахунок ефективності кодування:

Кількість перемикань тригерів:

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

P (19,21)*d (19,21) + P (19,22)*d (19,22) + P (20,21)*d (20,21) + P (21,22)*d (21,22) =

1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 = 52

Мінімально можлива кількість перемикань тригерів

Wmin = E P (i, j) = 40

Коефіціент ефективності кодування: 1.30

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

2.2.2. Функції збудження тригерів та вихідних сигналів

Введемо слідуючі позначення:

A=b3NX1 П=b21Х4NX3

Б=b5X4 Р= b5NX4Х3

H=b9X1 С=В15Х5

Г=b11X4 Т= b17Х4NX3

Д=b13X2 У= b19NX5X6

Е=b13NX2 Ф= b21NX4NX1

Ж=b14X2 Х= b3Х1

З=b14NX2 Ц= b5NX4NX3

И=b15NX5NX6 Ч= b11NX4NX3

К=b17NX4NX1 Ш= b15NX5X6

Л=b9NX1 Щ= b17X4X3

М=b11NX4X3 Э= b17NX4X1

O= b19NX5NX6 Ю= b21X4X3

Я= b21NX4X1 В=В19Х5

Виписуємо з таблиці вирази для тригерів:

T₁=b7+Г+Ч+П

Т₂=b2+А+b4+Б+b6+Л+Н+М+З+О+П

Т₃=b1+Р+b8+Е+С+И+Т+У+b20

Т₄ =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22

Т₅=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22

Формуємо функції виходів автомата:

Y1=А+b4+Л+b10+Д

Y2=b1+b7

Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22

Y4=b1+Б+b6+b7+Г+b12

Y5=b6+b12+Е+b16+b20

Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22

Y7=b2+b8+С+В

Y8=Х+b4+Н+b10+Д+И+О

Y9=А+Л+Е+b16+b20

Y10=Ц+Ч+Ж+Т+П

2.2.3. Переведеня у базис:

T₁=b7+Г+Ч+П= Nb7•NГ•NЧ•NП

Т₂=b2+А+b4+Б+b6+Л+Н+М+З+О+П=

=Nb2•NА•Nb4•NБ•Nb6•NЛ•NН•NМ+NЗ•NО•NП

Т₃=b1+Р+b8+Е+С+И+Т+У+b20=

=Nb1•NР•Nb8•NЕ•NС•NИ•NТ•NУ+b20

Т₄ =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22=

=NА•Nb10•NД•NЕ•NЖ•NЗ•Nb16•NК+Nb18•Nb20•NФ•Nb22

Т₅=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22=

=NХ•NБ•NЦ•NH•NЧ•Nb12•NД•NЖ+NИ•NШ•NЩ•NЭ•NK•NЮ•NЯ•Nb22

Y1=А+b4+Л+b10+Д= NА•Nb4•NЛ•Nb10•NД

Y2=b1+b7= Nb1•Nb7

Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22=NЦ•NЧ•NЖ•NШ•NТ•NК•Nb18•NУ+

+NП•NФ•Nb22

Y4=b1+Б+b6+b7+Г+b12=Nb1•NБ•Nb6•Nb7•NГ•Nb12

Y5=b6+b12+Е+b16+b20= Nb6•Nb12•NЕ•Nb16•Nb20

Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22= NМ•NЗ•NЩ•NЭ•NК•Nb18•NЮ•NЯ+

+NФ•Nb22

Y7=b2+b8+С+В= Nb2•Nb8•NС•NВ

Y8=Х+b4+Н+b10+Д+И+О= NХ•Nb4•NН•Nb10•NД•NИ•NО

Y9=А+Л+Е+b16+b20= NА•NЛ•NЕ•Nb16•Nb20

Y10=Ц+Ч+Ж+Т+П= NЦ•NЧ•NЖ•NТ•NП Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами.

Висновок

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

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

Перелік використаної літератури

1. Методичні вказівки до курсової роботи по дисципліні «Прикладна теорія ци фрових автоматів». Одеса. ОГПУ. 1998р.

2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр НТТМ ОГПУ. 1975 г.

3. ГОСТ 2.708−81 ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.

ГОСТ 2.743−82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.