Структурная схема конечного автомата

В структурной теории автомат предполагают в виде композиции 2-ух частей: запоминающей части, состоящей из частей памяти, и комбинационной доли, состоящей из логических элементов (рисунок 9).

Рисунок 9. Логическая схема конечного автомата Комбинационная схема основывается на логических элементах, образующих функционально полную систему, а память — на элементарных автоматах, владеющих полной системой переходов и выходов.

Любое состояние абстрактного автомата а_i, где i={0, n}, кодируется в структурных автоматах комплектом состояний частей памяти Q_i,.

r={1, R}. Так как в качестве элементов памяти употребляются обычные триггера, то любое состояние можно закодировать двоичным числом а_i = Q₁^а1Q₂^а2… Qr^аr. Здесь а_i={0, 1}, а Q — состояние автомата (таблица 19).

Таблица 19. Матрица переходов JK-триггера.

Общее число необходимых элементов памяти можно определить из следующего неравенства.

(2).

где (n+1) — число состояний.

Логарифмируя это неравенство получим:

(3).

где ]С[ - значит, что нужно взять ближайшее целое число, большее или равное С.

В отличии от абстрактного автомата, имеющего один входной и один выходной каналы, на которые поступают сигналы во входном Х={х₁, х₂,…, х_m} и выходном Y={y₁, y₂,…, y_k} алфавитах, структурный автомат владеет L входных и N выходных каналов. Любой входной х_j и выходной y_j сигналы абстрактного автомата имеют все шансы существовать закодированы двоичным комплектом состояний входных и выходных каналов структурного автомата.

Очевидно, количество каналов L и N можно определить по формулам (4,5), подобным формуле для определения R.

(4).

Изменение состояния частей памяти происходит под действием сигналов U=(U₁, U₂,…, U_r), поступающих на их входы. Данные сигналы создаются комбинационной схемой II и именуются сигналами побуждения элементарных автоматов. На вход комбинационной схемы II, не считая входного сигнала х_j, по цепи обратной взаимосвязи поступают сигналы Q=(Q₁, Q₂, …, Q_R), именуемые функцией обратной взаимосвязи от памяти автомата к комбинационной схеме. Комбинационная схема I работает для формирования выходного сигнала y_g, при этом в случае автомата Мили на вход данной схемы поступает входной сигнал х_j, а в случае автомата Мура — сигнал х_j, не поступает, так как y_g не зависит от х_j,.

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

Рассмотрим примеры синтеза, которые разрешают сформулировать совместный алгоритм структурного синтеза конечных автоматов. В качестве элементарных автоматов будем применять JK-триггера, а в качестве логических частей — элементы И, ИЛИ, НЕ. Итак, имеем А={а₀, а₁, а₂}; Х={х₁, х₂}; Y={y₁, y₂, y₃}. Здесь n=2, n+1=3; m=2, k=3.

Пусть нужно синтезировать автомата Мили, данный совмещенной таблицей переходов и выходов (таблица 20).

Таблица 20. Таблица переходов и выходов автомата Мили.

Перейдем от абстрактного автомата к структурному, для чего определим численность частей памяти R и количество входных L и выходных N каналов. По формуле 1, 2, 3 получим следующую таблицу (таблица 21).

Таблица 21. Параметры абстрактного автомата.

Таким образом, нужно иметь 2 элементарных автомата Q₁ и Q₂ (так как R=2), один входной канал О₁ и два выходных канала Z₁ и Z₂.

Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов (таблица 22).

Таблица 22. Таблица кодирования.

Так как автомат имеет 3 состояния, то комбинация состояний элементарных автоматов 11 не употребляется и считается запрещенной (автомат в это состояние никогда не попадет). Тут и в дальнейшем станем применять естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата (таблица 23).

Таблица 23. Совмещенная таблица переходов и выходов.

В таблицах кодировки выходные каналы Z₁ и Z₂ именуются физическими выходами автомата.

Пользуясь таблицами кодировки, разрешено на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний Q_i(t+1)элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предыдущий момент времени t.

Кодированная таблица переходов и выходов (совмещенная) имеет следующий вид (таблица 24):

Таблица 24. Кодированная таблица переходов и выходов.

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

Таблица 25. Матрица переходов JK-триггера.

С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках данной таблицы записываются значения J и K, обеспечивающие подходящий переход.

Так как функции возбуждения J (t) и K (t)определенны в тот же момент времени, что и их аргументы Q₁(t), Q₂(t) и О₁(t), то данные функции считаются переключательными. В итоге мы получим систему переключательных функций Z₁(t), Z₂(t), J₁(t), K₁(t), J₂(t) и K₂(t) данных в виде таблиц их истинности.

Следующий шаг — синтез комбинационной доли конечных автоматов. На данном шаге по приобретенным переключательным функциям синтезируются комбинационные схемы. Обычно полученную систему ПФ минимизируют вместе. Но совместная минимизация всех ПФ представляет собой достаточно трудоемкую и долгую операцию, применимую, в общем случае, при применении машины. В итоге минимизации мы получим следующую схему конечного автомата (рисунок 10).

Рисунок 10. Схема конечного автомата.

Функциональные схемы, получаемые в итоге структурного синтеза, в дальнейшем на шаге инженерной доработки подвергаются изменениям. Данные конфигурации связаны с тем, что прибавляются специальные цепи, нужные для работы разработанной схемы в составе остальных схем ЭВМ. К примеру, в схеме регистра сдвига информации прибавляется цепь «установка в 0». Остальные конфигурации связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов.