Построение кодированной таблицы переходов и выходов

	Код вх.букв	Код сост в момент T	Код сост в момент T+1	Функции возбуждения	Код вых.букв
	a	Z1(t)	Z2(t)	Z1(t+1)	Z2(t+1)	V1	V2	b
X1
X2

Запись кодов состояний.

В столбцы Z₁(t) и Z₂(t) записывается набор кодов состояний автомата последовательно для всех вариантов кодов входных букв. Для данного примера – сначала перечислены все коды состояний (01; 00; 10; 11) для кода входной буквы X₁ , затем записываются все коды состояний для кода входной буквы X₂ .

В столбцы Z₁(t+1) и Z₂(t+1) записываются коды состояний автомата, в которые по соответствующей букве происходит переход. Происходит анализ переходов по графу или таблице автомата. Например (1-я строка кодированной таблицы переходов), из состояния S₀ (код 01) по входной букве X₁ (код 0) происходит переход в состояние S₁ (код 00), в столбец «код вых.буквы» (b) этой же строки будет записан код выходной буквы Y₁ (код 0), т.е. выходная реакция, соответствующая этому переходу. На рисунке ниже представлен рассмотренный переход графа автомата.

Рис. Переход графа автомата

Если из текущего состояния перехода по указанной входной букве нет, то начиная со столбцов Z₁(t+1) и Z₂(t+1) и до конца в текущей строке записываются прочерки и в последующем строка исключается из рассмотрения.

При заполнении столбцов функций возбуждения. Потребуется анализ таблицы переходов T-триггера.

T	Q t	Q t+1

Для заполнения столбца V₁ проводится анализ столбцов Z₁(t) и Z₁(t+1) . Столбец Z₁(t) сопоставляется со столбцом Q ^t таблицы переходов T-триггера, а Z₁(t+1) с Q ^t+1 таблицы переходов T-триггера. Например, в рассматриваемой 1-й строке кодированной таблицы в столбцах Z₁(t) и Z₁(t+1)стоят 0 и 0 соответственно, далее в таблице переходов Т-триггера в столбцах Q ^t и Q ^t+1 ищется такая же комбинация 0 и 0 и соответствующее значение столбца T записывается в ячейку столбца V₁ . Выполнив такие же действия с данными столбцов Z₂(t) и Z₂(t+1) (имеем 1 и 0) в в ячейку столбца V₂ будет записана 1, соответствующая комбинации 10 для Q ^t и Q ^t+1 таблицы переходов T-триггера.

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

Рис. Схема заполнения кодированной таблицы переходов

Запись функций возбуждения.

Для записи ФВ используются строки, содержащие 1 в столбце, соответствующем рассматриваемой ФВ. Для анализа потребуются столбцы a, Z₁(t) и Z₂(t) .1 соответствует истинному значению столбца, 0 – его отрицанию, т.е., если в анализируемой строке столбца а записан 0, то в выражение для ФВ будет записано « », если стоит 1, то будет записано «а». Логическое произведение значений столбцов a, Z₁(t) и Z₂(t) для строк, содержащих 1 записывается через логическое ИЛИ.

Если в столбце ФВ находятся все 0, то ФВ равна 0 (V=0) и в КЛС на вход триггера, которому соответствует данная ФВ подается 0.

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

Построение КЛС на основе логических выражений для ФВ и функций выходов.

Сначала логическими элементами формируются ФВ

Пример 2. Провести структурный синтез по заданному графу автомата

;

Решение.

1. Выбор элементов памяти и логических элементов.

В качестве ЭП выбирается RS-триггер. Логические элементы – элементы булева базиса. В данном случае выбор триггера сделан для демонстрации примера использования RS-триггера.

Q t	Q t+1	Rt	S

Таблица входов RS-триггера.

2. Кодирование входных, выходных букв и состояний автомата.

– входные сигналы ,

- потребуется минимум 2 буквы для кодирования

– выходные сигналы

- потребуется минимум 2 буквы для кодирования

– внутренние состояния

- потребуется минимум 2 RS-триггера

X	a1	a2		Y	b1	b2
X1				Y1
				Y2
X2				Y3
				Y4

S	Z1	Z2
S1
S2
S3
S4

3. Построение кодированной таблицы переходов и выходов.

Код вх.букв

Код сост в момент T

Код сост в момент T+1

Функции возбуждения

Код вых.букв

a1

a2

Z1(t)

Z2(t)

Z1(t+1)

Z2(t+1)

Vr1

Vs1

Vr2

Vs2

b1

b2

X1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

X2

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Кодированную таблицу переходов можно сократить, исключив строки с прочерками.

Код вх.букв

Код сост в момент T

Код сост в момент T+1

Функции возбуждения

Код вых.букв

a1

a2

Z1(t)

Z2(t)

Z1(t+1)

Z2(t+1)

Vr1

Vs1

Vr2

Vs2

b1

b2

X1

X2

Функции возбуждения.

Функции выходов.

КЛС