Кодування станів та складність комбінаційної схеми автомата
Аналогічно кодування внутрішніх станів дляD-тригерів можна кодувати вихідні сигнали будь-якого типу тригерів, тобто. що частіше виробляється даний вихідний сигналwi, то менше одиниць у його коді. Так для автомата (рис.41.) маємо:
Передбачається самостійно закінчити синтез автомата при даному кодуванні та за будь-якого іншого. Результати порівняти.
Евристичний алгоритм кодування.
Даний алгоритм мінімізує сумарне число перемикання елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базіT,RS,JK-тригерів. Для даних типів тригерів (на відміну відD-тригерів!) на кожному переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа перемикань тригерів призводить до зменшення кількості одиниць відповідних функцій збудження, що за відсутності мінімізації однозначно призводить до спрощення комбінаційної схеми автомата.
Введемо деякі визначення.
НехайГ(S) – неорієнтований граф переходів автоматаS. Вершини графа ототожнюються із станами автомата. Вершиниiіjз'єднані ребром, якщо є перехід заiіаjабо навпаки.
Позначимоq(i, j) число різноманітних переходів автомата заiваj. Кожному ребру (i, j) графаГ(S)поставимо у відповідність вага ребрар(i, j) =q(i, j)+q(j, i).
Функціяw(i, j) має простий фізичний зміст. Перехід автомата заiваj(або навпаки) супроводжується перемиканням стільки тригерів, скількими компонентами відрізняються коди цих станів,тобто. їх число дорівнюєw(i, j). Отже, при переході автомата по всіх ребрах, що з'єднують станиаiіаj(їх числоp(i, j)!) всього переключиться кількість тригерів, що дорівнюєp(i, j)d(i ,j) =w(i, j).
Але тоді функція показує, скільки перемикається тригерів при проходженні автомата по всіх можливих переходах. Функціяwпоказує, скільки всього одиниць у функції збудження, тобто. дозволяє оцінювати складність комбінаційної схеми автомата.Wможна розглядати як таку собі цільову функцію, мінімум якої визначить таке кодування, при якому комбінаційна схема найбільш проста. До речі, мінімальна кодова відстань між різними станами дорівнює 1 і якщо вдається закодувати всі стани сусіднім кодуванням, то очевидно, щоwбуде мінімально можливим і рівним
З виразу дляwвипливає, що перехід заiваi, для якогоd(i,i)=0, не впливає наw(що цілком очевидно, якщо врахувати, що на цьому переході жоден тригер не перемикається).
Розглянемо застосування евристичного алгоритму конкретному прикладі автомата, заданого таблицями переходів і виходів (рис.41. ). Для цього автомата можна побудувати орієнтований граф (без урахування петель), представлений на рис.42. На кожному ребрі вказано його вагу.