Кодирование состояний автоматов с целью минимизации аппаратурных затрат

Если сложный автомат имеет более двух внутренних состояний, то возникает проблема кодирования внутренних состояний.

Первый вопрос как определить разрядность R необходимую для кодирования всех состояний.

Число R определяется как наименьшее число, удовлетворяющее неравенству

где N _IS - количество внутренних состояний.

Определенное число R соответствует минимальной требуемой разрядности для представления кода в двоичной системе.

При кодировании внутренних состояний каждому состоянию автомата ставится в соответствие двоичная комбинация. Различные состояния соответствуют различным кодам.

Если N_IS =4, то R =2, т.е. понадобится 2 бита. Если N_IS =5, то R =3, т.е. необходимо 3 бита.

Проблема выбора становится очень сложной, т. к. количество способов кодирования внутренних состояний очень велико. Число вариантов кодирования определяются по формуле:

Если N _IS=10 и n=4, то значение M_var приближенно равно 29∙10⁹.

Из перестановки разрядов не следует увеличение сложности схемы или стоимости аппаратной части, таким образом, количество вариантов кодирования уменьшается, но все еще является большим:

Таким образом, полный перебор вариантов кодов внутренних состояний приводит к неприемлемым временным затратам.

Для ухода от полного перебора используются эвристические алгоритмы, которые используют определенные правила (эвристики), благодаря которым перебор сводится к минимуму. Таким образом, время решения задачи становится приемлемым, а результат становится близким к желаемому. Точный результат может гарантировать только полный перебор (если не существует детерминированного алгоритма получения точного результата).

Эвристический алгоритм кодирования – один из таких алгоритмов.

Сложность реализации комбинационных схем в автомате оценивается по значению функционала (коэффициента качества кодирования К_кач):

где p (a_m, a_s) – вес (число переходов из состояния a_m в состояние a_s); d^’ (a_m, a_s) – число сигналов возбуждения входов триггеров на переходе с номером h; H – общее число переходов.

Чем меньше значение К _КАЧ, тем меньше средняя сложность системы булевых функций, описывающих комбинационную часть (КЧ) автомата.

Число сигналов возбуждения d^’ (a_m, a_s) на переходе h зависит от кодов состояний k (a_m) и k (a_s) и типа триггера, используемого в запоминающей части (ЗЧ) автомата.

Выбор варианта кодирования в большой степени влияет на сложность комбинационной части. Выбор зависит от типа триггера. В соответствии с типом триггера используется своя стратегия кодирования.

Выбор стратегии кодирования.

Стратегия кодирования внутренних состояний (ВС) зависит от особенностей матрицы переходов триггера, используемого в запоминающей части автомата.

Все типы триггеров по типу МП можно разделить на пять групп. Для триггеров первой группы (типа T, RS, KJ, и т.п.) МП имеет единичные значения сигналов возбуждения во второй и третей строках

Qt – Qt +1	T
0–0
0–1
1–0
1–1

Компонент вектора соответствует числу единичных сигналов возбуждения для каждого типа перехода: 0–0; 0–1; 1–0; 1–1.

Для триггеров первой группы целесообразно при кодировании ВС использовать стратегию минимизации суммарного числа изменений состояний элементов памяти (триггеров) на всех переходах автомата. В этом случае минимизируется число термов в минимальных дизъюнктивных нормальных формах (МДНФ) функций выхода и функций возбуждения входов триггеров, и достигается минимальное значение критерия К _кач.

МП триггеров второй группы типа Т *, (K * J *) и т. п. имеют единицы в первой и четвертой строках:

Qt – Qt +1	T *
0–0
0–1
1–0
1–1

Для триггеров второй группы следует использовать стратегию максимизации суммарного числа изменений состояний элементов памяти на всех переходах автомата. Если на некотором переходе автомата из состояния а_i в состояние а_j все триггеры изменяют свои состояния на противоположные, то число единичных сигналов возбуждения на этом переходе равно нулю, что для триггеров первой группы не возможно.

МП триггеров третей группы типа D содержит единицы во второй и четвертой строках:

Qt - Qt +1	D
0–0
0–1
1–0
1–1

Наличие единицы в МП D -триггера непосредственно определяются наличием единиц в коде состояния перехода Q _t+1.

Поэтому для триггеров D -типа следует использовать частотную стратегию кодирования, согласно которой состояния с максимальным числом появлений кодируются нулевой комбинацией. Следующие n состояний (n-разрядность кода ВС) с убывающим числом появления должны быть закодированы комбинациями с одной единицей. Затем для кодирования оставшихся незакодированных состояний используют вначале коды с двумя единицами, затем с тремя и т. д. до тех пор, пока все состояния не будут закодированы.

Применение триггеров третей группы может минимизировать функционал К _кач по сравнению с триггерами первой группы в случае, если частоты появлений различных состояний сильно разнятся.

При использовании триггеров четверной группы (типа D * и т. п.) единицы имеются в первой и третьей строках матрицы:

Qt – Qt +1	D *
0–0
0–1
1–0
1–1

В этом случае также имеет смысл использовать частотную стратегию кодирования внутренних состояний. Но для кодирования состояния с максимальным числом появления следует использовать единичную кодовую комбинацию (нулевое число сигналов возбуждения на всех переходах в это состояние).

Затем следует использовать n кодовых комбинаций с одним нулем, затем с двумя нулями, с тремя и т. д.

В последнюю очередь используют нулевую кодовую комбинацию. Легко увидеть, что триггера четвертой и третьей групп по возможностям идентичны и поэтому на практике достаточно использовать только одну из этих групп (третью).

К триггерам пятой группы относятся триггер с инверсными входами R * S * и т. п., имеющий МП вида:

Qt – Qt +1	R * S *
0–0	b 1 1
0–1	1 0
1–0	0 1
1–1	1 b 2

Легко увидеть, что число сигналов возбуждения на переходе из состояния а _m в состояние а _s не зависит от кодов состояний и всегда равно n – разрядности кода ВС.

Такую стратегию кодирования отнесем к безразличной. Её нецелесообразно применять на практике, так как число единичных значений сигналов возбуждения для триггеров пятой группы в два раза больше, чем для триггеров предыдущих групп.

Таким образом, ограничиться на практике возможностью использования в запоминающей части автоматов только триггеров первых трех групп (Т, Т * и D) и выбирать для построения запоминающей части тот из указанных триггеров, который позволяет минимизировать значение функционала К_кач.

Рассмотрим эвристический алгоритм кодирования состояний автомата для первого типа триггеров.

Главная цель данного алгоритма получить кодировку с минимальной разницей кодов перехода между начальным и конечным состоянием.

Алгоритм состоит из следующих этапов:

1. Построить по графу переходов или по структурной таблице автомата матрицу

состоящую из всех пар номеров , , для которых , т.е. в автомате есть переход из в .

2. Упорядочить строки матрицы T так, чтобы по возможности выполнялось условие упорядочения весов p ₁ ³ p ₂ ³... ³ p_r ³... ³ p_R и обязательно выполнялось условие зацепления

Условие зацепления означает, что один из номеров состояния r -й строки (a_{a 1} или a_{b 1})должен присутствовать в любой из предшествующих строк (не обязательно в (r -1)-й строке). Упорядочение выполнить за счет перестановки строк матрицы Т. В результате получим матрицу М.

3. Закодировать состояния из первой строки матрицы:

4. Вычеркнуть из матрицы М строки с полностью закодированными состояниями. Получить в результате матрицу М '.

5. Выбрать из первой строки М ' незакодированный элемент и обозначить его через .

6. Построить матрицу , выбрав из М ' строки, содержащие . Пусть - множество элементов из матрицы , которые уже закодированы. Их коды соответственно.

7. Для каждого найти - множество кодов, соседних с и еще не занятых для кодирования состояний автомата. Построить множество . Если , то построить , где - множество кодов, у которых кодовое расстояние по отношению к коду равно двум. Если и , то строить аналогично до тех пор, пока (К=1,2,...). Пусть

8. Для каждого найти оценочную функцию

где - кодовое расстояние Хемминга между кодовыми комбинациями , ; p _r - вес r -й строки матрицы .

9. Из множества выбираем для кодирования состояние код , для которого W_g = min W_g.

10. В матрице М ' вычеркнуть строки с полностью закодированными состояниями. Получить в результате новую матрицу М '.

11. Проверить новую матрицу М '. Если в матрице М ' не осталось ни одной строки, то перейти к п. 12, если остались - то к п. 4.

12. Вычислить значения коэффициентов качества кодирования

,

где Н - число строк структурной таблицы, т.е. число всех переходов.

Рассмотрим пример, в котором необходимо закодировать ВС автомата, заданного графом перехода (рис. 5.15).

Рисунок 5.15 – Граф переходов

Строим матрицу Т.

T =

1 2 3 2 2 4 4 3 2 5 5 4 4 5 5 1

5 4 4 5

эквивалентно

5 4

T =

1 2 3 2 2 4 4 3 2 5 5 4 5 1

М =

5 4 2 5 5 1 1 2 3 2 2 4 4 3

М ’=

2 5 5 1 1 2 3 2 2 4 4 3

N_BC =3; K ₅=000; K ₄=001, убираем первую строку из матрицы М – B ₁={(5,4)};

Формируем матрицу M ₂, включаем в нее строки, содержащие g =2, где один элемент закодирован, а другой нет (т.е. 2 – 5, 2 - 4) K ₂=?. Записываем список кодов претендентов D¹₂. Вычисляем оценочную функцию:

M 2=

2 5 2 4

;

;

W ₁₀₀=|2 5|×1+|2 4|×1=|100Å000|×1+|100Å001|×1= 1×1+2×1=3;

W ₀₁₀= 1×1+2×1=3;

W ₁₀₁= 2×1+1×1=3;

W ₀₁₁= ;

Примем в качестве К ₂=100;

Убираем B ₂={(2,5), (2,4)}строки из матрицы М'.

М’=

5 1 1 2 3 2 4 3

М1=

5 1 1 2

К ₄=001; К ₅=000; К ₂=100; K ₁=?;

={000, 110, 101}; ={100, 010, 001};

.

К ₁=010;

Убираем B ₃={(5,1), (1,2)} строки из матрицы М'.

М ’=

3 2 4 3

g=3; M 3=

3 2 4 3

K ₂=100; K ₄=001; K ₃=?;

К ₃=101;

Переходим к п. 12, т. к. в М’ нет ни одной строки.

(см. рис. 5.16)

Рисунок 5.16 – Граф переходов с закодированными состояниями

Алгоритм кодирования состояний автомата для второго типа триггеров (с инверсными входами) имеет тот же вид, за исключением стратегии кодирования, предполагающей подбор кодов претендентов с максимальными отличиями.

Далее сформулируем алгоритм быстрого кодирования ВС с перебором типа триггера для запоминающей части и рассмотрим пример кодирования ВС по этому алгоритму.

Алгоритм быстрого кодирования внутренних состояний автомата с выбором типа триггера содержит следующие шаги.

1. Строится граф переходов (ГП) автомата.

2. Выделяется на ГП самый длинный (по числу вершин) цикл. Для ряда автоматов этот цикл будет являться циклом Гамильтона (для Т *- триггера выбирается максимальный цикл с четным числом состояний).

Гамильтонов цикл (или контур) это ориентированный цикл (контур), проходящий ровно один раз через каждую вершину графа.

3. В соответствии со стратегией кодирования для указанного типа триггера кодируются состояния из этого цикла.

4. Для оставшихся незакодированных состояний d _j используется эвристический алгоритм кодирования, который был рассмотрен выше.

5. Вычисляется коэффициент качества кодирования.

6. Шаги 3-6 повторяются для всех рассматриваемых типов триггеров (вначале для Т -триггера, затем для Т *).

7. Кодируются состояния с использованием частотного алгоритма, если используется D* -триггер или D -триггер (как в примере на рис. 5.15).

8. Для запоминающей части выбираем тип триггера с минимальным значением числа сигналов возбуждения (минимальным значением К_кач). Если таких типов триггеров несколько, выбираем любой из них.

ГП автомата Мили для трех типов триггеров Т, Т * и D приведены на рис. 5.15.

Рисунок 5.15 – ГП автомата Мили для трех случаев Т, Т * и D -триггеров

Для случая использования Т *-триггера целесообразно выделить по возможности самый длинный цикл с четным числом состояний и закодировать парами противоположных (инверсных) кодов пары наиболее связанных состояний.

Так в четном цикле из состояний а₁, а₂, а₃, а₄ между парами а₁, а₂ и а₃, а₄ всего по одной дуге. Закодируем а₂ кодом К (а ₂)=000; К (а ₃)=111; а ₄ – кодом К (а₄)=001, а состояние а₁ – кодом К (а₁)=110. В результате на других циклах будет только две отметки: Т * _i. Код оставшегося состояния К (а₅) вычисляется с использованием эвристического алгоритма кодирования, К (а₅)=010.

В соответствии с МП Т *-триггера число отметок сигналов возбуждения на переходе равно числу разрядов, сохраняющих неизменное значение.

Для случая Т -триггера выделяем самый длинный цикл из состояний а₁, а₂, а₃, а₄, а₅ и назначаем для этих состояний соседние коды К (а₁)=000; К (а₂)=001; К (а₃)=011; К (а₄)=010; К (а₅)=110.

Для D -триггера используется частотный алгоритм.

Если в графе автомата много петель, лучше использовать триггеры с прямыми входами (первый тип), если петель нет, бывает, что выгоднее использовать триггеры с инверсными входами.