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

ЗМІСТ

Введення

1. Вибір варіанта завдання

1.1. Граф-схема автомата Мура

1.2. Граф-схема автомата Мілі

2. Основна частина

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

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

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

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

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

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

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

2.1.3. Переведеня у базис Висновок Список використаної літератури

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

1.1. Граф-схема алгоритму

Граф-схема складається з чотирьох блоків E, F, G, H і вершин «BEGIN» та «END». Кожен з блоків має два входи (А, В) і два виходи (C, D). Я вибираю блоки E, F, G, H з п’яти блоків з номерами 0, 1, 2, 3, 4 (вони подаються в п. 5 на рис.3−7 у методичних вказівках) на підставі чисел А, В, С, А+В+С (де, А — число, В — місяць народження, С — номер студента в журналі), за такими правилами:

— блок «Е» має схему блока за номером А (MOD 5);

— блок «F» має схему блока за номером B (MOD 5);

— блок «G» має схему блока за номером C (MOD 5);

— блок «H» має схему блока за номером (А+B+C)(MOD 5).

В моєму варіанті:

А=30;

В=06;

С=22.

«Е»: А (MOD 5)=30(MOD 5)=0;

«F»: B (MOD 5)=06(MOD 5)=1;

«G»: C (MOD 5)=22(MOD 5)=2;

«H»: (А+B+C)(MOD 5)=(30+06+22)(MOD 5)=58(MOD 5)=3.

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

Згідно з моїм варіантом завдання, граф-схема автомата має такий вигляд:

BEGIN

END

Рис. 1.1. Граф-схема алгоритму автомата Мілі

BEGIN

END

Рис. 1.2. Граф-схема алгоритму автомата Мура

1.2. Тип тригера

Тип тригера вибирається за значенням числа A (MOD 3) на підставі табл.2 в методичних вказівках. Згідно з моїм варіантом завдання:

A (MOD 3)=30(MOD 3) =0.

Тому, згідно таблиці 2 у методичних вказівках, тип тригера в моєму завданні для синтезу автомата Мура — D, а для синтезу автомата Мілі - Т.

1.3. Серія інтегральних мікросхем

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

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

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

2.1.1. Розмітка станів ГСА

На етапі одержання відміченої ГСА входи вершин, які слідують за операторними, відмічають символами a₁, a₂, … за наступними правилами:

1) символом а₁ відмічають вхід вершини, яка слідує за початковою, а також вхід кінцевої вершини;

2) входи усіх вершин, які слідують за операторними, повинні бути відмічені;

3) входи різних вершин, за винятком кінцевої, відмічаються різними символами;

4) якщо вхід вершини відмічається, то тільки одним символом.

За ціми правилами в мене вийшло 22 стани (а₂₂).

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

Для кожного стану a_i визначаю по ГСА всі шляхи, які ведуть в інші стани і проходять обов’язково тільки через одні операторну вершину. Виняток становить перехід в кінцевий стан (вершину).

Для мікропрограмних автоматів таблиці переходів-виходів будуються у вигляді списку, тому що велика кількість станів. Розрізняють пряму та зворотну таблицю переходів. Зворотна таблиця переходів будується для D-тригера. Для автомата Мілі я буду будувати пряму таблицю переходів.

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

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

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

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

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

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

i j P (i, j)

1 2 1

2 4 1

2 6 1

3 4 1

4 5 1

5 8 1

5 9 1

5 10 1

5 11 1

6 5 1

6 7 1

7 9 1

7 11 2

7 12 1

8 9 1

9 10 1

10 3 1

10 7 1

10 4 1

10 5 1

T= 11 12 1

12 13 1

13 14 1

13 15 1

14 17 1

15 17 1

15 19 1

16 19 1

17 18 1

18 1 1

18 20 1

19 18 1

19 20 1

19 21 1

20 1 1

20 22 1

21 22 1

22 13 1

22 15 1

22 16 1

Далі, за допомогою програми ECODE 3, виконую кодування станів автомата на ЕОМ. При цьому вказую глибину кодування (від 4 до 6) та вибираю те кодування, коефіцієнт якого ближче до 1 (у мене коефіцієнт кодування 1,26). Результати кодування заношу до таблиці 1. Ось кінцеві результати кодування:

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

Кількість переключень тригерів:

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

+P (14,17)*d (14,17) + P (15,17)*d (15,17) + P (15,19)*d (15,19) + +P (15,22)*d (15,22) +P (16,19)*d (16,19) + P (16,22)*d (16,22) + +P (17,18)*d (17,18) + P (18,19)*d (18,19) +P (18,20)*d (18,20) + +P (19,20)*d (19,20) + P (19,21)*d (19,21) + P (20,22)*d (20,22) +

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

= 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 +1*1 + 1*2 + + 2*1 + 1*2 + 1*2 + 1*1 + 1*2 + 2*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + +1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + +1*1+ 1*2 + 1*2 = 53

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

Wmin = E P (i, j) = 42

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

2.1.4. Структурний синтез автомата на підставі заданого типу тригерів

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

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

На підставі цієї таблиці я вказую у табл.1 який тригер встановиться в 1, а який в 0.

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

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

А=; B=; C=; F=; G=;

L=; P=; Q=; R=; S=;

T=; U=; V=; Б=; Y=;

Z=; D=; E=; H=; I= ;

J=; K=; O=; W=; X=;

Г=; Д=; M=; N=.

=

=

+ ;

;

;

;

.

;

;

;

;

;

;

;

;

;

.

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

2.2.1. Розмітка станів ГСА

Для автомата Мура на етапі одержання відміченої ГСА розмітка провадиться відповідно до наступних правил:

1) символом а₁ відмічаються початкова і кінцева вершини;

2) різні операторні вершини відмічаються різними символами;

3) всі операторні вершини повинні бути відмічені.

Відповідно до цих правил я відмітив 25 станів, які показані на рис. 2.

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

Для кожного стану a_i визначаю по ГСА всі шляхи, які ведуть в інші стани.

Я буду будувати зворотну таблицю переходів для автомата Мура, тому що я синтезую автомат на базі D-тригера.

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

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

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

Кожному стану автомата а_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-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу.

Результати кодування за цим алгоритмом заношу до таблиці 3.

2.2.4. Структурний синтез автомата на підставі заданого типу тригерів

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

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

На підставі цієї таблиці я вказую у табл.1 який тригер встановиться в 1, а який в 0.

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

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

U=; A=; B=; W=; D=;

H=; I=; J=; L=; N=;

O=; P=; Q=; S=; C=;

E=; F=; X=; G=; K=;

M=; R=; T=; V=.

;

;

;

;

.

;

;

;

;

;

;

;

;

;

.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Прикладная теория цифрових автоматов/К.Г.Самофалов, А. М. Романкевич, В. Н. Валуйский и др.-К.:Вища шк., 1987.

2. Савельєв А. Я. Прикладная теория цифрових автоматов.-М.: Высш. шк., 1987.

3. Справочник по интегральным микросхемам / Под ред. Б. В. Тарабрина,-М.: Радио и связь, 1987.

4. ГОСТ 2.708−81 ЕСКД. Правила выполнения электрических схем цифровой вычислительной техники.

5. ГОСТ 2.743−82 ЕСКД. Обозначения условные графические в схемах. Элементы цифровой техники.