553d4c3a

Сжатие двоичной последовательности в сигнатуру


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

Для сжатия двоичной последовательности в сигнатуру используем следующее соотношение:

                                                       (2.2)

где 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(х). Дальнейшие упоминания о таких вероятностях будут менее точны, поэтому когда надо будет уточнить, обращайтесь к этому абзацу.



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