б) Построение таблицы переходов по заданной таблице последовательностной машины

Пусть требуется на устойчивых состояниях построить последовательностную машину, заданную в форме исходной таблицей — совмещенной таблицей автомата и преобразователя (табл. 5.6).

Таблица 5.6

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

Это перестроение таблиц продемонстрируем здесь на примере табл. 5.6.

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

Подсчитывается величина где — число различных состояний входа. В нашем случае . Далее заготовляется таблица (табл. 5.7), имеющая такое же количество столбцов, как и исходная, а количество строк в ней делается равным . Входная (верхняя) строка табл. 5.7 заполняется так же, как и исходная, символами , а во входной (в крайний левый) столбец вписываются подряд символы новой переменной . Для нашего случая . Далее начинается заполнение клеток таблицы. В первый столбец вписываются подряд, начиная с первой строки, различные символы (общим числом ), взятые из первого столбца исходной таблицы. В случае исходной табл. 5.6 это будут (последовательность расположения этих символов в столбце табл. 5.7 может быть любой). В эти же клетки вписываются соответствующие строкам символы . Этим клеткам соответствуют равновесные состояния; их отметим квадратиками. Во втором столбце таким же образом заполняется клеток, но заполнение идет не с первой строки таблицы, а с первой пустой строки. В нашем случае в четвертую и пятую клетки второго столбца вписываются пары Подобным же образом заполняется по клеток каждого столбца.

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

Таблица 5.7

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

В нашем случае получаем вписанными во вторую, третью и четвертую клетки первой строки символы Точно так же поступая с каждой строкой табл. 5.7, заполним все ее клетки символами . Теперь в клетки (табл. 5.7), заполненные лишь символами , вписываем еще и символы и делаем это так, чтобы в одном столбце одним и тем же соответствовали одни и те же , иначе говоря, в каждом столбце мы разносим в соответствии с этим условием символы , взятые из квадратов. Таким образом, табл. 5.7 оказывается заполненной. Она эквивалентна так называемой таблице переходов Хафмана. Ее следует интерпретировать как таблицу «быстрой» последовательностной машины, заданной в форме П — П. Эта «быстрая» машина, если в ней наблюдать переменные лишь в равновесных состояниях, будет работать как исходная.