|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 13 Jul 2003 20:37:50
To : Rodion Gorkovenko
Subject : Re: чем CRC лучше sum?
--------------------------------------------------------------------------------
Hi!
> Or> Hу например сумма проспит пеерстановку двух любых слов в блоке данных.
> Or> Ибо от перестановки слагаемых сумма не меняется.
> Я, возможно, ошибаюсь, но, поскольку размер и CRC и суммы одинаковый, то и
> вариантов ошибки будет одинаковое число... если мыслить логически... ;)
>
> Скажем из 256^20 вариантов 20-байтовых строк получается 65536 вариантов
CRC и
> 65536 вариантов сумм - в идеале... Если CRC несет в себе доп.
возможности -
> соответственно, доп. информацию - то при условии не использования ее он в
> принципе должен быть хуже... ;(
CRC более "размазан". Если не ошибаюсь, то нужно сделать ошибку не менее чем
в 16 битах подряд, или не менее чем в 3 битах в пределах потока из 65536 бит
или не менее чем 2 битах на большем расстоянии, чтобы CRC16 выдал ошибочно
тот же результат. Возможно для промежуточных расстояний между 16 и 65536
битами эта зависимость сохраняется.
То есть хорошо отлавливает компактные ошибки, идущие группами, чаще
встречающиеся на реальных носителях и каналах передачи. Обычная сумма таким
эффектом не обладает, она хорошо отлавливает только один бит и поблизости от
него всегда находится множество бит, поменяв любой из которых получишь ту же
сумму. Hа маленьких блоках данных сумма к тому-же несет меньше информации
(старшие биты пусты).
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
