Нахождение полинома CRC, Нахождение полинома CRC Опции

[uk8adi]

Господа! Нижайшая просьба.
Есть последовательность данных (передаются сегментами по 6 (шесть) байт) и есть значения CRC для этих байт (сегментов). Необходимо узнать применяемый полином.

323333333331 hex 233331 ANSII 5E23 - CRC
323333333332 233332 FE76
323333333333 233333 2E5D
323333333334 233334 6EF4
323333333335 233335 BEDF
323333333336 233336 1E8A
323333333337 233337 CEA1

Данные сняты с рабочего устройства.

Буду признателен за любую помощь.

[Epikur]

Да, отправь посылку со всеми нулями.

[uk8adi]

Да, отправь посылку со всеми нулями.

CRC посылки 000000000000hex снято 0003 hex

[Fast]

перед прямым вскрытием порождающего полинома
неплохо проверить на соответствие 2 основный полинома CRC-16
g(x)=x16 + x12 + x5 + 1,
g(x)=x16 + x5 + x2 + 1.

возможно, полином не циклический, а допустим порождающая матрица задана таблично
тогда уже выстраиваем каноническую матрицу для нахождения базиса (методом Гаусса, что предложен выше)

[uk8adi]

неплохо проверить на соответствие 2 основный полинома CRC-16
g(x)=x16 + x12 + x5 + 1,
g(x)=x16 + x5 + x2 + 1.

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

Сообщение отредактировал uk8adi - Oct 12 2006, 12:51

[Fast]

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

А как Вы проверяли, простым делением на порождающий? Инвертировали ли первые 2 байта перед делением согласно рекомендации V.42 (ну мало ли..) и результат деления?

кстати, D02B полинома не существует в природе
список неприводимых многочленов степени 16 имеется, только я его найти не могу, видел в какой-то книжке
знаю, что их можно получить в Матлабе

[uk8adi]

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

А как Вы проверяли, простым делением на порождающий? Инвертировали ли первые 2 байта перед делением согласно рекомендации V.42 (ну мало ли..) и результат деления?

кстати, D02B полинома не существует в природе
список неприводимых многочленов степени 16 имеется, только я его найти не могу, видел в какой-то книжке
знаю, что их можно получить в Матлабе

Все далалось по данной рекомендации (CCITT V.24).
Причем считалось, как вручную на бумаге, так и программой "Hex Workshop v4.23". У нее есть функция подсчета CRC, как со стандартными полиномами, так и с пользовательскими, задаваемыми вручную.

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

[Fast]

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

Ну могу предложить следующее - вырубить все топором

принять 48 последовательностей и CRCi к ним (i = 1...48)
100000000000hex
200000000000hex
400000000000hex
800000000000hex
010000000000hex
... ... ... ... ...
000000000001hex
т.е. с единичкой в каждом разряде
отнять от каждого CRCi CRC0 (crc для нулевого КС)

CRC любой кодовой последовательности(кодового слова = КС) будет равно сумме частных СRСi,
соответствующих каждому ненулевому биту КС

[uk8adi]

Доброе утро.
По поводу единичек в каждом разряде. До устройства пока не добрался, но проверил на стандартном полиноме CRC16CCITT 1021hex. Вот данные:

двоичные данные.......HEX.......CRC..............Разность:
(2 байта)................................p1021.......XOR.....алгебраическая

0000000000000000......0000......1D0F
0000000000000001......0001......0D2E......1021......0FE1
0000000000000010......0002......3D4D......2042......DFC2
0000000000000100......0004......5D8B......3063......BF84
0000000000001000......0008......9C07......8108......8108
0000000000010000......0010......0F3E......1231......0DD1
0000000000100000......0020......396D......2462......E3A2
0000000001000000......0040......55CB......48C4......C744
0000000010000000......0080......8C87......9188......9088
0000000100000000......0100......2E3E......3331......EED1
0000001000000000......0200......7B6D......6662......A1A2
0000010000000000......0400......D1CB......CCC4......4B44
0000100000000000......0800......94A6......89A9......8869
0001000000000000......1000......1E7C......0373......FE93
0010000000000000......2000......1BE9......06E6......0126
0100000000000000......4000......10C3......0DCC......0C4C
1000000000000000......8000......0697......1B98......1678

Как я правильно понял, CRC для данных 0003hex будет сумма разностей для нулевого и первого бита.

Правильное CRC, расчитанное программой для данных 0003hex будет 2D6Chex.
По варианту, предложенному Вами, CRC будет 3063hex, при сложении XOR, и EFA3hex при алгебраическом.

Извеняюсь за первое сообщение, не проследил за табуляцией.

Сообщение отредактировал uk8adi - Oct 13 2006, 06:14

[Fast]

uk8adi, Неверно

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

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

3. чтобы найти правильный полином, надо для каждого полинома CRC-16 (и все-таки найти их все)
получить XOR -разницу с нашими частными CRCi
если это будет величина постоянная, то полином мы угадали
останется только найти предустановку регистра

[uk8adi]

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу.
Сообщу о результатах.

[Сергей Борщ]

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу.
Сообщу о результатах.

Если не получится попробуйте еще полином 0x8408 (CRC-XMODEM) вкупе со сдвигом в другую сторону