caxapa.ru :: Существуют ли контрольные коды, вроде CRC, но обладающие свойством "коммутативности" что ли, не знаю как назвать, чтоб их удобно было применять к скользящему окну (чтоб не пересчитывать заново всё окно, только учесть вновь прибывший и

fk0, легенда (18.01.2012 13:49, просмотров: 3256)

Существуют ли контрольные коды, вроде CRC, но обладающие свойством "коммутативности" что ли, не знаю как назвать, чтоб их удобно было применять к скользящему окну (чтоб не пересчитывать заново всё окно, только учесть вновь прибывший и исключённый члены). Например обычная сумма годится, или комбинация суммы и XOR, но их негативные свойства известны...

[ZX]

Ответить

- Rolling hash? -> - Snaky(20.01.2012 05:19, ссылка)
- дык любая сумма на полиномах (стандартные циклические CRC типа CCITТ и т.п.) это же сумма (в алгебраическом так сказать смысле), просто + в ней переопределен - ыыыы(18.01.2012 20:34, )
  - На полиномах это не совсем сумма - это остаток от деления. - Сергей Борщ(23.01.2012 13:12)
- Checksum для IP пакетов обладает таким свойством. lentjaj1(146 знак., 18.01.2012 14:01)
  - там как раз простая сумма - koyodza(18.01.2012 19:43)
    - не совсем простая, а с переносом переполнения в младший разряд. - LightElf(19.01.2012 17:32)
      - ну да. Но по-моему это не сильно усложняет дело - koyodza(19.01.2012 20:08)
        
        это изменяет эффективность кода! - lentjaj1(20.01.2012 09:51)
  - Например в uIP так обходятся с пингами - LightElf(18.01.2012 18:25)

Микроконтроллеры