9.2.3.1 Универсальный способ кодирования
Прежде всего опишем универсальный способ кодирования, позволяющий с помощью введения дополнительных состояний выполнить кодирование состояний для любого асинхронгного автомата. Согласно этому способу, для кодирования автомата, имеющего m состояний, требуется m элементов памяти. Каждому состоянию приписывается код, содержащий одну единицу и остальные нули. Эта единица расположена в позиции, номер котой определяется номер состояния. Для каждой пары состояний si и sj, между которыми существует хотябы один переход, вводится дополнительное неустойчивое состояние, которому приписывается код, содержащий две единицы в позициях, определяемых номерами сотояний si и sj. Такое дополнительное состояние может использоваться для всех переходов между состояниями si и sj, поскольку они должны выполняться при действии различных входных сигналов. Кроме того, введение таких дополнительных состояний всегда возможно, поскольку коды с двумя единицами не используются для кодирования основных состояний.
Для пояснения описанного способа рассмотрим кодированмие состояний автомата А1, заданного табл. 2. Диаграмма этого автомата изображена на рис. 4,а. Чтобы сделать процедуру кодирования нагляднее, обычно использщуют граф связей автомата. Такой граф строят следующим образом. Каждому
состоянию автомата ставят в соответствие узел графа, а затем каждую пару узлов соединяют ребром, если между состояниями, соответствующими этим узлам, определен хотя бы один переход. Граф связей автомата А1 приведен на рис. 4,б.
рис4
a) b)
в) г)
9.2.3.2. Эвристический способ кодирования
Универсальный способ кодирования редко используется на практике для реализации автоматов с большим числом состояний, поскольку схемы в этом случае получаются весьма сложными за счет большого чсисла элементов памяти. Чаще всего при решении практических задач применяют эвристический способ, основанный на последовательном введении дополнительных состояний и увеличении числа внутренних переменных. В качестве иллюстрации этого способа рассмотрим два примера.Прежде всего попытаемся реализовать автомат А1 с использованием двух внутренних переменных. Для этого воспользуемся графом связи этого автомата, изображенным на рис. 4,б. Нетрудно убедиться в том, что закодировать такой граф и помощью четырех кодов таким образом, чтобы при каждом переходе изменялось значение только одной переменной, невозможно. Выберем вариант кодирования, при котором наибольшее число переходов выполняется с изменением одной переменной (в нашем примере два перехода), и введем дополнительное состояние для перехода, при котором изменяются две переменные. В результате получаем граф, приведенный на рис. 5. Таблица переходов автомата при таком кодировании изображена в виде табл. 4.
,
В качестве второго примера рассмотрим кодирование автомата А2, заданного табл. 5. Граф связей этого автомата приведен на рис. 6. Для однозначного кодирования четырех состояний достаточно двух внутренних переменных. Однако выполнить кодирование без состояний с помощью двух переменных оказывается невозможно. Увеличим число внутренних переменных до трех и снова попытаемся произвести кодирование без введения дополнительных состояний.
Рассматривая различные варианты, нетрудно убедиться, что получить кодирование без состояний в этом случае также невозможно. Выберем вариант кодирования, позволяющий получить наибольшее число переходов с изменением одной переменной и введем дополнительные состояния. В результате получаем граф автомата, изображенный на рис. 6,б. Используя этот граф, нетрудно построить кодированную таблицу переходов автомата А2 (табл. 6).
В заключение отметим, что описанный универсальный способ кодирвания не является единственным. Например, в работах [1, 3] можно найти описание способа Хаффмэна, который позволяет закодирвать любой автомат, имеющий m состояний, используя 2]log2m[ - 1 элементов памяти, где ]a[ означает ближайшее целое не меньше а. На практике же для построения схем без состояний чаще всего применяют структурный способ, основанный на использовании удвоенного числа элементов памяти. Этот способ будет рассмотрен подробнее в параграфе, посвященном построению элементов памяти, а также в следующем выпуске.
