553d4c3a

Общий вид алгоритма


Для того чтобы изменение одного бита (или группы битов) воздействовало на все остальные, поступим следующим образом: будем вычислять сигнатуру двоичной последовательности и одновременно некоторой функцией преобразовывать биты, сигнатура для которых уже рассчитана. Естественно, эта функция должна иметь соответствующую ей обратную функцию для восстановления исходного текста. Преобразовывать можно как один бит, так сразу и группу битов. Шаг алгоритма может быть длиной как в один бит, так и в несколько бит.

Для простоты понимания рассмотрим алгоритм, с функцией, преобразующий один бит, и шагом в один бит.

k – длина последовательности, бит;

m – старшая степень полинома для расчёта сигнатуры, а также количество бит в элементах памяти (prev и next), хранящих сигнатуру;

сигнатура(предыдущая сигнатура, новый бит) – функция, осуществляющая сжатие последовательности в сигнатуру;

f(x, ai) – функция, осуществляющая преобразование бита ai некоторым числом x;

ai – i-ый бит последовательности.

Базовое преобразование (прямой ход) будет выглядеть так:

(3.1)

prev = 0;

для i от 1 до k

{

          next = сигнатура(prev, ai);

          ai = f(prev, ai);

          prev = next;

}

Обратное преобразование (прямой ход) будет выглядеть так:

                                                                                                                   (3.2)

prev = 0;

для i от 1 до k

{

          ai = f

-1(prev, ai);

          prev = сигнатура(prev, ai);

}

Как видим, изменение бита ai воздействует на все последующие биты, и вероятность того, что изменение этого бита отразиться на последующих, очень близка к единице. А что же делать с битами, предшествующими ai, ведь изменение их не затронет? Поступим просто – совершим такое же преобразование повторно, но в обратном направлении.

Базовое преобразование, обратный ход:

(3.3)

prev = 0;

для i от k до 1

{

          next = сигнатура(prev, ai);

          ai = f(prev, ai);

          prev = next;

}

Обратное преобразование, обратный ход:



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