48171 (Прикладна теорія цифрових автоматів), страница 2
Описание файла
Документ из архива "Прикладна теорія цифрових автоматів", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48171"
Текст 2 страницы из документа "48171"
= 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. Таблиця переходів Т-тригера
Qt | Qt+1 | T |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
На підставі цієї таблиці я вказую у табл.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) символом а1 відмічаються початкова і кінцева вершини;
2) різні операторні вершини відмічаються різними символами;
3) всі операторні вершини повинні бути відмічені.
Відповідно до цих правил я відмітив 25 станів, які показані на рис. 2.
2.2.2. Таблиця переходів автомата
Для кожного стану ai визначаю по ГСА всі шляхи, які ведуть в інші стани.
Я буду будувати зворотну таблицю переходів для автомата Мура, тому що я синтезую автомат на базі D-тригера.
Табл.3. Таблиця переходів D-тригера
Am as(Y) Kas Xamas D1 D2 D3 D4 D5 | a23 | a24 a1(-) 00010 1 | X2 D4 | D4 | U | a12 | a11 a2(Y1,Y2) | 00100 | 1 |
1 | D3 | D3 | a1 a3(Y1,Y4) 11000 1 D1 D2 | a2 a4(Y3) 00111 X4 D3 D4 D5 A | a3 a5(Y7) 01011 X3 D2 D4 D5 B | a2 a6(Y4,Y5) 10011 X4X2 D1 D4 D5 C | |||
a3 | a4 a7(Y2,Y6) | 01000 | X3 | 1 D2 | D2 | a2 | a5 | a6 | |
a7 a8(Y1,Y8) 00000 X4X2X1 | X1 | 1 | 1 | a2 | a5 a9(Y5,Y9) 10000 X4X2X1 | X1 D1 | D1 V | W | a8 a10(Y4) 01110 X4 D2 D3 D4 D |
a10 a11(Y4,Y5) 10110 1 D1 D3 D4 | a8 | a9 a12(Y3,Y10) 00011 X4X3 | X4X3 D4 | D4 D5 | D5 E | F | a8 | a9 | a9 a13(Y6) 00001 X4X3 |
X4X3 | X4X1 | D5 | D5 | D5 X | a9 | a13 a14(Y2,Y4) 00101 X4X1 | 1 D3 | D3 D5 | |
D5 G | a24 | a25 a15(Y3,Y6) 01001 X2 | 1 D2 | D2 D5 | D5 H | a14 | a15 a16(Y7) 10001 1 | X5 D1 | |
D1 D5 | D5 | I | a16 a17(Y1,Y9) 11100 X1 D1 D2 D3 J | a15 | a16 a18(Y8) 00100 X5X6 | X1 D3 | D3 D4 | D4 K | L |
a15 a19(Y3) 10101 X5X6 D1 D3 D5 M | a17 | a18 a20(Y2,Y4) 01010 1 | X2 D2 | D2 D4 | D4 | N | a18 | a19 a21(Y3,Y6) 10010 X2 | 1 D1 |
D1 D4 | D4 O | a20 | a21 a22(Y7) 01100 1 | X5 D2 | D2 D3 | D3 | P | a22 a23(Y1,Y9) 01101 X1 D2 D3 D5 Q | a21 |
a22 a24(Y8) 10100 X5X6 | X1D1 | D1 D3 | D3 R | S | a21 a25(Y3) 11001 X5X6 D1 D2 D5 T |
2.2.3. Кодування станів
Кодування станів буде проводитися за таким алгоритмом:
-
Кожному стану автомата аm (m = 1,2,...,M) ставиться у відповідність ціле число Nm, рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ).
-
Числа N1, N2, ..., Nm упорядковуються по убуванні.
-
Стан аs з найбільшим Ns кодується кодом: , де R-кількість елементів пам'яті.
-
Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.
-
Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім із трьома і так далі поки не будуть закодовані вес стани.
У результаті виходить таке кодування, при якому чим більше мається переходів у деякий стан, тим менше одиниць у його коді. Вираження для функцій збудження будуть простіше для D-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу.