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

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

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

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

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

который для меня очень важен.

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

Ответ 1

На практике требуется только одна таблица. Это будет для GP (256) умножить. Обратите внимание, что вся арифметика не имеет отношения к переносу, что означает, что распространение переноса отсутствует.

Сложение и вычитание без переноса эквивалентно xor.

Итак, в GF (256), a + b и a - b оба эквивалентны a xor b.

GF (256) умножение также не требует переноса и может быть выполнено с использованием непереходного умножения аналогичным образом с добавлением/вычитанием без переноса. Это можно сделать с помощью аппаратной поддержки с помощью набора команд Intel CLMUL.

Однако жесткая часть уменьшает модулю 100011101. В нормальном целочисленном делении вы делаете это с помощью серии шагов сравнения/вычитания. В GF (256) вы делаете это почти одинаковым образом, используя серию шагов сравнения /xor.

На самом деле, это плохо, где еще быстрее, чтобы просто прекомпотировать все 256 х 256 умножить и поместить их в таблицу поиска 65536.

стр. 3 из следующего pdf имеет неплохую ссылку на арифметику GF256:

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

Я выполнил исправление ошибок Рида-Соломона, используя GF (256), но это было с полиномом 10010010 вместо 100011101.

Ответ 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 уникальных полномочий "x", а также для журнала. Таким образом, их легко найти в таблице поиска. Таблицы будут "обтекать" по 256, поэтому вы видите "% size". "/size" немного сложнее объяснить в предложении - это потому, что действительно 1-255 "обернуть", а не 0-255. Так что это не совсем простой модуль, который вам нужен.

Последняя часть, возможно, заключается в том, как вы уменьшаете по модулю неприводимый многочлен. Неприводимый многочлен х ^ 8 плюс некоторые члены с более низкой степенью, правый - назовем его я (x) = x ^ 8 + R (x). И этот полином, по определению, конгруэнтен нулю в поле; я (x) == 0. Итак, x ^ 8 == -R (x). И, что удобно, сложение и вычитание одинаковы, поэтому x ^ 8 == -R (x) == R (x).

Единственный раз, когда нам нужно уменьшить многочлены более высокой мощности, является построение таблицы показателей. Вы просто продолжаете умножать на x (это сдвиг влево), пока он не станет слишком большим - получает член x ^ 8. Но x ^ 8 совпадает с R (x). Итак, вы вынимаете x ^ 8 и добавляете R (x). R (x) просто обладает степенями до x ^ 7, поэтому все в байте все еще в GF (256). И вы знаете, как добавить в это поле.

Помогает?