Кодирование

 

Абстрактный ЦА может быть описан в виде .

При переходе на структурный уровень представления каждая буква входного алфавита автомата, представляется как двоичный набор (вектор), число компонентов которого равно числу физически реализованных элементарных входных каналов структурного автомата, т.е. каждая буква кодируется двоичным вектором. Минимальное число физически реализованных элементарных входных каналов в автомате может быть определено по формуле , где - мощность входного алфавита . Если , то , т.е. каждая буква кодируется двоичным вектором, состоящим из двух компонент, например . Минимальное число элементарных выходных каналов . Для множества состояний .

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

Пример: Абстрактный автомат Мили задан совмещенной таблицей переходов-выходов 1. Кодирование букв алфавита , представлено таблицами 2, 3, 4. При этом , , , , , .

 

 

Таблица 1       Таблица 2 вх. сигн. код       Таблица 3 вых. сигн. код       Таблица 4 состояния код      

 

 

Таблица 5

    входные сигналы
 
состояния
10/00

 

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

 

 

12.2 Выбор элементов памяти автомата

Замена таблиц переходов ЦА на структурную таблицу переходов приводит к тому, что функция переходов ЦА становится векторной. В соответствии со структурной таблицей переходов ЦА его векторная функция каждой паре двоичных векторов ставит в соответствие определенный двоичный вектор , что определяется соотношением . Из этого следует. Что структурный автомат должен запоминать двоичный вектор каждого очередного состояния ЦА, для чего служат элементы памяти.

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

Полнота системы переходов-выходов для любой пары состояний ЦА существует входной сигнал, переводящий ЦА из одного состояния в другое.

Полнота системы выходов – различным состояниям автомата соответствуют различные выходные сигналы; обычно нулевому состоянию элементарного автомата соответствует нулевой выходной сигнал , а единичному состоянию - единичный выходной сигнал .

Число элементов памяти структурного автомата равно числу компонент вектора его состояний.

В качестве элементов памяти структурного автомата обычно используются D -, T -, RS - и JK - триггеры, удовлетворяющие требованиям относительно полноты переходов и выходов. Каждый из приведенных триггеров является автоматом Мура. Входы D, T, RS и JK называются информационными. Таблицы переходов триггеров составляются только для информационных входов. Остальные входы являются вспомогательными (C, R, S). Каждый триггер имеет два выхода и.