|
Алгоритм CRC16 |
|
|
|
Apr 10 2010, 07:39
|

Частый гость
 
Группа: Свой
Сообщений: 156
Регистрация: 10-03-10
Из: Уфа
Пользователь №: 55 882

|
Устройство на sam7x должно обмениваться по uart пакетами длинной 76 байт + 2 байта CRC16 с программой на компьютере. Исходника программы компа нет, но есть исходник (в icc) предыдущей версии рабочего устройства (правильно рассчитываеющего CRC и успешно обменивающегося с программой), из которого был взят фрагмент рассчёта CRC. По какой то причине CRC рассчитывается неверно. Фрагмент для IAR: Код // пакет лежит в uart1_buffer // len - длина пакета, по которому считается CRC (76 байт) void CRC16(unsigned int len) { unsigned char i; unsigned int k; unsigned int CRC;
CRC=k=0; while(k<len){ CRC=CRC^((unsigned int)uart1_buffer[k++]<<8); i=8; do{ if(CRC & 0x8000) CRC=(CRC<<1)^0x1021; else CRC=CRC<<1; } while(--i); } // дописываем в конец буфера CRC16 uart1_buffer[76]=CRC & 0xff; uart1_buffer[77]=(CRC>>8) & 0xff; } Для пакета Код 0A 90 00 00 00 00 00 00 00 00 4F 33 40 40 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 CRC16 должна быть равна A1 01, а рассчитывается 0B D1, перепробовал ещё кучу стандартных алгоритмов, все рассчитывают новые CRC, но ни одна не посчитала A1 01. Голову сломал на этом затыке. Буду благодарен за любые мысли по проблеме
--------------------
Руслан
|
|
|
|
|
 |
Ответов
|
Apr 10 2010, 09:01
|

Частый гость
 
Группа: Свой
Сообщений: 156
Регистрация: 10-03-10
Из: Уфа
Пользователь №: 55 882

|
Цитата(AHTOXA @ Apr 10 2010, 14:24)  Видимо то устройство, что работало, было 16-битное?  Попробуйте заменить unsigned int на unsigned short. Устройство было на меге2561  Цитата(baralgin @ Apr 10 2010, 14:40)  Если перед расчётом CRC проинициализировать 0x6DA5 (вместо 0), то получится как-раз "A1 01" . Просто брутфорс  . Исходник один в один скопировали? да, брал исходник как есть Всё разобрался, рядом с этой функцией лежала такая же с постфиксом New в имени  , в которой алгоритм гораздо проще, опробовал - считает правильно: Код void SumCRCNew(unsigned int len) { unsigned char i; unsigned int CRC;
CRC=0; for(i=0;i<76;i++) CRC+=uart1_buffer[i]; uart1_buffer[76]=CRC & 0xff; uart1_buffer[77]=(CRC>>8) & 0xff; } Видимо для обмена по uart прошлым разработчикам пришлось упростить контроль целостности пакета, а я эту функцию проморгал  Всем отписавшимся огромное спасибо
--------------------
Руслан
|
|
|
|
|
Apr 13 2010, 15:40
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(ASN @ Apr 10 2010, 16:22)  athlon64 Видимо, это стандартный CRC16 для обмена по стыку IRDA. В Linux есть исходники расчёта CRC на С.Считается табличным методом. Замена на сложение принципиально ухудшает обнаруживающую ошибки способность. Всегда интересовало - почему "Замена на сложение принципиально ухудшает обнаруживающую ошибки способность"? Одиночные ошибки - одинаково. Обнаруживаются всегда. Двойные - от статистики зависит. Если они часто в одном разряде, CRC лучше, если они независимы, сложение лучше.
|
|
|
|
|
Apr 13 2010, 17:01
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(ASN @ Apr 13 2010, 20:43)  vallav Теорию не помню. По опыту. Работаем в очень сложной помеховой обстановке. Сложение ошибок не обнаруживало, CRC - обнаруживало. Не очень понятно. Может - сложение иногда многкратных ошибок не обнаруживало ( пропускало пакет с ошибками ). CRC пропускало пакет с ошибками в несколько раз реже. Такое может быть, если многократные ошибки сильно и специфически коррелированы. А вот чтобы - сложение всех ошибок не обнаруживало а CRC все ошибки обнаруживало - такое вряд ли.
|
|
|
|
|
Apr 14 2010, 10:13
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(demiurg_spb @ Apr 13 2010, 23:23)  Вы к чему эту ссылку привели? Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью. Кроме одного случая - в случае, когда двойные ошибки в одном разряде, CRC лучше. А разве с этим кто либо спорил?
|
|
|
|
|
Apr 14 2010, 19:05
|

неотягощённый злом
     
Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643

|
Цитата(vallav @ Apr 14 2010, 14:28)  Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью. Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!! Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно)  во столько же раз больше. За всё надо платить - закон сохранения энергии, однако! Цитата(defunct @ Apr 14 2010, 02:19)  По крайней мере можно так: Код if (crc & 1) crc = (crc >> 1) ^ 0xA001; else crc = (crc >> 1); Не, не моё это:-) Я либо в строку форматирую, либо уж по полной программе со скобочками. К полумерам не привык! Два по сто в одной посуде!:)
--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
|
|
|
|
|
Apr 15 2010, 05:10
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(demiurg_spb @ Apr 14 2010, 23:20)  Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!! Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно)  во столько же раз больше. За всё надо платить - закон сохранения энергии, однако! Вы полагаете, это аргумент - все так делают, поэтому так делать - правильно? Закон сохранения энергия вроде не гласит - чем больше энергии затрачено, тем лучше вещь получается... Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32 - знаете, как считается? Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она породит нужное, равна 1 к 2^16. Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы. Исторически CRC появилась по простой причине - в механических телетайпах основной ошибкой были сбои в одном из реле, что порождало многократные ошибки в одном из разрядов. СRC тут намного лучше прямой суммы. Но времена те ушли, а CRC осталось... Кстати, прямая сумма чуть лучше побитового XOR - пропускает в два раза меньше двойных ошибок в одном разряде.
|
|
|
|
|
Apr 15 2010, 06:11
|

Гуру
     
Группа: Свой
Сообщений: 2 399
Регистрация: 10-05-06
Из: г. Новочеркасск
Пользователь №: 16 954

|
Цитата(vallav @ Apr 15 2010, 08:25)  Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она породит нужное, равна 1 к 2^16. Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы. Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока
|
|
|
|
|
Apr 15 2010, 06:22
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 15 2010, 10:26)  Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока Вы хотели сказать, при размерах поражения порядка длины контрольного слова? То есть когда поражено несколько бит? Повторюсь - CRC лучше для двойных регулярных ошибок ( когда они в одном разряде ). В остальных случаях - надо специально разбираться.
|
|
|
|
|
Apr 15 2010, 07:19
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 15 2010, 11:12)  Интуитивно понятно, и - спору нет. При длине блока даже в 256 байт простая сумма будет менее 2^16. Даже при бОльшей длине блока не будет выполняться равновероятность пораждения одного из значений CRC (ситуацию нЕсколько спасёт циклическая сумма). Для суммы: только при очень большой длине блока (строго говоря - бесконечной) это условие выполнится. При длине блока в 4 байта простая сумма может быть больше, чем 2^16. Или Вы хотите суммировать байты для получения 16 разрядной контрольной суммы? Какой смысл - складывать в старший байт переносы? Вроде при этом надо суммировать 16 разрядные слова. Кстати, простая сумма не пропустит ни одного едеичного поражения длиной менее 17 бит. CRC может пропустить ( от конкретного способа перемешивания бит зависит ).
|
|
|
|
|
Apr 15 2010, 09:34
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 15 2010, 12:19)  Извините, но Вы так и делаете: получаете сумму значений 76 байт, а не 38 слов (см. функцию void SumCRCNew(unsigned int len) ).
P.S.Поправка: делает это athlon64, но Вы его решения защищаете С чего Вы взяли, что я настаиваю именно на таком вычислении контрольной суммы? Я просто спросил - почему CRC лучше прямой суммы. Вы согласны, что посчитать 16 битную сумму столь же просто, как и 8 битную? И намного проще и быстрее, чем правильное 16 битное CRC? Так что скажите для случая 16 битной суммы?
|
|
|
|
|
Apr 15 2010, 13:34
|

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

|
Цитата(vallav @ Apr 15 2010, 12:49)  С чего Вы взяли, что я настаиваю именно на таком вычислении контрольной суммы? Я просто спросил - почему CRC лучше прямой суммы. ... Так что скажите для случая 16 битной суммы? Есть такое понятие - кодовое расстояние. Это число разрядов в двух битовых последовательностях которые отличается. Если у Вас в принимаемой последовательности сбойнул один бит, то кодовое расстояние между правильной и ошибочно принятой последовательности равно 1, если два бита - то 2 и т.д. Так вот, математически доказано, что CRC (которое является фактически делением на определенные полиномы) покрывает максимально возможное кодовое расстояние ошибок для данной длины корректирующего кода . То есть, обнаруживает максимально возможно количество единичных искажений. Если принято какое-то значение CRC, то для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16). Если же у Вас просто сумма, то достаточно исказить всего два бита (например, инвертировать младшие биты в байтах в которых эти биты несовпадают) и ошибка уже не будет обнаружена. Вот поэтому CRC намного лучше простой суммы.
|
|
|
|
|
Apr 15 2010, 17:17
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(VslavX @ Apr 15 2010, 17:49)  Есть такое понятие - кодовое расстояние. Это число разрядов в двух битовых последовательностях которые отличается. Если у Вас в принимаемой последовательности сбойнул один бит, то кодовое расстояние между правильной и ошибочно принятой последовательности равно 1, если два бита - то 2 и т.д. Так вот, математически доказано, что CRC (которое является фактически делением на определенные полиномы) покрывает максимально возможное кодовое расстояние ошибок для данной длины корректирующего кода . То есть, обнаруживает максимально возможно количество единичных искажений. Если принято какое-то значение CRC, то для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16). Если же у Вас просто сумма, то достаточно исказить всего два бита (например, инвертировать младшие биты в байтах в которых эти биты несовпадают) и ошибка уже не будет обнаружена. Вот поэтому CRC намного лучше простой суммы. Одиночные ошибки обоими способами обнаруживаются все. Для двойных - зависит от статистики ошибок. Вполне допускаю, что есть такие CRC, которые обнаруживают их все. Но ничто не дается даром. Эти CRC будут проигрывать простой сумме в обнаружении достаточно типичных ошибок, вызванных помехой - одиночных многобитных сбоев. Прямая сумма будет обнаруживать все такие сбои длиной меньше или равной длине контрольного слова. CRC, заточенная на двойные разнесенные ошибки, часть из таких сбоев не заметит. И больше похоже на правду, что для такого CRC число это не 14 а 3. Так что, что лучше - зависит от того - а какие именно ошибки нужно обнаруживать. Цитата(ASN @ Apr 15 2010, 15:48)  Палыч Пример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока: Требуется 16 триггеров. Не больше чем для простой суммы. А разве ктот то утверждал, что на плиске алгоритм CRC нереализуем? Цитата(ASN @ Apr 15 2010, 15:48)  Расчёт для 8-ми битной ЭВМ табличным способом: Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее. Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC. Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы. А расзве кто то утверждал, что табличного алгоритма вычисления CRC не существует? Он есть, и он в разы медленнее и больше по объему кода, чем вычисление простой суммы. А то, что одна из причин использования CRC ( если не единственная ) - Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы - с этим тоже вроде никто не спорит. Речь о другом - в чем преимущества CRC при обнаружении ошибок при блочной передаче. И стьль ли они подавляющи ( если есть ) чтобы принебрегать вариантом с простой суммой?
|
|
|
|
|
Apr 15 2010, 17:39
|
Местный
  
Группа: Свой
Сообщений: 459
Регистрация: 15-07-04
Из: g.Penza
Пользователь №: 326

|
vallav Пример на VHDL приведён как подтверждение того факта, что реализация на аппаратной логике вычисления CRC как минимум не уступает по производительности и ресурсам вычислению прямой суммы. Пример кода на С приведёт как подтверждение того факта, что реализация табличным способом не намного сложнее и медленнее, чем прямая сумма. Для данного конкретного случая он в разы не медленнее. Поясните почему специалисты, разработавшие STANAG5066, не стали использовать обычное сложение, а применили для контроля целостности пакета CRC16 и CRC32. Поскольку STANAG5066 использует в качестве основы STANAG4285, где применён свёрточный код, ошибки при его декодировании пакетные (длина искажённой последовательности как больше длины проверочного слова, так и меньше).
|
|
|
|
|
Apr 16 2010, 05:20
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(ASN @ Apr 15 2010, 21:54)  vallav Пример на VHDL приведён как подтверждение того факта, что реализация на аппаратной логике вычисления CRC как минимум не уступает по производительности и ресурсам вычислению прямой суммы. Пример кода на С приведёт как подтверждение того факта, что реализация табличным способом не намного сложнее и медленнее, чем прямая сумма. Для данного конкретного случая он в разы не медленнее. Поясните почему специалисты, разработавшие STANAG5066, не стали использовать обычное сложение, а применили для контроля целостности пакета CRC16 и CRC32. Поскольку STANAG5066 использует в качестве основы STANAG4285, где применён свёрточный код, ошибки при его декодировании пакетные (длина искажённой последовательности как больше длины проверочного слова, так и меньше). Вообще то реализация сумматора на логике заметно сложнее реализации CRC. Речь о ситуации, когда сумматор в системе уже есть. И реализован достаточно эффективно. То есть, там не важно обнаружение двойных разрозненных ошибок а важно определение еденичных поражений порядка длины поверочного слова? Тогда не знаю почему. Может исходя из - поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.
Сообщение отредактировал vallav - Apr 16 2010, 05:24
|
|
|
|
|
Apr 16 2010, 06:02
|

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

|
Цитата(vallav @ Apr 16 2010, 08:35)  То есть, там не важно обнаружение двойных разрозненных ошибок а важно определение еденичных поражений порядка длины поверочного слова? Тогда не знаю почему. ИМО, "единичные поражения порядка длины поверочного слова" CRC выловит ничуть не хуже простой суммы. Ну и как бонус выловит _ВСЕ_ единичные ошибки числом менее или равное кодовому расстоянию для данных длин блока и суммы. Можно сделать простой эксперимент - берем блок, вычисляем сумму и CRC. Потом вносим определенное "поражение длиной в кодовое слово" - и смотрим сколько вариантов "поражения" не поймает сумма и сколько CRC. Если сумма 16-битная, сложение побайтовое и 16-битовое "поражение" выровнять на границе байта, то будет 255 "непойманных" вариантов для простой суммы, для CRC-16, думаю, будут единичные значения (так как CRC это остаток от деления - нужно будет подобрать такое значение искажения чтобы делилось на образующий полином с нулевым остатком, а таких значений для полиномов применяемых для CRC может быть одно-два).
|
|
|
|
|
Apr 16 2010, 07:35
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(VslavX @ Apr 16 2010, 10:17)  ИМО, "единичные поражения порядка длины поверочного слова" CRC выловит ничуть не хуже простой суммы. Ну и как бонус выловит _ВСЕ_ единичные ошибки числом менее или равное кодовому расстоянию для данных длин блока и суммы. Можно сделать простой эксперимент - берем блок, вычисляем сумму и CRC. Потом вносим определенное "поражение длиной в кодовое слово" - и смотрим сколько вариантов "поражения" не поймает сумма и сколько CRC. Если сумма 16-битная, сложение побайтовое и 16-битовое "поражение" выровнять на границе байта, то будет 255 "непойманных" вариантов для простой суммы, для CRC-16, думаю, будут единичные значения (так как CRC это остаток от деления - нужно будет подобрать такое значение искажения чтобы делилось на образующий полином с нулевым остатком, а таких значений для полиномов применяемых для CRC может быть одно-два). А что не побитовое сложение? Разница еще разительнее получится. Вы где то нашли микроконтроллер, в котором затруднительно делать 16 битные сложения? Полная сумма не пропустит ни одного еденичного многобитового поражения длиной меньше или равного 16 бит. CRC же, в зависимости от вида перемешивания битов. Чем лучше заточена на отлов двойных разрозненных ошибок, тем более короткие еденичные многобитные будет пропускать.
|
|
|
|
|
Apr 16 2010, 08:17
|

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

|
Цитата(vallav @ Apr 16 2010, 10:50)  А что не побитовое сложение? ... Вы где то нашли микроконтроллер, в котором затруднительно делать 16 битные сложения? А Вы где-то четко указали что сложения идут 16-битными словами? Обычно программа упрощена - идет поток байтов и складываются байты - не надо рассматривать случаи с нечетным количеством и т.д. И не уводите ситуацию в сторону - я просто привел Вам пример когда простая сумма оказалась многократно хуже CRC. Разумеется и наоборот, можно натянуть условия, и показать что CRC хуже суммы для каких-то конкретных условий, но все равно - не столь кратно. И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили? Линии передачи ведь разные бывают, и вероятности возникновения различных ошибок тоже разные. Я думаю, CCITT несколько более осведомлен в этом вопросе, раз уж выбрана CRC (как я понимаю - для модемных соединений).
|
|
|
|
|
Apr 16 2010, 10:25
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(Палыч @ Apr 16 2010, 13:17)  Присоединюсь к мнению, что единичное многобитовое поражение - скорее, нетипичная ситуация. А то у Вас прям какая-то интеллектуальная помеха: строго инвертирует последовательность бит в данных... Такая ситуация вероятнее всего, если в потоке данных имеется большая последовательность нулей (или единиц), а помеха привела к декодированию на приёмнике единиц (нулей). Но, это - уже недостатки кодирования данных, а не проверки их целостности. Я разве говорил, что многобитовая помеха - это когда все 16 бит перевернуты? Не, не обязательно, часть бит из этих 16 может быть не перевернутой. На то она и помеха. Цитата(VslavX @ Apr 16 2010, 12:32)  А Вы где-то четко указали что сложения идут 16-битными словами? Обычно программа упрощена - идет поток байтов и складываются байты - не надо рассматривать случаи с нечетным количеством и т.д. И не уводите ситуацию в сторону - я просто привел Вам пример когда простая сумма оказалась многократно хуже CRC. Разумеется и наоборот, можно натянуть условия, и показать что CRC хуже суммы для каких-то конкретных условий, но все равно - не столь кратно. И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили? Линии передачи ведь разные бывают, и вероятности возникновения различных ошибок тоже разные. Я думаю, CCITT несколько более осведомлен в этом вопросе, раз уж выбрана CRC (как я понимаю - для модемных соединений). Дык если не указано, из примерно одинакового рассматривать надо лучшее а не худшее. Или Вы все же настаиваете, что для микроконтроллеров 16 битное сложение реализуется существенно сложнее 8 битного? А с нечетным числом байт в блоке фиксированной длины - полагаете, непреодолимо? И еще раз - я не утверждаю, что CRC хуже прямой суммы, я утверждаю, что прямая сумма не хуже CRC во многих случаях но много проще в реализации. По поводу - какие ошибки - как раз сторонники CRC должны привести обоснование, что в данной конкретной ситуации ( где применен более сложный в реализации метод ) ошибки таковы, что усложнение оправдано.
|
|
|
|
|
Apr 16 2010, 16:03
|

Гуру
     
Группа: Свой
Сообщений: 13 372
Регистрация: 27-11-04
Из: Riga, Latvia
Пользователь №: 1 244

|
Цитата(vallav @ Apr 16 2010, 13:40)  И еще раз - я не утверждаю, что CRC хуже прямой суммы, я утверждаю, что прямая сумма не хуже CRC во многих случаях.. Вероятностно ХУЖЕ во всех случаях, кроме одного единственного - одиночная ошибка. В этом случае она ЛУЧШЕ. Все, достаточно толочь воду в ступе. Цитата(vallav @ Apr 16 2010, 19:11)  Я этим термином именую ситуацию, когда ошибок много, но все ни в пределах 16 последовательных бит. А с помехой Вы как договариваетесь, о том, что-бы эти биты еще и располагались выровненно относительно размера суммируемого фрейма?
--------------------
Feci, quod potui, faciant meliora potentes
|
|
|
|
|
Apr 16 2010, 17:19
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(zltigo @ Apr 16 2010, 20:18)  Вероятностно ХУЖЕ во всех случаях, кроме одного единственного - одиночная ошибка. В этом случае она ЛУЧШЕ. Все, достаточно толочь воду в ступе. Откуда такая уверенность? Вроде для обнаружения многобитной одиночной ошибки CRC хуже. Лучше оно только для обнаружения двух разнесенных по блоку однобитных ошибок. Цитата(zltigo @ Apr 16 2010, 20:18)  А с помехой Вы как договариваетесь, о том, что-бы эти биты еще и располагались выровненно относительно размера суммируемого фрейма? А зачем? Разве я где то говорил про какую то выровненность?
|
|
|
|
|
Apr 17 2010, 13:44
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(zltigo @ Apr 16 2010, 23:04)  Да Вы даже об этом и не задумывались, и сейчас не думаете, судя по изобретению дивного термина "многобитная одиночная ошибка"  . Так поясните. Вдруг это Вы не задумывались? И заодно предложите другой термин для многибной ошибки, локализованной в пределах n последовательных бит ( ошибки, вызванные одиночной мощной помехой ).
|
|
|
|
|
Apr 17 2010, 14:16
|

Гуру
     
Группа: Свой
Сообщений: 13 372
Регистрация: 27-11-04
Из: Riga, Latvia
Пользователь №: 1 244

|
Цитата(vallav @ Apr 17 2010, 16:59)  И заодно предложите другой термин для многибной ошибки, локализованной в пределах n последовательных бит ( ошибки, вызванные одиночной мощной помехой ). Другие термины для изобретенного Вам сферического коня в вакууме не требуются. Для битового потока одиночная ошибка это бит. Все остальные это множественные ошибки. Их локализация в пределах произвольного количества бит, отстоящих на произвольное количество бит от начала фрейма ничего не дает для простейшего суммирования.
--------------------
Feci, quod potui, faciant meliora potentes
|
|
|
|
|
Apr 17 2010, 14:30
|
Частый гость
 
Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977

|
Цитата(zltigo @ Apr 17 2010, 18:31)  Другие термины для изобретенного Вам сферического коня в вакууме не требуются. Для битового потока одиночная ошибка это бит. Все остальные это множественные ошибки. Их локализация в пределах произвольного количества бит, отстоящих на произвольное количество бит от начала фрейма ничего не дает для простейшего суммирования. Вы забыли пройтись по первому пункту. Кто там мало подумал? А по поводу вида ошибок - ошибки бывают разные. Под те, что Вы описали - как раз CRC заточено. Это канал с постоянным но небольшим шумом. Но есть и другие например, когда в канале возможна редкая но мощная помеха. В этом случае сбойных битов много, но они в одном месте сосредоточены. Вот для этого CRC мало пригодна.
|
|
|
|
|
Apr 17 2010, 15:11
|

Гуру
     
Группа: Свой
Сообщений: 13 372
Регистрация: 27-11-04
Из: Riga, Latvia
Пользователь №: 1 244

|
Цитата(vallav @ Apr 17 2010, 17:45)  Вы забыли пройтись по первому пункту. Кто там мало подумал? Зачем повторяться? Но если хотите, то последний раз - Вы, и продолжаете бездумствовать  , даже после лобовых указаний. Ну так имеющий разум да поймет, ну хотя-бы со временем. Я все сказал. Цитата Вот для этого CRC мало пригодна. Притчу про повторение слова халва слышать приходилось? Можете продолжать, но мне надоело. Цитата(mdmitry @ Apr 17 2010, 18:20)  В этом случае требуется помехоустойчивое кодирование. Не то. В данном случае речь идет просто о банальной вероятности обнаружения ошибки.
--------------------
Feci, quod potui, faciant meliora potentes
|
|
|
|
|
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:59
|

Гуру
     
Группа: Свой
Сообщений: 2 399
Регистрация: 10-05-06
Из: г. Новочеркасск
Пользователь №: 16 954

|
Цитата(vallav @ Apr 19 2010, 15:52)  ...Это то, что пропустил контроль побайтовой четности. А где в блоке байты и где в байтах ошибки - не важно. Конкретно - искажены два байта, по два бита в каждом, на одних и тех же позициях - это то, что прямая сумма пропускает. А CRC может пропустить не эти, а другие, удовлетворяющие исходному условию. Ну, что Вы так разошлись? Вашу бы энергию - да в мирных целях... Контроль чётности в Вашем примере - слабое утешение, раз помеха у Вас столь продолжительная, что действует в течении времени передачи двух байтов (помеха и на биты четности может повлиять). Поэтому суммирование может пропустить и блок, в котором информация искажена всего в двух битах. Конечно же, CRC - не панацея, и по её анализу тоже может принято неверное решение о целостности пакета, но на "малых" длинах пакетов, имхо, CRC всяко лучше простой суммы.
|
|
|
|
Сообщений в этой теме
athlon64 Алгоритм CRC16 Apr 10 2010, 07:39 AHTOXA Видимо то устройство, что работало, было 16-битное... Apr 10 2010, 08:09 demiurg_spb Код//=============================================... Apr 10 2010, 08:13 defunct Цитата(demiurg_spb @ Apr 10 2010, 11:28) ... Apr 10 2010, 23:07  demiurg_spb Цитата(defunct @ Apr 11 2010, 03:22) И эт... Apr 13 2010, 06:47   defunct Цитата(demiurg_spb @ Apr 13 2010, 10:02) ... Apr 13 2010, 19:16    demiurg_spb Цитата(defunct @ Apr 13 2010, 23:31) Не п... Apr 13 2010, 19:28     defunct Цитата(demiurg_spb @ Apr 13 2010, 22:43) ... Apr 13 2010, 22:04 baralgin Если перед расчётом CRC проинициализировать 0x6DA5... Apr 10 2010, 08:25 zltigo Цитата(AHTOXA @ Apr 10 2010, 10:24) Видим... Apr 10 2010, 08:59 demiurg_spb zltigo, нет предела совершенству, можно и так:
Код... Apr 10 2010, 09:37  zltigo Цитата(demiurg_spb @ Apr 10 2010, 11:52) ... Apr 10 2010, 12:17               Палыч Цитата(vallav @ Apr 15 2010, 12:49) Вы со... Apr 15 2010, 10:00               ASN vallav
А вот с тем, что посчитать 16 битную сумму ... Apr 15 2010, 10:07                Палыч Цитата(ASN @ Apr 15 2010, 13:22) А вот с ... Apr 15 2010, 10:31                 ASN Палыч
Пример на аппаратной логике расчёта обсуждае... Apr 15 2010, 11:33                vallav Цитата(ASN @ Apr 15 2010, 14:22) vallav
А... Apr 15 2010, 11:26                Палыч Цитата(VslavX @ Apr 15 2010, 16:49) для п... Apr 15 2010, 14:06                 VslavX Цитата(Палыч @ Apr 15 2010, 17:21) Имхо, ... Apr 15 2010, 14:56                        VslavX Цитата(vallav @ Apr 16 2010, 13:40) Или В... Apr 16 2010, 11:16                        Палыч Цитата(vallav @ Apr 16 2010, 13:40) Я раз... Apr 16 2010, 11:49                         vallav Цитата(Палыч @ Apr 16 2010, 16:04) Ну, ды... Apr 16 2010, 15:56                              mdmitry Цитата(vallav @ Apr 17 2010, 18:45) Но ес... Apr 17 2010, 15:05                               demiurg_spb Цитата(zltigo @ Apr 17 2010, 19:26) Я все... Apr 17 2010, 20:13                                            VslavX Цитата(vallav @ Apr 19 2010, 15:52) http:... Apr 19 2010, 17:48                                             vallav Цитата(VslavX @ Apr 19 2010, 22:03) Призн... Apr 20 2010, 04:56                                              vallav Посчитал.
Надеюсь, если и ошибся, то не сильно.
По... Apr 25 2010, 09:33                                               ASN vallav
Прямая сумма хуже CRC16 в Вашем случае боле... Apr 25 2010, 11:31                                                vallav Цитата(ASN @ Apr 25 2010, 15:46) vallav
П... Apr 25 2010, 13:20                                        defunct Цитата(vallav @ Apr 19 2010, 10:18) CRC д... Apr 19 2010, 14:28                                         vallav Цитата(defunct @ Apr 19 2010, 18:43) Чтоб... Apr 19 2010, 15:04                                          defunct Цитата(vallav @ Apr 19 2010, 18:19) Дык н... Apr 19 2010, 16:07                                VslavX Цитата(vallav @ Apr 18 2010, 16:32) Что п... Apr 18 2010, 20:13        defunct Цитата(demiurg_spb @ Apr 14 2010, 22:20) ... Apr 17 2010, 20:47         demiurg_spb Цитата(defunct @ Apr 18 2010, 01:02) полу... Apr 18 2010, 10:12 mdmitry О CRC
Считая CRC верным можно пытаться восстанови... Apr 14 2010, 11:34 vallav Цитата(mdmitry @ Apr 14 2010, 15:49) О CR... Apr 14 2010, 12:05
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|