Алгоритм CRC16 Опции

[athlon64]

Устройство на 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. Голову сломал на этом затыке. Буду благодарен за любые мысли по проблеме

[vallav]

Зачем повторяться? Но если хотите, то последний раз - Вы, и продолжаете бездумствовать , даже после лобовых указаний. Ну так имеющий разум да поймет, ну хотя-бы со временем.
Я все сказал.

Притчу про повторение слова халва слышать приходилось? Можете продолжать, но мне надоело.

Не то. В данном случае речь идет просто о банальной вероятности обнаружения ошибки.

Хорошо, вот Вам конкретика.
По зашумленному каналу передаются данные.
Передача идет пакетами по 256 байт.
Примерно каждый десятый пакет сбойный - одиночная ошибка.
Многократные ошибки соответственно реже.
Обнаруженные сбойные пакеты пересылаются повторно.
Естественно включен побайтовый контроль четности.
Вопрос - какой метод лучше для обнаружения сбойных пакетов, пропущенных
побайтовым контролем четности?
Прямая 16 битная сумма пропустит сбойный пакет, у которого в одном байте две ошибки и в другом, отстоящем от первого
на четное число байт две ошибки в тех же разрядах. В среднем одну из 4х таких ошибок.
То есть, четверную ошибку достаточно специального вида.
Что пропустит CRC?
Хуже в такой достаточно типичной ситуации CRC или лучше.

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

Как Вам такая конкретика?
Жду Вашего обоснованого выбора.

В этом случае требуется помехоустойчивое кодирование. Битовый поток кодируют и перемежают, а потом передают по каналу связи.

Помехоустойчивое кодирование требуется в случае, если или 90% пакетов сбойные или повторная посылка сбойного
пакета затруднена.
Если сбойных пакетов ~10% и нет проблем повторить посылку пакета - зачем нам паровоз?
А вот между велосипедом и самокатом повыбирать стоит...

[Палыч]

Если сбойных пакетов ~10% ...

Это - результат Вашего неправильного проектирования...

[vallav]

Это - результат Вашего неправильного проектирования...

Полагаете, работать не будет?
А как должно быть правильно?
И каков ответ - что лучше?

[Палыч]

Полагаете, работать не будет?
А как должно быть правильно?

Работать - будет. Но - плохо... Если каждый десятый пакет - сбойный, это - просто отвратительно... Скорее всего, при проектировании канала передачи информации приняты неправильные технические решения.

[VslavX]

Что пропустит CRC?

Ничего не пропустит - все обнаружит. Описанная ошибка это некоторое K разрядностью менее длины проверочного слова умноженное на X^n + 1, где n - число бит между ошибками. А X^n + 1 гарантировано без останка не делится для выбранного полинома для достаточно большого n (которое не может превышать общую длину блока, для которого кодовое расстояние 2+). А раз не делится - значит CRC при такой ошибке гарантировано изменится и такую ошибку обнаружит - то есть любое инвертирование бит (менее длины проверочного кода) подряд дважды в любом месте блока будет обнаружено.

[vallav]

Работать - будет. Но - плохо... Если каждый десятый пакет - сбойный, это - просто отвратительно... Скорее всего, при проектировании канала передачи информации приняты неправильные технические решения.

Полагаете, удлинение времени передачи на 10% - категорически неприемлимо?
Но если так уж случилось - что выбрать - прямую сумму или CRC?
Вариант - вообще не пользоваться этим каналом - не интересен.

Ничего не пропустит - все обнаружит. Описанная ошибка это некоторое K разрядностью менее длины проверочного слова умноженное на X^n + 1, где n - число бит между ошибками. А X^n + 1 гарантировано без останка не делится для выбранного полинома для достаточно большого n (которое не может превышать общую длину блока, для которого кодовое расстояние 2+). А раз не делится - значит CRC при такой ошибке гарантировано изменится и такую ошибку обнаружит - то есть любое инвертирование бит (менее длины проверочного кода) подряд дважды в любом месте блока будет обнаружено.

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

Кстати, чтобы CRC обнаруживало все двойные ошибки, нужно чтобы в конце была выполнена холостая прокрутка.
Иначе двойная ошибка - бит в последнем слове и бит в слове CRC может быть пропущена.

[VslavX]

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

Вы не поняли что я написал. Будет обнаружена двойная ошибка для ЛЮБОЙ последовательности в 'к' бит, если 'к' меньше длины проверочного кода. Длина байта - 8 бит, длина CRC-16 - 16 бит. Причем между сбойными последовательностями может быть произвольное количество битов, не обязательно выравнено на байт. То есть, если одинаково сбоят, например биты 1 и 5 в любых даух байтах - это обнаруживается. Даже если одинаково сбоят биты 0..14 в любых 15 битах - то есть правильная последовательность в двух местах по-XOR-ена с одной и той же 15-битовой комбинацией - то такое тоже 100% обнаруживается.
Если же ошибки в байтах разные, то может уже и пропустить.

[vallav]

Вы хоть в курсе - что это такое - CRC и как именно это делается?
Похоже, что нет.
У Вас - просто наоборот, чем получается при простом XOR без сдвига.
Но это не CRC, это что то другое...

Причина редактирования: Бездумное цитирование

[VslavX]

Вы хоть в курсе - что это такое - 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 бит включительно.

[vallav]

Ну что Вам сказать.
Вы настолько в этм всем уверены, что ...

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

Причина редактирования: Бездумное цитирование

[VslavX]

Ну что Вам сказать.
Вы настолько в этм всем уверены, что ...

Ясно, значит будем сомневаться в арифметике. Более просто и строго я объяснить не в силах.

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

Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых.

Но это не дается даром.

Чем надо платить?
На самом деле, CRC в "железе" реализуется намного проще чем упомянутая Вами обычная арифметическая сумма. Программная реализация CRC тоже не особо сложна - если понять принцип. Я Вам даже открою "секрет" - в криптографии, там где очень длинные числа, полиномиальное деление и сложение как правило работают быстрее обычных - так как нет этого дурацкого распространяемого между словами переноса. Медленее работает умножение - и то исключительно потому что у большинства процессоров нет инструкции полиномиального умножения.

CRC довольно плох при отлавливания многобитовых ошибок.

Любую однократную в "k бит подряд" CRC отлавливает. Ну а умеючи-то - все что хошь сломать можно

В часности, в данном случае нужно ловить четырехкратную ошибку.

Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.

[vallav]

Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.

Значит Ваша версия - в приведенном примере лучше использовать CRC.
Так как Вы уверены, что она отлавливает все четверные ошибки.
Так?

И даже отлавливает все ошибки большей кратности, вплоть до 16.
И зыждется эта уверенность на том, что "полиномиальная арифметика в частности, и теория линейных кодов в общем".
Если не секрет, CRC с каким полиномом обладает таким замечательным свойством?
Для пакета длиной в 256 байт и контрольном слове длиной 16 бит.
Можно попробовать проверить это замечательное свойство прямым вычислением
( если полином приведете ).

Кстати, на поясните Ваше - "Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых".
Чем именно двухкратная многобитовая ошибка отличается от однократной многобитовой?

[VslavX]

Так как Вы уверены, что она отлавливает все четверные ошибки.

Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях.

И даже отлавливает все ошибки большей кратности, вплоть до 16.

Да, если эти 16 бит расположены подряд.

Если не секрет, CRC с каким полиномом обладает таким замечательным свойством?
Для пакета длиной в 256 байт и контрольном слове длиной 16 бит.
Можно попробовать проверить это замечательное свойство прямым вычислением
( если полином приведете ).

Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылка
OK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.

[vallav]

Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях.

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

Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылка
OK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.

Вы про
http://rsdn.ru/article/files/classes/SelfCheck/crcguide.pdf

И что именно Вы там обнаружили?
Или Вы туда даже не заглядывали...

[defunct]

CRC довольно плох при отлавливания многобитовых ошибок.

- несомненно ваша арифметическая сумма гораздо лучше.

Вероятность того, что CRC32 пропустит серьезную ошибку - например весь пакет искажен нафиг - равна 1 / 2^32.
Вероятность же, что такую ошибку пропустит ваша сумма равна - 1/2. --> если пакет будет занулен - пропустит, если "заединичен" - непропустит.
Вот собсно и вся надежность децкой суммы - 50/50.

А CRC может пропустить не эти, а другие, удовлетворяющие исходному условию.

Чтобы Вам не быть голословным, можете привести конкретный пример, - когда CRC16 пропускает искажение любых 4-х битов сообщения?
А мы потом пообсуждаем.