Сложение и умножение в поле Галуа

Question

Я пытаюсь сгенерировать QR-коды на чрезвычайно ограниченной встроенной платформе.Все в спецификации кажется довольно простым, за исключением генерации кодовых слов с исправлением ошибок.Я посмотрел на кучу существующих реализаций, и все они пытаются реализовать кучу полиномиальной математики, которая идет прямо мне в голову, особенно в отношении полей Галуа.Самый простой способ, который я вижу, как в математической сложности, так и в требованиях к памяти, - это принципиальная схема, изложенная в самой спецификации:

С их описанием яЯ уверен, что смогу реализовать это, за исключением частей, помеченных как GF (256) и GF (256).

Они предлагают эту помощь:

Полиномиальная арифметика для QRКод рассчитывается с использованием побитовой арифметики по модулю 2 и побитовой арифметики по модулю 100011101.Это поле Галуа 2 ^ 8 с 100011101, представляющим полином модуля простого модуля x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.

, который в значительной степени греческийдля меня.

Итак, мой вопрос заключается в следующем: как проще всего выполнить сложение и умножение в этом виде арифметики поля Галуа?Предположим, что оба входных числа имеют ширину 8 бит, и мой вывод должен быть также шириной 8 бит.Несколько реализаций предварительно рассчитывают, или используют жесткий код в двух таблицах поиска, чтобы помочь с этим, но я не уверен, как они рассчитываются, или как бы я использовал их в этой ситуации.Я бы предпочел не принимать 512-байтовый удар по памяти для двух таблиц, но это действительно зависит от того, что является альтернативой.Мне действительно нужна помощь в понимании того, как выполнить одну операцию умножения и сложения в этой схеме.

Answer 1

На практике нужна только одна таблица.Это было бы для 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:

http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf

Answer 2

(я отслеживаю указатель на zxing в первом ответе, так как я являюсь автором.)

Ответ о сложении совершенно правильный; поэтому работать в этой области удобно на компьютере.

См. http://code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/reedsolomon/GenericGF.java

Да, умножение работает, и это для 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). И вы знаете, как добавить в это поле.

Помогает