2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Перерасчет CRC-суммы для фрагментарно изменного массива
Сообщение25.07.2012, 00:02 


23/12/07
1603
Есть массив данных, для которого получена 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 
Модератор
Аватара пользователя


11/01/06
5367
Да, можно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group