2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Перерасчет CRC-суммы для фрагментарно изменного массива
Сообщение25.07.2012, 00:02 
Есть массив данных, для которого получена CRC-контрольная сумма. Можно ли после изменения фрагмента массива обновить контрольную сумму без полного ее перерасчета. Ликбез по CRC вроде бы как наводит на мысль, что можно. Соображения такие: согласно Wiki (http://en.wikipedia.org/wiki/Generator_polynomial), если отождествлять бинарные последовательности с полиномами из $GF(2)[x]$, то полином $C_m(x)$, отвечающий контрольной сумме размера $m$ бит, для данных, представленных полиномом $P_k(x)$, должен находиться из условия:

$$x^m P_k(x) + C_m(x) = 0 \quad \big(\!\!\!\!\!\! \mod G_m(x) \big),$$

где $G_m(x)$ - некоторый фиксированный полином.
Как я понимаю, пользуясь тем, что полиномы с операциями сложения и умножения по модулю $G_m(x)$ образуют кольцо, можно записать:
$$C_m(x) = -x^m P_k(x) \quad \big(\!\!\!\!\!\! \mod G_m(x) \big).$$

Тогда для полинома $P_k'(x) $ фрагментарно измененного массива полином $C_m'(x) $ его контрольной суммы можно представить как

$$C_m'(x) = -x^m P_k'(x)   \,= \,-x^m P_k(x) \,- \,x^m \Delta_s(x) \, =\,  C_m(x) \,-\, x^m \Delta_s(x) \quad \big(\!\!\!\!\!\! \mod G_m(x) \big),$$
где $\Delta_s(x) = P_k'(x) - P_k(x)$.

Откуда вытекает, что для расчета CRC-контрольной суммы измененного массива достаточно:
1) выполнить побитовое вычитание фрагментов массива (соответствует нахождению $\Delta_s(x)$);
2) для полученной разности выполнить побитовый сдвиг влево на $m$-разрядов (соответствует нахождению $x^m\Delta_s(x)$);
3) полученный результат вычесть побитово из прежней контрольной суммы;
4) рассчитать остаток от деления на $G_m(x)$. Он и будет искомой обновленной контрольной суммой измененного массива.

Так ли это?

 
 
 
 Re: Перерасчет CRC-суммы для фрагментарно изменного массива
Сообщение10.12.2012, 22:28 
Аватара пользователя
Да, можно.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group