Алгоритм Рида-Соломона как важная составляющая QR-кодов

QR-код — это специальный двухмерный штрих-код, разработанный компанией Denso-Wave в 1994 году для быстрого распознавания информации из него с помощью камеры мобильного телефона.

Для корректировки ошибок в QR-кодировании используются коды Рида-Соломона (RS), записываемые после всей остальной информации.

В 1960 году сотрудники из лаборатории Линкольна Массачуссетского технологического института Ирвин Рид и Густав Соломон изобрели код и назвали его Код Рида-Соломона. В статье «Polynomial Codes over Certain Finite Fields» была представлена идея использования данного кода. Элвин Берлекэмп и Джэймс Месси в 1969 году предложили эффективные алгоритмы декодирования, а также Давид Мандельбаум предложил метод, использующий Алгоритм Евклида. Впервые код Рида-Соломона был применен в 1982 году при серийном выпуске компакт-дисков [2].

Код Рида-Соломона позволяет считать с камеры коды даже при наличии неких проблем (например, повреждение, стёртость, зачеркивание).

QR-коды имеют специальные уровни коррекции ошибок, каждый из которых позволяет восстанавливать определенный процент информации при повреждении кода:

• 1)    L-уровень восстанавливает 7% информации, в основном используется для QR-кодов в сети Интернет, где они не могут повредиться;

• 2)    M-уровень восстанавливает 15% информации, является лучшим вариантом в создании QR-кодов на плакатах, стендах;

• 3)    Q-уровень восстанавливает 25% информации, используется при создании наклеек, упаковок и т.д., так как их вероятность повреждения более высокая;

• 4)    H-уровень восстанавливает 30% информации, используется как и Q-уровень, но с большим процентом восстановления информации.

Чтобы создавать QR-коды с неординарным и привлекательным дизайном, необходимо использовать 30% от данных QR-кода, которые могут отсутствовать или быть испорченными, и при этом код будет рабочим. Использование H-уровня коррекции ошибок добавляет много шума (экстра-блоки) и тем самым дает возможность использовать 30% места кода для добавления интересных элементов дизайна.

В создании QR-кода можно выделить несколько основных этапов [3].

Этап 1. Кодирование данных.

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

• •    цифровое кодирование – только цифры;

• •    буквенно-цифровое – цифры и латинские буквы;

• •    байтовое кодирование – двоичные данные;

• •    кодирование иероглифов Кандзи – символы японского алфавита Kanji.

Перед началом кодирования, должна быть создана пустая последовательность бит, которая потом заполняется. Это яв-

ляется общим для всех способов. В дальнейшем она заполняется согласно правилам каждого конкретного способа.

При цифровом кодировании можно закодировать максимальное количество символов – 7089. Вначале последовательность цифр должна быть разбита на цифирные блоки, по 3 символа в каждом. Для каждого блока выделяется по 10 бит. Полученные трехзначные числа переводятся в двоичную систему. В дальнейшем они должны быть добавлены к общей последовательности бит в том порядке, в котором стояли до перевода в двоичное число. Для экономии места оставшиеся не в тройках числа могут быть закодированы 7 или 4 битами.

Буквенно-цифровое кодирование (латиница) кодирует максимум 4296 символов. При использовании этого способа разбитие происходит на блоки по два символа, которые кодируются в соответствии со специальной таблицей значений. После получения значения символа, оно должно быть умножено на 45. Результат суммируется со значением следующего символа. После этого можно приступать к переводу в 11 битное число двоичного вида. Все полученные биты так же добавляются в единую последовательность бит в оригинальном порядке. Здесь так же для экономии места разрешено использование 6 битного числа для завершающей группы символов.

При использовании байтового кодирования (двоичный код) – максимум 2953 байт (следовательно, около 2953 букв кириллицы в кодировке windows-1251 или около 1450 букв кириллицы в utf-8).

Кодирование иероглифов Кандзи кодирует до 1817 байт. Позволяет кодировать иероглифы в системе Shift JIS, используемой для японских символов. Каждому иероглифу соответствует свое кодовое значение, по аналогии с кодами для латинских букв. Перевод осуществляется в 13 битовое число. Сложность состоит в том, что таблиц и списков для перевода иероглифов достаточно много и их можно спутать.

Этап 2. Добавление служебной информации.

На данном этапе генерации QR-кода определяется версия кода и значение коррекции ошибок (один из четырех уровней). Кроме того добавляются служебные поля с информацией о способе кодирования и количестве данных.

Этап 3. Деление на блоки.

Сформированная последовательность байт группируется в несколько блоков (число зависит от версии кода и значения коррекции ошибок). Важным условием является заполнение всех блоков данными.

Этап 4. Создание байтов коррекции.

Именно на данном этапе генерации QR-кода ключевую роль играет алгоритм Рида-Соломона. Он применяется к каждому блоку информации с учетом выбранного варианта кода и значения коррекции ошибок. После ориентируясь по этим данным, создается многочлен генерации.

Этап 5. Объединение блоков информации.

Готовые блоки (исходные данные, коррекция ошибок) сводятся в одну двоичную последовательность.

Область применения кодов Рида-Соломона необычайно широка [4]. Их используют в ленточных запоминающих устройствах, контроллерах оперативной памяти, жестких дисках, модемах, CD-ROM/DVD-приводах и т. д. Это объясняется их умением обнаружения и исправления как одиночных, так и групповых ошибок и безболезненным переносом порчи нескольких секторов носителя, содержащего архив, и даже полное разрушение целого тома многотомного архива. И именно поэтому код Рида-Соломона является необходимой составляющей при разработке QR-кодов, так как они довольно часто могут быть испорчены.