5 Економічне кодування станів автомату
ЛАБОРАТОРНА РОБОТА № 5
Мета роботи. Вивчити структурно-функціональну організацію структурного автомата, принцип дії D-тригерів та їх види. Навчитися виконувати економічне кодування станів МПА.
5.1 Структурний автомат
Основною задачею структурного синтезу МПА є побудова логічної схеми автомата з елементарних автоматів – тригерів, які утворюють код поточного стану автомата K(am) і перемикаються у відповідності до алгоритму роботи МПА. Тобто кожному стану автомата am відповідає певна кодова комбінація K(am), утворена тригерами пам'яті автомата.
Структурно-функціональна організація структурного автомата наведена на рис.5.1. Вона складається з двох частин – пам'яті і комбінаційної схеми (КС).
Рисунок 5.1 – Структурний автомат
Тут
X = {x1..,xL} – сигнали логічних умов;
Y= {y1..,yN} – коди мікрооперацій;
D1..,DR – функції збудження елементів пам'яті;
T1..,TR – функції зворотного зв'язку автомата.
Звичайно використовують максимальне кодування станів автомата. Кількість елементів пам'яті R за такої стратегії кодування розраховується за формулою (5.1).
(5.1)
де M – кількість станів автомата.
За максимального кодування кожному стану відповідає код, що має мінімальну кількість розрядів (дужки "] [" у формулі (5.1) інтерпретуються як "найменше ціле від..").
5.2 Тригери
В якості елементів пам'яті найбільш часто використовують D-тригери. У загальному випадку D- тригер має інформаційний вхід D, тактовий вхід CLK, вхід скидання CLR (установлення логічного нуля), вхід попереднього установлення логічної одиниці PRE. Виходи D-тригера: T – поточний логічний стан тригера, Tn – інверсія логічного стану. На рис.5.2 зображені умовні графічні позначення (УГП) і таблиці дійсності різних типів D-тригерів.
Рисунок 5.2 – Типи D-тригерів
Мовою VHDL можна описати поведінку будь-якого цифрового пристрою. Наприклад, листинг 5.1 містить опис D-тригера типу DFC1 мовою VHDL.
Листинг 5.1 – Файл DLATCH.VHD
library IEEE;
use IEEE.std_logic_1164.all;
-- декларативна частина
entity DLATCH is
port (
D, CLK, CLR: in STD_LOGIC;
T: out STD_LOGIC
);
end DLATCH;
-- виконавча частина
architecture DLATCH_BEH of DLATCH is
begin
process (CLK, CLR)
begin
if
CLR = '1' then T <= '0';
else
if CLK'event and CLK = '1' then T <= D;
endif;
endif;
end process;
end DLATCH_BEH;
5.3 Економічне кодування станів
Комбінаційна схема автомата – це структурний елемент логічної схеми МПА, який реалізує систему булевих функцій (БФ). Ця система складається з БФ збудження елементів пам'яті D1,..,DR (реалізують функцію переходів δ абстрактного автомата) і БФ виходу y1,..,yN (реалізують функцію виходу λ).
Різні варіанти кодування станів автомата приводять до різних виразів функцій збудження пам'яті і функцій виходів [9]. Складність КС автомата істотно залежить від вибраного варіанту кодування. Знаходження варіантів кодування станів, які створюють ослаблену функціональну залежність для функцій збудження, дає більш економічну КС, ніж за інших кодуваннях.
Використовування економічного кодування станів МПА дозволяє зменшити залежність функцій збудження КС від змінних зворотного зв'язку.
Ефективність кодування можна оцінити. Кожному переходу (am, as) графа переходів Г(S) поставимо у відповідність вагову функцію (5.2), яка характеризує ефективність вибраного варіанту кодування станів am і as.
(5.2) де
p(m,s) = q(m,s)+q(s,m) – число всіляких переходів q(m,s) із стану am в стан as (в тому числі симетричних переходів q(s,m) із стану as в стан am);
d(m,s) – кількість бітів, якими коди K(am) і K(as) відрізняються між собою (відстань Хеммінга між K(am) і K(as)).
Приклад П5.1 – Визначення відстані Хеммінга між кодом стану-передавача K(am) і кодом стану-одержувача K(as)
Наприклад, в автоматі на переході із стану am (K(am) = "000") в стан as (K(as) = "100") відстань Хеммінга дорівнює 1, оскільки їх коди відрізняються в одному біті.
Нижче приведений опис евристичного алгоритму кодування станів, який мінімізує сумарне число перемикань елементів пам'яті на всіх переходах автомата. В якості критерію оптимізації алгоритм А5.1 використовує вагову функцію W (5.2). Спрощення комбінаційної схеми буде тим більше, чим менше вагова функція.
Алгоритм 5.1 – Економічне кодування станів МПА [9]
1. Будується матриця T,
-
α1
β1
T
=
.
.
.
αR
βR
яка складається зі всіх пар
номерів (αr,
βr),
r = 1,..,R, для
яких p(αr,
βr)
≠ 0, тобто
в автоматі є перехід із стану-передавача
в
стан-одержувач
,
або з 
в
,
αr
< βr.
Рефлексивні переходи виключаються з
матриці T.
Всі переходи повинні бути унікальними,
тому, якщо є симетричні переходи, то в
матриці T
залишається
тільки одна копія такого переходу.
2. Упорядковуються
рядки матриці T, для чого будується
матриця M таким чином. В перший рядок
матриці M поміщається пара (
,
)з
найбільшою вагою p(
,
).
Зі всіх пар, що мають
загальний компонент з парою (
,
),
вибирається пара
(
,
)
з найбільшою вагою
і заноситься в другий рядок матриці M.
Потім зі всіх пар, що мають загальний
компонент хоча б з однією з внесених в
список пар, вибирається пара з найбільшою
вагою і заноситься в матрицю M. Вказана
процедура продовжується до тих пір,
поки всі пари матриці T не будуть
перенесені в матрицю M. У разі рівності
ваги пар обчислюються суми ваги
компонентів пар (вагою
p(αr)
компоненту
αr
називається число появ
αr
в матриці T) і в матрицю M
заноситься пара з найбільшою сумою ваги
компонентів.
3. Кодуються стани з першого рядка матриці M таким чином:
K(αr1) = 00..00; K(βr1) = 00..01.
4. З матриці
M викреслюється перший рядок, відповідний
закодованим станам
і
.
Виходить матриця M'.
5. Через впорядкування в п.2 в першому рядку матриці M' закодований рівно один елемент. З першого рядка M' вибирається незакодований елемент і позначається γ.
6. Будується матриця Mγ, вибравши з M' строчки, що містять γ. Нехай Bγ = {γ1, .., γf, .., γF} – множина елементів з матриці Mγ, які вже закодовані. Їх коди K(γ1), .., K(γf), .., K(γF) відповідно.
7. Для кожного K(γf), f =1,..,F знаходиться Cγf(1) – множина кодів, сусідніх з K(γf), і ще не зайнятих для кодування станів автомата. Будується множина
.
Якщо Dγ(1)
=
,
то будується нова множина
,
де Cγf(2)
– множина
кодів, у яких відстань Хеммінга до коду
K(γf)
дорівнює двом. Якщо
Dγ(2)
=
,
аналогічним чином будується
Dγ(3),..,
Dγ(n)
до тих пір, поки не
знайдеться Dγ(n)
≠
(n=1,2,3,..).
Нехай
Dγ(n)={K(δ1),
.., K(δg),..,
K(δG)}.
8. Для кожного K(δg) знаходиться d(δg, γf) – кодова відстань між K(δg) і всіма використаними кодами K(γf).
9. Знаходиться
,
g = 1, .., G. (5.3)
10. З Dγ(n) вибирається K(γ) у якого Wg = min (Wg). Елемент γ (стан aγ) кодується кодом K(γ).
11. З матриці M' викреслюються рядки, в яких обидва елементи закодовано, внаслідок чого виходить нова матриця M'. Якщо в матриці M' не залишилося жодної строчки, то перехід до п.12, інакше – до п.5.
12. Обчислюється функція
. (5.4)
Приклад П5.2 – Економічне кодування станів МПА Мура S1
Виконаємо кодування станів МПА S1. За графом переходів Г(S1) (рис.1.8) складемо матрицю T. Для кожного рядка T розрахуємо:
p(αr,
βr)
– кількість
гілок, що сполучають вершини
і
;
p(αr)+ p(βr) – сумарне число появ αr і βr в матриці T.
Складемо матрицю M – результат сортування матриці T (п.2 А5.1).
-
αr
βr
p(αr, βr)
p(αr)+ p(βr)
αr
βr
p(αr, βr)
p(αr)+ p(βr)
T
=
1
2
=1
=4+4=8
M
=
1
2
1
8
221
5
1
8
2
3
=1
=4+2=6
2
4
1
7
2
4
=1
=4+3=7
2
6
1
7
2
6
=1
=4+3=7
1
4
1
7
3
5
=1
=2+4=6
5
7
1
7
1
4
=1
=4+3=7
5
6
1
7
4
7
=1
=3+3=6
1
8
1
7
1
5
=1
=4+4=8
2
3
1
6
5
7
=1
=4+3=7
3
5
1
6
5
6
=1
=4+3=7
4
7
1
6
666
8
1
6
6
8
=1
=3+3=6
7
8
1
6
7
8
=1
=3+3=6
1
8
=1
=4+3=7
Виконаємо кодування першого рядка матриці M: K(a1) = 000, K(a2) = 001.
Викресливши закодований перший рядок матриці M, складемо матрицю M'.
Черговий незакодований елемент γ = 2.
-
M'
=
1
5
γ = 5
M5
=
1
5
B5={ 1 }
2
4
5
7
2
6
5
6
1
4
3
5
5
7
5
6
1
8
2
3
3
5
4
7
6
8
7
8
Складемо множину невикористаних кодів, відносно закодованого стану a1, що мають відстань Хеммінга, яка дорівнює 1.
C1(1)
= {010, 100};
D5(1)
= C1(1)
= {010, 100} ≠
.
Обчислюємо вагову функцію W для кожного елемента множини D5(1).
|
γ |
δg |
p(γ, δg) |
|
K(δg) |
K(a1) = 000 |
|
5 |
1 |
1 |
|
010 |
1 |
|
|
|
|
|
100 |
1 |
W010 = 1∙1+1∙1 = 2; W100 = 1∙1+1∙1 = 2; min (W) = W010 = W100 = 2.
Виконаємо кодування стану a5: K(a5) = 010.
Викресливши закодовані рядки, складемо нову матрицю M'.
Черговий незакодований елемент γ = 6.
-
M'
=
2
4
γ = 4
M4
=
2
4
B4={ 1,2 }
2
6
1
4
1
4
4
7
5
7
5
6
1
8
2
3
3
5
4
7
6
8
7
8
Складемо множину невикористаних кодів, що мають відносно закодованих станів a1, a2 відстань Хеммінга, яка дорівнює 1.
C1(1)
= {100 }; C2(1)
= {101, 011 }; D4(1)
= {100, 101, 011 } ≠
.
Обчислюємо вагову функцію W для кожного елемента множини D4(1).
|
γ |
δg |
p(γ, δg) |
|
|
|
K(δg) |
K(a1) = 000 |
K(a2) = 001 |
|
4 |
1 |
1 |
|
|
|
100 |
1 |
2 |
|
2 |
1 |
|
|
|
101 |
2 |
1 | |
|
|
|
|
|
|
|
011 |
2 |
1 |
W100 = 1∙1+1∙2 = 3; W101 = 2∙1+1∙1 = 3; W011 = 1∙2+1∙1 = 3; min (W) = W100 = W101 = W011 = 3.
Виконаємо кодування стану a4: K(a4) = 101.
Викресливши закодовані рядки, складемо нову матрицю M'.
Черговий незакодований елемент γ = 6.
-
M'
=
2
6
γ = 6
M6
=
2
6
B6={ 2,5 }
5
7
5
6
5
6
6
8
1
8
2
3
3
5
4
7
6
8
7
8
Складемо множину невикористаних кодів, що мають відносно закодованих станів a2, a5 відстань Хеммінга, яка дорівнює 1.
C2(1)
= {011}; C5(1)
= {110, 011 }; D6(1)
= {011, 110 } ≠
.
Обчислюємо вагову функцію W для кожного елемента множини D6(1).
|
γ |
δg |
p(γ, δg) |
|
|
|
K(δg) |
K(a2) = 001 |
K(a5) = 010 |
|
6 |
2 |
1 |
|
|
|
011 |
1 |
1 |
|
5 |
1 |
|
|
|
110 |
3 |
1 |
W011 = 1∙1+1∙1 = 2; W110 = 3∙1+1∙1 = 4; min (W) = W011 = 2.
Виконаємо кодування стану a6: K(a6) = 011.
Викресливши закодовані рядки, складемо нову матрицю M'.
Черговий незакодований елемент γ = 7.
-
M'
=
5
7
γ = 7
M7
=
5
7
B7={ 4,5 }
1
8
4
7
2
3
7
8
3
5
4
7
6
8
7
8
Складемо множину невикористаних кодів, що мають відносно закодованих станів a4, a5 відстань Хеммінга, яка дорівнює 1.
C4(1)
= {111, 100}; C5(1)
= {110 }; D7(1)
= {111, 100, 110 } ≠
.
|
γ |
δg |
p(γ, δg) |
|
|
|
K(δg) |
K(a4) = 101 |
K(a5) = 011 |
|
7 |
4 |
1 |
|
|
|
111 |
1 |
1 |
|
5 |
1 |
|
|
|
100 |
1 |
3 | |
|
|
|
|
|
|
|
110 |
2 |
2 |
W111 = 1∙1+1∙1 = 2; W100 = 1∙1+3∙1 = 4; W110 = 1∙2+1∙2 = 4; min (W) = W111 = 2.
Виконаємо кодування стану a7: K(a7) = 111.
Викресливши закодовані рядки, складемо нову матрицю M'.
Черговий незакодований елемент γ = 8.
-
M'
=
1
8
γ = 8
M8
=
1
8
B8={ 1,6,7 }
2
3
6
8
3
5
7
8
6
8
7
8
Складемо множину невикористаних кодів, відносно закодованих станів a1, a6 і a7, що мають відстань Хеммінга, яка дорівнює 1.
C1(1)
= { 100
}; C6(1)
=
;
C7(1)
= { 110
};
D8(1)
= { 100, 110 } ≠
.
Обчислюємо вагову функцію W для кожного елемента множини D8(1).
|
γ |
δg |
p(γ, δg) |
|
|
|
K(δg) |
000 |
011 |
111 |
|
8 |
1 |
1 |
|
|
|
100 |
1 |
3 |
2 |
|
6 |
1 |
|
|
|
110 |
2 |
2 |
1 | |
|
7 |
1 |
|
|
|
|
|
|
|
W100 = 1∙1+1∙3+1∙2 = 6; W110 = 2∙1+2∙1+1∙1 = 5; min (W) = W110 = 5.
Виконаємо кодування стану a8: K(a8) = 110.
Викресливши закодовані рядки, складемо нову матрицю M'.
Черговий незакодований елемент γ = 3.
-
M'
=
2
3
γ = 3
M3
=
2
3
B3={ 2,5 }
3
5
3
5
Виконаємо кодування стану a3: K(a3) = 100.
В табл.5.1 наведені коди станів МПА Мура S1.
Таблиця 5.1 – Кодування станів МПА S1
-
ai
Код
T1
T2
T3
а1
0
0
0
а2
0
0
1
а3
1
0
0
а4
1
0
1
а5
0
1
0
а6
0
1
1
а7
1
1
1
а8
1
1
0
Алгоритм 5.2 – Розрахунок показника ефективності кодування станів
Розраховується кількість унікальних переходів МПА – P. Вона дорівнює кількості рядків матриці T (див. А5.1).
Відносно станів МПА складається матриця суміжності (див. табл.5.2). Рядки матриці відповідають коду стану-передавача K(am). Стовпці - коду стану-одержувача K(as).
В позиціях матриці суміжності, що відповідають переходам (am, as), записують результати обчислення відповідної вагової функції W.
Відносно кожного рядка матриці суміжності виконується підсумовування результатів обчислення вагових функцій WΣ.
Розділивши WΣ на кількість унікальних переходів P, одержують міру оцінки ефективності кодування станів автомата k.
Приклад П5.3 – Розрахунок показника k для МПА S1
-
αr
βr
p(αr, βr)
p(αr)+ p(βr)
T
=
1
2
1
8
1
5
1
8
2
4
1
7
2
6
1
7
1
4
1
7
5
7
1
7
5
6
1
7
1
8
1
7
2
3
1
6
3
5
1
6
4
7
1
6
6
8
1
6
7
8
1
6
Кількість унікальних переходів P = 13.
Таблиця 5.2 – Розрахунок міри ефективності кодування
-
а1
а2
а3
а4
а5
а6
а7
а8
000
001
100
101
010
011
111
110
а1
000
1
2
1
2
6
а2
001
2
1
1
4
а3
100
2
2
а4
101
1
1
а5
010
1
2
3
а6
011
2
2
а7
111
1
1
а8
110
Міра ефективності: WΣ /P = 1.46
WΣ =
19
Міра ефективності кодування дорівнює 1.46.