|
|
  |
Алгоритм CRC16 |
|
|
|
Apr 18 2010, 13:17
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(zltigo @ Apr 17 2010, 19:26)  Зачем повторяться? Но если хотите, то последний раз - Вы, и продолжаете бездумствовать  , даже после лобовых указаний. Ну так имеющий разум да поймет, ну хотя-бы со временем. Я все сказал. Притчу про повторение слова халва слышать приходилось? Можете продолжать, но мне надоело. Не то. В данном случае речь идет просто о банальной вероятности обнаружения ошибки. Хорошо, вот Вам конкретика. По зашумленному каналу передаются данные. Передача идет пакетами по 256 байт. Примерно каждый десятый пакет сбойный - одиночная ошибка. Многократные ошибки соответственно реже. Обнаруженные сбойные пакеты пересылаются повторно. Естественно включен побайтовый контроль четности. Вопрос - какой метод лучше для обнаружения сбойных пакетов, пропущенных побайтовым контролем четности? Прямая 16 битная сумма пропустит сбойный пакет, у которого в одном байте две ошибки и в другом, отстоящем от первого на четное число байт две ошибки в тех же разрядах. В среднем одну из 4х таких ошибок. То есть, четверную ошибку достаточно специального вида. Что пропустит CRC? Хуже в такой достаточно типичной ситуации CRC или лучше. Еще добавим - иногда бывает мощная одиносчная помеха, которая приводит к многократным ошибкам, локализованным компактно. Опять же - что в этой ситуации лучше - прямая сумма или CRC? Как Вам такая конкретика? Жду Вашего обоснованого выбора. Цитата(mdmitry @ Apr 17 2010, 19:20)  В этом случае требуется помехоустойчивое кодирование. Битовый поток кодируют и перемежают, а потом передают по каналу связи. Помехоустойчивое кодирование требуется в случае, если или 90% пакетов сбойные или повторная посылка сбойного пакета затруднена. Если сбойных пакетов ~10% и нет проблем повторить посылку пакета - зачем нам паровоз? А вот между велосипедом и самокатом повыбирать стоит...
|
|
|
|
|
Apr 18 2010, 14:32
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 18 2010, 18:37)  Это - результат Вашего неправильного проектирования... Полагаете, работать не будет? А как должно быть правильно? И каков ответ - что лучше?
|
|
|
|
|
Apr 19 2010, 04:22
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 18 2010, 19:18)  Работать - будет. Но - плохо... Если каждый десятый пакет - сбойный, это - просто отвратительно... Скорее всего, при проектировании канала передачи информации приняты неправильные технические решения. Полагаете, удлинение времени передачи на 10% - категорически неприемлимо? Но если так уж случилось - что выбрать - прямую сумму или CRC? Вариант - вообще не пользоваться этим каналом - не интересен. Цитата(VslavX @ Apr 19 2010, 00:28)  Ничего не пропустит - все обнаружит. Описанная ошибка это некоторое K разрядностью менее длины проверочного слова умноженное на X^n + 1, где n - число бит между ошибками. А X^n + 1 гарантировано без останка не делится для выбранного полинома для достаточно большого n (которое не может превышать общую длину блока, для которого кодовое расстояние 2+). А раз не делится - значит CRC при такой ошибке гарантировано изменится и такую ошибку обнаружит - то есть любое инвертирование бит (менее длины проверочного кода) подряд дважды в любом месте блока будет обнаружено. Да, двойные ошибки будут все обнаружены. Но интересует обнаружение четверных ошибок, пропущенных байтовым контролем по четности ( то есть, два сбойных байта в блоке, в каждом байте двухбитовая ошибка ). Кстати, чтобы CRC обнаруживало все двойные ошибки, нужно чтобы в конце была выполнена холостая прокрутка. Иначе двойная ошибка - бит в последнем слове и бит в слове CRC может быть пропущена.
|
|
|
|
|
Apr 19 2010, 05:26
|

embarrassed systems engineer
    
Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038

|
Цитата(vallav @ Apr 19 2010, 07:37)  Да, двойные ошибки будут все обнаружены. Но интересует обнаружение четверных ошибок, пропущенных байтовым контролем по четности ( то есть, два сбойных байта в блоке, в каждом байте двухбитовая ошибка ). Вы не поняли что я написал. Будет обнаружена двойная ошибка для ЛЮБОЙ последовательности в 'к' бит, если 'к' меньше длины проверочного кода. Длина байта - 8 бит, длина CRC-16 - 16 бит. Причем между сбойными последовательностями может быть произвольное количество битов, не обязательно выравнено на байт. То есть, если одинаково сбоят, например биты 1 и 5 в любых даух байтах - это обнаруживается. Даже если одинаково сбоят биты 0..14 в любых 15 битах - то есть правильная последовательность в двух местах по-XOR-ена с одной и той же 15-битовой комбинацией - то такое тоже 100% обнаруживается. Если же ошибки в байтах разные, то может уже и пропустить.
|
|
|
|
|
Apr 19 2010, 05:52
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Вы хоть в курсе - что это такое - CRC и как именно это делается? Похоже, что нет. У Вас - просто наоборот, чем получается при простом XOR без сдвига. Но это не CRC, это что то другое...
Причина редактирования: Бездумное цитирование
|
|
|
|
|
Apr 19 2010, 06:21
|

embarrassed systems engineer
    
Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038

|
Цитата(vallav @ Apr 19 2010, 09:07)  Вы хоть в курсе - что это такое - CRC и как именно это делается? Похоже, что нет. У Вас - просто наоборот, чем получается при простом XOR без сдвига. Но это не CRC, это что то другое... Это, похоже, Вы не в курсе. Почитали бы что ли хоть азы полиномиальной арифметики, тогда поняли о чем пишется: "Пакет" = "Передаваемые данные" + "Ошибка" В этом тождестве все переменные - полиномы, а операция сложения выполняется полиномиально - именно "простым XOR-ом". CRC- это остаток от полиномиального деления: CRCp = "Пакет" % "проверочный полином" Для правильный данных: CRCd = "Передаваемые данные" % "проверочный полином" CRCp будет равно CRCd (пакет ошибочно считается правильным) тогда и только тогда, когда CRCe = "Ошибка" % "проверочный полином" = 0 (равно нулю, то есть делится без остатка на проверочный полином) Для Вашего примера ошибка представляется так: "Ошибка" = (00..00100..n-bit...00100..00) x K, битовая длина произвольного K меньше длины проверочного полинома CRCe будет нулевым если K или (00..100..n-bit..00100..00) делится на полином без остатка К - не делится, так как его длина меньше чем длина полинома (00..1..1..00) - не делится для любой возможной комбинации в пакете, так как полином и разрядность CRC всегда выбирается такой чтобы мин кодовое расстояние было не менее 2. Поэтому ошибка того типа про которую Вы толкуете ловится CRC "влет". Компрене? Upd: Для CRC-16 длина проверочного полинома на самом деле 17 бит, поэтому длина К может быть до 16 бит включительно.
|
|
|
|
|
Apr 19 2010, 07:03
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Ну что Вам сказать. Вы настолько в этм всем уверены, что ... На самом деле, CRC заточена на отлавливание двух битовых ошибок произвольно расположенных в передаваемогм пакете ( двухкратная ошибка ). Но это не дается даром. CRC довольно плох при отлавливания многобитовых ошибок. В часности, в данном случае нужно ловить четырехкратную ошибку.
Причина редактирования: Бездумное цитирование
|
|
|
|
|
Apr 19 2010, 07:26
|

embarrassed systems engineer
    
Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038

|
Цитата(vallav @ Apr 19 2010, 10:18)  Ну что Вам сказать. Вы настолько в этм всем уверены, что ... Ясно, значит будем сомневаться в арифметике. Более просто и строго я объяснить не в силах. Цитата(vallav @ Apr 19 2010, 10:18)  На самом деле, CRC заточена на отлавливание двух битовых ошибок произвольно расположенных в передаваемогм пакете ( двухкратная ошибка ). Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых. Цитата(vallav @ Apr 19 2010, 10:18)  Но это не дается даром. Чем надо платить?  На самом деле, CRC в "железе" реализуется намного проще чем упомянутая Вами обычная арифметическая сумма. Программная реализация CRC тоже не особо сложна - если понять принцип. Я Вам даже открою "секрет" - в криптографии, там где очень длинные числа, полиномиальное деление и сложение как правило работают быстрее обычных - так как нет этого дурацкого распространяемого между словами переноса. Медленее работает умножение - и то исключительно потому что у большинства процессоров нет инструкции полиномиального умножения. Цитата(vallav @ Apr 19 2010, 10:18)  CRC довольно плох при отлавливания многобитовых ошибок. Любую однократную в "k бит подряд" CRC отлавливает. Ну а умеючи-то - все что хошь сломать можно  Цитата(vallav @ Apr 19 2010, 10:18)  В часности, в данном случае нужно ловить четырехкратную ошибку. Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.
|
|
|
|
|
Apr 19 2010, 10:35
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(VslavX @ Apr 19 2010, 11:41)  Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться. Значит Ваша версия - в приведенном примере лучше использовать CRC. Так как Вы уверены, что она отлавливает все четверные ошибки. Так? И даже отлавливает все ошибки большей кратности, вплоть до 16. И зыждется эта уверенность на том, что "полиномиальная арифметика в частности, и теория линейных кодов в общем". Если не секрет, CRC с каким полиномом обладает таким замечательным свойством? Для пакета длиной в 256 байт и контрольном слове длиной 16 бит. Можно попробовать проверить это замечательное свойство прямым вычислением ( если полином приведете ). Кстати, на поясните Ваше - "Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых". Чем именно двухкратная многобитовая ошибка отличается от однократной многобитовой?
|
|
|
|
|
Apr 19 2010, 11:27
|

embarrassed systems engineer
    
Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038

|
Цитата(vallav @ Apr 19 2010, 13:50)  Так как Вы уверены, что она отлавливает все четверные ошибки. Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях. Цитата(vallav @ Apr 19 2010, 13:50)  И даже отлавливает все ошибки большей кратности, вплоть до 16. Да, если эти 16 бит расположены подряд. Цитата(vallav @ Apr 19 2010, 13:50)  Если не секрет, CRC с каким полиномом обладает таким замечательным свойством? Для пакета длиной в 256 байт и контрольном слове длиной 16 бит. Можно попробовать проверить это замечательное свойство прямым вычислением ( если полином приведете ). Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылкаOK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.
|
|
|
|
|
Apr 19 2010, 12:37
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(VslavX @ Apr 19 2010, 15:42)  Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях. Не не так. В двух байтах по двухбитной ошибке. Это то, что пропустил контроль побайтовой четности. А где в блоке байты и где в байтах ошибки - не важно. Конкретно - искажены два байта, по два бита в каждом, на одних и тех же позициях - это то, что прямая сумма пропускает. А CRC может пропустить не эти, а другие, удовлетворяющие исходному условию. Цитата(VslavX @ Apr 19 2010, 15:42)  Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылкаOK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт. Вы про http://rsdn.ru/article/files/classes/SelfCheck/crcguide.pdfИ что именно Вы там обнаружили? Или Вы туда даже не заглядывали...
|
|
|
|
|
Apr 19 2010, 14:28
|

кекс
     
Группа: Свой
Сообщений: 3 825
Регистрация: 17-12-05
Из: Киев
Пользователь №: 12 326

|
Цитата(vallav @ Apr 19 2010, 10:18)  CRC довольно плох при отлавливания многобитовых ошибок.  - несомненно ваша арифметическая сумма гораздо лучше. Вероятность того, что CRC32 пропустит серьезную ошибку - например весь пакет искажен нафиг - равна 1 / 2^32. Вероятность же, что такую ошибку пропустит ваша сумма равна - 1/2. --> если пакет будет занулен - пропустит, если "заединичен" - непропустит. Вот собсно и вся надежность децкой суммы - 50/50. Цитата А CRC может пропустить не эти, а другие, удовлетворяющие исходному условию. Чтобы Вам не быть голословным, можете привести конкретный пример, - когда CRC16 пропускает искажение любых 4-х битов сообщения? А мы потом пообсуждаем.
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|