Алгоритм построения КАМСИ-композиции

В Table 16 показан процесс последовательного кодирования и декодирования с помощью двух последовательно включенных КАМСИ-автоматов А1 и А2.

Рассмотрим теперь способ построения композиции последовательно включенных двух КАМСИ-автоматов.

Алгоритм построения КАМСИ–композиции из компонентов КАМСИ рассмотрим на примере композиции двух автоматов.

Пример 2

Пусть заданы две КАМСИ ?1 и ?2

(см. Table 18 (а) и (b)). Построим таблицу переходов автомата ?, эквивалентного последовательному соединению КАМСИ ?1>?2.

	P,E1
P=0	P=1
A	B,0	A,0
B	A,1	B,1

(a)

	Е1,E2
P=0	P=1
A	A,1	B,1
B	B,0	A,0

(b)

P,E2

P=0

P=1

BA,1

AA,1

BB,0

AB,0

AB,1

BB,1

AA,0

BA,0

(c)

?	P,E2
P=0	P=1
A	C,1	A,1
B	D,0	B,0
C	B,1	D,1
D	A,0	C,0

(d)

Table 18

P	1	1	0	1	0	0	1	1	0	0	1	0	0	1	1	1				(a)
?	A	A	A	C	D	A	C	D	C	B	D	C	B	D	C	D	C			(b)
		1	1	1	1	0	1	1	0	1	0	0	1	0	0	1	0			(c)
SS2		S0	S2	S4	S4	S4	S3	S2	S4	S3	S2	S3	S1	S2	S3	S1	S2	S3		(d)
E			0	1	0	0	0	1	1	0	1	1	1	0	1	1	0	1		(e)
SS1			S0	S1	S2	S3	S1	S1	S2	S4	S3	S2	S4	S4	S3	S2	S4	S3	S2	(f)
				1	1	0	0	1	1	0	1	0	0	1	1	0	0	1	0	(g)

Table 19

Для построения композиции выполним последовательность операций:

создать таблицу переходов, содержащую 2х2=4 ([14]) строки;

в первом столбце вписать все сочетания по два состояний КАМСИ ?1

и ?2 при этом необходимо, чтобы первым стояло обозначение состояния ?1, а вторым – ?2;

на пересечении АА (см. первую строку Table 18(с)) и столбца Р=0 записать:

символ В (переход при Р=0 в КАМСИ ?1 из А в В, Е1=0);

символ А (переход при Е1=0 в КАМСИ ?2 из А в А, Е2=1);

через запятую записать значение Е2 равное 1; Аналогично заполнить остальные клетки столбцов 2 и 3.

построить Table 18(d). Для этого АА из Table 18 (с) заменить: АА на А, АВ на В, ВА на С и ВВ на D ([15]).

Приведенный пример показывает, что если число компонентов КАМСИ в композиции равно m, и таблица переходов i-го автомата имеет ni состояний, то общее число N состояний композиции равно

.

Примеры на стр. 26 и 29 позволяют сформулировать следующее утверждение:

Утверждение 6: «Последовательному соединению m компонентов КАМСИ соответствует КАМСИ-композиция, которая имеет µ-порядок, равный

и таблицу переходов с

состояниями».

Доказательство этого Утверждения можно провести по индукции, если считать, что примеры на стр. 26 и 29 позволяют доказать это утверждение для m=2.

Далее, можно продолжить доказательство, увеличивая m на единицу.

Сформулируем еще одно Утверждение:

Утверждение 7. Для md КАМСИ-автоматов декомпозиции ([16]) КАМСИ, всегда выполняется условие ?d ? ?, где: µd

- µ-порядок последовательного соединения КАМСИ-компонентов, равный:

, а µ - µ-порядок исходной КАМСИ-композиции.

Допустим обратное, то есть условие Утверждения не выполняется, то есть ?d > ?. Если это так, то, в соответствии с «Утверждение 6» композиция этих mdk

КАМСИ-компонентов должна иметь µ-порядок, больший, чем исходная КАМСИ. Это значит, что в результате композиции компонентов мы получим ту же КАМСИ, но с бОльшим µ-порядком, что не возможно.

Из приведенных Утверждений можно сделать следующие выводы.

Следствие 1. Если композиция КАМСИ состоит из минимизированных компонентов КАМСИ, то ее таблица переходов не имеет эквивалентных состояний.

Введем определение:

Определение. 9 КАМСИ, которая является компонентом композиции, называется КАМСИ-примитивом ([17]).

Примером КАМСИ-примитива являются КАМСИ ?1 или ?2, приведенные в Table 18(a), (b) , а КАМСИ-композиция показанная в Table 18(d) - ?.

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

Главная сайта