Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Обсуждение: Ross N. Williams. A Painless Guide to CRC Error Detection Algorithm  (Прочитано 8476 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« : 29-06-2015 19:23 » 

Доброго вечера.

Почитал, и, как понял, CRC контроль не обеспечивает 100% исключения ошибок. Так самое интересное - каким критерием надёжности пользуются разработчики при выборе того или иного полинома?

Автор советует почитать: Tanenbaum, A.S., "Computer Networks", Prentice Hall,
1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132.
Записан
Dale
Блюзмен
Модератор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 29-06-2015 21:04 » 

Доброго вечера.

Почитал, и, как понял, CRC контроль не обеспечивает 100% исключения ошибок.

Здравствуйте.

Конечно, 100% не сможет обеспечить в принципе. Например, возьмем 32-разрядный вариант CRC. Он каждой последовательности данных ставит в соответствие контрольный код. Поскольку вариантов кода 232 (хоть и относительно большое, порядка четырех миллиардов с хвостиком, но все же конечное число), а возможных последовательностей - бесконечное число, то всегда можно умышленно исказить данные так, что контроль CRC не сможет обнаружить подлога.

Мысленный эксперимент - берем 232+1 случайных файлов и вычисляем CRC. Как минимум у двух контрольные суммы совпадут при различном содержимом. Следовательно, о 100% не может быть и речи.

Главное тут, чтобы вероятность обнаружения случайной ошибки (помехи, пора носителя и т.д.) была достаточно мала для практических применений.

каким критерием надёжности пользуются разработчики при выборе того или иного полинома?

Обычно используют статистику помех, с которыми собираются бороться. Например, если это помехи в линии связи, то вероятнее повреждение одним импульсом помехи смежных битов посылки, чем далеко отстоящих. То же самое с носителями - пылинка или царапина на ленте стриммера или диске опять же с наибольшей вероятностью повредит смежные биты (хотя пример надуманный, конечно, там обычно контрольные коды помощнее, чем CRC, с исправлением ошибок).

Соответственно и полином стараются подобрать такой, чтобы повреждение соседних битов давало большой разброс контрольного кода.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 29-06-2015 22:01 » 

Практический пример: Ethernet использует CRC32. Подсчитано, что эффективность обнаружения ошибок при размерах кадра в районе 12к падает до неудовлетворительной и потому большинство производителей поддерживают большой кадр (jumbo frame) в 9000 байт полезной нагрузки.
https://en.wikipedia.org/wiki/Jumbo_frame#Error_detection
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 30-06-2015 05:50 » 

Вроде, стандартный кадр Ethernet - примерно 1500 октетов? Увеличение до 9000, получается, способствует лучшему выявлению ошибок, даже не смотря на увеличение вероятности появления таковых, ввиду увеличения размера передаваемой порции данных?

Тем не менее, оценка всё равно качественная. Например, мы послали 1000 кадров, в которых 400 кадров пришли и в них была обнаружена ошибка, а 1 кадр пришёл и был принят, как безошибочный. При таком раскладе можно было бы сказать, что связь работает неудовлетворительно, но 1 к 1000 - считать нормой или это очень плохой результат?

CRC получается как бы фильтр, но как поступить, если требуется повысить отказоустойчивость - те же банковские операции - ошибка 1 к 10^10 будет означать ошибку перевода средств у одного из ныне живущих людей, что недопустимо. И, как повлияет увеличение/уменьшение размера контрольной суммы на детектирование?
Записан
Dale
Блюзмен
Модератор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 30-06-2015 06:42 » new

Вроде, стандартный кадр Ethernet - примерно 1500 октетов?

Классический - да.

Увеличение до 9000, получается, способствует лучшему выявлению ошибок, даже не смотря на увеличение вероятности появления таковых, ввиду увеличения размера передаваемой порции данных?

Я понял это скорее так: увеличение фрейма более 9К приводит к неприемлемо резкому возрастанию числа ошибок.

1 к 1000 - считать нормой или это очень плохой результат?

Как говорится, it depends. Если это мультимедийный поток и время от времени проскакивают битые пиксели или сэмплы аудио, то вполне можно мириться. Если передается архив, который в итоге не может быть раскрыт, то это крах.

Впрочем, мы сейчас говорим о фреймах канального уровня. Обычно верхом на них едут пакеты/сообщения вышележащих уровней, которые также защищены собственными контрольными кодами и процедурами восстановления (например, TCP). Вероятность необнаруженной ошибки существенно снизится. Кроме того, на прикладном уровне можно применить еше более строгий контроль с обнаружением и исправлением множественных ошибок, дублирование сообщений и т.п. Например, сигнатура MD5 дает количество значений, превышающее число атомов во Вселенной. Все равно не 100%, конечно, но вполне сойдет.

как повлияет увеличение/уменьшение размера контрольной суммы на детектирование?

Чем длиннее контрольный код, тем больше значений он принимает. Соответственно, меньше вероятность случайного совпадения.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines