Кодирование автоматов

Все переменные, приведенные на рис. 7, – двоичные, т.е. принимающие значение из множества {0, 1}.

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

Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных {0, 1} таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов код. Для этого необходимо, чтобы выполнялось условие

 

N £ 2ⁿ,

 

где N – число символов входного алфавита;

n – число элементов памяти.

Точно так же кодировка M символов выходного алфавита требует, чтобы число m обеспечивало равенство M £ 2^m, а кодировка S символов алфавита состояний было связано с числом k равенством S £ 2^k.

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

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

При выполнении курсовой работы в качестве элементов памяти используются или счётный триггер, или элемент типа линии задержки, в зависимости от варианта задания. Каждый из этих элементов является нетривиальным полуавтоматом Мура, имеющим два состояния (обозначим как 0 и 1).

В счётном триггере при поступлении входного сигнала, равного нулю, элемент остаётся в том же состоянии, что и был. При единичном сигнале состояние элемента меняется с 0 на 1 и с 1 на 0. Таблица переходов для счетного триггера представлена табл. 35.

Таблица 35

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

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит

Таблица 36

из состояния s _m с кодом 0101 в состояние s _n, с кодом 1001, то это означает, что триггер Т₁, переходит из состояния 0 в состояние 1, триггер Т₂ - из состояния 1 в состояние 0, а состояние триггеров Т₃, и Т₄ не изменяются.

В качестве примера проведем кодирование компонентных автоматов В, С и D, полученных в результате декомпозиции и представленные таблицами 30, 31 и 32, а также выходных сигналов исходного автомата, представленных табл. 33.

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

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

Проведем кодирование состояний автоматов В, С и D. Введем обозначение: b₁ => 1, b₂ => 0; с₁ => 1, с₂ => 0; d₁ => 1, d₂ => 0. Символ => означает соответствие состояния выбранному коду.

Проведем кодирование входных сигналов автоматов В, С и D. Введем обозначение: u₁ => 1, u₂ => 0; v₁ => 1, v₂ => 0; w₁ => 1, w₂ => 0.

С учетом проведенного кодирования таблицы 31, 31 и 32 будут представлены кодовыми таблицами автоматов 37, 38 и 39

Таблица 37 Таблица 38 Таблица 39

d1
1 1
1 0
0 1
0 0

d2
1 1
1 0
0 1		*
0 0		*

d3
1 1 1
1 1 0
0 1 1
0 1 0
1 0 1
1 0 0

 

 

При кодировании табл. 34 выходов исходного автомата введем обозначения:

x₁ => 00, x₂ => 01, x₃ => 10, x₄ => 11; y₁ => 01, y₂ => 10, y₃ => 11.

Кодовая таблица выходов исходного автомата представлена табл. 40.

При использовании счётного триггера таблицы переходов получаются как результат операции сложения по модулю два кодов текущего и следующего состояний. Необходимо помнить правила сложения по модулю два: 0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1, 1 + 1 = 0. Сложение осуществляется без переноса единицы в старший разряд.

Таблица 40

g	b1хc1хd1	b1хc1хd2	b1хc2хd1	b1хc2хd2	b2хc1хd1	b2хc1хd2
1 1 1	1 1 0	1 0 1	1 0 0	0 1 1	0 1 0

Кодирование состояний автоматов В, С и D, входных и выходных сигналов проведем аналогично кодированию при применении триггера типа линии задержки. В качестве примера рассмотрим кодирование автомата В (табл. 39).

Находясь в состоянии b₁ (1) по сигналу d₁, u₁ (1, 1) автомат В переходит в состояние b₁ (1).

Складывая коды предыдущего состояния b₁ (1) и последующего состояния b₁ (1) по модулю 2 получаем 1 + 1 = 0. Следовательно, код состояния автомата В будет равен 0 и в ячейке на пересечении строки d₁, u₁ (1, 1) и столбца b₁ (1) ставиться 0.

Находясь в состоянии b₂ (0) по сигналу d₁, u₁ (1, 1) автомат В переходит в состояние b₁ (1). Складывая коды предыдущего состояния b₂ (0) и последующего состояния b₁ (1) по модулю 2 получаем 0 + 1 = 1. Следовательно, код состояния автомата В будет равен 1 и в ячейке на пересечении строки d₁, u₁ (1, 1) и столбца b₂ (0) ставиться 1.

Используя вышеприведенную методику, закодированные таблицы переходов цифрового автомата будут иметь вид, представленный в таблицах 41, 42 и 43.

Таблица 41 Таблица 42 Таблица 43

d1
1 1
1 0
0 1
0 0

d2
1 1
1 0
0 1		*
0 0		*

d3
1 1 1
1 1 0
0 1 1
0 1 0
1 0 1
1 0 0

 

 

Кодирование таблицы выходов при использовании счётного триггера проводится аналогично, как и при использовании триггера типа линии задержки.