Прикладна теорія цифрових автоматів (стр. 2 из 3)
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. Таблиця переходів Т-тригера
| 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-тригера
| Amas(Y)KasXamasD1D2D3D4D5 | a23 | a24a1(-)000101 | X2D4 | D4 | U | a12 | a11a2(Y1,Y2) | 00100 | 1 |
| 1 | D3 | D3 | a1a3(Y1,Y4)110001D1D2 | a2a4(Y3)00111X4D3D4D5A | a3a5(Y7)01011X3D2D4D5B | a2a6(Y4,Y5)10011X4X2D1D4D5C | |||
| a3 | a4a7(Y2,Y6) | 01000 | X3 | 1D2 | D2 | a2 | a5 | a6 | |
| a7a8(Y1,Y8)00000X4X2X1 | X1 | 1 | 1 | a2 | a5a9(Y5,Y9)10000X4X2X1 | X1D1 | D1V | W | a8a10(Y4)01110X4D2D3D4D |
| a10a11(Y4,Y5)101101D1D3D4 | a8 | a9a12(Y3,Y10)00011X4X3 | X4X3D4 | D4D5 | D5E | F | a8 | a9 | a9a13(Y6)00001X4X3 |
| X4X3 | X4X1 | D5 | D5 | D5X | a9 | a13a14(Y2,Y4)00101X4X1 | 1D3 | D3D5 | |
| D5G | a24 | a25a15(Y3,Y6)01001X2 | 1D2 | D2D5 | D5H | a14 | a15a16(Y7)100011 | X5D1 | |
| D1D5 | D5 | I | a16a17(Y1,Y9)11100X1D1D2D3J | a15 | a16a18(Y8)00100X5X6 | X1D3 | D3D4 | D4K | L |
| a15a19(Y3)10101X5X6D1D3D5M | a17 | a18a20(Y2,Y4)010101 | X2D2 | D2D4 | D4 | N | a18 | a19a21(Y3,Y6)10010X2 | 1D1 |
| D1D4 | D4O | a20 | a21a22(Y7)011001 | X5D2 | D2D3 | D3 | P | a22a23(Y1,Y9)01101X1D2D3D5Q | a21 |
| a22a24(Y8)10100X5X6 | X1D1 | D1D3 | D3R | S | a21a25(Y3)11001X5X6D1D2D5T |
2.2.3. Кодування станів
Кодування станів буде проводитися за таким алгоритмом:
1. Кожному стану автомата аm (m = 1,2,...,M) ставиться у відповідність ціле число Nm, рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ).
2. Числа N1, N2, ..., Nm упорядковуються по убуванні.
3. Стан аs з найбільшим Ns кодується кодом:
, де R-кількість елементів пам'яті.4. Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.