Page 85 - 4128

Позначимо q(i, j) число всіляких переходів автомата з аi в
аj. Кожному ребру (i, j) графа Г(S) поставимо у відповідність вагу
ребра р(i, j)= q(i, j)+ q(j, i).
Введемо функцію w(i, j)= р(i, j) d(i, j), де d(i, j) – число
компонентів, якими коди станів аi в аj відрізняються один від
одного (тобто кодова відстань між кодами аi в аj).
Функція w(i,j) має простий фізичний сенс. Перехід
автомата з аi в аj (або навпаки) супроводжується перемиканням
стількох тригерів, скількома компонентами відрізняються коди
цих станів, тобто їх число рівне w(i,j). Отже, під час переходу
автомата по всіх ребрах, сполучаючих станах аi і аj (їх число p(i,
j)!) всього перемкнеться кількість тригерів, рівна p(i,
j)d(i,j)=w(i,j).
Але тоді функція
w   w , (i ) j   p i , ( j )d , (i ) j показує, скільки всього
, (i ) j  (Sд ) , (i ) j  (Sд )
перемикається тригерів при проходженні автомата по всіх
можливих переходах. Функція w показує, скільки всього одиниць
у функції збудження, тобто дозволяє оцінювати складність
комбінаційної схеми автомата. W можна розглядати як якусь
цільову функцію, мінімум якої визначить таке кодування, при
якому комбінаційна схема найпростіша. До речі, мінімальна
кодова відстань між різними станами рівна 1 і якщо вдається
закодувати всі стани сусіднім кодуванням, то очевидно, що w буде
мінімально можливим і рівним w   p , (i ) j , тобто сумарному
, (i ) j  (Sд )
числу переходів для автомата.
З виразу для w витікає, що перехід з аi в аi, для якого
d(i,i)=0, не впливає на w (що цілком очевидне, якщо врахувати,
що на цьому переході жоден тригер не перемикається).
Розглянемо застосування евристичного алгоритму на
конкретному прикладі автомата, заданого таблицями переходів і
виходів (рис.4.5). Для даного автомата можна побудувати
орієнтований граф (без урахування петель), представлений на
рис.4.6. На кожному ребрі вказана його вага.

84