Кодирование числа в Micro QR Code версии М1

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

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

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

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

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

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

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

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

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

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

• Лист2 – M1 7;

• Лист3 – M1 77;

• Лист4 – M1 777;

• Лист5 – M1 7777;

• Лист6 – M1 77777.

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

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

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

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

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

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

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

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

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

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

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

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

-     77777 → 1100001001 и 1001101 (2 группы);

-     7777 → 1100001001 и 0111 (2 группы);

-     777 → 1100001001;

-     77 → 1001101;

-     7 → 0111;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=СЦЕП(P14:AD14)

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

Таблица 2 – Корректирующие последовательности информации о формате

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

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

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

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

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

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

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

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

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

 На основе матрицы исходных данных в диапазоне ячеек D4:N14 и матрицы маскирования в диапазоне ячеек AH4:AR14 получаем матрицу немаскированных данных в диапазоне ячеек D18:N28 с использованием функции XOR. Пример готового результата представлен на рисунке 16.

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

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

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

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

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

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

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

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

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

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

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

Таблица 3 – Функциональные ячейки битовых последовательностей

В ячейках T19:V19 указан код 001 – обозначает наличие цифрового режима (таблица 3 ГОСТ), где биты дают число 1 – одна цифра в микрокоде.

Следующий диапазон из 4-х бит в ячейках W19:Z19 – диапазон, отображающий саму цифру – 0111 или число 7. Проверим, автоматизируем процесс перевода из двоичной системы в десятичную и сделаем проверку с корректирующим кодом на листе Code:

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

=СЦЕП(W19:Z19)

2.    В ячейку R19 добавим функцию перевода двоичного кода в десятичное значение:

=ДВ.В.ДЕС(P19)

3.    Объединим ячейки в одну P20:R20. В полученную ячейку P20 добавим функцию поиска и вызова соответствующего значения для десятичного числа (в данном случае – 7) на странице Code:

=ИНДЕКС(Code!$C$3:$C$7;ПОИСКПОЗ($R$19;Code!$B$3:$B$7;0))

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

=ЕСЛИ(P19=P20;"ОК!";"не ОК!")

5.    На данном этапе можно остановиться, но остальное поле занимают коды Рида-Соломона и интересно было бы тоже получить для проверки, правильное ли получили число или нет. Автоматизируем процесс получения кодов в ячейках:

В результате получена комбинация из последовательности чисел: 46, 0, 12, 184, 6.

ВАЖНО: здесь пока не разобрался. Стандартный алгоритм, когда есть полная комбинация из 8-битных значений в данном случае не работает. Одна битовая последовательность неполная, всего 4 бита. Как в данном случае делать проверку – непонятно. Пробовал разные комбинации, пока результат не совпадает с вариантом бесплатных библиотек. В ГОСТ указано, что исходных данных должно быть 3 числа, корректирующих – 2.

 Этап 4. Применение полученного алгоритма для М1 77

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

Копируем диапазон ячеек P5:AD16 на странице М1 7, переходим на страницу М1 77. Выбираем ячейку P5, добавляем скопированный фрагмент P5:AD16 получаем новый анализ служебной информации (рис. 20).

Для М1 77 служебная информация полностью дублирует служебную информацию для М1 7. Следовательно, будем использовать аналогичную маску – 00.

Переходим ко второй составляющей – анализ рабочей области микрокода. Результат представлен на рисунке 21.

Необходимо внести всего одно изменение. В ячейке P19 заменить функцию на:

=СЦЕП(W19:AA19;T21:U21)

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

 Этап 5. Применение полученного алгоритма для М1 777

 Аналогично предыдущему этапу, числовая последовательность для трех цифр заготовлена заранее, и основной алгоритм также схож (необходимо будет поменять только маску и функцию комбинации итогового кода при переводе в десятичный формат), то воспользуемся данным обстоятельством и просто продублируем страницу М1 7 на М1 777 с учетом замены исходного микрокода.

Копируем диапазон ячеек P5:AD16 на странице М1 7, переходим на страницу М1 777. Выбираем ячейку P5, добавляем скопированный фрагмент P5:AD16 получаем новый анализ служебной информации (рис. 22).

Для М1 777 служебная информация не дублирует служебную информацию для М1 7, будет применена новая маска – 01.

Переходим ко второй составляющей – анализ рабочей области микрокода. Результат представлен на рисунке 23.

Необходимо внести несколько изменений. Так как ячейка P19 посредник и значение не столько нужно как итоговое, то пожертвуем расстояние и снимем объединение ячеек P19:Q19. В ячейке P19 необходимо заменить функцию на:

=СЦЕП(W19:AA19;T21:X21)

Объединяем ячейки Q19:R19. В новую ячейку Q19 добавляем функцию:

=ДЕС(P19;2)

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

 Этап 6. Применение полученного алгоритма для М1 7777

 Числовая последовательность для четырех цифр заготовлена заранее, основной алгоритм также схож. Продублируем страницу М1 777 на М1 7777 с учетом замены исходного микрокода.

Копируем диапазон ячеек P5:AD16 на странице М1 777, переходим на страницу М1 7777. Выбираем ячейку P5, добавляем скопированный фрагмент P5:AD16 получаем новый анализ служебной информации (рис. 24).

Для М1 7777 служебная информация не дублирует служебную информацию для М1 777, будет применена новая маска – 11.

Переходим ко второй составляющей – анализ рабочей области микрокода. Результат представлен на рисунке 25.

Необходимо внести несколько изменений. В диапазоне ячеек P19:R19 ничего не изменяем.

Сделаем ячейку P20 так же, как посредника. В ячейку P20 добавляем функцию:

=СЦЕП(Y21:AA21;T23)

Объединяем ячейки Q20:R20. В новую ячейку Q20 добавляем функцию:

=ДЕС(P20;2)

Объединяем ячейки P21:R21. В новую ячейку P21 добавляем функцию:

=СЦЕП(Q19:R20)

В диапазоне ячеек P22:R22 изменяем функцию на:

=ИНДЕКС(Code!$C$3:$C$7;ПОИСКПОЗ(ЗНАЧЕН($P$21);Code!$B$3:$B$7;0))

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

 Этап 7. Применение полученного алгоритма для М1 77777

 Числовая последовательность для пяти цифр заготовлена заранее, основной алгоритм также схож. Продублируем страницу М1 7777 на М1 77777 с учетом замены исходного микрокода.

Копируем диапазон ячеек P5:AD16 на странице М1 7777, переходим на страницу М1 77777. Выбираем ячейку P5, добавляем скопированный фрагмент P5:AD16 получаем новый анализ служебной информации (рис. 26).

Для М1 7777 служебная информация не дублирует служебную информацию для М1 777, будет применена новая маска – 01.

Переходим ко второй составляющей – анализ рабочей области микрокода. Результат представлен на рисунке 27.

Необходимо внести только одно изменение. В ячейку P20 добавляем функцию:

=СЦЕП(Y21:AA21;T23:W23)

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

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