Синтез автомата Мили.

Реализация конечного автомата сводится к синтезу комбинационной схемы и его памяти. При реализации автомата во втором структурном алфавите можно использовать известные методы синтеза комбинационных схем. Для этого необходимо закодировать состояния автомата и представить функции λ, δ в виде булевых функций двух переменных. Такое кодирование можно осуществить преобразованием автоматной таблицы к таблице соответствия во втором структурном алфавите.

Пример 1.

Синтезировать логический комбинационный автомат с 3 клавишами на входе и светодиодной матрицей 4х3 на выходе, реализующий связь входа с выходом такую, чтобы комбинация светящихся светодиодов всегда образовывала десятичную цифру, двоичный код которой задан состоянием входных клавиш.

	О О О О О О О О О О О О

|A|=3, |B|=12

● ● ● ● o ● ● o ● ● ● ●

o o ● o o ● o o ● o o ●

● ● ● o o ● o ● o ● ● ●

● ● ● o ● ● o o ● ● ● ●

● o ● ● o ● ● ● ● o o ●

● ● ● ● ● ● o ● o ● o o

o o ● ● ● ● ● o ● ● ● ●

● ● ● o ● o ● o o ● o o

o o o o o ● o ● o o ● ● ● o o ● o ● ● ● o ● ● ●

a1

a2

a3

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

b11

b12

Пример 2. Пусть конечный автомат задан автоматной таблицей.

Q\ A	a0	a1	a2	a3
q0	3,0	2,0	1,0	3,0
q1	3,1	2,0	1,0	3,1
q2	3,1	2,0	2,1	3,1
q3	3,0	0,0	0,1	1,1

|A| = 4, |Q| = 4, |B| = 2

δ: Q x A → Q

λ: Q x A → B

Представим автоматную таблицу в следующем виде.

ai

qj

qj+1

bl

Заменяя десятичные числа их двоичным эквивалентом, читаемыми сверху вниз, получаем таблицу соответствия.

ai	ai1
	ai2
qj	qj1
	qj2
qj+1	qj1+1
	qj2+1
bl	bl

Из этой таблицы соответствия видно, что комбинационная схема синтезируемого автомата должна иметь 4 входа для переменных a_i1, a_i2, q_j1, q_j2 и 3 выхода b, q_j1+1, q_j2+1.

		U=<A, Q, B, δ, λ> |A|=4, |Q|=4, |B|=2 b={0,1}

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

ai1	ai2	qj1	qj2	qj1+1	qj2+1	b

Используя Совершенную конъюктивную нормальную форму (СКНФ) или Совершенную дизъюнктивную нормальную форму (СДНФ) логической функции, получаем ее формульное (однозначное) представление. Минимизировав полученные выражения, строим по ним в базисе схем "и", "не", "или" комбинационную часть проектируемого конечного автомата, структурная схема которого представлена выше.

Дата добавления: 2015-07-10