Форум РадиоКот

Здесь можно немножко помяукать :)
https://radiokot.ru/forum/

Как вычислять контрольную сумму - CRC8 CRC16 ?

https://radiokot.ru/forum/viewtopic.php?t=2375

Страница 2 из 3

Добавлено: Чт окт 01, 2009 19:35:22
svamoscow
Начал изучать 1-wire и столкнулся с проблемой подсчёта CRC8, не могу понять алгоритм. В частности почему на wikipedia.ru http://ru.wikipedia.org/wiki/CRC таблица CRC8 одна, а на radiokot.ru http://radiokot.ru/articles/13/ таблица совсем другая, хотя вроде бы используется один и тот же полином. Руками попробовал посчитать таблицу с полиномом X^8+X^5+X^4+X^0, получилась такая же как на википедии. В чём разница???

Добавлено: Чт окт 01, 2009 20:09:40
uldemir
Различие, IMHO, в том с какого конца считать биты. CRC это остаток деления потока на полином. А вот в каком порядке этот поток идет - старшим битом вперед или младшим - это уже вопрос конкретного соглашения.
Таблицы одинаковые, только для разных направлений.
Таблица в радиокоте совпадает с далласовской AN27. А даллас пихает данные начиная с младшего бита первого байта.

Добавлено: Чт окт 01, 2009 21:28:43
svamoscow
Полином 100110001 - X^8+X^5+X^4+X^0
Перевёрнутый 100011001
считаю второй элемент таблицы индекс 1

Код: Выделить всё

1 0000 0000
1 0001 1001
--------------
        1 1001 = 25 (dec)
что то не совпадает, в таблице 94
Покажите наглядно как считать.

Добавлено: Чт окт 01, 2009 23:29:09
uldemir
А... теория... я - пас. Может кто-нибудь поумнее может разжевать этот вопрос.
Может эта ссылка прольёт свет на этот вопрос?http://en.wikipedia.org/wiki/Computation_of_CRC

Добавлено: Пт окт 02, 2009 00:04:44
uldemir
у меня получилось...

Код: Выделить всё

Поток     000000001
полином   100011001
         ----------
      0000100011000
       100011001
-----------------
       10011101
      100011001
----------------
      110000100
    100011001
--------------
    1011110 = 5e = 94
Как я и говорил, надо сдвигать в ДРУГУЮ сторону.

Добавлено: Пт окт 02, 2009 09:52:34
svamoscow
По аналлогии с прямым алгоритмом слева нужно добавлять количество нулей такое сколько бит CRC, CRC 8ми битная, почему же у вас добавляется 14 нулей вместо 8? Каков алгоритм? И вконце почему то спустился ноль справа, опять же какая логика? Сколько нулей спускать? Конечно получилось 94, но это метод подгонки по моему.

Добавлено: Пт окт 02, 2009 10:03:46
uldemir
Должно быть 15 - припиши нолик слева в последней строке где получилось 0x5e. 8 нулей из буфера начального состояния CRC и 7 нулей из числа 0x01. Просто я эти нули не писал и выбросил строчки где отнимается 0. Всего вычитаний должно быть 8.
но это метод подгонки по моему
Извини, математическое доказательство привести я не могу. Могу только показать как это считать и почему имеются две "правильных" таблицы.

Добавлено: Пт окт 02, 2009 10:22:35
Meteor
Глянь сюда http://atmel.com/dyn/resources/prod_doc ... oc1143.pdf вдруг поможет

Добавлено: Пт окт 02, 2009 10:51:28
svamoscow
uldemir писал(а): Извини, математическое доказательство привести я не могу. Могу только показать как это считать и почему имеются две "правильных" таблицы.
Математическое док-во мне и не нужно. Благодарю за объяснения :) Всё понял, но один вопрос остался, почему вконце справа от остатка добавляется ноль?
Meteor писал(а): Глянь сюда http://atmel.com/dyn/resources/prod_doc ... oc1143.pdf вдруг поможет
Спасибо за ссылку, пригодится.

Добавлено: Пт окт 02, 2009 11:51:44
uldemir
Ну, может так нагляднее. В конце, я вставил два вычитания, чтобы было видно откуда взялся ноль справа (да и слева). Так же, два вычитания 0 нужно было бы вставить после первого вычитания. И еще, в первой строчке разделил Начальное значение CRC и первый байт. Те нули, что я ставлю перед остатком слева - берутся справа от 1 в первой строчке. Т.е. "10000000" надо рассматривать как 0x01, а не 0x80. Младшим битом вперед.

Код: Выделить всё

           00000000 10000000
-          10001100 1 
-------------------------
           10001100 0 
-       100011001 
-------------------------
        10011101 
-      100011001 
-------------------------
       110000100 
-     000000000
-------------------------
      011000010
-    100011001
-------------------------
     101111000
-   000000000
-------------------------
    01011110
Устал подгонять выравнивание, необессудьте, если у вас не выглядит красивым столбиком, почему-то при копировании все съехало.

Добавлено: Пт окт 02, 2009 18:27:36
uldemir
Эй! неужели нет здесь ни одного спеца, который бы сказал, что я за лажу тут понаписал? Или все берут готовый код из даташитов и особо не вникают?

Добавлено: Сб окт 03, 2009 12:42:27
uldemir

Код: Выделить всё

0        000000000             10001000
-        100110001
-------------------------
1         001100010 = 8c        0001000
-         000000000
-------------------------
2          011000100 = 46        001000
-          000000000
-------------------------
3           110001000 = 23        01000
-           100110001
-------------------------
4            101110010 = 9d        1000
-            000000000
-------------------------
5            1011100100 = 4e        000
-             000000000
-------------------------
6              111001000 = 27        00
-              100110001
-------------------------
7               111110010 = 9f        0
-               100110001
-------------------------
=                110000110 = c3
Развернул зеркально. младшие биты в обоих случаях слева. Похоже так, что самое главное - это что вычитать: полином или 0. И это зависит от совпадения младшего бита остатка с битом из потока. Если равны, что ничего не вычитаем. Как правильно интерпретировать левую "1" в 1-й и 5-й строчках - не понимаю.

Добавлено: Сб окт 03, 2009 13:58:41
Meteor
Вот надыбал кое что ( http://rsdn.ru/article/files/classes/Se ... cguide.pdf ), времени пока разбираться нет...:(((((

Добавлено: Сб окт 03, 2009 18:33:10
svamoscow
Используется та же самая таблица, правда, содержимое каждой ее позиции зеркально обращено относительно центра позиции.
Используется то же самое исходное значение регистра, только так же отраженное.
Байты сообщения обрабатываются в том же порядке, что и раньше, то есть само сообщение не является зеркальным.
Сами байты сообщения не нужно зеркально отображать, так как все остальное уже было отражено!
Взято из:
Meteor писал(а):Вот надыбал кое что ( http://rsdn.ru/article/files/classes/Se ... cguide.pdf ), времени пока разбираться нет...:(((((
Вобщем как таблица получается одна из другой я понял. Но "нетабличный" алгоритм подсчёта обратной CRC я не понял :( не хотелось бы память контроллера забивать таблицами.

Добавлено: Сб окт 03, 2009 19:16:44
Meteor
svamoscow писал(а): Но "нетабличный" алгоритм подсчёта обратной CRC я не понял :( не хотелось бы память контроллера забивать таблицами.
Вот еще попробуйте ехемплы посмотреть от иара http://supp.iar.com/Support/?note=91733&from=note+16492, наверняка не таблицами шьют...
ЗЫ. Хотя похоже что предыдущее - перевод текущего, но ехемплы есть:)

Добавлено: Сб окт 03, 2009 20:03:13
uldemir
Примеры кочуют из книги в книгу со страницы на страницу в неизменном виде.
Хотя этот CRCguide действительно внятно написан.

Добавлено: Вс окт 04, 2009 14:16:25
Meteor
uldemir писал(а):Примеры кочуют из книги в книгу со страницы на страницу в неизменном виде.
Увы, что поделать.:dont_know: Мне не приходилось применять такого рода контроль. Предпочитаю или побайтное исключающее ИЛИ (вариант для МК), или коды Хемминга (больше применяю для шин, реализуя в ПЛИС). :tea:

Помогите разобраться с кашей в голове

Добавлено: Вт окт 06, 2009 08:20:58
nppElM
Помогите пожалуйста расчитать CRC16 табличным методом, ибо у меня используя различные вылженные коды для расчета, для каждого кода свой результат.

И так:
AtMega2561, AVRStudio
Поток: 0х00С8 (сдесь первый вопрос: Использовать 0хС8 или все таки 0х00С8 )
Полином: 8005
Нач. значение: 0xFFFF
Последнее с XOR: 0xFFFF
Отражения: нет

Используя реальное вычисение CRC получаю:
0xC8 : 1100 1000
8005 : 1000 0000 0000 0101
W: 15

Код: Выделить всё

11001000000000000000000
1000000000000101| || |
============ | || |
01001000000001010|| |
  1000000000000101|| |
  ============ || |
  0001000000001111000
       1000000000000101
       ============ 
                       1111101000 -> 0x03E8
Используя табличный алгоритм вычесления предложенный romeuz результат 0xD630 (но в его алгоритме я так понял используется отраженный метод)

Используя калькулятор http://zorc.breitbandkatze.de/crc.html вводя исходные данные
CRC order: 16
CRC polynom: 8005
Initial value: 0xFFFF
Final XOR value:0xFFFF
Data sequence: 00c8
Result: F6D9 (hex), 4 data bytes

Исользуя калькулятр(вложенный файл)
Резултат: 89BE

И наконец попробывал написать свою программу (код во влжении)
Результат 0xBED6

Помогите пожалуйсто разобраться как правильно расчитать CRC 16

Re: Как вычислять контрольную сумму - CRC8 CRC16 ?

Добавлено: Сб ноя 27, 2010 23:01:05
ARV
для 1-wire CRC я сделал небольшую утилитку-калькулятор. в отличие от других известных калькулятров моя утилитка может вести посчет CRC для произвольного количества байтов, а не только семи или восьми.

Re: Как вычислять контрольную сумму - CRC8 CRC16 ?

Добавлено: Пн ноя 29, 2010 14:08:22
a_skr
использую такой код с ds18b20:

Код: Выделить всё

  
uint8_t iInfo[9]; // здесь лежат данные с датчика
uint8_t iCheckCRC(void)
{
  uint8_t a, b, i, j, crc=0;
  for(i=0; i<9; i++)
  {
    a = iInfo[i];
    for(j=0; j<8; j++)
    {
      b = a;
      a ^= crc;
      if(a & 1) crc = ((crc^0x18)>>1) | 0x80;
      else crc >>= 1;
      a = b >> 1;
    }
  }
  if(crc == 0) return 1;
  else return 0;
}
Часовой пояс: UTC+03:00
Страница 2 из 3

Создано на основе phpBB® Forum Software © phpBB Limited

Русская поддержка phpBB