|
ru.unix
- RU.UNIX ----------------------------------------------------------------------
From : Eugene B. Berdnikov 2:5020/400 11 May 2000 18:39:53
To : sales@gpz.fi
Subject : Re: Что быстрей?
--------------------------------------------------------------------------------
sales@gpz.fi wrote:
sgf> "Eugene B. Berdnikov" wrote:
>>
>> Вообще, откуда взялась величина 1/65536 для вероятности необнаружения
>> ошибки, да еще с загадочным словом "очевидно"? Для меня, например,
>> совершенно очевидно, что эта величина определяется алгоритмом
>> вычисления CRC. Hе могли бы Вы пояснить свою "очевидную" мысль,
>> Александр, конкретно для алгоритма, использующемся в tcp?
sgf>
sgf> Имеется ввиду, что случайный набор битов нужной длины будет
sgf> воспринят как имеющий правильную CRC с такой вот вероятностью.
sgf> Зависит вероятность только от длины контрольной суммы, в смысле
sgf> улучшить сверх этого невозможно. Ухудшить - пожалуйста...
А не бывает таких ошибок, как "случайный набор битов нужной длины". :)
Бывает такая ошибка, как изменение одного бита. Обнаружимая даже
при таких дубовых алгоритмах вычисления CRC, как побайтовый XOR
или сложение по фиксированому модулю. Бывает другая ошибка -
изменение 2х случайных битов, вероятность которой примерно равна
вероятности изменения одного бита в квадрате. Это при самых
общих предположениях о шуме в среде передачи. Вот давайте всем
остальным пренебрежем, и подумаем об ее обнаружимости.
Ошибка не будет обнаружена, если вклады от изменений обоих битов
компенсируются. Если CRC - побайтовый XOR, то она вероятность
необнаружения равна вероятности попадания битов на одно и то же
место в байте, т.е. 1/8. Разумеется, такая CRC никому не нужна.
Если CRC - умножение на порядковый номер байта в последовательности
и сложение по фиксированному модулю, вероятность компенсации
сильно зависит от расстояния между байтами. Грубо говоря, изменения
в соседних байтах обнаружимы всегда. А в среднем вероятность
обнаружения равна 1/2^n, где n - величина модуля (разрядность
контрольной суммы).
Да, согласен, лучше чем 1/65536 для 16-битной суммы не сделать.
Hо это лишь асимптотика, т.е. для пакетов бесконечной длины.
Я готов поверить, что на пакетах в 64К вероятность близка к
асимптотической. Hо что-то мало верится, что используемый в tcp
алгоритм настолько плох, что даже на пакетах в 1000 байт,
которые обсуждались в примере от Alexander Pevzner, эта
вероятность столь высока. :)
sgf> Самое начало курса по теории информации...
Признаюсь, не информатику учил. Hо незнание информатики не освобождает
меня от догадки, что зависимость от алгоритма здесь очень сильная.
Поэтому я и спрашиваю Александра, что именно ему "очевидно". :-)
sgf> Vladimir Tchoukharev
--
Eugene Berdnikov
--- ifmail v.2.15dev5
* Origin: Institute for High Energy Physics, Protvino, Russia (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Что быстрей? 