Минимальная инверсная машина

Мы продемонстрируем процедуру построения минимальной инверсии на примере М показанной в Table 7а. Эта машина третьего ?-порядка (µ=3), поэтому, если мы знаем исходное состояние и значения трех

соответствующих выходных символов при переходах из начального состояния, мы можем определить первый входной символ. Определим множество триплов, обозначая их: S(t)zt+1,zt+2.

Первый компонент каждого трипла (S(t)) есть любое из исходных состояний машины М, второй (zt+1) – один из выходных символов, который может быть продуцирован при одном из переходов из этого состояния и третий (zt+2) –выходной символ, который может быть продуцирован при переходе из этого состояния. Трипл определяется для каждого возможного исходного состояния и для всех возможных последовательностей длиной 2. Для машины М

полученные триплы показаны в Table 7c. Из этой таблицы видно, что, например, трипл (А,0,1) - не определен, потому, что, если исходное состояние А, то после нулевого значения на выходе (переход А=>C), следующим значением не может быть единица.

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

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

Перейдем к построению таблицы переходов инверсной машины. Для этого обозначим инверсную машину через *М, которая, в соответствии с примером имеет 8 состояний, соответствующих восьми триплам (см. Table 7c).

Начнем построение таблицы переходов машины *М.

Она соответствует автомату, на входы которого подаются биты z, а на выходе формируются сигналы x.

Такая таблица имеет три столбца: PS, z=0, z=1.

Приступим к заполнению таблицы. Для этого:

Переписать в первый столбец построенные нами триплы из Table 7с.

Для строки (A,0,0) в столбце z=0 строим трипл:

Первый элемент трипла: С – название состояния, в которое перейдет машина из А при х=0.

Второй элемент трипла – 0, - это второй компонент трипла (A,0,0).

Третий элемент трипла - значение выхода (z), соответствующее значению z=0

столбца *М.

Значение выхода машины *М, равное значению х, при переходе А=>C. Получаем трипл (С,0,0),0

В этой же строке в столбце z=1:

Первый элемент трипла: С - название состояния, в которое перейдет машина из А при х=0.

Второй элемент трипла – 0, - это второй компонент трипла (A,0,0).

Третий элемент трипла - значение выхода (z), соответствующее значению z=1

столбца *М.

Значение выхода машины *М, равное значению х, при переходе А=>C. Получаем трипл (С,0,0),0. Получаем (С,0,1),0

Таблица состояний машины *М приведена в Table 7b.

Допустим, например, что *М находится в состоянии (A,0,0) и текущее значение входа – 0. Чтобы определить его 0-преемник мы увидим, что машина М, если она находится в состоянии А,

PS	NS,z
PS	x=0	x=1
A	C,0	D,1
B	D,0	С,1
C	А,0	B,0
D	C,1	D,1

PS

NS,x

z=0

z=1

(A,0,0)

(C,0,0),0

(C,0,1),0

(A,1,1)

(D,1,0),1

(D,1,1),1

(B,0,1)

(D,1,0),0

(D,1,1),0

(B,1,0)

(C,0,0),1

(C,0,1),1

(C,0,0)

(A,0,0),0

(B,0,1),1

(C,0,1)

(B,1,0),1

(A,1,1),0

(D,1,0)

(C,0,0),0

(C,0,1),0

(D,1,1)

(D,1,0),1

(D,1,1),1

a)

b)

c)

может продуцировать три последовательных нуля на выходе только если первый входной символ есть 0; как результат, первый переход *М есть состояние С и первый компонент трипла 0-преемника из (A,0,0) есть С.

Второй компонент трипла равен третьему компоненту трипла (A,0,0), а его третий компонент - это текущее значение выхода М, который, в действительности, является входом в *М и записанный в заголовке ее

таблицы переходов. Выход *М - это задержанный выход на вход М; так что выход *М в момент t равен ее входу в момент t-2.

Множество состояний, сгенерированных в виде множества триплов определяет ее таблицу переходов для реализации инверсной машины. Это не просто множество состояний. Машина *М, например, может быть упрощена, так как (A,0,0) эквивалентно (D,1,0) и (A,1,1) эквивалентно (D,1,1). Если обозначить через S1 (A,0,0), S2 - (A,1,1) и т.д., то мы получим минимальную таблицу инверсии, показанную в Table 8.

(A,0,0)	(B,0,1)	(C,0,0)	(D,1,0)
(A,1,1)	(B,1,0)	(C,0,1)	(D,1,1)
Table 7

PS	NS,z
PS	z=0	z=1
S1	S5,0	S6,0
S2	S1,1	S2,1
S3	S1,0	S2,0
S4	S5,1	S6,1
S5	S1,0	S3,1
S6	S1,1	S3,0
Table 8

Рассмотренная процедура применима для любой информацию сохраняющей машины конечного порядка. В общем, для машины порядка µ, мы определим множество µ-кортежей, которые образуют множество состояний инверсии. Первый элемент каждого µ-кортежа – состояние М; остальные элементы – возможные выходные последовательности длиной, равной µ-1, которые могут быть произведены при последующих переходах из этого состояния. Очевидно, что эта процедура выдает более экономичную реализацию, чем приведенная на Рис. 7, так как в ней мы запоминаем выходную последовательность в сдвиговом регистре и использовать копию М, чтобы определить состояние в исходной М.

Допустим, что М (Table 7b) находится в начальном состоянии и в ответ на некоторую входную последовательность она продуцирует одну из последовательностей 00 или 11. Тогда *М двумя шагами позднее должна быть в состоянии, которое соответствует А и соответствующую выходную последовательность, то есть (А,0,0) или (А,1,1). Но поскольку S4: (B,1,0) единственное состояние, из которого *М может достигнуть (А,0,0) и (А,1,1), когда будет подан на вход 00 и 11, соответственно. Из этого следует что, если начальное состояние М есть А, то начальное состояние *М должно быть (В,1,0). Не трудно убедиться, что если М находится в состоянии В, то *М может быть либо в состоянии S1 либо в состоянии S4, и когда М находится в состоянии С или D, М* может находиться в одном из состояний S2, S3, S5 или S6.([9])

Как пример, демонстрирующий декодирующие свойства *М, допустим, что М и *М находятся в состоянии А и S4, соответственно, и допустим, что на вход М подана последовательность 010001101. Процесс кодирования-декодирования показан в Table 9.

Состояние М	A		С		B		D		C		A		D		D		C		B
Вход М		0		1		0		0		0		1		1		0		1
Выход М		0		0		0		1		0		1		1		1		0
Состояние М*	S4		S5		S1		S5		S3		S1		S6		S2		S2		S1
Выход М*		-		-		0		1		0		0		0		1		1

Table 9

Первые два символа в начале и в конце следует игнорировать. В оставшихся позициях, обе последовательности, входная для М и выходная для М* - идентичны, хотя сдвинуты во времени.([10])

Содержание раздела