AHTOXA 18 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Так а как раскодировать, если для двух разных данных может быть одинаковая CRC? Как принять решение, какое из этих двух данных корректное? Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Очевидно, Это не доказательство. Вот для арифметического деления, доказательство четкое (математически), что однозначности нет. По причине того, что число 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. Проверка опять показала, что поделено правильно, и остаток именно такой. Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Вопрос - как при помощи некой функции закодировать данные так, чтобы они раскодировались методом подсчета CRC. Я не уверен в том, что существует такая функция в принципе (то есть, математически, является функцией, сопоставляя каждому аргументу из ее области определения единственное значение результата). То, что можно подобрать такой поток данных, чтобы на выходе получить требуемую последовательность - да с этим никто не спорит ни разу! Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC. Раскодировать нужно не в одно число, а весь массив. Слово за словом, используя аппаратный блок CRC. Задача, что подсунуть этому блоку, чтобы после каждого вычисления CRC получался исходный код. В интернете это называется reversing CRC. http://stackoverflow.com/questions/1514040/reversing-crc32 Вижу, математики запутали своим полиномиальным делением. Куда логичнее по-инженерному пользоваться регистрами сдвига и исключающим ИЛИ. Не вижу препятствий написать реверсивный алгоритм CRC, двигая данные в регистре в обратную сторону. :rolleyes: XOR, естественно, тоже ... тоже что-то с ними сделать. :rolleyes: Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010"... Это уже пара данных, требующая в данной задаче двух выходных CRC. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Это уже пара данных, требующая в данной задаче двух выходных CRC. Так и речь именно о паре (или больше). Что при одном четырехбитном данном при инициализации нулями будет однозначность, это, вроде, вопрос бесспорный. С арифметическим аналогом тоже самое - при начальном значении, меньшим, чем делитель-256, тоже все однозначно для одного байта. Неоднозначности начинаются, когда байт больше, или начальное значение больше определенного. Просто, я неудачную пару данных привел, наоборот, когда для двух разных начальных значений будет одинаковый код на выходе для одинаковых данных. Подобрать наоборот? Чтобы для одного начального значения и двух разных данных получился одинаковый полином? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Полином CRC известен, он не от балды берется. x^4 + x^1 + 1. Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число (от предыдущего расчета) - это к вопросу о начальном значении. Не подберете. :) Давайте так. Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной нулями, даст на выходе нужное мне значение? Да. Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной неким известным числом, даст на выходе нужное мне значение? Да. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Полином 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) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Могу только повторить - 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.pdf upd. Исправляю остатки - выбрасываю старший 0. Тогда CRC от последовательности исходного числа и остатка даст 0. Это связано с разрядностью используемых чисел, в данном случае 4. Для проверки в CRC калькуляторе нужно задавать 30F0. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Могу только повторить - 0x30...0x3F И я могу только повторить. Что 0x30 - это пара 4-битных чисел. Сначала 3, потом 0. И даже Вашу же просьбу процитировать: Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число Вот я и приписал 0x3 к паре чисел, 0x5 и 0x6. Получилось 0х35 и 0х36. 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 - Вы хоть сами бы проверили умножением, прежде чем сюда то писать. Для 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, которого близко не было! Для этого третий полубайт нужен! 0x31 / 0x13 = 0x34, 0x0C Заканчивайте писать лажу, ПРОВЕРЯЙТЕ УМНОЖЕНИЕМ!!!! Должно сходиться div*(x^4+x+1)+mod = исходное число! У Вас и близко не сходится. Вот результат (ПРОВЕРЕННЫЙ УМНОЖЕНИЕМ!!!!) для всех пар 4-битных чисел : 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 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Любая методика, которая не подтверждается проверкой умножением, некорректная. частное * делитель + остаток = делимое, если нет - то методика неверная. Извините, но это аксиома. Точнее, определение деления. Мы говорим о полиномиальном делении? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Мы говорим о полиномиальном делении? Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д. Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 16 марта, 2015 Опубликовано 16 марта, 2015 · Жалоба Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д. Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять. Я уже натренирован. Мои расчеты показаны выше. И они полностью соответствуют моим предположениям. А вы умножаете неправильно. x^9 там, действительно, быть никак не может. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 17 марта, 2015 Опубликовано 17 марта, 2015 · Жалоба А вы умножаете неправильно. 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; } } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 17 марта, 2015 Опубликовано 17 марта, 2015 · Жалоба А вы замените умножение последовательными сложениями, и вспомните, что в данной математике переносы не распространяются. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 17 марта, 2015 Опубликовано 17 марта, 2015 · Жалоба А вы замените умножение последовательными сложениями, и вспомните, что в данной математике переносы не распространяются. Это некорректно. Читайте про умножение полиномов в GF в учебнике. Ну, хотя бы, тут - http://habrahabr.ru/post/212095/ До первого примера умножения, остальное нас не интересует, так как у нас поле простое, GF(2^m) с m=1, а остальное касается m>1, когда надо приводить результат. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 17 марта, 2015 Опубликовано 17 марта, 2015 · Жалоба http://depa.usst.edu.cn/chenjq/www2/softwa...calculation.htm Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться