48173 (Прикладна теорія цифрових автоматів), страница 2

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

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

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

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

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

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

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

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

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

Y 1=a4+a5+a10+a11=Na4∙Na5∙Na10∙Na11

Y 2=a2+a8= Na2∙Na8

Y 3=a15+a17+a18+a19+a22+a23= Na15∙Na17∙Na18∙Na19∙Na22∙Na23

Y 4=a2+a6+a7+a8+a12+a13= Na2∙Na6∙Na7∙Na8∙Na12∙Na13

Y 5=a7+a13+a20+a24= Na7∙Na13∙Na20∙Na24

Y 6=a18+a21+a22+a25= Na18∙Na21∙Na22∙Na25

Y 7=a3+a9= Na3∙Na9

Y 8=a5+a11+a14+a16= Na5∙Na11∙Na14∙Na16

Y 9=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 01011

b2 01111

b3 00111

b4 01101

b5 00101

b6 01100

b7 00100

b8 10100

b9 10000

b10 11000

b11 11010

b12 01010

b13 00110

b14 11001

b15 00011

b16 00010

b17 00000

b18 00001

b19 10001

b20 10101

b21 10011

b22 10010

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

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

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. Функції збудження тригерів та вихідних сигналів