6.2 Структурное кодирование входных, выходных сигналов и состояний автомата

На первоначальных этапах проектирования конечных автоматов их входные и выходные сигналы представляются некоторыми абстрактными символами, которые понятны проектировщикам, но принципиально не могут быть поняты синтезируемым автоматом. Аналогичными символами некоторого абстрактного алфавита первоначально представляются и состояния автомата, общее количество которых определяется в результате разметки ГСА проектируемого автомата. По этой причине необходимо представить все абстрактные символы, обозначающие входные, выходные сигналы и состояния автомата, некоторым стандартным образом, причем так, чтобы такое обозначение было бы однозначным, технически реализуемым и “понятным” тем элементам, на которых предполагается реализация синтезируемого автомата. Такое единообразное представление всех абстрактных символов, необходимых для задания автомата, и называют структурным кодированием входных, выходных сигналов и состояний автомата.

В настоящее время самым распространенным способом структурного кодирования является двоичное кодирование. Структурное кодирование проводится в два этапа: определяется количество () двоичных разрядов, необходимое и достаточное для двоичного представления некоторого множества абстрактных символов; осуществляется сопоставление каждому отдельному абстрактному символу  - разрядного двоичного кода.

В самом простейшем случае величина  находится на основе следующего соотношения:

 = 1 + int ( log₂ ( -1)), (6.1)

где  - мощность множества кодируемых символов абстрактного алфавита;

int (w) – целая часть (w).

В

64

том случае, когда алгоритм функционирования синтезируемого автомата задан в виде граф-схемы алгоритма (ГСА), то структурного кодирования абстрактных символов входного и выходного алфавитов не производят. Это обусловлено тем, что при описании работы автомата в виде ГСА каждое логическое условие x_i = {1,0} и каждый выходной сигнал y_j = {1,0}, то есть уже имеют двоичное кодирование.

Для структурного кодирования состояний синхронного автомата используются специальные методы кодирования, наиболее распространенными из которых являются:

• тривиальное кодирование;

• эффективное кодирование (1-й способ);

• эффективное кодирование (2-й способ).

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

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

Для всех этих способов структурного кодирования достаточное и необходимое количество триггеров определяется на основании соотношения (6.1).

При тривиальном кодировании исходными данными является мощность символов абстрактного алфавита состояний автомата, полученных в результате разметки ГСА. Количество двоичных разрядов, необходимое и достаточное для структурного кодирования состояний автомата, определяется соотношением (6.1). Данным соотношением, по сути, определяется количество триггерных схем, необходимых для реализации блока памяти автомата. После определения количества двоичных разрядов, необходимых для структурного кодирования, каждому абстрактному символу состояния автомата сопоставляется двоичный код, отличный от всех остальных и без какого – либо регламентирующего правила, вплоть до случайного сопоставления. Структурный код начального состояния автомата используется для определения соответствующих асинхронных входов R и S, которые должны быть объединены и подключены к сигналу начальной установки.

П

65

риэффективном кодировании по первому способу количество двоичных разрядов (т. е. число элементов памяти), необходимых для структурного кодирования, определяется также как и при тривиальном кодировании. Затем по таблице переходов, графу автомата или расширенной таблице переходов определяется количество вхождений в каждое из состояний автомата (например, из графы а_s в таблицах 5.1 и 5.2). Состояния автомата, т. е. соответствующие им символы абстрактного алфавита, упорядочиваются в порядке убывания числа вхождений в каждое состояние. То состояние автомата, в которое имеется максимальное число вхождений, кодируется двоичным кодом, содержащем одну единственную единицу в каком – либо двоичном разряде. Последующие состояния автомата кодируются кодами, также содержащими одну единственную единицу, но отличающимися между собой. По мере исчерпания таких кодов для кодирования используются структурные коды, содержащие по две единицы в каких – либо разрядах. Эти коды также должны быть различны между собой. Затем используются структурные коды, содержащие по 3, 4 … единицы, до тех пор, пока все состояния автомата не окажутся закодированными.

Найденный структурный код начального состояния автомата используется для определения соответствующих асинхронных входов R и S, которые должны быть объединены и подключены к сигналу начальной установки.

При эффективном кодировании по второму способу (этот способ применяется только для автоматов типа Мура) состояния автомата (из графы а_m в таблице 5.2) упорядочиваются в следующем порядке: первым выбирается такое состояние автомата, в котором формируется максимальное количество выходных сигналов, после чего все остальные состояния автомата упорядочиваются в порядке уменьшения количества одновременно формируемых выходных сигналов. Далее кодирование производится таким же образом, как и для эффективного кодирования по первому способу.

Найденный структурный код начального состояния автомата используется для определения соответствующих асинхронных входов R и S, которые должны быть объединены и подключены к сигналу начальной установки.

Процесс структурного кодирования кратко проиллюстрируем следующим примером.

Пусть в результате разметки некоторой ГСА определено следующее множество (А) внутренних состояний автомата, каждое из которых представлено следующими абстрактными символами: а₁, а₂,а₃, а₄, а₅, т.е.

А = { а₁, а₂,а₃, а₄, а₅}. (6.2)

Предположим, что символом а₁ отмечено начальное состояние синтезируемого автомата.

Мощность множества А (или количество внутренних состояний) равна:

66

А = 5. (6.3)

На основании (6.1) находим потребное количество триггеров (r), необходимое для реализации блока памяти:

r = 1 + int ( log₂ (А -1)) = 1 + int ( log₂ (5 -1)) = 3. (6.4)

Так как предполагается структурное кодирование состояний автомата в двоичном коде, который является позиционным кодом, следует условиться о том, что каждый триггер будет соответствовать определенному разряду трех - разрядных двоичных чисел. С учетом данного обстоятельства, а также рис. 2.1, для единичных выходов каждого триггера введем соответствующие обозначения, а именно: d₁,d₂,d₃, имея в виду, что d₁ – младший разряд структурного двоичного кода, а d₃ – старший разряд структурного кода. Далее реализуется один из способов структурного кодирования, конечный итог которого может быть представлен таблицей 6.5:

Таблица 6.5

Структурные коды
Абстрактные символы		d3	d2	d1
	а1	1	0	1
	а2	0	0	1
	а3	1	1	0
	а4	1	0	0
	а5	0	1	0

Т

67

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