Чтение Micro QR Code версии М3 (числовой режим)

Задание: необходимо прочитать Micro QR Code версии М3, содержащий кодовое слово, состоящее из цифр (на примере – 777777777777777777 (18 цифр) и максимальном кодовом расстоянии (23 цифры) – 77777777777777777777777; почему выбрано именно такое количество цифр будет также расшифровано) на основе алгоритма, приведенного в ГОСТ Р ИСО/МЭК 18004-2015 (п. 7.4.3, пример 2). Аналогично версии М2 данный режим невозможно прочитать стандартными ресурсами мобильных устройств, производимых GAFAM (как оказалось, свободно распространяемые библиотеки страшно глючат, поэтому Ассоциация отказалась и от этого режима).

Примечание: здесь и далее будет использоваться информация ГОСТ Р ИСО/МЭК 18004-2015 или в оригинале ISO/IEC 18004:2015 (далее – ГОСТ).

Этап 0. Подготовка исходных данных

Рассмотрим М3 поближе. Имеем матрицу размерностью 15x15 бинарных символов (рис. 11 ГОСТ), один индикатор и два определителя (горизонтальный и вертикальный) (рис. 1).

Первый наносимый ограничитель символ на матрицу М3 – надлежащие битовые последовательности информации о формате (рис. 2). Чтение битовой последовательности начинается с 14 бита, т.е. последовательность чтения/записи будет 14, 13, 12, 11, 10 и т.д.

Второй не менее важный элемент М3 – маршрут последовательности заполнения битами данных поля матрицы (рис. 3). Данная схема отражена на рисунке 11 ГОСТ.

Примечание: приведенные в ГОСТ маршруты для M3-M и M3-L практически одинаковые. Если присмотреться внимательнее, то оба маршрута дублируют друг друга и не вносят изменения в последовательность чтения/записи. Единственное различие – это учет блока в 4-бита для RS-алгоритма (9 и 11 блоки). Далее приводится вариант маршрутов для M3-M и M3-L, примененные в распространяемом бесплатном модуле Ассоциации (рис. 4). Маршруты идентичны и не совпадают с приведенными в ГОСТ (ноу-хау программистов моделистов).

Если наложить маршрут на матрицу, получаем последовательность из 124 бит кода М3 (рис. 4). Число 124 пригодится позже при добавлении кода по алгоритму Рида-Соломона на поле Галуа.

Примечание: здесь и далее будем использовать один из доступных программных инструментов Ассоциации практически на любом ПК – MS Excel (русскоязычная версия). Как следствие, все команды автоматизации процессов будут на кириллице.

Запускаем программное приложение MS Excel. Готовим последовательность листов Книги для дальнейшей работы:

-     Лист1 – называем Code;

-     Лист2 – M3 7×18;

-     Лист3 – M3 7×23.

Лист1 (Code) – для размещения корректирующих данных и сверки полученных на листах результатов. Остальные листы нужны для декодирования соответствующих последовательностей.

На листах с семерками (Лист2 – Лист3) делаем размерность ячеек одинаковой (например, 23 на 23 пикселя) и по горизонтали, и по вертикали (рис. 5a). Затем закрашиваем поле серым фоновым цветом (рис. 5b).

Примечание: для удобства дальнейшего описания ссылок на ячейки листа перейдем от современного отображения адресов ячеек в виде R1C1 (относительные ссылки) к старому формату в виде A1 (буквенно-числовое отображение). Выбираем в Меню Файл → Параметры. В категории Формулы в группе Работа с формулами снимаем галочку напротив пункта Стиль ссылок R1C1. В результате названия столбиков должны поменяться с чисел на латинские буквы (рис. 6).

Если посчитать количество пикселей (квадратиков) микрокода М3 (рис. 1) по горизонтали и/или по вертикали, то получится матрица (табличка) размерностью 15×15. Создадим новую схему шаблон для микрокода М3 на листах с семерками: Лист2 – Лист3 начиная с ячейки D4 (рис. 6).

Воспользуемся любым кодировщиком микрокодов в Интернет или рисунками далее для переноса битовой маски рабочего поля микрокода на листы книги MS Excel (рис. 7-8).

Каждый микрокод располагается на индивидуальном листе книги. Верхний левый угол каждого микрокода начинается в ячейке D4.

Исходные данные для декодирования готовы. Переходим к заполнению первого листа книги Code.

В системе QR Code существует несколько разновидностей кодирования: числовой, алфавитно-цифровой, байтовый, кандзи, структурированное соединение и FNC1.

Примечание: каждый из методов имеет ряд собственных особенностей. Не получится использовать предложенный ниже алгоритм для байтовых последовательностей или для кандзи.

Используем числовую систему кодирования для выполнения требований задания. Следующее ограничение – необходимо кодировать 18 и 23 цифровых символа. М3 поддерживает два уровня исправления ошибок – L и M. Обращаемся к таблице 7 ГОСТ, получаем, что уровни L и M поддерживают емкость 18 цифровых символов, а 13 цифровых символа поддерживает только уровень L (табл. 1, емкость данных для цифрового режима).

Таблица 1 – Число знаков символа и емкость входных данных для QR Code (Таблица 7 ГОСТ)

Воспользуемся алгоритмом, представленном в ГОСТ (п. 7.4.3). Кодовая группа для трех цифр из десятичного числа преобразуем в 10-битовый двоичный эквивалент, для двух цифр в 7-битовый двоичный эквивалент и для одной цифры в 4-битовый двоичный эквивалент. Бòльшие комбинации разбиваются на подгруппы из 3-х символов, остаточные биты – 2 или 1. Для примеров получаем:

-     77777777777777777777777 → 1100001001, 1100001001, 1100001001, 1100001001, 1100001001, 1100001001 и 1001101 (8 групп);

-     777777777777777777 → 1100001001, 1100001001, 1100001001, 1100001001, 1100001001 и 1100001001 (6 групп);

-     777 → 1100001001;

-     77 → 1001101;

-     7 → 0111.

Открываем лист Code. Пример готового результата представлен на рисунке 9.

Для автоматизации ячеек C3-C7 воспользуемся следующими функциями:

Лист с корректирующими данными готов.

Переходим к основным микрокодам. Открываем лист книги М3 7×18 с исходным битовым полем (рис. 10a). К сожалению, за долгие годы MS Excel так и не научился работать с цветом ячеек. Добавим в каждую цветную ячейку соответствующее битовое значение: белая ячейка – 0, черная ячейка – 1 (рис. 10b).

Для удобства отделим цветом индикатор служебной информации (рис. 11a) – битовая последовательность информации о формате. Чтение последовательности начинается с 14 бита, т.е. последовательность чтения будет 14, 13, 12, 11, 10 и т.д.

Также отделяем цветом индикатор распознавания микрокода (рис. 11b).

Полученная матрица готова для дальнейшего анализа (рис. 12).

Переходим к первому этапу – работа со служебной информацией.

 Этап 1. Служебная информация

Перед тем как начать работать с основной рабочей областью микрокода, необходимо расшифровать служебную информацию. Пример итогового результата приведен на рисунке 13.

Сначала переводим служебную информацию также в бинарное представление, т.е. ряды ячеек E12-L12 и L5-L12 представляем как набор 0 (светлые ячейки) и 1 (темные ячейки) (рис. 13).

Выносим служебную информацию из микрокода, т.е. дублируем полученный ряд в угловом представлении и в представлении – один ряд. Получаем следующие ссылочные ячейки:

Воспользуемся рядом бит служебной информации 14 строки для определения версии и уровня микрокода, а также для получения вида используемой в данном коде маски. Сначала найдем соответствие в таблице ГОСТ, потом сделаем самопроверку.

Объединяем ячейки T16-AH16 в единую. В полученную новую ячейку T16 добавляем функцию (рис. 14):

=СЦЕП(T14:AH14)

По таблице С.1 ГОСТ (табл. 2) находим битовую последовательность информации о формате и соответствующую последовательность бит данных до маскирования. Для данного примера – 10000.

Проверим полученный результат. Заполняем ячейки в соответствии с таблицей:

Воспользуемся алгебраической функцией XOR для получения версии и уровня микрокода, и кода маски. Заполняем ячейки восьмой строчки:

В результате получаем последовательность 10000, полностью соответствующую полученной по таблице ГОСТ. Расшифруем полученную комбинацию. Разделим на две части: 100 и 00 (3 и 2 бита соответственно). Обратимся к таблице 13 ГОСТ (табл. 2).

Таблица 2 – Номер символа для Micro QR Code

Получаем, что в данном микрокоде используется версия М3 и уровень M, т.е. комбинация M3-M. Запомним, на последующих этапах данная информация пригодится.

Разбираем вторую часть служебной информации, комбинацию маски 00. Обратимся к рисунку 22 ГОСТ. Перенесем маску с соответствующим битовым кодом на Лист, начиная с ячейки AL4 (рис. 14).

Аналогично основной матрице, каждая черная ячейка обозначена как 1, а каждая белая – 0.

 Все необходимые данные на основе служебной информации получены, переходим ко 2-му этапу.

 Этап 2. Расшифровка данных основной рабочей области

 На основе матрицы исходных данных в диапазоне ячеек D4:R18 и матрицы маскирования в диапазоне ячеек AL4:AZ18 получаем матрицу немаскированных данных в диапазоне ячеек D22:R36 с использованием функции XOR. Пример готового результата представлен на рисунке 15.

В ячейке M23 добавлена следующая формула:

=БИТ.ИСКЛИЛИ(M5;AU5)

Далее за нижний правый угол выделенной ячейки (магический квадрат) дублируем данную формулу на всю поверхность рабочей матрицы. В результате получаем немаскированный вариант для диапазона ячеек M23:R36 и E31:L36.

Самый простой вариант для подготовки к следующему этапу, перенести полученную немаскированную матрицу в таблицу символов вручную. Но это не так интересно. Подготовим таблицу маршрута и заготовку для заполнения битовых комбинаций с учетом особенностей числового режима.

Перенесем маршрут (рис. 4) на Лист MS Excel, начиная с ячейки AJ20, где каждую ячейку подпишем соответствующим числовым значением. Результат представлен на рисунке 16.

Напомню: не обязательно каждую ячейку прописывать вручную. MS Excel умеет строить прогрессии. Например, заполняем ячейки AZ36 и AZ35 значениями 1 и 3 соответственно. Затем выделяем заполненные ячейки AZ36:AZ35 и за магический квадратик выделенного диапазона (нижний правый угол ячейки) тянем до ячейки AZ23. В результате весь ряд будет заполнен. Остальное рабочее поле можно заполнить аналогичным образом.

Начиная с ячейки R20 в диапазоне ячеек R20:AD32 делаем шаблон-заготовку для последующего наполнения битовой комбинацией в алфавитно-цифровом режиме. Пример полученного результата представлен на рисунке 17 (цветовая дифференциация произвольная). Цветом отделена служебная информация и кодовая комбинация декодируемого числа.

Так как этой информации достаточно для расшифровки сообщения, переходим к третьему этапу.

 Этап 3. Преобразование кода в набор символов

 Пример итогового варианта представлен на рисунке 18.

Как было упомянуто ранее, битовые комбинации в диапазон ячеек T23:AC36 можно перенести вручную (простой вариант). Но можно и автоматизировать. Таблица функций заполнит битовые ячейки автоматически (табл. 3).

В диапазоне ячеек T24:U24 указан код 00 – обозначает наличие числового режима (таблица 2 ГОСТ).

Следующий диапазон из пяти бит в ячейках V24:Z24 – диапазон, отображающий битовую комбинацию – 10010 или число 18 (по количеству искомых в микрокоде цифр). Проверим, автоматизируем процесс перевода последовательности бит из двоичной системы в десятичную:

1.    Объединим ячейки битовых комбинаций в одну AB24:AC24. В полученную ячейку AB24 добавим функцию:

=ДЕС(СЦЕП(V24:Z24);2)

2.    Аналогичным образом получим искомые группы цифр 777, 777, 777, 777, 777 и 777. Добавим функции в ячейки, согласно следующие таблице:

3.    Объединим ячейки в одну T38:AF38. Добавляем функцию сцепления битовых комбинаций:

=СЦЕП(AE26;AE28;AE30;AE32;AE34;AE36)

4.    Объединим ячейки в одну T39:AF39. Переносим аналогичную комбинацию цифр со страницы Code для дальнейшего сравнения:

=Code!B6

5.    Объединим ячейки в одну T40:AF40. В полученную ячейку Т40 добавим условие сравнения предыдущих двух комбинаций. Если совпадают – «ОК!», если не совпадают – не «ОК!»:

=ЕСЛИ(T38=T39;"ОК!";"не ОК!")

6.    На данном этапе можно остановиться, остальное поле занимает код Рида-Соломона. В более сложном алгоритме «Пишем микрокод» будет расшифрован данный этап детально на примере.

 Этап 4. Применение полученного алгоритма для М3 7×23

 Так как заготовлена битовая последовательность для десяти цифр заранее, а основной алгоритм очень схож (необходимо будет поменять только маску и функцию комбинации итогового кода при переводе в десятичный формат), то воспользуемся данным обстоятельством и просто продублируем страницу М3 7×18 на М3 7×23 с учетом замены исходного микрокода.

Копируем диапазон ячеек T4:AZ18 на странице М3 7×18, переходим на страницу М3 7×23. Выбираем ячейку T4, добавляем скопированный фрагмент T4:AZ18 получаем новый анализ служебной информации (рис. 19).

Для М3 7×23 служебная информация не дублирует служебную информацию для М3 7×18. Необходимо использовать другую маску – 11.

Переходим ко второй составляющей – анализ рабочей области микрокода. На странице М3 7×18 выделяем диапазон ячеек B20:AZ40 и переносим на страницу М3 7×23. Вносим редакцию (рис. 20).

Необходимо внести несколько изменений. Сначала дополним таблицу 3 набором ячеек:

Аналогично предыдущему этапу, в диапазоне ячеек T24:U24 указан код 00 – обозначает наличие числового режима (таблица 2 ГОСТ). Следующий диапазон из 4-х бит в ячейках V24:Z24 – диапазон, отображающий битовую комбинацию – 10111 или число 23 (по количеству искомых в микрокоде цифр). Проверка в ячейке AB24:AC24 подтверждает полученное значение.

1.    Далее получим искомые группы цифр для новых комбинаций 777 и 77. Добавим функции в ячейки, согласно следующие таблице:

1.    Объединенную ячейку T38:AF38 переносим в T42:AF42. Изменяем функцию сцепления битовых комбинаций:

=СЦЕП(AE26;AE28;AE30;AE32;AE34;AE36;AE38;AE40)

2.    Объединенную ячейку T39:AF39 переносим в T43:AF43. Переносим аналогичную комбинацию цифр со страницы Code для дальнейшего сравнения:

=Code!B7

3.    Объединенную ячейку T40:AF40 переносим в T44:AF44. В полученной ячейке T44 изменим условие сравнения предыдущих двух комбинаций. Если совпадают – «ОК!», если не совпадают – не «ОК!»:

=ЕСЛИ(T42=T43;"ОК!";"не ОК!")

В результате получаем полное совпадение кодовой составляющей.

 Удачи в декодировании числовых последовательностей Micro QR Code версии M3!!!