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

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

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

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

,

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

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

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

 

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

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

bm	qi	bs
B1	Q1	B1
B1	Q2	B2
B1	Q3	B3
B2	Q3	B1
B2	Q1	B2
B2	Q2	B3
B3	Q2	B1
B3	Q3	B2
B3	Q1	B3

ПРИМЕР:

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

	A1	A2	A3
Z1	A2	-	A1
Z2	A3	A1	-
Z3	A2	A3	A3

	U1	U2	U1
	A1	A2	A3
Z1	W1	-	W2
Z2	W1	W3	-
Z3	W2	W1	W3

 

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

	a1	a2	a3
z1	a2	-	a1
z2	a3	a1	-
z3	a2	a3	a3

 

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

	u1	u2	u3
a1	a2	a3
z1	w1	-	w2
z2	w4	w3	-
z3	w2	w1	w3

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

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

	b1	b2
q1	b1	b2
q2	b2	b1

 

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

 

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

	α
q1
q2

 

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

	τ
b1
b2

 

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

 

Поскольку у абстрактного С-автомата имеется три внутренних состояния 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

x1

x2

y1

y2

r

а1

z1

w1

u1

a2

z2

w2

u2

a3

z3

w3

w4

 

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

 

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

		-
			-

 

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

		-
			-

 

Таким образом, после выбора элементов памяти и кодирования состояний автомата синтез структурного автомата сводится к синтезу комбинационных схем КС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> все компоненты функции выходов не определены.