Сложение и умножение в поле Галуа
Я пытаюсь сгенерировать QR-коды на чрезвычайно ограниченной встроенной платформе. Все в спецификации кажется довольно простым, за исключением генерации кодовых слов для исправления ошибок. Я посмотрел на кучу существующих реализаций, и все они пытаются реализовать кучу полиномиальной математики, которая идет прямо мне в голову, особенно в отношении полей Галуа. Самый простой способ, который я вижу, как в математической сложности, так и в требованиях к памяти, - это принципиальная схема, которая изложена в самой спецификации:
С их описанием я вполне уверен, что смогу реализовать это, за исключением частей, помеченных как GF(256) сложение и GF(256) умножение.
Они предлагают эту помощь:
Полиномиальная арифметика для QR-кода должна быть рассчитана с использованием побитовой арифметики по модулю 2 и побитовой арифметики по модулю 100011101. Это поле Галуа 2^8, где 100011101 представляет собой полином модуля простого модуля x^8+x^4+x^3+x^2+1.
что все в значительной степени греческое для меня.
Итак, мой вопрос заключается в следующем: как проще всего выполнить сложение и умножение в этом виде арифметики поля Галуа? Предположим, что оба входных числа имеют ширину 8 бит, и мой вывод должен быть также шириной 8 бит. Несколько реализаций предварительно рассчитывают или жестко кодируют в двух таблицах поиска, чтобы помочь с этим, но я не уверен, как они рассчитываются, или как бы я использовал их в этой ситуации. Я бы предпочел не принимать 512-байтовое попадание памяти для двух таблиц, но это действительно зависит от альтернативы. Мне просто нужна помощь в понимании того, как сделать одну операцию умножения и сложения в этой схеме.
2 ответа
На практике нужен только один стол. Это было бы для GP(256) умножить. Обратите внимание, что вся арифметика не содержит переносов, что означает отсутствие переноса.
Сложение и вычитание без переноса эквивалентно xor.
Так в GF(256) a + b а также a - b оба эквивалентны a xor b,
Умножение GF(256) также выполняется без переноса и может быть выполнено с использованием умножения без переноса аналогичным образом с сложением / вычитанием без переноса. Это может быть эффективно выполнено с помощью аппаратной поддержки, например, с помощью набора инструкций Intel CLMUL.
Тем не менее, сложная часть, это уменьшение по модулю 100011101, В обычном целочисленном делении вы делаете это с помощью ряда шагов сравнения / вычитания. В GF(256) вы делаете это почти идентичным образом, используя серию шагов сравнения /xor.
Фактически, это достаточно плохо, когда все еще быстрее просто предварительно вычислить все умножения 256 x 256 и поместить их в справочную таблицу на 65536 записей.
на странице 3 следующего pdf есть довольно хорошая справка по арифметике GF256:
(Я отслеживаю указатель на zxing в первом ответе, так как я автор.)
Ответ о сложении совершенно правильный; поэтому работать в этой области удобно на компьютере.
Да, умножение работает, и это для GF256. a * b действительно то же самое, что exp(log(a) + log(b)). И поскольку GF256 имеет только 256 элементов, у него есть только 255 уникальных степеней "х", и то же самое для журнала. Так что их легко положить в таблицу поиска. Таблицы "обернутся" в 256, поэтому вы видите "% size". "/ size" немного сложнее объяснить в предложении - это потому, что на самом деле 1-255 "обтекание", а не 0-255. Так что нужен не просто простой модуль.
Последняя часть, возможно, состоит в том, как вы уменьшаете по модулю неприводимый многочлен. Неприводимый многочлен - это x^8 плюс некоторые младшие члены, верно - назовите его I(x) = x^8 + R(x). И полином конгруэнтен 0 в поле по определению; I(x) == 0. Так что x^8 == -R(x). И, удобно, сложение и вычитание одинаковы, так что x^8 == -R(x) == R(x).
Единственное время, когда нам нужно уменьшить многочлены большей мощности, - это построение таблицы показателей. Вы просто продолжаете умножаться на x (что означает сдвиг влево), пока оно не станет слишком большим - получится член x^8. Но х ^ 8 такой же, как R (х). Итак, вы берете x^8 и добавляете R(x). R(x) просто имеет полномочия вплоть до x^7, поэтому он все еще находится в байте, все в GF(256). И вы знаете, как добавить в этом поле.
Помогает?