|
Алгоритм 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, 11:33
|
Местный
  
Группа: Свой
Сообщений: 459
Регистрация: 15-07-04
Из: g.Penza
Пользователь №: 326

|
ПалычПример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока: Код function nextCRC16 (Data: std_logic; crc: std_logic_vector(15 downto 0)) return std_logic_vector is
variable d: std_logic_vector(0 downto 0); variable c: std_logic_vector(15 downto 0); variable newcrc: std_logic_vector(15 downto 0);
begin d(0) := Data; c := crc; newcrc(0) := d(0) xor c(15); newcrc(1) := c(0); newcrc(2) := c(1); newcrc(3) := c(2); newcrc(4) := c(3); newcrc(5) := d(0) xor c(4) xor c(15); newcrc(6) := c(5); newcrc(7) := c(6); newcrc(8) := c(7); newcrc(9) := c(8); newcrc(10) := c(9); newcrc(11) := c(10); newcrc(12) := d(0) xor c(11) xor c(15); newcrc(13) := c(12); newcrc(14) := c(13); newcrc(15) := c(14); return newcrc; end nextCRC16; Требуется 16 триггеров. Не больше чем для простой суммы. Расчёт для 8-ми битной ЭВМ табличным способом: Код void set_fcs(uint16 fcs_init, uint8 *buff, uint16 len) { while(len--) fcs_init = (fcs_init >> 8) ^ fcs_table[(fcs_init ^ *buff++)]; fcs_init ^= 0xFFFF; *buff++ = (uint8)fcs_init; *buff = (uint8)(fcs_init>>8);} Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее. Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC. Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.
|
|
|
|
Сообщений в этой теме
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                vallav Цитата(ASN @ Apr 15 2010, 14:22) vallav
А... Apr 15 2010, 11:26               VslavX Цитата(vallav @ Apr 15 2010, 12:49) С чег... Apr 15 2010, 13:34                Палыч Цитата(VslavX @ Apr 15 2010, 16:49) для п... Apr 15 2010, 14:06                 VslavX Цитата(Палыч @ Apr 15 2010, 17:21) Имхо, ... Apr 15 2010, 14:56                vallav Цитата(VslavX @ Apr 15 2010, 17:49) Есть ... Apr 15 2010, 17:17                 ASN vallav
Пример на VHDL приведён как подтверждение т... Apr 15 2010, 17:39                  vallav Цитата(ASN @ Apr 15 2010, 21:54) vallav
П... Apr 16 2010, 05:20                   VslavX Цитата(vallav @ Apr 16 2010, 08:35) То ес... Apr 16 2010, 06:02                    vallav Цитата(VslavX @ Apr 16 2010, 10:17) ИМО, ... Apr 16 2010, 07:35                     VslavX Цитата(vallav @ Apr 16 2010, 10:50) А что... Apr 16 2010, 08:17                      Палыч Цитата(VslavX @ Apr 16 2010, 11:32) И тут... Apr 16 2010, 09:02                       vallav Цитата(Палыч @ Apr 16 2010, 13:17) Присое... Apr 16 2010, 10:25                        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                        zltigo Цитата(vallav @ Apr 16 2010, 13:40) И еще... Apr 16 2010, 16:03                         vallav Цитата(zltigo @ Apr 16 2010, 20:18) Вероя... Apr 16 2010, 17:19                          zltigo Цитата(vallav @ Apr 16 2010, 20:34) Разве... Apr 16 2010, 18:49                           vallav Цитата(zltigo @ Apr 16 2010, 23:04) Да Вы... Apr 17 2010, 13:44                            zltigo Цитата(vallav @ Apr 17 2010, 16:59) И зао... Apr 17 2010, 14:16                             vallav Цитата(zltigo @ Apr 17 2010, 18:31) Други... Apr 17 2010, 14:30                              mdmitry Цитата(vallav @ Apr 17 2010, 18:45) Но ес... Apr 17 2010, 15:05                              zltigo Цитата(vallav @ Apr 17 2010, 17:45) Вы за... Apr 17 2010, 15:11                               demiurg_spb Цитата(zltigo @ Apr 17 2010, 19:26) Я все... Apr 17 2010, 20:13                               vallav Цитата(zltigo @ Apr 17 2010, 19:26) Зачем... Apr 18 2010, 13:17                                Палыч Цитата(vallav @ Apr 18 2010, 16:32) Если ... Apr 18 2010, 14:22                                 vallav Цитата(Палыч @ Apr 18 2010, 18:37) Это - ... Apr 18 2010, 14:32                                  Палыч Цитата(vallav @ Apr 18 2010, 17:47) Полаг... Apr 18 2010, 15:03                                   vallav Цитата(Палыч @ Apr 18 2010, 19:18) Работа... Apr 19 2010, 04:22                                    VslavX Цитата(vallav @ Apr 19 2010, 07:37) Да, д... Apr 19 2010, 05:26                                     vallav Вы хоть в курсе - что это такое - CRC и как именно... Apr 19 2010, 05:52                                      VslavX Цитата(vallav @ Apr 19 2010, 09:07) Вы хо... Apr 19 2010, 06:21                                       vallav Ну что Вам сказать.
Вы настолько в этм всем уверен... Apr 19 2010, 07:03                                        VslavX Цитата(vallav @ Apr 19 2010, 10:18) Ну чт... Apr 19 2010, 07:26                                         vallav Цитата(VslavX @ Apr 19 2010, 11:41) Мне т... Apr 19 2010, 10:35                                          VslavX Цитата(vallav @ Apr 19 2010, 13:50) Так к... Apr 19 2010, 11:27                                           vallav Цитата(VslavX @ Apr 19 2010, 15:42) Про _... Apr 19 2010, 12:37                                            Палыч Цитата(vallav @ Apr 19 2010, 15:52) ...Эт... Apr 19 2010, 14:59                                            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
|
|
|