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

[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, получилась такая же как на википедии. В чём разница???

[uldemir]

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

[svamoscow]

Полином 100110001 - X^8+X^5+X^4+X^0
Перевёрнутый 100011001
считаю второй элемент таблицы индекс 1

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

1 0000 0000
1 0001 1001
----------
        1 1001 = 25 (dec)

что то не совпадает, в таблице 94
Покажите наглядно как считать.

[uldemir]

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

[uldemir]

у меня получилось...

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

Поток     000000001
полином   100011001
         ----------
      0000100011000
       100011001
----------
       10011101
      100011001
----------
      110000100
    100011001
----------
    1011110 = 5e = 94

Как я и говорил, надо сдвигать в ДРУГУЮ сторону.

[svamoscow]

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

[uldemir]

Должно быть 15 - припиши нолик слева в последней строке где получилось 0x5e. 8 нулей из буфера начального состояния CRC и 7 нулей из числа 0x01. Просто я эти нули не писал и выбросил строчки где отнимается 0. Всего вычитаний должно быть 8.

но это метод подгонки по моему

Извини, математическое доказательство привести я не могу. Могу только показать как это считать и почему имеются две "правильных" таблицы.

[Meteor]

Глянь сюда http://atmel.com/dyn/resources/prod_doc ... oc1143.pdf вдруг поможет

[svamoscow]

Извини, математическое доказательство привести я не могу. Могу только показать как это считать и почему имеются две "правильных" таблицы.

Математическое док-во мне и не нужно. Благодарю за объяснения Всё понял, но один вопрос остался, почему вконце справа от остатка добавляется ноль?

Глянь сюда http://atmel.com/dyn/resources/prod_doc ... oc1143.pdf вдруг поможет

Спасибо за ссылку, пригодится.

[uldemir]

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

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

           00000000 10000000
-          10001100 1 
----------
           10001100 0 
-       100011001 
----------
        10011101 
-      100011001 
----------
       110000100 
-     000000000
----------
      011000010
-    100011001
----------
     101111000
-   000000000
----------
    01011110

Устал подгонять выравнивание, необессудьте, если у вас не выглядит красивым столбиком, почему-то при копировании все съехало.

[uldemir]

Эй! неужели нет здесь ни одного спеца, который бы сказал, что я за лажу тут понаписал? Или все берут готовый код из даташитов и особо не вникают?

[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-й строчках - не понимаю.

[Meteor]

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

[svamoscow]

Используется та же самая таблица, правда, содержимое каждой ее позиции зеркально обращено относительно центра позиции.
Используется то же самое исходное значение регистра, только так же отраженное.
Байты сообщения обрабатываются в том же порядке, что и раньше, то есть само сообщение не является зеркальным.
Сами байты сообщения не нужно зеркально отображать, так как все остальное уже было отражено!

Взято из:

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

Вобщем как таблица получается одна из другой я понял. Но "нетабличный" алгоритм подсчёта обратной CRC я не понял не хотелось бы память контроллера забивать таблицами.

[Meteor]

Но "нетабличный" алгоритм подсчёта обратной CRC я не понял не хотелось бы память контроллера забивать таблицами.

Вот еще попробуйте ехемплы посмотреть от иара http://supp.iar.com/Support/?note=91733&from=note+16492, наверняка не таблицами шьют...
ЗЫ. Хотя похоже что предыдущее - перевод текущего, но ехемплы есть:)

[uldemir]

Примеры кочуют из книги в книгу со страницы на страницу в неизменном виде.
Хотя этот CRCguide действительно внятно написан.

[Meteor]

Примеры кочуют из книги в книгу со страницы на страницу в неизменном виде.

Увы, что поделать. Мне не приходилось применять такого рода контроль. Предпочитаю или побайтное исключающее ИЛИ (вариант для МК), или коды Хемминга (больше применяю для шин, реализуя в ПЛИС).

[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

[ARV]

для 1-wire CRC я сделал небольшую утилитку-калькулятор. в отличие от других известных калькулятров моя утилитка может вести посчет CRC для произвольного количества байтов, а не только семи или восьми.

[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;
}