Кодирование автоматовВсе переменные, приведенные на рис. 7, – двоичные, т.е. принимающие значение из множества {0, 1}. Переход от абстрактного автомата к структурному осуществляется через процедуру кодирования входов, выходов и состояний абстрактного автомата. Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных {0, 1} таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов код. Для этого необходимо, чтобы выполнялось условие
N £ 2n,
где N – число символов входного алфавита; n – число элементов памяти. Точно так же кодировка M символов выходного алфавита требует, чтобы число m обеспечивало равенство M £ 2m, а кодировка S символов алфавита состояний было связано с числом k равенством S £ 2k. В общем случае можно считать, что кодировка может быть достаточно произвольной. Функции ui называются функциями возбуждения элементов памяти и должны переводить элементы памяти в состояния, определяющие следующее состояние. Вид этих функций зависит от того, какие элементы памяти используются. При выполнении курсовой работы в качестве элементов памяти используются или счётный триггер, или элемент типа линии задержки, в зависимости от варианта задания. Каждый из этих элементов является нетривиальным полуавтоматом Мура, имеющим два состояния (обозначим как 0 и 1). В счётном триггере при поступлении входного сигнала, равного нулю, элемент остаётся в том же состоянии, что и был. При единичном сигнале состояние элемента меняется с 0 на 1 и с 1 на 0. Таблица переходов для счетного триггера представлена табл. 35. Таблица 35 В триггере типа линия задержки состояние автомата определяется только входным сигналом и не зависит от текущего состояния элемента. Единичный входной сигнал устанавливает триггер в единичное состояние, нулевой сигнал – в нулевое состояние. Таблица переходов для триггера типа линия задержки представлена табл. 36. Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит Таблица 36 из состояния s m с кодом 0101 в состояние s n, с кодом 1001, то это означает, что триггер Т1, переходит из состояния 0 в состояние 1, триггер Т2 - из состояния 1 в состояние 0, а состояние триггеров Т3, и Т4 не изменяются. В качестве примера проведем кодирование компонентных автоматов В, С и D, полученных в результате декомпозиции и представленные таблицами 30, 31 и 32, а также выходных сигналов исходного автомата, представленных табл. 33. При кодировании автоматов в качестве элементов памяти будим использовать триггера типа линии задержки. Таблица переходов автомата в этом случае получается заменой входов и состояний автомата их кодами. Все автоматы имеют по два состояния и, следовательно, в соответствии с условиями кодирования каждый из них будет реализован на одном элементе памяти. Проведем кодирование состояний автоматов В, С и D. Введем обозначение: b1 => 1, b2 => 0; с1 => 1, с2 => 0; d1 => 1, d2 => 0. Символ => означает соответствие состояния выбранному коду. Проведем кодирование входных сигналов автоматов В, С и D. Введем обозначение: u1 => 1, u2 => 0; v1 => 1, v2 => 0; w1 => 1, w2 => 0. С учетом проведенного кодирования таблицы 31, 31 и 32 будут представлены кодовыми таблицами автоматов 37, 38 и 39 Таблица 37 Таблица 38 Таблица 39
При кодировании табл. 34 выходов исходного автомата введем обозначения: x1 => 00, x2 => 01, x3 => 10, x4 => 11; y1 => 01, y2 => 10, y3 => 11. Кодовая таблица выходов исходного автомата представлена табл. 40. При использовании счётного триггера таблицы переходов получаются как результат операции сложения по модулю два кодов текущего и следующего состояний. Необходимо помнить правила сложения по модулю два: 0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1, 1 + 1 = 0. Сложение осуществляется без переноса единицы в старший разряд. Таблица 40
Кодирование состояний автоматов В, С и D, входных и выходных сигналов проведем аналогично кодированию при применении триггера типа линии задержки. В качестве примера рассмотрим кодирование автомата В (табл. 39). Находясь в состоянии b1 (1) по сигналу d1, u1 (1, 1) автомат В переходит в состояние b1 (1). Складывая коды предыдущего состояния b1 (1) и последующего состояния b1 (1) по модулю 2 получаем 1 + 1 = 0. Следовательно, код состояния автомата В будет равен 0 и в ячейке на пересечении строки d1, u1 (1, 1) и столбца b1 (1) ставиться 0. Находясь в состоянии b2 (0) по сигналу d1, u1 (1, 1) автомат В переходит в состояние b1 (1). Складывая коды предыдущего состояния b2 (0) и последующего состояния b1 (1) по модулю 2 получаем 0 + 1 = 1. Следовательно, код состояния автомата В будет равен 1 и в ячейке на пересечении строки d1, u1 (1, 1) и столбца b2 (0) ставиться 1. Используя вышеприведенную методику, закодированные таблицы переходов цифрового автомата будут иметь вид, представленный в таблицах 41, 42 и 43. Таблица 41 Таблица 42 Таблица 43
Кодирование таблицы выходов при использовании счётного триггера проводится аналогично, как и при использовании триггера типа линии задержки.
|
