реклама на сайте
подробности

 
 
2 страниц V   1 2 >  
Reply to this topicStart new topic
> Восстановить полином CRC16 по функции табличного рассчета
Dima_G
сообщение Aug 17 2011, 02:27
Сообщение #1


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Добрый день!
Нужно восстановить полином (для реализации его в FPGA) по следующему алгоритму расчета CRC16
Код
unsigned crc16_table[256] = {

    0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,

    0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,0xe97e,0xf8f7,

    0x1891,0x0918,0x3b83,0x2a0a,0x5eb5,0x4f3c,0x7da7,0x6c2e,

    0x94d9,0x8550,0xb7cb,0xa642,0xd2fd,0xc374,0xf1ef,0xe066,

    0x3122,0x20ab,0x1230,0x03b9,0x7706,0x668f,0x5414,0x459d,

    0xbd6a,0xace3,0x9e78,0x8ff1,0xfb4e,0xeac7,0xd85c,0xc9d5,

    0x29b3,0x383a,0x0aa1,0x1b28,0x6f97,0x7e1e,0x4c85,0x5d0c,

    0xa5fb,0xb472,0x86e9,0x9760,0xe3df,0xf256,0xc0cd,0xd144,

    0x6244,0x73cd,0x4156,0x50df,0x2460,0x35e9,0x0772,0x16fb,

    0xee0c,0xff85,0xcd1e,0xdc97,0xa828,0xb9a1,0x8b3a,0x9ab3,

    0x7ad5,0x6b5c,0x59c7,0x484e,0x3cf1,0x2d78,0x1fe3,0x0e6a,

    0xf69d,0xe714,0xd58f,0xc406,0xb0b9,0xa130,0x93ab,0x8222,

    0x5366,0x42ef,0x7074,0x61fd,0x1542,0x04cb,0x3650,0x27d9,

    0xdf2e,0xcea7,0xfc3c,0xedb5,0x990a,0x8883,0xba18,0xab91,

    0x4bf7,0x5a7e,0x68e5,0x796c,0x0dd3,0x1c5a,0x2ec1,0x3f48,

    0xc7bf,0xd636,0xe4ad,0xf524,0x819b,0x9012,0xa289,0xb300,

    0xc488,0xd501,0xe79a,0xf613,0x82ac,0x9325,0xa1be,0xb037,

    0x48c0,0x5949,0x6bd2,0x7a5b,0x0ee4,0x1f6d,0x2df6,0x3c7f,

    0xdc19,0xcd90,0xff0b,0xee82,0x9a3d,0x8bb4,0xb92f,0xa8a6,

    0x5051,0x41d8,0x7343,0x62ca,0x1675,0x07fc,0x3567,0x24ee,

    0xf5aa,0xe423,0xd6b8,0xc731,0xb38e,0xa207,0x909c,0x8115,

    0x79e2,0x686b,0x5af0,0x4b79,0x3fc6,0x2e4f,0x1cd4,0x0d5d,

    0xed3b,0xfcb2,0xce29,0xdfa0,0xab1f,0xba96,0x880d,0x9984,

    0x6173,0x70fa,0x4261,0x53e8,0x2757,0x36de,0x0445,0x15cc,

    0xa6cc,0xb745,0x85de,0x9457,0xe0e8,0xf161,0xc3fa,0xd273,

    0x2a84,0x3b0d,0x0996,0x181f,0x6ca0,0x7d29,0x4fb2,0x5e3b,

    0xbe5d,0xafd4,0x9d4f,0x8cc6,0xf879,0xe9f0,0xdb6b,0xcae2,

    0x3215,0x239c,0x1107,0x008e,0x7431,0x65b8,0x5723,0x46aa,

    0x97ee,0x8667,0xb4fc,0xa575,0xd1ca,0xc043,0xf2d8,0xe351,

    0x1ba6,0x0a2f,0x38b4,0x293d,0x5d82,0x4c0b,0x7e90,0x6f19,

    0x8f7f,0x9ef6,0xac6d,0xbde4,0xc95b,0xd8d2,0xea49,0xfbc0,

    0x0337,0x12be,0x2025,0x31ac,0x4513,0x549a,0x6601,0x7788

};


/* compute 16 bit CCITT crc using the table */

unsigned crc16(unsigned crc,unsigned b)

{

    unsigned ret = crc16_table[(b ^ crc) & 0xff] ^ (crc >> 8);

    return ret;

}


Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает sad.gif
Пробовал сравнивать с иными полиномами - тоже безуспешно.
Железяка защищает этой CRC данные по HDLC

Может кто-нибудь сталкивался и сможет помочь?
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Aug 17 2011, 04:53
Сообщение #2


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 640
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



Цитата(Dima_G @ Aug 17 2011, 06:27) *
Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает sad.gif

А задом наперед?


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 04:59
Сообщение #3


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(MrYuran @ Aug 17 2011, 11:53) *
А задом наперед?

Вы про данные? Крутил и так и сяк (q[7:0], q[0:7])
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Aug 17 2011, 05:21
Сообщение #4


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 640
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



Цитата(Dima_G @ Aug 17 2011, 08:59) *
Вы про данные?

Не, про полином... (полиномы)

Сдается мне, первое значение в таблице (не нулевое) и есть искомый полином.


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 05:43
Сообщение #5


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(MrYuran @ Aug 17 2011, 12:21) *
Не, про полином... (полиномы)

Сдается мне, первое значение в таблице (не нулевое) и есть искомый полином.


Хм, пробовал крутить 1189 на калькуляторе
http://zorc.breitbandkatze.de/crc.html

В качестве тестового примера взял байт '0'==0x30
Расчет с помощью функции из первого поста дает значение
29B3

с помощью калькулятора
Код
(polynom reverse=0,data reverce=0) 1B2B
(polynom reverse=0,data reverce=1) CAC6
(polynom reverse=1,data reverce=0) 9956
(polynom reverse=1,data reverce=1) B7DD


Go to the top of the page
 
+Quote Post
klop
сообщение Aug 17 2011, 06:14
Сообщение #6


Местный
***

Группа: Свой
Сообщений: 433
Регистрация: 28-02-06
Пользователь №: 14 788



Когда то игрался с подобным. Вроде для реверсивного полинома надо в конце накопленные 16 бит инвертировать и байты в них местами поменять.
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 06:21
Сообщение #7


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(klop @ Aug 17 2011, 13:14) *
Когда то игрался с подобным. Вроде для реверсивного полинома надо в конце накопленные 16 бит инвертировать и байты в них местами поменять.

Попробовал сделать инверсию, не помогло (или не так делаю )
Go to the top of the page
 
+Quote Post
des00
сообщение Aug 17 2011, 06:52
Сообщение #8


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Dima_G @ Aug 17 2011, 00:21) *
Попробовал сделать инверсию, не помогло (или не так делаю )

может инициализация не правильная ? например надо с 0xFFFF начинать.


--------------------
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 07:02
Сообщение #9


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(des00 @ Aug 17 2011, 13:52) *
может инициализация не правильная ? например надо с 0xFFFF начинать.

Я в тестовом примере пробовал инициализацию с нуля (так именно та плата считает)
те

Код
  
unsigned short crc = 0;
crc = crc16(crc, 0x30);
printf("CRC=0x%X\n"m crc);


Соответственно и в калькуляторах начальное значение 0 делал. В принципе, пока из положения вышел (ПЗУ в FPGA + расчет аналогичный как в плате), но ИМХО это не сильно красиво да и свои минусы есть (либо создавать по инстансу ПЗУ для каждого контроллера (а их десятки будут, те затраты Nx256*2), либо продумывать разделение доступа к одному
Go to the top of the page
 
+Quote Post
klop
сообщение Aug 17 2011, 08:34
Сообщение #10


Местный
***

Группа: Свой
Сообщений: 433
Регистрация: 28-02-06
Пользователь №: 14 788



было приблизительно так

Код
// 0x1021
function [15:0] fn_crc_ccitt;
input[15:0] crc_current;
input[7:0] data;
begin
fn_crc_ccitt[0]  = data[4] ^ data[0] ^ crc_current[8] ^ crc_current[12];
fn_crc_ccitt[1]  = data[5] ^ data[1] ^ crc_current[9] ^ crc_current[13];
fn_crc_ccitt[2]  = data[6] ^ data[2] ^ crc_current[10] ^ crc_current[14];
fn_crc_ccitt[3]  = data[7] ^ data[3] ^ crc_current[11] ^ crc_current[15];
fn_crc_ccitt[4]  = data[4] ^ crc_current[12];
fn_crc_ccitt[5]  = data[5] ^ data[4] ^ data[0] ^ crc_current[8] ^ crc_current[12] ^ crc_current[13];
fn_crc_ccitt[6]  = data[6] ^ data[5] ^ data[1] ^ crc_current[9] ^ crc_current[13] ^ crc_current[14];
fn_crc_ccitt[7]  = data[7] ^ data[6] ^ data[2] ^ crc_current[10] ^ crc_current[14] ^ crc_current[15];
fn_crc_ccitt[8]  = data[7] ^ data[3] ^ crc_current[0] ^ crc_current[11] ^ crc_current[15];
fn_crc_ccitt[9]  = data[4] ^ crc_current[1] ^ crc_current[12];
fn_crc_ccitt[10] = data[5] ^ crc_current[2] ^ crc_current[13];
fn_crc_ccitt[11] = data[6] ^ crc_current[3] ^ crc_current[14];
fn_crc_ccitt[12] = data[7] ^ data[4] ^ data[0] ^ crc_current[4] ^ crc_current[8] ^ crc_current[12] ^ crc_current[15];
fn_crc_ccitt[13] = data[5] ^ data[1] ^ crc_current[5] ^ crc_current[9] ^ crc_current[13];
fn_crc_ccitt[14] = data[6] ^ data[2] ^ crc_current[6] ^ crc_current[10] ^ crc_current[14];
fn_crc_ccitt[15] = data[7] ^ data[3] ^ crc_current[7] ^ crc_current[11] ^ crc_current[15];
end     
endfunction     


// 0x8408
function [7:0] fn_reverse_data;
input[7:0] data;
integer    i;
begin
for(i=0;i<8;i=i+1)  fn_reverse_data[i]    = data[7-i];
end     
endfunction     

function [15:0] fn_reverse_inverse_crc;
input[15:0] crc;
integer    i;
begin
for(i=0;i<16;i=i+1)  fn_reverse_inverse_crc[i]    = ~crc[15-i];
end     
endfunction



always@(negedge ireset or posedge cp2)
begin:state_machines_seq
if(!ireset)// Reset
begin
crc_current <= {16{1'b1}}; <<<<<<<<<
Go to the top of the page
 
+Quote Post
thermit
сообщение Aug 17 2011, 09:19
Сообщение #11


Знающий
****

Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730



Цитата
Dima_G:
Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает sad.gif
Пробовал сравнивать с иными полиномами - тоже безуспешно.
Железяка защищает этой CRC данные по HDLC

Может кто-нибудь сталкивался и сможет помочь?


Полином правильный, табличка с алгоритмом - тоже. Инициализация регистра - 0xFFFF. В качестве CRC берется поразрядная инверсия последнего содержимого регистра. СRC посылается начиная с младшего байта. При проверке байты crc тоже обрабатываются в порядке поступления байт. Если пакет корректный - регистр должен всегда содержать константу 0xF0B8. CRC можно и не обрабатывать, но тогда придется поразрядно инвертировать последнее содержимое регистра, переставлять байты и сравнивать полученное значение с пришедшим CRC.

Сообщение отредактировал thermit - Aug 17 2011, 09:25
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 09:42
Сообщение #12


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(thermit @ Aug 17 2011, 16:19) *
Полином правильный, табличка с алгоритмом - тоже. Инициализация регистра - 0xFFFF. В качестве CRC берется поразрядная инверсия последнего содержимого регистра. СRC посылается начиная с младшего байта. При проверке байты crc тоже обрабатываются в порядке поступления байт. Если пакет корректный - регистр должен всегда содержать константу 0xF0B8. CRC можно и не обрабатывать, но тогда придется поразрядно инвертировать последнее содержимое регистра, переставлять байты и сравнивать полученное значение с пришедшим CRC.


Что-то у меня не получается.. Загоняю в функцию из первого поста 1 байт данных 0x30;
Начальное значение FFFF. crc=0x5EC4
Начальное значение 0000. crc=0x29b3

Если Вам не трудно, покажите на калькуляторе ту же CRC
http://zorc.breitbandkatze.de/crc.html
(где стоят галки, какие поля чем заполняли)

Go to the top of the page
 
+Quote Post
thermit
сообщение Aug 17 2011, 10:16
Сообщение #13


Знающий
****

Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730



Вот
Эскизы прикрепленных изображений
Прикрепленное изображение
 
Go to the top of the page
 
+Quote Post
Dima_G
сообщение Aug 17 2011, 12:22
Сообщение #14


Местный
***

Группа: Свой
Сообщений: 279
Регистрация: 2-07-08
Из: Новосибирск
Пользователь №: 38 699



Цитата(thermit @ Aug 17 2011, 17:16) *
Вот

что-то у меня не получилось для моих данных (0х30)
Прикрепленное изображение
Go to the top of the page
 
+Quote Post
thermit
сообщение Aug 17 2011, 13:02
Сообщение #15


Знающий
****

Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730



Все нормально получается. У Вас-то что выходит?
Go to the top of the page
 
+Quote Post

2 страниц V   1 2 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 19th July 2025 - 04:43
Рейтинг@Mail.ru


Страница сгенерированна за 0.01502 секунд с 7
ELECTRONIX ©2004-2016