Евристичний алгоритм кодування

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

Нехай Г(S) - неорієнтований граф переходів автомата S. Вершини графа ототожнюються із станами автомата. Вершини i і j сполучені ребром, якщо є перехід з q_i і q_j або навпаки.

Позначимо g(i, j) число всіляких переходів автомата з q_i в q_j. Кожному ребру (i, j) графа Г(S) поставимо у відповідність вагу ребра

р(i, j) = q(i, j) + g(j, i).

Введемо функцію

w(i, j) = р(i, j)(d(i, j),

де d(i, j) - число компонентів, якими коди станів q_i в q_j відрізняються один від одного (тобто кодова відстань між кодами q_i в q).

Функція w(i, j) має простий фізичний сенс. Перехід автомата з q_i в q_j (чи навпаки) супроводжується перемиканням стількох тригерів, скількома компонентами відрізняються коди цих станів, тобто їх число рівне w(i, j). Отже, під час переходу автомата по усіх ребрах, які сполучають стани q_i і q_j (їх число p(i, j)!) усього перемкнеться кількість тригерів, яка дорівнює

p(i, j)(d(i, j) =w(i, j).

Але тоді функція

показує, скільки усього перемикається тригерів при проходженні автомата по усіх можливих переходах.

Функція w показує, скільки усього одиниць у функції збудження, тобто дозволяє оцінювати складність комбінаційної схеми автомата. W можна розглядати як деяку цільову функцію, мінімум якій визначить таке кодування, при якому комбінаційна схема найбільш проста. Мінімально кодова відстань між різними станами дорівнює 1 і якщо вдається закодувати усі стани сусіднім кодуванням, то очевидно, що w буде мінімально можливим і дорівнює

,

тобто сумарному числу переходів для автомата.

З виразу для w витікає, що перехід з q_i в q_i, для якого d(i, i)= 0, не впливає на w (що цілком очевидно, якщо врахувати, що на цьому переході жоден тригер не перемикається).

Розглянемо застосування евристичного алгоритму на конкретному прикладі автомата. Для цього автомата можна побудувати орієнтований граф (без урахування петель), представлений на рис 2.15. На кожному ребрі вказана його вага.

Рисунок 2.15 – Орієнтований граф автомата

Евристичний алгоритм складається з наступних кроків:

1. Будуємо матрицю , що складається з усіх пар номерів (i, j), для яких

р(i, j) ¹0 (тобто в автоматі є перехід з q_i в q_j або навпаки) і i<j. Для кожної пари в матриці вказуємо її вагу р(i, j), яка співпадає з вагою ребра що сполучає q_i і q_j.

		i	j	p(i,j)
T	=

2. Упорядкуємо рядки матриці , для чого побудуємо матрицю таким чином. У перший рядок матриці помістимо пару (a,b), з найбільшою вагою р (a,b). В нашому випадку (a,b) = (2,3), р (2,3) = 3. З усіх пар, що мають загальний компонент з парою (a,b), вибирається пара (g,d) з найбільшою вагою і заноситься в другий рядок матриці . Ясно, що { a,b }×{ g,d }¹0. Потім з усіх пар, що мають загальний компонент хоч би з однією з внесених вже в матрицю пар вибирається пара з найбільшою вагою і заноситься в матрицю і т.д. У разі рівності ваг пар обчислюються суми ваг компонентів пар (вагою р (a) компонента a називається числом появ a в матриці ) і в матрицю заноситься пара з найбільшою сумою ваг.

У даному автоматі на друге місце услід за парою (2,3) претендують пари: (1,2) з р (1,2) = 2; (3,4) з р (3,4) = 2, (3,5) з р (3,5) = 2

Для визначення того, яка пара займе друге місце в матриці знаходимо ваги компонентів пар:

р(1) = 3 р(2) = 3 р(1) + р(2) = 6

р(3) = 4 р(4) = 2 р(3) + р(4) = 6

р(3) = 4 р(5) = 2 р(3) + р(5) = 6

В даному випадку для усіх пар співпадають і їх ваги і ваги їх компонентів. Тому на друге місце матриці може бути поставлена будь-яка з пар (1,2) (3,4) (3,5). Але тоді на 3-м і 4-м будуть інші дві. Виконавши впорядковування усіх пар, отримаємо матрицю у виді:

		i	j	p(i, j)
M	=

3. Визначаємо розрядність коду для кодування станів автомата (кількість елементів пам'яті - тригерів). Всього станів M =5. Тоді

R = ]log₂M[ = ]log₂5[ =3.

Закодуємо стани з першого рядка матриці таким чином: K₂ = K(q₂) = 000; K3 = K(q₃) = 001.

Для зручності кодування ілюструватимемо цей процес картою Карно:

4. Викреслимо з матриці перший рядок, відповідний закодованим станам q₂ і q₃. Отримаємо матрицю .

		i	j	p(i, j)
M'	=

5. Через впорядковування п.2 в першому рядку закодований рівно один елемент. Виберемо з першого рядка незакодований елемент і позначимо його g. (В нашому випадку g = 1).

6. Будуємо матрицю , вибравши з строчки, що містять g.

				i	j	p(i, j)
M g	=	M'	=

Нехай B g = {g₁,..,g_F } - множина елементів з матриці, які вже закодовані. Їх коди K_g1,.., K_gF відповідно. У нашому випадку:

B_g = B₃ = {2,3} K₂ = 000 K₃ = 001.

7. Для кожного K_gf (f =1,.., F) знайдемо С¹_gf - множину кодів, сусідніх з K_gf і ще не зайнятих для кодування станів автомата. (Для сусідніх кодів кодова відстань d =1).

K ₂ = 000 = {100, 010}

K ₃ = 001 = {011, 101}.

Побудуємо множину

Якщо виявляється, що , то будуємо нову множину , де - множина кодів, у яких кодова відстань до коду дорівнює 2 і т.д.

8. Для кожного коду з безлічі D_g знаходимо кодову відстань до коду .

K ₂ = 000 K ₃ = 001

d (100, 000) = 1 d (100, 001) = 2

d (010, 000) = 1 d (010, 001) = 2

d (011, 000) = 2 d (011, 001) = 1

d (101, 000) = 2 d (100, 001) = 1

9. Знаходимо значення функції w для кожного коду з множини D_g.

10. З множини D_g вибираємо код K_g, у якого вийшло мінімальне значення w в п.9. Вибираємо код для стану q₁ К₁ =100.

11. З матриці викреслюємо рядки, в яких обидва елементи вже закодовано, внаслідок чого отримаємо нову матрицю . Якщо в новій матриці не залишилося жодного рядка, то кодування закінчене. Інакше повертаємося до п.5. У нашому випадку маємо:

		i	j	p(i,j)
M’	=

К ₂ = 000 = {010}

K ₃ = 001 = {011, 101}

K ₂ = 000 K ₃ = 001

d (010, 000) = 1 d (010, 001) = 2

d (011, 000) = 2 d (011, 001) = 1

d (101, 000) = 2 d (101, 001) = 1

Вибираємо К ₄ = 101.

К ₁ = 100 = {110}

K ₂ = 000 = {010}

К ₃ = 001 = {011}

К ₁ = 100 K ₂ = 000 K ₃ = 001

d (110, 100) = 1 d (110, 000) = 2 d (110, 001) = 3

d (010, 100) = 2 d (010, 000) = 1 d (010, 001) = 2

d (011, 100) = 3 d (011, 000) = 2 d (011, 001) = 1

Вибираємо К ₅ = 011.

Так як усі стани автомата закодовані, то робота алгоритму закінчується. Загальна кількість перемикань тригерів:

Мінімальна можлива кількість перемикань (якби стани були закодовані сусіднім кодуванням)

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

Розглянутий алгоритм кодування є машино-орієнтовним, існують програми, що реалізовують цей алгоритм.

Необхідно відмітити, що використання алгоритму кодування для D - тригерів або евристичного алгоритму для інших типів тригерів забезпечує найбільш просту з точки зору реалізації схему, але при цьому можливі перегони. Для радикального усунення останніх використовують апаратні методи - тригери з подвійною пам'яттю: тригери, керовані фронтом і т.д.

Контрольні питання і завдання

1. Що називають перегонами або змаганнями в автоматах?

2. Що розуміють під стійкістю функціонування автомата?

3. Що таке сусіднє кодування?

4. Які перегони вважаються критичними? некритичними?

5. Які існують методи усунення критичних перегонів?

6. Перерахуєте основні пункти алгоритму кодування для D -тригерів.

7. Перерахуєте основні пункти евристичного алгоритму кодування.

8. Що називається коефіцієнтом ефективності кодування?

9. У чому фізичний сенс коефіцієнт ефективності кодування?