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

Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе 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)× 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 можно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным , т.е. суммарному числу переходов для автомата.

Из выражения для w следует, что переход из а_i в а_i, для которого d(i,i)=0, не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

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