Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели


Свойства последовательного соединения КАМСИ


Рассмотрим последовательное соединение  двух КАМСИ А1 и А2 (см. Рис. 5). Выше, на стр. 38 (см. Рис. 3) мы уже рассматривали последовательное соединение двух КАМСИ, кодера и декодера, которые соединены информационным каналом. Теперь мы рассмотрим такое объединение конечных автоматов, которое интересует нас постольку, поскольку его можно заменить эквивалентным конечным автоматом. Нас интересует способ построения такого автомата и его свойства и параметры.

Рис. 5

Докажем следующее утверждение.

Утверждение 1  Композиция  двух последовательно включенных КАМСИ А1=>А2 (Рис. 5) является КАМСИ, которая имеет порядок ?= ?(A1) + ?(A2), где ?(A1) и ?(A2) - ?-порядки КАМСИ А1 и А2, соответственно

Доказательство. Из определения КАМСИ следует, что ?(A1) символов входного потока битов (Р)поданных на вход КАМСИ А1 достаточно, чтобы определить первый символ Р на выходе Е1. Однако, на выходе Е2 он может появиться только через ?(A2)  битов

Е1 на входе КАМСИ А2. Отсюда следует, что первый символ Р на выходе Е2 может быть получен после  ?= ?(A1)

+ ?(A2), символов, поданных на вход Р, то есть, композиция  КАМСИ А1,А2 также является КАМСИ и имеет порядок ?= ?(A1) + ?(A2).

Пример 2

 В Table 2(a) и (b) приведены таблицы переходов КАМСИ А1 и А2 µ-порядка 2, а в  Table 2(c) и (d) – инверсные им автоматы SS1 и SS2, соответственно ([30]).

А1

P,E

P=0

P=1

A

B,0

A,0

B

A,1

B,1

(a)

А2

P,E

P=0

P=1

A

A,1

B,1

B

B,0

A,0

(b)

?(A1) = 2

SS1

P,E

E=0

E=1

S0

S1,1

S2,1

S1

S1,1

S2,1

S2

S3,0

S4,0

S3

S1,0

S2,0

S4

S3,1

S4,1

(c)

SS2

P,E

E=0

E=1

S0

S1,0

S2,0

S1

S1,0

S2,0

S2

S3,1

S4,1

S3

S1,1

S2,1

S4

S3,0

S4,0

(d)

Table 2

 

Обозначим через А1 и SS1 кодер и декодер, соответственно, (аналогично А2 и SS2). В Table 3 и в Table 4 (строка (а))  приведен один и тот же поток Р бит (кодируемый текст, который известен только отправителю, см. Table 3(а)). В строках (b) таблиц приведены состояния, в которые переходят автоматы А1 и А2, соответственно. В  строках (с) – значения на выходе – закодированный текст, который может быть известен всем. В строках (d) и (e) приведены результаты декодирования, которые показывают, что результаты декодирования совпадают с исходным текстом, но появляются, начиная с третьего бита, то есть, с задержкой, равной двум.




Начало  Назад  Вперед



Книжный магазин