Алгоритм Рида-Соломона для генератора QR-кода
В своем классе структур данных я хотел создать генератор QR-кода для моего окончательного проекта. Однако у меня возникли некоторые затруднения с пониманием части «Форматированная коррекция ошибок». Я хочу использовать исправление ошибок 11 (L) и шаблон маскирования 100 (каждый второй ряд). Поскольку я являюсь старшекурсником, я хочу попытаться сделать это довольно просто, имея дело с QR-кодом версии 1 и используя байт-кодировку.
Тогда я не понимаю, как придумать блоки исправления ошибок после вывода данных.
Решение
Что касается некоторых спецификаций, уровень коррекции ошибок L (низкий, может исправить 7%) идентифицируется как двухбитовая комбинация 01, а не 11. Ссылка на строки формата QR-кода, которые включают маску и уровень коррекции ошибок.
http://www.thonky.com/qr-code-tutorial/format-version-information
Так как вы выбрали определенный уровень исправления ошибок и шаблон маски, которые совпадают с используемыми на веб-странице thonky.com, строка формата будет фиксированным 15-битным шаблоном битов: «последняя строка формата для кода с Уровень исправления ошибок L и шаблон маски 4 — 110011000101111 «, так что вам не придется его вычислять.
Для QR-кодов 8-битное поле GF (2 ^ 8) основано на 9-битном полиноме
x^8 + x^4 + x^3 + x^2 + 1 = hex 11d
the primitive α = x + 0 = hex 2
Обратите внимание, что сложение и вычитание для двоичного поля совпадают с xor.
Версия 1 QR-кода представляет собой матрицу из 21 на 21 бит = 441 бит, представленную в виде черных или белых квадратов, с 208 битами == 26 байтов, используемыми для данных и ecc.
QR-код с уровнем исправления ошибок L имеет 152 бита == 19 байтов данных и 56 битов == 7 байт ecc, 4 используются для коррекции, 3 используются для обнаружения. 4 байта, используемые для исправления, могут исправить 2 из 26 байтов, что составляет около 7% из 26 байтов данных. В дополнение к 3 байтам, используемым для обнаружения, также обнаруживается неисправимая ошибка, если во время декодирования любое из вычисленных местоположений находится вне диапазона 26 байтов данных.
Генераторный многочлен g (x) представляет собой 8-членный полином, который приводит к 7-членному остатку. 7 корней g (x) = 0 являются последовательными степенями α, в этом случае α ^ 0, α ^ 1, … α ^ 6 == hex 01, 02, 04, 08, 10, 20, 40.
g(x) = (x-1)(x-α)(x-α^2)(x-α^3)(x-α^4)(x-α^5)(x-α^6)
Поскольку сложение == вычитание == xor, минусы можно заменить на плюсы:
g(x) = (x+1)(x+α)(x+α^2)(x+α^3)(x+α^4)(x+α^5)(x+α^6)
g(x) = (x+01)(x+02)(x+04)(x+08)(x+10)(x+20)(x+40)
g(x) = 01 x^7 + 7f x^6 + 7a x^5 + 9a x^4 + a4 x^3 + 0b x^2 + 44 x + 75
Рассмотрим 19 байтов данных как полином m (x) (m означает сообщение). 19 байтов данных дополняются 7 байтами нуля путем умножения на x ^ 7. Затем 26-байтовый полином делится на генераторный полином, а остаток «вычитается» (xor’ed или так как заполнение дает нули, остаток просто заменяет заполненные байты) на младшие 7 байтов дополненных данных. Вызов остатка r (x) и закодированного результата c (x):
r(x) = (m(x) x^7) % g(x)
c(x) = (m(x) x^7) - r(x)
Снова обратите внимание, что вычитание — это xor, то же самое, что и сложение.
В Вики есть достойная статья о Риде Соломоне:
http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
и НАСА имеет учебник:
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf
Другие решения
Других решений пока нет …
detector