| |
|
  |
 Нахождение полинома CRC, Нахождение полинома CRC |
|
|
|
|
 Oct 13 2006, 05:47
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Доброе утро.
По поводу единичек в каждом разряде. До устройства пока не добрался, но проверил на стандартном полиноме 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
|
|
|
|
|
|
|
|
Oct 13 2006, 06:39
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Цитата(Сергей Борщ @ Oct 12 2006, 18:37)  Цитата(uk8adi @ Oct 12 2006, 16:14)
Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.
Лично я применяю начальное значение CRC отличное от нуля. Попробуйте просчитать свою нулевую посылку по стандартным полиномам с начальным значением отличным от нуля. Еще у Скляра в "Цифровой связи" на стр. 933 описан метод взлома системы шифрования на регистре с обратными связями - оно не поможет? Как я понял, вычислить начальное значение (init по описанию CRC) для нулевой посылки и после применять ее для дальнейшего расчета других данных. Это было сделано, и расчитанные CRC отличались от принятых, причем довольно сильно и без видимой мною системы.
|
|
|
|
|
|
|
|
Oct 13 2006, 06:51
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Цитата(Epikur @ Oct 13 2006, 02:45) Попробуйте полином D027 в комбинации со стартовым значением. Какое пока сказать не знаю.
Предлагаю попробовать прогнать комбинацию FFFF00000000 Подсчитано с полиномом D027 и стартовым значением FFFF00000000 (стандартное для CRC16 CCITT): .............................принятые...расчитанные ........................................CRC 303333333330..........6B3D..........EB11 303333333331..........BB16..........FB36 303333333332..........1B43..........CB5F 303333333333..........CB68..........DB78 303333333334..........8BC1..........AB8D 303333333335..........5BEA..........BBAA
|
|
|
|
|
|
|
|
Oct 13 2006, 09:06
|
Местный
Группа: Свой
Сообщений: 216
Регистрация: 31-03-05
Из: Зеленоград
Пользователь №: 3 839
|
uk8adi, Неверно 1. я говорил, что от всех частных CRCi надо было отнять CRC0, конечно по модулю тут я что-то уже запутался, т.к. было это дело давно, но что надо от чего-то отнять CRC0, помню точно наверное, от конечного результата 2. Пусть  - сложение по модулю  - вычитание по модулю CRC для данных 0003hex будет равно CRC1 CRC2 CRC0 или 0D2E 3D4D 1D0F = 2D6C 3. чтобы найти правильный полином, надо для каждого полинома CRC-16 (и все-таки найти их все) получить XOR -разницу с нашими частными CRCi если это будет величина постоянная, то полином мы угадали останется только найти предустановку регистра
|
|
|
|
|
|
|
|
Oct 13 2006, 09:42
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Цитата(Fast @ Oct 13 2006, 14:06) 2. Пусть - сложение по модулю - вычитание по модулю CRC для данных 0003hex будет равно CRC1 CRC2 CRC0 или 0D2E 3D4D 1D0F = 2D6C Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу. Сообщу о результатах.
|
|
|
|
|
|
|
|
Oct 13 2006, 12:25
|
Гуру
Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095
|
Цитата(uk8adi @ Oct 13 2006, 12:42) Цитата(Fast @ Oct 13 2006, 14:06) 2. Пусть - сложение по модулю - вычитание по модулю CRC для данных 0003hex будет равно CRC1 CRC2 CRC0 или 0D2E 3D4D 1D0F = 2D6C Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу. Сообщу о результатах. Если не получится попробуйте еще полином 0x8408 (CRC-XMODEM) вкупе со сдвигом в другую сторону
--------------------
На любой вопрос даю любой ответ"Write code that is guaranteed to work, not code that doesn’t seem to break" ( C++ FAQ)
|
|
|
|
|
|
|
|
Oct 16 2006, 12:27
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Что и куда двигаем. Не понятно. Пожалуйста, поподробнее.
Сообщение отредактировал uk8adi - Oct 16 2006, 12:31
|
|
|
|
|
|
|
|
Oct 16 2006, 14:36
|
Гуру
Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095
|
Цитата(uk8adi @ Oct 16 2006, 15:27) Что и куда двигаем. Не понятно. Пожалуйста, поподробнее. Меняется порядок обработки битов. Можно я на примере? Код //==============================================================//
// Calculate one byte of CCITT CRC-16 //
//==============================================================//
void CRC_CRC16 (uint8_t Data, uint16_t &CRC) {
CRC ^= (uint16_t)(Data) << 8;
uint8_t i = 8;
do {
if (CRC & 0x8000) { CRC <<= 1; CRC ^= 0x1021; }
else CRC <<= 1;
}while(--i);
}
//==============================================================//
// Calculate one byte of XModem CRC //
//==============================================================//
void CRC_XMODEM (uint8_t Data, uint16_t &CRC) {
CRC ^= Data;
uint8_t i = 8;
do {
if (CRC & 0x01) { CRC >>= 1; CRC ^= 0x8408; }
else CRC >>= 1;
} while(--i);
}
--------------------
На любой вопрос даю любой ответ"Write code that is guaranteed to work, not code that doesn’t seem to break" ( C++ FAQ)
|
|
|
|
|
|
|
|
Oct 17 2006, 11:08
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Господа!
Сделал эту таблицу, с одной единичкой в каждом бите.
Работает все прекрасно!
ВСЕМ СПАСИБО!
Но как всетаки вытащить образующий полином, я не понял.
|
|
|
|
|
|
|
|
Oct 17 2006, 15:14
|
Местный
Группа: Свой
Сообщений: 216
Регистрация: 31-03-05
Из: Зеленоград
Пользователь №: 3 839
|
Цитата(uk8adi @ Oct 17 2006, 15:08) Но как всетаки вытащить образующий полином, я не понял. ну.. это волшебство.. возможно это устройство так же табличным методом формирует циклическую проверку. конечно, какой-то полином изначально используется для построения таблицы, но в таблице могут быть переставлены строки (т.е. переставлены частные CRCi для каждой единички), поэтому опубликуйте полученную таблицу, может кто-нибудь Вам скажет полином его найти вполне возможно: нужно сгенерировать для всех известных полиномов CRC-16 такие же таблички с единицами и попытаться найти закономерность
|
|
|
|
|
|
|
|
Oct 17 2006, 18:09
|
Местный
Группа: Свой
Сообщений: 314
Регистрация: 13-07-06
Из: Москва
Пользователь №: 18 797
|
Цитата(Fast @ Oct 17 2006, 19:14) Цитата(uk8adi @ Oct 17 2006, 15:08) Но как всетаки вытащить образующий полином, я не понял. ну.. это волшебство.. Колеги, поправте меня, если я не прав. О полиноме можно говорить только тогда, когда испльзуется именнто циклический блочный код, а в данном случае имеет место какой-то другой блочный код, задаваемый порождающей матрицей.
Сообщение отредактировал DuHast - Oct 17 2006, 18:10
|
|
|
|
|
|
|
|
Oct 18 2006, 08:25
|
Местный
Группа: Свой
Сообщений: 216
Регистрация: 31-03-05
Из: Зеленоград
Пользователь №: 3 839
|
Цитата(DuHast @ Oct 17 2006, 22:09) Колеги, поправте меня, если я не прав. О полиноме можно говорить только тогда, когда испльзуется именнто циклический блочный код, а в данном случае имеет место какой-то другой блочный код, задаваемый порождающей матрицей. Вы правы, но очень часто для построения порождающей матрицы систематических кодов используется циклический полином. Дабы не изобретать долго и нудно велосипед. Потом производится хитрая перестановка и сложение строк матрицы (линейная комбинация строк). Обычно это делается для придания коду нужных спектральных характеристик, когда какие-то кодовые слова (КС) передаются чаще других.
|
|
|
|
|
|
|
|
Oct 18 2006, 18:44
|
Местный
Группа: Свой
Сообщений: 314
Регистрация: 13-07-06
Из: Москва
Пользователь №: 18 797
|
Цитата(Fast @ Oct 18 2006, 12:25) часто для построения порождающей матрицы систематических кодов используется циклический полином. Дабы не изобретать долго и нудно велосипед. Это понятно, существует алгоритм при помощи которого из полинома циклического кода получают соответствующую пораждающую матрицу того же кода. Причём в нижней строке этой матрицы будет пораждаю многочлен. А вот Цитата хитрая перестановка и сложение строк матрицы (линейная комбинация строк). приведёт только к получению матрицы(не пораждающей) в строках которой будут кодовые слова того же кода, но никак не пораждающая матрица другого кода. Похоже Вы ошибаетесь, или я Вас не так понял.
Сообщение отредактировал DuHast - Oct 18 2006, 18:44
|
|
|
|
|
|
|
|
Oct 19 2006, 06:32
|
Группа: Новичок
Сообщений: 14
Регистрация: 10-04-06
Пользователь №: 15 982
|
Добрый день.
Снятая и частично вычисленная таблица:
000000000000...........0003
000000000001...........D028
000000000002...........707D
000000000004...........E0FF
000000000008...........11D0
000000000010...........23A6
000000000020...........474A
000000000040...........8E92
000000000080...........CD09
000000000100...........4A3C
000000000200...........947E
000000000400...........F8D1
000000000800...........218C
000000001000...........431E
000000002000...........863A
000000004000...........DC59
000000008000...........689C
000000010000...........D13E
000000020000...........7251
000000040000...........E4A7
000000080000...........1960
000000100000...........32C6
000000200000...........658A
000000400000...........CB12
000000800000...........4609
000001000000...........8С17
000002000000...........С800
000004000000...........402D
000008000000...........805F
000010000000...........D090
000020000000...........710D
000040000000...........E21F
000080000000...........1410
000100000000...........2826
000200000000...........504A
000400000000...........A092
000800000000...........9109
001000000000...........F23C
002000000000...........3455
004000000000...........68AF
008000000000...........D15B
010000000000...........7298
020000000000...........E536
040000000000...........1A41
080000000000...........3487
100000000000...........690B
200000000000...........D213
400000000000...........7408
800000000000...........E816
Заметил еще одну вещь. Сегмент данных проверяется на четность (количество едениц), если четно, то еще прибавляется 0003.
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
