Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Восстановить полином CRC16 по функции табличного рассчета
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
Dima_G
Добрый день!
Нужно восстановить полином (для реализации его в 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

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

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

Вы про данные? Крутил и так и сяк (q[7:0], q[0:7])
MrYuran
Цитата(Dima_G @ Aug 17 2011, 08:59) *
Вы про данные?

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

Сдается мне, первое значение в таблице (не нулевое) и есть искомый полином.
Dima_G
Цитата(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


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

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

может инициализация не правильная ? например надо с 0xFFFF начинать.
Dima_G
Цитата(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), либо продумывать разделение доступа к одному
klop
было приблизительно так

Код
// 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}}; <<<<<<<<<
thermit
Цитата
Dima_G:
Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает sad.gif
Пробовал сравнивать с иными полиномами - тоже безуспешно.
Железяка защищает этой CRC данные по HDLC

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


Полином правильный, табличка с алгоритмом - тоже. Инициализация регистра - 0xFFFF. В качестве CRC берется поразрядная инверсия последнего содержимого регистра. СRC посылается начиная с младшего байта. При проверке байты crc тоже обрабатываются в порядке поступления байт. Если пакет корректный - регистр должен всегда содержать константу 0xF0B8. CRC можно и не обрабатывать, но тогда придется поразрядно инвертировать последнее содержимое регистра, переставлять байты и сравнивать полученное значение с пришедшим CRC.
Dima_G
Цитата(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
(где стоят галки, какие поля чем заполняли)

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

что-то у меня не получилось для моих данных (0х30)Нажмите для просмотра прикрепленного файла
thermit
Все нормально получается. У Вас-то что выходит?
Dima_G
Цитата(thermit @ Aug 17 2011, 20:02) *
Все нормально получается. У Вас-то что выходит?


Используя функцию из первого поста: 0x5EC4
Используя калькулятор с вашими настройками 0x3E04
5EC4 != 3E04

Или я что-то не так понимаю?
thermit
Табличка какая-то левая.
У меня такая:
Код
        0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
    0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
    0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
    0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
    0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
    0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
    0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
    0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
    0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
    0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
    0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
    0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
    0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
    0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
    0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
    0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
    0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
    0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
    0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
    0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
    0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
    0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
    0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
    0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
    0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
    0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
    0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
    0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
    0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
    0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
    0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
    0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
Dima_G
Цитата(thermit @ Aug 17 2011, 21:12) *
Табличка какая-то левая.
У меня такая:

Ага, ясно. Я такую тоже встречал - начинает отличаться с третьей строчки...
А поиском по строчке из моей таблицы выдает всего пару исходников (причем, похоже что родственных).
Похоже, не судьба полином подобрать будет sm.gif
Спасибо всем, кто старался помочь!
MrYuran
Табличку можно самому сформировать для любого полинома.
Чтобы не было недоразумений.
Ixt
Цитата(Dima_G @ Aug 17 2011, 06:27) *
Нужно восстановить полином (для реализации его в FPGA) по следующему алгоритму расчета CRC16


Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.
Dima_G
Цитата(Ixt @ Aug 18 2011, 14:20) *
Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.



http://electronix.ru/forum/index.php?showt...st&p=962810

Цитата
В принципе, пока из положения вышел (ПЗУ в FPGA + расчет аналогичный как в плате), но ИМХО это не сильно красиво да и свои минусы есть (либо создавать по инстансу ПЗУ для каждого контроллера (а их десятки будут, те затраты Nx256*2), либо продумывать разделение доступа к одному


MrYuran
Цитата(Ixt @ Aug 18 2011, 11:20) *
Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.

Ага, а потом сравните затраты на полкило таблицы и один 16р сдвиговый регистр с обратными связями.
К тому же, как оказалось, таблица неправильная.
Dima_G
Цитата(MrYuran @ Aug 19 2011, 12:09) *
К тому же, как оказалось, таблица неправильная.

В том то и беда, что неправильная. Девайс генерит CRC именно по этой, неправильной таблице. А вносить изменения в девайс пока нет ни времени, ни возможности.
MrYuran
Цитата(Dima_G @ Aug 19 2011, 10:45) *
В том то и беда, что неправильная. Девайс генерит CRC именно по этой, неправильной таблице. А вносить изменения в девайс пока нет ни времени, ни возможности.

Значит, это уже не ЦРЦ, а чертечто. Можно ещё граблей наловить.

Например, свернув сообщение и сумму и не получив ожидаемого нуля.
Dima_G
Цитата(MrYuran @ Aug 19 2011, 13:49) *
Например, свернув сообщение и сумму и не получив ожидаемого нуля.

Если такое будет вылезать, то возможен другой подход: считать CRC принятого пакета до старой CRC и затем сравнивать их.
i-mir
Проблема в том что ваши таблицы не простые, а разбиты по блокам из 16 значений,
для которых есть свое число инициализации. Например таблица из поста 17:

- Для первых 16 значений [0x0000, 0x1189, 0x2312 ... ] CRC poly : $1189 CRC init: $0000
- Для вторых 16 значений [0x1081, 0x0108, 0x3393 ... ] CRC poly : $1189 CRC init: $5DEF
- Для третьих 16 значений [0x2102, 0x308b, 0x0210 ... ] CRC poly : $1189 CRC init: $BBDE

Честно говоря сам полином и числа инициализации выбраны не стандартные.

Можно проверить и на калькуляторе, для числа $10, CRC poly : $1189 CRC init: $5DEF
результат будет 0x1081 (по таблице).
Нажмите для просмотра прикрепленного файла
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.