Сжатие двоичной последовательности в сигнатуру
Сигнатура – это небольшой объём информации, максимально характеризующей длинную двоичную последовательность. Сущность сигнатуры в том, что для двух различных последовательностей , сигнатуры, характеризующие их, с очень большой вероятностью различаются.
Для сжатия двоичной последовательности в сигнатуру используем следующее соотношение:
где y(k) Î {0,1} – k-й символ сжимаемой последовательности {y(k)}, k = 1..l; aiÎ{0,1} – коэффициенты порождающего полинома j(x); ai(k-1)Î{0,1} – содержимое i-го элемента памяти в k-1-й такт. Процедура сдвига информации описывается соотношением
aj(k) = aj-1(k-1), j = 2..m.
Для описания процедуры сжатия информации, основанной на применении примитивных полиномов, используются различные математические модели и алгоритмы. Одной из наиболее часто применяемых является модель, реализующая идею представления процедуры сжатия информации как операцию деления полиномов над полем GF(2). При этом в качестве делимого используется поток сжимаемых данных, описываемых полиномом c(x) степени l-1, где l-количество бит в последовательности. Так, например, последовательность 10011 имеет вид полинома c(х) = x4ÅxÅ1. Делителем служит примитивный полином y(х), в результате деления на который получается частное q(х) и остаток S(х), связанные классическим соотношением вида
c(x) = q(x)y(x) Å S(x), (2.3)
где остаток S(х), представляющий собой полином степени, меньшей, чем
m = deg y(x), называется сигнатурой.
Результат сжатия C(x) (m-разрядное число, содержащееся в a1..am), получающийся по выражению (2.2), не совпадает с S(x), C(x)¹S(x), но линейно с ним связан.
Каковы же вероятности того, что сигнатуры различаются для двух различных последовательностей? Сигнатуры различаются для двух последовательностей любой длины l, отличающихся на один бит, и для всех последовательностей длиной l£2m-1, отличающихся на два любых бита [2]. Для n-кратных изменений (l=2m-2), при достаточно большом m, сигнатуры различаются с вероятностью » 1-1/2m, что при m>7 практически равно единице. Единственный параметр, влияющий на значения вероятности - старшая степень m полинома j(х). Дальнейшие упоминания о таких вероятностях будут менее точны, поэтому когда надо будет уточнить, обращайтесь к этому абзацу.
