Выбор CRC

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

Выбор CRC

Сообщение mirk » 04.05.2019 11:36:24

Есть куча возможных размеров CRC - 8, 10, 16, 24, 32 и наверное еще куча других.
Но как выбрать нужный размер?
Может есть табличка для какого размера блока данных какой размер CRC?
mirk
постоялец
 
Сообщения: 317
Зарегистрирован: 24.09.2007 10:03:39

Re: Выбор CRC

Сообщение olegy123 » 05.05.2019 00:05:21

Странно, почему моего ответа нет..
mirk писал(а):Но как выбрать нужный размер?

если для себя, то чем больше размер члена CRC тем естественно луче.. меньше коллизий, меньше нарваться на дубликат CRC.

А если нужно работать с чужими механизмами то там этот размер строго оговаривается..
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: Выбор CRC

Сообщение mirk » 05.05.2019 01:05:15

olegy123 писал(а):Странно, почему моего ответа нет..

Был удален, ибо флуд :wink:

olegy123 писал(а):если для себя, то чем больше размер члена CRC тем естественно луче.. меньше коллизий, меньше нарваться на дубликат CRC.

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

Вот возьмем пример IP - там CRC 2 байта и только для заголовка.
В UDP тоже есть CRC 2 байта, но уже для заголовка с данными - а это может быть уже до 1.5 кб в обычном режиме и как минимум до 8к в режиме Jumbo Frame.
Вот хватит ли этих 2 байт для 1.5кб? А хватит ли для 8кб?
Может надо 4? А может 8? А может еще больше? Так сколько же надо?
mirk
постоялец
 
Сообщения: 317
Зарегистрирован: 24.09.2007 10:03:39

Re: Выбор CRC

Сообщение Снег Север » 05.05.2019 08:08:52

Наиболее вероятно, что размер берется минимальный для статистически обработанных случаев сбоев. Никакой другой математики я тут не вижу.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2993
Зарегистрирован: 27.11.2007 16:14:47

Re: Выбор CRC

Сообщение iskander » 05.05.2019 08:31:44

Битовая ширина CRC определяет вероятность необнаружения ошибки.
Обсуждение связанных с этим вопросов встречалось в книге Таненбаума "Компьютерные сети".
Никакой таблички, впрочем, там нет.
Хотелось бы верить, что проблема выбора размера CRC лежит все-таки в сфере связи, а не программирования. :?
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

Re: Выбор CRC

Сообщение mirk » 05.05.2019 11:36:14

iskander писал(а):Хотелось бы верить, что проблема выбора размера CRC лежит все-таки в сфере связи, а не программирования.

С одной стороны да, есть надежда в правильном выборе при использовании стандартных протоколов.
Но когда начинаешь лезть немного в сторону (например увеличитавть размер пакета или наоборот сильно уменьшать и экономить каждый байт канала связи), то и возникает вопрос как сделать эффективно и надежно.
mirk
постоялец
 
Сообщения: 317
Зарегистрирован: 24.09.2007 10:03:39

Re: Выбор CRC

Сообщение serbod » 05.05.2019 14:51:19

кроме числа битов ещё имеет значение полином и методика подсчета. В целом, 8 бит очень слабая CRC, даже для коротких посылок до 12 байтов даёт коллизии. 16 бит уже вполне норм для пакетов в несколько кбайт, но там десятки вариантов, нужно проверять их на совместимость. А CRC32 самая распространенная и вполне стандартная, реализована в железе.
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: Выбор CRC

Сообщение mirk » 06.05.2019 13:25:41

8 отбрасывем, остается 16 и 32.
Для мелких посылок (до 1.5 кб) можно легко пользоваться как я понимаю 16 битами.
А вот с 1.5 до 8-9 кб хватит 16 бит или уже надо 32?
mirk
постоялец
 
Сообщения: 317
Зарегистрирован: 24.09.2007 10:03:39

Re: Выбор CRC

Сообщение Vadim » 06.05.2019 13:48:36

mirk
Если сильно хочется сэкономить, то можно использовать банальный бит чётности. ;-)
А так, с чисто теоретической точки зрения советуют собирать собственную статистику ошибок для каждого конкретного CRC с Вашими типичными наборами данных.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Выбор CRC

Сообщение vada » 06.05.2019 16:02:59

Стоит обратиться к информации 90-х годов. Период расцвета FidoNET
https://bourabai.ru/telecom/9.htm

Связь по медной телефонной паре была не ахти какая. Помехи, качество линий, наводки,... Но это все работало.

Ну и про гидру
https://docplayer.ru/90046438-Hydralink ... gidra.html
Аватара пользователя
vada
энтузиаст
 
Сообщения: 691
Зарегистрирован: 14.02.2006 13:43:17

Re: Выбор CRC

Сообщение mirk » 06.05.2019 16:22:30

Vadim писал(а):Если сильно хочется сэкономить, то можно использовать банальный бит чётности.

Это не позволит надежно определять наличие ошибки.

vada писал(а):Связь по медной телефонной паре была не ахти какая. Помехи, качество линий, наводки,... Но это все работало.

Там размер пакета в большинстве случаев 128 байт, и максимум 1к.
С этим все уже понятно - 16 бит достаточно, а вот хватит ли 16 для больших объемов?
mirk
постоялец
 
Сообщения: 317
Зарегистрирован: 24.09.2007 10:03:39

Re: Выбор CRC

Сообщение serbod » 06.05.2019 22:59:52

Для пакета в 100 байтов, CRC32 это всего лишь 4% оверхеда. А для 1000 байтов 0.4%
Но при этом CRC32 практически полностью исключает вероятность коллизии.
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: Выбор CRC

Сообщение ev » 07.05.2019 01:15:58

еще можно добавить, что CRC32C аппаратно может ускоряться на современных процессорах
ev
долгожитель
 
Сообщения: 1763
Зарегистрирован: 27.04.2005 23:19:06
Откуда: Москва

Re: Выбор CRC

Сообщение Vadim » 07.05.2019 09:55:44

ev писал(а):еще можно добавить, что CRC32C аппаратно может ускоряться на современных процессорах

На всех? Или каких-то специальных, типа как в телевизоры вставляют?
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Выбор CRC

Сообщение iskander » 07.05.2019 11:02:49

Если правильно путаю, инструкция CRC32 появилась в SSE4.2
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

След.

Вернуться в Общее

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

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

Рейтинг@Mail.ru
cron