Структурный синтез С-автомата

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

Модуль памяти С-автомата строится из элементарных полных автоматов Мура. Т.о. после выбора элементов памяти, каждое состояние С-автомата представляется (кодируется) в структурном автомате вектором a_m=(l₁……l_i).

Если все элементы памяти одинаковы, то их число определяется следующим образом

,

Переход абстрактного автомата из состояния a_m в состояние a_s под действием входного сигнала z_f с выдачей выходного сигнала

cоотвествует в структурном автомате переходу из состояния

После выбора типа элементов памяти и кодирования состояния автоматов, следует этап синтеза комбинационной схемы, реализующий следующие функции:

Каноническое уравнение функции возбуждения ЭП

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

ПРИМЕР:

Необходимо синтезировать частичный С-автомат, заданный следующей таблицей переходов и выходов.

Таблица переходов автомата:

Таблица выходов автомата:

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

Таблица переходов автомата памяти:

Так как в элементарном автомате памяти (ЭАП) два входных сигнала q₁ и q₂ и два выходных сигнала b₁ и b₂, то в структурном автомате памяти будут один входной и один выходной сигналы.

Произведем кодирование входных сигналов ЭАП (α - функция возбуждения памяти):

Произведем кодирование выходных сигналов с элементов памяти:

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

Поскольку у абстрактного С-автомата имеется три внутренних состояния a₁, a₂ и a₃, то структурный С-автомат должен иметь два элемента памяти для кодирования.

Поскольку абстрактный С-автомат имеет три входных (z₁, z₂ и z₃) и четыре выходных сигнала типа 1 (w1, w2, w3 и w4), то в структурном автомате необходимо иметь два входных и два выходных канала для сигнала типа 1.

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

Таким образом, структурный автомат будет содержать:

1. Два элемента памяти (П₁ и П₂);

2. Два входных канала (x₁ и x₂);

3. Два выходных канала типа 1 (y₁ и y₂);

4. Выходной канал типа 2 (r₁).

Тогда структурная схема автомата, реализующего данные функции имеет следующий вид.

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

Таблица переходов структурного С-автомата:

Таблица выходов:

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

Схема КС1 должна реализовать следующие функции:

y₁ = y₁(τ₁,τ₂,x₁,x₂);

y₂ = y₂(τ₁,τ₂,x₁,x₂);

α₁ = α₁(τ₁,τ₂,x₁,x₂);

α₂ = α₂(τ₁,τ₂,x₁,x₂).

Комбинационная схема КС2 должна реализовать функцию r₁ = r₁(τ₁,τ₂).

Функции у₁ и у₂ можно получить непосредственно из отмеченной таблицы выходов структурного С-автомата:

Функции возбуждения элементарных автоматов памяти П1 и П2 будут соответствовать таблице переходов структурного С-автомата с учетом выбранных ЭП.

Таблица переходов элементарного автомата памяти:

Модифицированная таблица переходов:

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

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

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

3. Если для некоторой пары <a_i,z_j> функция переходов не определена, то на всех наборах всевозможных значений <a_i,z_i> все компоненты функции выходов не определены.