crc8 даласса

[FILIK]

тема конечно истёртая до дыр,но хоть убейте не как не пойму это crc8.читал множество информации почти весь интернет облазил да и на нашем сайте читал.на бумажке вроде расчет хороший а в реальности нето.калькулятор crc показывает одно а у меня другое.да и с этими полиномами всё темно.если есть желания и терпение прошу вдалбить мне всё с самого начала как говорят на молекулярном уровне

[blackx]

Ну напишите пример сюда, как вы "на бумажке считаете". Тогда напишем где ошибка.

[FILIK]

привожу свой расчет+калькулятор где я проверял

[blackx]

Калькулятором вашим пользоваться не умею, производил проверку на онлайн-калькуляторе.

Начнем с того, что у нас CRC8 - это значит, что расчеты будут производиться над восьмибитным
числом. При этом размер числа и старшая степень полинома должны совпадать.
У вас: 10110, полином P(x) = x4 + x2 + x1 - старшая степень тут 4 (т. е. подойдет для crc4)
Приведу пример рассчета для полинома, используемого в 1-wire:
100110001 или P(x) = x8 + x5 + x4 + 1

число 01100100 (MSB, дес. 100), дополним нулем справа до размера полинома (9 бит):
011001000

для CRC8 выполняем 8 проходов по алгоритму:
если число начинается с "1", выполняем операцию XOR (^) над числом с полиномом и производим сдвиг влево (<<) на 1 бит;
иначе, если начинается с "0", то просто производим сдвиг влево на 1 бит.

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

1) 011001000: 011001000 << 1 = 110010000
2) 110010000: 110010000 ^ 100110001 << 1 = 010100001 << 1 = 101000010
3) 101000010: 101000010 ^ 100110001 << 1 = 001110011 << 1 = 011100110
4) 011100110: 011100110 << 1 = 111001100
5) 111001100: 111001100 ^ 100110001 << 1 = 011111101 << 1 = 111111010
6) 111111010: 111111010 ^ 100110001 << 1 = 011001011 << 1 = 110010110
7) 110010110: 110010110 ^ 100110001 << 1 = 010100111 << 1 = 101001110
8) 101001110: 101001110 ^ 100110001 << 1 = 001111111 << 1 = 01111111

Итого, мы получили в конце восьмого шага нашу контрольную сумму 01111111.

Проверим на калькуляторе:
http://ghsi.de/CRC/index.php?Polynom=10 ... Message=64

[FILIK]

спасибо,что ответили.вроде становится немного понятнее тоесть: моя первая ошибка не верно выбраный полином я выбрал 4разрядный(10110двоичн=22десятич=16h),а надо 8 разрядный как вашем примере(100110001десятич=305десятич=131h).вторая ошибка я добавлял количество "0"в конец по количеству разрядов полинома и третья ошибка где-то находится в вычислениях если вам не трудно пожалуйста повторите ваши пример вычеслеия столбиком.
если я правильно мыслю запись "x8 + x5 + x4 + 1"означает позиция "1"в разрядах.

[blackx]

Запись вида 100110001 - это числовое представления полинома. Да, единицы в этом представлении означают наличие члена полинома с соответствующей степенью.
Добавление нулей в конец - не ошибка. Я добавлял по одному нулю на каждом шаге, вы - сразу нужное количество. Вот тут есть пример вычисления с нулями в конце: http://en.wikipedia.org/wiki/Computation_of_CRC#Example. Мне лично так не очень удобно считать.

[FILIK]

немного непонятно, если можно пожалуйста приведите пример расчета столбиком как в моем примере где я расчитывал.

[dron2012]

Привет всем подскажите пожалуйста не как не могу понять как получить контрольную сумму и по примеру пробовал считать и на калькуляторе не как у меня эта цифра не получается 234

62,1,7,19,122,0,132,30, 234

11111000

10000000

11100000

10011000

11110100

00000000

10000100

11110000


1111100010000000111000001001100011110100000000001000010011110000


http://ghsi.de/CRC/index.php?Polynom=10 ... Message=64

[GiGaHerz]

Самому была интересна эта тема, раньше пользовался чужим решением но где то потерял пришлось разбираться )
Вот к чему пришёл для AVR:

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

.def crc_tmp	=r5
.def tmp		=r16
.def tmp1		=r17

clr tmp
ldi tmp1,0x22
rcall  calc_crc8
ldi tmp1,0xF5
rcall  calc_crc8
; tmp - содержет crc

calc_crc8:
	eor tmp,tmp1  ; сложить с предыдущим значением CRC 
	ldi tmp1,9 ; степень полинома +1 (потому что цикл с предусловием)
	mov crc_tmp,tmp1 ;загрузить счётчик
	ldi tmp1,0x31 ;полином 100110001 старший бит не учитываем т.к. выполняем XOR только если старший бит сообщения = 1 и результатом всегда будет 0
lab_crc:
	dec crc_tmp ;как и обещал цикл с предусловием
	breq ret_crc
	SBRS tmp,7 ; проверка на 1 в 7 бите
	rjmp only_lsl ; нет
	lsl tmp ; сдвинем, писал выше о старшем бите полинома 
	eor tmp,tmp1 ; ну собственно отнимем или прибавим тут в CRC вычислениях это одно и тоже )
	rjmp lab_crc
only_lsl: 
	lsl tmp ;просто сдвинем влево 
	rjmp lab_crc
ret_crc:
[color=#0000FF]ret[/color]

Надеюсь будет кому ни будь полезно

[da-nie]

Вот общая теория по CRC.

CRC_Guide.pdf

(199.59 КБ) 1449 скачиваний

[Laplaskin]

задавал вопрос в другой теме, не отвечают. Скажите, каким образом считается crc8 в датчике ds18b20?
перевел кучу бумаги чтобы разобраться... оно может и проще кусок кода скопировать у кого-нибудь, но хочется все таки разобраться самому.
вот беру я последовательность 28A1B2C3D40000, прибавляю еще 8 нулей в конец и делю на полином восьмой же степени 100110001.
ответ F7, совпадает с калькулятором, на котором считал blackx
http://ghsi.de/CRC/index.php?Polynom=10 ... b2c3d40000
но в симуляторе не получается f7, там 8f получается и на другом калькуляторе f8..
http://radiokot.ru/forum/viewtopic.php?f=2&t=49547 тут с картинками прям спрашивал.. последовательность правда без нулей была результат все равно не совпал

[Laplaskin]

[FILIK]

с новыми силами приступаю дальше к изучению этого crc и снова тупик.вот полином(100110001=305д=131h) вот число(110010=50д=32h) вот что получилось на онлайн калькуляторе(01111110=126д=7еh). у меня при вычисление на бумаге получилось 010100110=167д=а7h) не пойму как так. (ссылка на калькулятор http://ghsi.de/CRC/index.php?Polynom=10 ... Message=50)

[GARMIN]

Всё правильно на бумажке посчитал, только в калькуляторе надо было вставить шестнадцатеричные цифры:
http://ghsi.de/CRC/index.php?Polynom=10 ... Message=32

[FILIK]

ладно с этим разобрался.тепер такой вопрос из того же калькулятора там полином имеет вид 100110001=305д=131h,есть число 11110=30д=1eh сколько нужно добавить нулей в конец числа и вообще как правильно это делать?

[FILIK]

Спасибо всем кто откликнулся .Разобрался как надо расчитывать на бумаге .Теперь следующий вопрос-мне нужно понять как востановить мою последовательность бит при передачи с ошибкой вроде корекциис кодами рида соломона

[zöner]

CRC не поможет, только определяет наличие ошибки.
для коррекции нужно что-то типа ECC http://ru.wikipedia.org/wiki/ECC

[FILIK]

это я понял что crc может только определить факт ошибки.я не понял как какая-то комбиначия 1или 0 может востановить сообщение .если можно по подпобнее про код хеминга.

[Kavka]

Ещё один, кого поисковики забанили
http://yandex.ru/yandsearch?text=код+хемминга

PS: http://www.bugtraq.ru/forum/faq/general ... tions.html

[FILIK]

Поисковиком пользаватся умею и ссылки сморел.Только не понимаю то что там написано в смысли как что вычисляется .Мне нужно как можно проще.