| |
|
  |
 Полином для вычисления обратной CRC, Из CRC получить исходный код |
|
|
|
|
 Mar 16 2015, 19:04
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 16 2015, 21:46)  Очевидно, Это не доказательство. Вот для арифметического деления, доказательство четкое (математически), что однозначности нет. По причине того, что число G, выступающее в роли делителя, больше, чем 2^(N-1), где N - разрядность числа. И, поэтому, остатки от деления DATA mod G, большие, либо равные, чем 2^(N-1), зацикливаются внутри байта из-за отбрасывания старшего бита. Было бы логично распространить это и на полиномы. Потому, что там аналогия полная - полином на 1 разряд больше, чем CRC, поэтому результат от деления полиномов должен бы также зацикливаться внутри этого числа разрядностью на 1 меньше, чем полином, приводя к дублям. "Очевидно" - нет такого термина. Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010" , что соответствует полиному x^4+x - остаток от деления на x^4+x^1+1 будет равен x^4+x, что соответствует числу 2, если оставить 4 бита. Проверяем - 0*(x^4+x^1+1) + (x^4+x) = x^4+x - проверка показала, в делении не ошиблись, остаток именно такой. И, одновременно, для данного "0000 0010", что соответствует полиному x^1, остаток от деления на x^4+x^1+1 равен x^1, что также соответствует четырехбитному числу 2. Проверяем - 0*(x^4+x^1+1) + x^1 = x^1. Проверка опять показала, что поделено правильно, и остаток именно такой. Цитата(AHTOXA @ Mar 16 2015, 21:58) Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Вопрос - как при помощи некой функции закодировать данные так, чтобы они раскодировались методом подсчета CRC. Я не уверен в том, что существует такая функция в принципе (то есть, математически, является функцией, сопоставляя каждому аргументу из ее области определения единственное значение результата). То, что можно подобрать такой поток данных, чтобы на выходе получить требуемую последовательность - да с этим никто не спорит ни разу!
|
|
|
|
|
|
|
|
Mar 16 2015, 19:08
|
Универсальный солдатик
Группа: Модераторы
Сообщений: 8 634
Регистрация: 1-11-05
Из: Минск
Пользователь №: 10 362
|
Цитата(AHTOXA @ Mar 16 2015, 21:58) Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC. Раскодировать нужно не в одно число, а весь массив. Слово за словом, используя аппаратный блок CRC. Задача, что подсунуть этому блоку, чтобы после каждого вычисления CRC получался исходный код. В интернете это называется reversing CRC. http://stackoverflow.com/questions/1514040/reversing-crc32Вижу, математики запутали своим полиномиальным делением. Куда логичнее по-инженерному пользоваться регистрами сдвига и исключающим ИЛИ. Не вижу препятствий написать реверсивный алгоритм CRC, двигая данные в регистре в обратную сторону.  XOR, естественно, тоже ... тоже что-то с ними сделать. Цитата(SM @ Mar 16 2015, 22:04) Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010"... Это уже пара данных, требующая в данной задаче двух выходных CRC.
|
|
|
|
|
|
|
|
Mar 16 2015, 19:23
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 16 2015, 22:08) Это уже пара данных, требующая в данной задаче двух выходных CRC. Так и речь именно о паре (или больше). Что при одном четырехбитном данном при инициализации нулями будет однозначность, это, вроде, вопрос бесспорный. С арифметическим аналогом тоже самое - при начальном значении, меньшим, чем делитель-256, тоже все однозначно для одного байта. Неоднозначности начинаются, когда байт больше, или начальное значение больше определенного. Просто, я неудачную пару данных привел, наоборот, когда для двух разных начальных значений будет одинаковый код на выходе для одинаковых данных. Подобрать наоборот? Чтобы для одного начального значения и двух разных данных получился одинаковый полином?
|
|
|
|
|
|
|
|
Mar 16 2015, 20:25
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 16 2015, 22:33) Полином CRC известен, он не от балды берется. x^4 + x^1 + 1. Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число (от предыдущего расчета) - это к вопросу о начальном значении. Не подберете.  0x35. 0011 0101 - это x^5+x^4+x^2+1. Делим на x^4+x+1. Получаем частное (x+1), остаток 0 (обрезав до 4 бит, тоже ноль). Проверяем (x+1)*(x^4+x+1) = x^5+x^2+x+x^4+x+1 = x^5+x^4+x^2+1 - сходится. 0x36. 0011 0110 - это x^5+x^4+x^2+x. Делим на x^4+x+1. Получаем частное (x), остаток x^4 (обрезав до 4 бит, тоже ноль). Проверяем x*(x^4+x+1)+x^4 = x^5+x^2+x+x^4 = x^5+x^4+x^2+x - сходится. Для чисел 0x30...0x3F полные остатки от деления, не обрезая до 4 бит, затем, в скобках, частное, и, в конце, остаток, обрезая до 4-х бит: 30 mod 13 = 05 (div=03) => 5 31 mod 13 = 04 (div=03) => 4 32 mod 13 = 07 (div=03) => 7 33 mod 13 = 06 (div=03) => 6 34 mod 13 = 12 (div=02) => 2 35 mod 13 = 00 (div=03) => 0 36 mod 13 = 10 (div=02) => 0 37 mod 13 = 11 (div=02) => 1 38 mod 13 = 0D (div=03) => D 39 mod 13 = 0C (div=03) => C 3A mod 13 = 0F (div=03) => F 3B mod 13 = 0E (div=03) => E 3C mod 13 = 09 (div=03) => 9 3D mod 13 = 08 (div=03) => 8 3E mod 13 = 0B (div=03) => B 3F mod 13 = 0A (div=03) => A нет такого числа, чтобы получить с тройкой в старшем полубайте число три на выходе. Зато ноль можно получить двумя способами. Проверить многочлены перемножением можно все - я ради проверки это сам проделал для всех приведенных чисел ручкой на бумаге. Проверки для двух нулей привел выше. UPD: до числа 0x35 - обратимость присутствует везде. И, далее, тоже не все "приписки" необратимы. А вот, если "переделить" - то есть, продолжать деление, если в остатке присутствует x^4, но остаток уже меньше, чем полином-делитель (то есть, деление по факту уже закончено, так как остаток УЖЕ меньше, чем делитель, и он ну никак не может больше делиться на него, но, все равно, тупо и нагло выполнить итерацию), то обратимость появится, и при этом тоже проверка будет сходиться: 30 mod 13 = 05 (div=03) 31 mod 13 = 04 (div=03) 32 mod 13 = 07 (div=03) 33 mod 13 = 06 (div=03) 34 mod 13 = 01 (div=03) 35 mod 13 = 00 (div=03) 36 mod 13 = 03 (div=03) 37 mod 13 = 02 (div=03) 38 mod 13 = 0D (div=03) 39 mod 13 = 0C (div=03) 3A mod 13 = 0F (div=03) 3B mod 13 = 0E (div=03) 3C mod 13 = 09 (div=03) 3D mod 13 = 08 (div=03) 3E mod 13 = 0B (div=03) 3F mod 13 = 0A (div=03)
|
|
|
|
|
|
|
|
Mar 16 2015, 20:58
|
Универсальный солдатик
Группа: Модераторы
Сообщений: 8 634
Регистрация: 1-11-05
Из: Минск
Пользователь №: 10 362
|
Могу только повторить - 0x30...0x3F не укладываются в диапазон, который дает однозначное соответствие остатка от деления исходному числу. В данном случае CRC 4-битовая, значит, и числа должны быть 4-битовые. Ага, значит, приписали к 0..F впереди 3... сейчас... неправильно поделили, остаток от деления 0x36 на 0x13 будет 1 (5 вышло, промахнулся). 0x37 mod 0x13 = 6. Для 0x30 mod 0x13 я получил частное 0x35 и остаток 0xF. 0x30 / 0x13 = 0x35, 0xF 0x31 / 0x13 = 0x34, 0xC 0x32 / 0x13 = 0x37, 0x9 0x33 / 0x13 = 0x36, 0xA 0x34 / 0x13 = 0x31, 0x3 0x35 / 0x13 = 0x30, 0x0 0x36 / 0x13 = 0x33, 0x5 0x37 / 0x13 = 0x32, 0x6 0x38 / 0x13 = 0x3C, 0x4 0x39 / 0x13 = 0x3D, 0x7 0x3A / 0x13 = 0x3E, 0x2 0x3B / 0x13 = 0x3F, 0x1 0x3C / 0x13 = 0x38, 0x8 0x3D / 0x13 = 0x39, 0xB 0x3E / 0x13 = 0x3A, 0xE 0x3F / 0x13 = 0x3B, 0xD Методика деления описана в статье http://www.info-system.ru/library/algo/crc1.pdfupd. Исправляю остатки - выбрасываю старший 0. Тогда CRC от последовательности исходного числа и остатка даст 0. Это связано с разрядностью используемых чисел, в данном случае 4. Для проверки в CRC калькуляторе нужно задавать 30F0.
|
|
|
|
|
|
|
|
Mar 16 2015, 21:43
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 16 2015, 23:58) Могу только повторить - 0x30...0x3F И я могу только повторить. Что 0x30 - это пара 4-битных чисел. Сначала 3, потом 0. И даже Вашу же просьбу процитировать: Цитата(ViKo @ Mar 16 2015, 22:33) Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число Вот я и приписал 0x3 к паре чисел, 0x5 и 0x6. Получилось 0х35 и 0х36. Цитата(ViKo @ Mar 16 2015, 23:58) 0x37 mod 0x13 = 6. Извините, ошибочка у Вас. А частное сколько? Пробуем проверить для x и для (x+1). 6 - это 0110 - это x^2+x (x+1)*(x^4+x+1) + (x^2+x) = x^5+x^2+x+x^4+x+1+x^2+x = x^5+x^4+x+1 - это 0x33, а никак не 0x37. (что и подтверждается у меня, собственно, 0x33 mod 13 = 6) x*(x^4+x+1)+(x^2+x) = x^5+x^2+x+x^2+x = x^5 - это, вообще, 0x20, далеко от темы (и опять, у меня подтверждается, ниже запостил весь список). Считайте лучше! Тоже касается и 36 mod 13 = 1 - Вы хоть сами бы проверили умножением, прежде чем сюда то писать. Цитата(ViKo @ Mar 16 2015, 23:58) Для 0x30 mod 0x13 я получил частное 0x35 и остаток 0xF. А проверить???? 0x35 - x^5+x^4+x^2+1, 0x0F - x^3+x^2+x^1+1 (x^5+x^4+x^2+1)*(x^4+x+1) + (x^3+x^2+x^1+1) - это уже имеет член x^9, которого близко не было! Для этого третий полубайт нужен! Цитата(ViKo @ Mar 16 2015, 23:58) 0x31 / 0x13 = 0x34, 0x0C Заканчивайте писать лажу, ПРОВЕРЯЙТЕ УМНОЖЕНИЕМ!!!! Должно сходиться div*(x^4+x+1)+mod = исходное число! У Вас и близко не сходится. Вот результат ( ПРОВЕРЕННЫЙ УМНОЖЕНИЕМ!!!!) для всех пар 4-битных чисел : CODE
00 mod 13 = 00 (div=00)
01 mod 13 = 01 (div=00)
02 mod 13 = 02 (div=00)
03 mod 13 = 03 (div=00)
04 mod 13 = 04 (div=00)
05 mod 13 = 05 (div=00)
06 mod 13 = 06 (div=00)
07 mod 13 = 07 (div=00)
08 mod 13 = 08 (div=00)
09 mod 13 = 09 (div=00)
0A mod 13 = 0A (div=00)
0B mod 13 = 0B (div=00)
0C mod 13 = 0C (div=00)
0D mod 13 = 0D (div=00)
0E mod 13 = 0E (div=00)
0F mod 13 = 0F (div=00)
10 mod 13 = 10 (div=00)
11 mod 13 = 11 (div=00)
12 mod 13 = 12 (div=00)
13 mod 13 = 00 (div=01)
14 mod 13 = 07 (div=01)
15 mod 13 = 06 (div=01)
16 mod 13 = 05 (div=01)
17 mod 13 = 04 (div=01)
18 mod 13 = 0B (div=01)
19 mod 13 = 0A (div=01)
1A mod 13 = 09 (div=01)
1B mod 13 = 08 (div=01)
1C mod 13 = 0F (div=01)
1D mod 13 = 0E (div=01)
1E mod 13 = 0D (div=01)
1F mod 13 = 0C (div=01)
20 mod 13 = 06 (div=02)
21 mod 13 = 07 (div=02)
22 mod 13 = 04 (div=02)
23 mod 13 = 05 (div=02)
24 mod 13 = 02 (div=02)
25 mod 13 = 03 (div=02)
26 mod 13 = 00 (div=02)
27 mod 13 = 01 (div=02)
28 mod 13 = 0E (div=02)
29 mod 13 = 0F (div=02)
2A mod 13 = 0C (div=02)
2B mod 13 = 0D (div=02)
2C mod 13 = 0A (div=02)
2D mod 13 = 0B (div=02)
2E mod 13 = 08 (div=02)
2F mod 13 = 09 (div=02)
30 mod 13 = 05 (div=03)
31 mod 13 = 04 (div=03)
32 mod 13 = 07 (div=03)
33 mod 13 = 06 (div=03)
34 mod 13 = 12 (div=02)
35 mod 13 = 00 (div=03)
36 mod 13 = 10 (div=02)
37 mod 13 = 11 (div=02)
38 mod 13 = 0D (div=03)
39 mod 13 = 0C (div=03)
3A mod 13 = 0F (div=03)
3B mod 13 = 0E (div=03)
3C mod 13 = 09 (div=03)
3D mod 13 = 08 (div=03)
3E mod 13 = 0B (div=03)
3F mod 13 = 0A (div=03)
40 mod 13 = 0C (div=04)
41 mod 13 = 0D (div=04)
42 mod 13 = 0E (div=04)
43 mod 13 = 0F (div=04)
44 mod 13 = 08 (div=04)
45 mod 13 = 09 (div=04)
46 mod 13 = 0A (div=04)
47 mod 13 = 0B (div=04)
48 mod 13 = 04 (div=04)
49 mod 13 = 05 (div=04)
4A mod 13 = 06 (div=04)
4B mod 13 = 07 (div=04)
4C mod 13 = 00 (div=04)
4D mod 13 = 01 (div=04)
4E mod 13 = 02 (div=04)
4F mod 13 = 03 (div=04)
50 mod 13 = 0F (div=05)
51 mod 13 = 0E (div=05)
52 mod 13 = 0D (div=05)
53 mod 13 = 0C (div=05)
54 mod 13 = 0B (div=05)
55 mod 13 = 0A (div=05)
56 mod 13 = 09 (div=05)
57 mod 13 = 08 (div=05)
58 mod 13 = 07 (div=05)
59 mod 13 = 06 (div=05)
5A mod 13 = 05 (div=05)
5B mod 13 = 04 (div=05)
5C mod 13 = 10 (div=04)
5D mod 13 = 11 (div=04)
5E mod 13 = 12 (div=04)
5F mod 13 = 00 (div=05)
60 mod 13 = 0A (div=06)
61 mod 13 = 0B (div=06)
62 mod 13 = 08 (div=06)
63 mod 13 = 09 (div=06)
64 mod 13 = 0E (div=06)
65 mod 13 = 0F (div=06)
66 mod 13 = 0C (div=06)
67 mod 13 = 0D (div=06)
68 mod 13 = 02 (div=06)
69 mod 13 = 03 (div=06)
6A mod 13 = 00 (div=06)
6B mod 13 = 01 (div=06)
6C mod 13 = 06 (div=06)
6D mod 13 = 07 (div=06)
6E mod 13 = 04 (div=06)
6F mod 13 = 05 (div=06)
70 mod 13 = 09 (div=07)
71 mod 13 = 08 (div=07)
72 mod 13 = 0B (div=07)
73 mod 13 = 0A (div=07)
74 mod 13 = 0D (div=07)
75 mod 13 = 0C (div=07)
76 mod 13 = 0F (div=07)
77 mod 13 = 0E (div=07)
78 mod 13 = 12 (div=06)
79 mod 13 = 00 (div=07)
7A mod 13 = 10 (div=06)
7B mod 13 = 11 (div=06)
7C mod 13 = 05 (div=07)
7D mod 13 = 04 (div=07)
7E mod 13 = 07 (div=07)
7F mod 13 = 06 (div=07)
80 mod 13 = 0B (div=09)
81 mod 13 = 0A (div=09)
82 mod 13 = 09 (div=09)
83 mod 13 = 08 (div=09)
84 mod 13 = 0F (div=09)
85 mod 13 = 0E (div=09)
86 mod 13 = 0D (div=09)
87 mod 13 = 0C (div=09)
88 mod 13 = 10 (div=08)
89 mod 13 = 11 (div=08)
8A mod 13 = 12 (div=08)
8B mod 13 = 00 (div=09)
8C mod 13 = 07 (div=09)
8D mod 13 = 06 (div=09)
8E mod 13 = 05 (div=09)
8F mod 13 = 04 (div=09)
90 mod 13 = 08 (div=08)
91 mod 13 = 09 (div=08)
92 mod 13 = 0A (div=08)
93 mod 13 = 0B (div=08)
94 mod 13 = 0C (div=08)
95 mod 13 = 0D (div=08)
96 mod 13 = 0E (div=08)
97 mod 13 = 0F (div=08)
98 mod 13 = 00 (div=08)
99 mod 13 = 01 (div=08)
9A mod 13 = 02 (div=08)
9B mod 13 = 03 (div=08)
9C mod 13 = 04 (div=08)
9D mod 13 = 05 (div=08)
9E mod 13 = 06 (div=08)
9F mod 13 = 07 (div=08)
A0 mod 13 = 0D (div=0B)
A1 mod 13 = 0C (div=0B)
A2 mod 13 = 0F (div=0B)
A3 mod 13 = 0E (div=0B)
A4 mod 13 = 09 (div=0B)
A5 mod 13 = 08 (div=0B)
A6 mod 13 = 0B (div=0B)
A7 mod 13 = 0A (div=0B)
A8 mod 13 = 05 (div=0B)
A9 mod 13 = 04 (div=0B)
AA mod 13 = 07 (div=0B)
AB mod 13 = 06 (div=0B)
AC mod 13 = 12 (div=0A)
AD mod 13 = 00 (div=0B)
AE mod 13 = 10 (div=0A)
AF mod 13 = 11 (div=0A)
B0 mod 13 = 0E (div=0A)
B1 mod 13 = 0F (div=0A)
B2 mod 13 = 0C (div=0A)
B3 mod 13 = 0D (div=0A)
B4 mod 13 = 0A (div=0A)
B5 mod 13 = 0B (div=0A)
B6 mod 13 = 08 (div=0A)
B7 mod 13 = 09 (div=0A)
B8 mod 13 = 06 (div=0A)
B9 mod 13 = 07 (div=0A)
BA mod 13 = 04 (div=0A)
BB mod 13 = 05 (div=0A)
BC mod 13 = 02 (div=0A)
BD mod 13 = 03 (div=0A)
BE mod 13 = 00 (div=0A)
BF mod 13 = 01 (div=0A)
C0 mod 13 = 07 (div=0D)
C1 mod 13 = 06 (div=0D)
C2 mod 13 = 05 (div=0D)
C3 mod 13 = 04 (div=0D)
C4 mod 13 = 10 (div=0C)
C5 mod 13 = 11 (div=0C)
C6 mod 13 = 12 (div=0C)
C7 mod 13 = 00 (div=0D)
C8 mod 13 = 0F (div=0D)
C9 mod 13 = 0E (div=0D)
CA mod 13 = 0D (div=0D)
CB mod 13 = 0C (div=0D)
CC mod 13 = 0B (div=0D)
CD mod 13 = 0A (div=0D)
CE mod 13 = 09 (div=0D)
CF mod 13 = 08 (div=0D)
D0 mod 13 = 04 (div=0C)
D1 mod 13 = 05 (div=0C)
D2 mod 13 = 06 (div=0C)
D3 mod 13 = 07 (div=0C)
D4 mod 13 = 00 (div=0C)
D5 mod 13 = 01 (div=0C)
D6 mod 13 = 02 (div=0C)
D7 mod 13 = 03 (div=0C)
D8 mod 13 = 0C (div=0C)
D9 mod 13 = 0D (div=0C)
DA mod 13 = 0E (div=0C)
DB mod 13 = 0F (div=0C)
DC mod 13 = 08 (div=0C)
DD mod 13 = 09 (div=0C)
DE mod 13 = 0A (div=0C)
DF mod 13 = 0B (div=0C)
E0 mod 13 = 12 (div=0E)
E1 mod 13 = 00 (div=0F)
E2 mod 13 = 10 (div=0E)
E3 mod 13 = 11 (div=0E)
E4 mod 13 = 05 (div=0F)
E5 mod 13 = 04 (div=0F)
E6 mod 13 = 07 (div=0F)
E7 mod 13 = 06 (div=0F)
E8 mod 13 = 09 (div=0F)
E9 mod 13 = 08 (div=0F)
EA mod 13 = 0B (div=0F)
EB mod 13 = 0A (div=0F)
EC mod 13 = 0D (div=0F)
ED mod 13 = 0C (div=0F)
EE mod 13 = 0F (div=0F)
EF mod 13 = 0E (div=0F)
F0 mod 13 = 02 (div=0E)
F1 mod 13 = 03 (div=0E)
F2 mod 13 = 00 (div=0E)
F3 mod 13 = 01 (div=0E)
F4 mod 13 = 06 (div=0E)
F5 mod 13 = 07 (div=0E)
F6 mod 13 = 04 (div=0E)
F7 mod 13 = 05 (div=0E)
F8 mod 13 = 0A (div=0E)
F9 mod 13 = 0B (div=0E)
FA mod 13 = 08 (div=0E)
FB mod 13 = 09 (div=0E)
FC mod 13 = 0E (div=0E)
FD mod 13 = 0F (div=0E)
FE mod 13 = 0C (div=0E)
FF mod 13 = 0D (div=0E)
Цитата(ViKo @ Mar 16 2015, 23:58) Методика деления описана Любая методика, которая не подтверждается проверкой умножением, некорректная. частное * делитель + остаток = делимое, если нет - то методика неверная. Извините, но это аксиома. Точнее, определение деления.
|
|
|
|
|
|
|
|
Mar 16 2015, 21:54
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 17 2015, 00:52) Мы говорим о полиномиальном делении? Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д. Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять.
|
|
|
|
|
|
|
|
Mar 16 2015, 22:02
|
Универсальный солдатик
Группа: Модераторы
Сообщений: 8 634
Регистрация: 1-11-05
Из: Минск
Пользователь №: 10 362
|
Цитата(SM @ Mar 17 2015, 00:54) Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д.
Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять. Я уже натренирован. Мои расчеты показаны выше. И они полностью соответствуют моим предположениям. А вы умножаете неправильно. x^9 там, действительно, быть никак не может.
|
|
|
|
|
|
|
|
Mar 17 2015, 05:23
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 17 2015, 01:02) А вы умножаете неправильно. x^9 там, действительно, быть никак не может. Ну что тут поделать... Могу посоветовать лишь подучить математику... Чтобы вспомнить, что x^5 * x^4 = x^9. Даже в GF(2). Повторю проверку Вашего ошибочного расчета на всякий случай, чтобы остальные, желающие разобраться в сути, поняли, еще раз. Ошибочный результат: 0x30 / 0x13 = 0x35, 0x0F Проверка: 1) частное, 0x35, это 0011 0101 , в полиномиальном виде x^5+x^4+x^2+1. 2) остаток, 0x0F, это 0000 1111, в полиномиальном виде x^3+x^2+x+1 3) вычисляем произведение 0x35 на порождающий полином 0x13, в полиномиальном виде x^4+x+1: (x^5+x^4+x^2+1)*(x^4+x+1) = (x^9+x^6+x^5)+(x^8+x^5+x^4)+(x^6+x^3+x^2)+(x^4+x+1) = x^9 + x^8 + (x^6+x^6) + (x^5 + x^5) + (x^4+x^4) + x^3 + x^2 + x + 1 = x^9+x^8+x^3+x^2+x+1 умножение делается так. Каждый член первого множителя умножается на каждый член второго множителя, и все произведения суммируются. Это видно в первой операции - в каждой из скобок произведение второго множителя на каждый из членов первого. Члены с одинаковой степенью группируются (вторая операция), и если их четное количество, то они уничтожаются (коэффициент при члене=0), если нечетное, то остаются (коэффициент при члене=1). Это уже правила сложения в GF(2): 0+0=0; 1+0=1; 0+1=1; 1+1=0; 4) Прибавляем к произведению остаток от деления. (x^9+x^8+x^3+x^2+x+1) + (x^3+x^2+x+1) = x^9 + x^8 + (x^3+x^3) + (x^2+x^2) + (x+x) + (1+1) = x^9 + x^8. 5) проверяем: x^9 + x^8 это 0011 0000 0000 = 0x300. Что, никак не соответствует исходному 0x30 аккурат на 4 порядка. то есть, правильный результат, 0x300 / 0x13 = 0x35, 0x0F Теперь, алгоритм деления, который реально проходит проверку умножением, то есть, после него всегда исполняется условие "частное*полином+остаток == делимое", рассчитанный на 8-битные данные: Код делимое = данное;
делитель = полином
остаток = делимое;
сдвигатель = делитель << 8;
маска = 0x80 << 8;
частное = 0;
цикл ( 8 раз) {
сдвигатель >>= 1;
маска >>=1
частное <<= 1;
если (остаток >= делитель И (остаток & маска) != 0) {
остаток ^= сдвигатель;
частное |= 1;
}
}
|
|
|
|
|
|
|
|
Mar 17 2015, 05:59
|
Гуру
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881
|
Цитата(ViKo @ Mar 17 2015, 08:57) А вы замените умножение последовательными сложениями, и вспомните, что в данной математике переносы не распространяются. Это некорректно. Читайте про умножение полиномов в GF в учебнике. Ну, хотя бы, тут - http://habrahabr.ru/post/212095/До первого примера умножения, остальное нас не интересует, так как у нас поле простое, GF(2^m) с m=1, а остальное касается m>1, когда надо приводить результат.
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
