Задание: необходимо создать кодовое слово (сокращенный вариант собственной фамилии и инициалов) по алгоритму А.С. Пушкина. Затем создать для полученного сокращения Micro QR Code вер. М2. Данный режим невозможно прочитать стандартными ресурсами мобильных устройств, производимых GAFAM (как оказалось, свободно распространяемые библиотеки просто страшно глючат, поэтому Ассоциация отказалась и от этого режима).
Этап 0. Алгоритм А.С. Пушкина
Согласно классическому методу шифрования Александра Сергеевича, необходимо предложения разбить на ключевые фразы, перевести на французский язык (в данном случае на английский), выделить определяющие слоги, удалить незвучные буквы и на каждом пропуске ключевую букву сделать заглавной. Данный алгоритм успешно используется для сокращения быстрых сообщений и в чатах, и в мессенджерах, и в социальных сетях и т.д.
Немного упростим и применим данный алгоритм:
исходный текст (Фамилия И.О.) – Рыженко А.А.;
преобразуем в английский вариант – Ryzhenko A.A.;
убираем лишние символы и пробелы – RyzhenkoAA;
сокращаем до 6 символов (ограничение М2) – RznkAA;
и переводим в верхний регистр (еще одно ограничение М2) – RZNKAA.
Этап 1. Кодирование исходных данных
Рассмотрим М2 поближе. Имеем матрицу размерностью 13х13 бинарных символов, один индикатор и два определителя (горизонтальный и вертикальный) (рис. 1).
Примечание: здесь и далее будем использовать один из доступных программных инструментов Ассоциации – MS Excel (русскоязычная версия). Как следствие, все команды автоматизации процессов будут на кириллице.
Примечание: здесь и далее будет использоваться информация ГОСТ Р ИСО/МЭК 18004-2015 или в оригинале ISO/IEC 18004:2015 (далее – ГОСТ).
Первый наносимый ограничитель символ на матрицу М2 – надлежащие битовые последовательности информации о формате (рис. 2). Чтение битовой последовательности начинается с 14 бита, т.е. последовательность чтения/записи будет 14, 13, 12, 11, 10 и т.д.
Примечание: этап заполнения надлежащей битовой последовательности информации о формате кодовой битовой комбинацией в представленном алгоритме будет пятым, после определения маски.
Второй не менее важный элемент М2 – маршрут последовательности заполнения битами данных поля матрицы (рис. 3). Данная схема отражена на рисунке 11 ГОСТ.
Если наложить маршрут на матрицу, получаем последовательность из 80 бит кода М2 (рис. 4). Число 80 пригодится чуть позже при работе с кодами Рида-Соломона.
Переходим к реализации первого этапа – получение кодовой комбинации исходного текста. В системе QR Code существует несколько разновидностей кодирования: числовой, алфавитно-цифровой, байтовый, кандзи, структурированное соединение и FNC1. Самые простые – числовой (число определенной длины из цифр 0..9) и алфавитно-цифровой (табл. 1).
Таблица 1 – Кодирование/декодирование для алфавитно-цифрового режима (Таблица 5 ГОСТ)
Знак | Значение | Знак | Значение | Знак | Значение | Знак | Значение | Знак | Значение | Знак | Значение | Знак | Значение | Знак | Значение |
0 | 0 | 6 | 6 | С | 12 | I | 18 | О | 24 | U | 30 | SP | 36 | . | 42 |
1 | 1 | 7 | 7 | D | 13 | J | 19 | Р | 25 | V | 31 | $ | 37 | / | 43 |
2 | 2 | 8 | 8 | Е | 14 | К | 20 | Q | 26 | W | 32 | % | 38 | : | 44 |
3 | 3 | 9 | 9 | F | 15 | L | 21 | R | 27 | X | 33 | * | 39 |
|
|
4 | 4 | А | 10 | G | 16 | М | 22 | S | 28 | Y | 34 | + | 40 |
|
|
5 | 5 | В | 11 | Н | 17 | N | 23 | Т | 29 | Z | 35 | - | 41 |
|
|
В данной таблице есть одна особенность – используется исключительно латиница верхнего регистра, т.е. большие буквы. И именно эта особенность пригодится для дальнейшего кодирования. В таблице маркером отмечены используемые в исходном сообщении буквы алфавита RZNKAA.
Примечание: каждый из методов имеет ряд собственных особенностей. Не получится использовать предложенный ниже алгоритм для чисел или для байтовых последовательностей.
Используем алфавитно-цифровую систему кодирования для выполнения требований задания. Следующее ограничение – необходимо кодировать ровно 6 символов. М2 поддерживает два уровня исправления ошибок – L и M. Обращаемся к таблице 7 ГОСТ, получаем, что только уровень L поддерживает емкость 6 символов (табл. 2, емкость данных для алфавитно-цифрового режима). Выбор уровня исправления ошибок L будет отражен позже на пятом этапе в надлежащей битовой последовательности информации о формате (рис. 2).
Таблица 2 – Число знаков символа и емкость входных данных для QR Code (Таблица 7 ГОСТ)
Версия | Уровень исправления ошибок | Число кодовых слов данных | Число битов для данных | Емкость данных для разных режимов | |||
Цифровой | Алфавитно-цифровой | Байтовый | Кандзи | ||||
М1 | Только обнаружение ошибок | 3 | 20 | 5 | - | - | - |
М2 | L | 5 | 40 | 10 | 6 | - | - |
М | 4 | 32 | 8 | 5 | - | - | |
М3 | L | 11 | 84 | 23 | 14 | 9 | 6 |
М | 9 | 68 | 18 | 11 | 7 | 4 | |
М4 | L | 16 | 128 | 35 | 21 | 15 | 9 |
М | 14 | 112 | 30 | 18 | 13 | 8 | |
Q | 10 | 80 | 21 | 13 | 9 | 5 | |
Далее воспользуемся алгоритмом, представленном в ГОСТ (п. 7.4.4). Разбиваем кодовое слово на слоги по две буквы. Получаем следующие комбинации – RZ, NK и AA. Создадим в MS Excel новый пустой Лист. Пример готового результата представлен на рисунке 5.
Для автоматизации первого этапа сначала переносим таблицу символов (табл. 1), начиная с ячейки (2, 2). Резервируем восьмую строчку, начиная с ячейки (8, 3) для исходных данных. В ячейку (8,12) заносим число 45 – множитель кода первой буквы кодового слога. В десятой строке ячейки заполнены парами ссылок на слоги исходного слова. Например, в ячейке (10, 3) – =R[-2]C, а в ячейке (10, 10) – =R[-2]C[-2] (рис. 6).
В одиннадцатой строчке происходит автоматический поиск кода символа в последовательности символов. Например, в ячейке (11, 3):
=ИНДЕКС(R[-6]C[-1]:R[-6]C[43];ПОИСКПОЗ(R[-1]C;R[-7]C[-1]:R[-7]C[43];0))
где
R[-6]C[-1]:R[-6]C[43] – порядковый номер символа (строка 5 на рис. 5);
R[-1]C – искомый в последовательности символ (в данном случае в ячейке (10, 3));
R[-7]C[-1]:R[-7]C[43] – последовательность символов для поиска (строка 4 на рис. 5).
Заполним ниже таблицу 11 строки со ссылками на соответствующие ячейки:
(11, 3) | =ИНДЕКС(R[-6]C[-1]:R[-6]C[43];ПОИСКПОЗ(R[-1]C;R[-7]C[-1]:R[-7]C[43];0)) |
(11, 4) | =ИНДЕКС(R[-6]C[-2]:R[-6]C[42];ПОИСКПОЗ(R[-1]C;R[-7]C[-2]:R[-7]C[42];0)) |
(11, 6) | =ИНДЕКС(R[-6]C[-4]:R[-6]C[40];ПОИСКПОЗ(R[-1]C;R[-7]C[-4]:R[-7]C[40];0)) |
(11, 7) | =ИНДЕКС(R[-6]C[-5]:R[-6]C[39];ПОИСКПОЗ(R[-1]C;R[-7]C[-5]:R[-7]C[39];0)) |
(11, 9) | =ИНДЕКС(R[-6]C[-7]:R[-6]C[37];ПОИСКПОЗ(R[-1]C;R[-7]C[-7]:R[-7]C[37];0)) |
(11, 10) | =ИНДЕКС(R[-6]C[-8]:R[-6]C[36];ПОИСКПОЗ(R[-1]C;R[-7]C[-8]:R[-7]C[36];0)) |
В строке 13 объединяем ячейки (13, 3) и (13, 4). Также объединяем ячейки (13, 6) и (13, 7), и (13, 9) и (13, 10). В ячейку (13, 3) прописываем:
=R[-2]C*R[-5]C[9]+R[-2]C[1]
где
R[-2]C – ячейка с числом 27 (рис. 5);
R[-5]C[9] – ячейка с числом 45 (рис. 5);
R[-2]C[1] – ячейка с числом 35 (рис. 5);
В результате в ячейке должно появиться число 1250. Аналогичные ссылки на вторую и третью пары букв добавляем в ячейки (13, 6) и (13, 9):
=R[-2]C*R[-5]C[6]+R[-2]C[1]
=R[-2]C*R[-5]C[3]+R[-2]C[1]
Следующий этап – необходимо перевести полученные десятичные числа 1250, 1055 и 460 в двоичное представление. В 15 строке объединяем ячейки с 3 по 9. Аналогично объединяем ячейки в 17 и 19 строках (рис. 5).
В ячейку (15, 3) добавляем:
=ОСНОВАНИЕ(R[-2]C;2;11)
В ячейку (17, 3) добавляем:
=ОСНОВАНИЕ(R[-4]C[3];2;11)
В ячейку (19, 3) добавляем:
=ОСНОВАНИЕ(R[-6]C[6];2;11)
Далее необходимо объединить все три полученные бинарные кодовые последовательности в одну. В 21 строке объединяем ячейки с 3 по 20. В ячейку (21, 3) добавляем:
=R[-6]C&R[-4]C&R[-2]C
Полученная кодовая комбинация (рис. 5):
100111000101000001111100111001100
К полученной кодовой комбинации необходимо добавить служебную информацию: индикатор алфавитно-цифрового режима для вер. М2 и число знаков (в данном случае 6 знаков – RZNKAA). Воспользуемся таблицами 2 и 3 ГОСТ. В таблице индикаторов режима (табл. 3) определяем, что индикатор алфавитно-цифрового режима для вер. М2 – 1. В таблице числа битов в индикаторе числа знаков (табл. 4) определяем, что выделяется три бита на описание числа знаков, т.е. число 6 будет представлено как 110.
Таблица 3 – Индикаторы режима для QR Code (Таблица 2 ГОСТ)
Режим | Символы QR Code | Символы Micro QR Code | |||
версия | любой версии | М1 | М2 | М3 | M4 |
Длина индикатора режима, биты | 4 | 0 | 1 | 2 | 3 |
ECI | 0111 | n/a | n/a | n/a | n/a |
Числовой | 0001 | n/a | 0 | 00 | 000 |
Алфавитно-цифровой | 0010 | n/a | 1 | 01 | 001 |
Байтовый | 0100 | n/a | n/a | 10 | 010 |
Кандзи | 1000 | n/a | n/a | 11 | 011 |
Структурированное соединение | 0011 | n/a | n/a | n/a | n/a |
FNC1 | 0101 (1-я позиция) | n/a | n/a | n/a | n/a |
1001 (2-я позиция) | |||||
Ограничитель (конец сообщения) | 0000 | 000 | 00000 | 0000000 | 000000000 |
Таблица 4 – Число битов в индикаторе числа знаков для QR Code (Таблица 3 ГОСТ)
Версия | Числовой режим | Алфавитно-цифровой режим | Байтовый режим | Режим кандзи |
M1 | 3 | n/a | n/a | n/a |
М2 | 4 | 3 | n/a | n/a |
М3 | 5 | 4 | 4 | 3 |
M4 | 6 | 5 | 5 | 4 |
1-9 | 10 | 9 | 8 | 8 |
10-26 | 12 | 11 | 16 | 10 |
27-40 | 14 | 13 | 16 | 12 |
Для проверки воспользуемся функцией (рис. 7). В ячейку (10, 33) добавляем функцию:
=ДЕС.В.ДВ(RC[-1];3)
Объединяем служебную информацию и исходный код в единую последовательность:
1 110 100111000101000001111100111001100
Объединяем ячейки (12, 21) – (12, 40). В полученную ячейку (12, 21) добавляем код:
=R[-3]C[11]&R[-2]C[12]&R[9]C[-18]
Результат формирования текущей битовой последовательности представлен на рисунке 8.
Для дальнейшей работы с кодами Рида-Соломона (2 этап) необходимо сделать полученную последовательность по количеству символов кратной 8, добавить биты ограничители. В текущей битовой последовательности в ячейке (12, 21) ровно 37 символов. Для кратности 8 добавляем три бита ограничителя – 000 (рис. 10):
1110100111000101000001111100111001100 000
В строке 18 объединены ячейки с 21 по 40. В полученную ячейку (18, 21) добавлен следующий код:
=R[-6]C&R[-4]C[5]
В результате итоговая последовательность в ячейке (18, 21) представлена как:
1110100111000101000001111100111001100000
Проверяем по таблице 2 (ГОСТ Таблица 7) насколько получилась правильная комбинация. Напротив строки M2-L в столбце «Число кодовых слов данных» указано число 5, т.е. должно получиться 5 частей по 8 бит – 11101001 11000101 00000111 11001110 01100000. Следовательно, полученная последовательность полностью соответствует требованиям ГОСТ.
Для разделения итоговой битовой комбинации на пять 8-битных последовательностей воспользуемся командой =ПСТР(ссылка на ячейку; позиция первого символа; количество бит). Получаем следующие комбинации (рис. 10):
Диапазон ячеек | Значение |
(20, 24)-(20, 29) | =ПСТР(R[-2]C[-3];1;8) |
(21, 24)-(21, 29) | =ПСТР(R[-3]C[-3];9;8) |
(22, 24)-(22, 29) | =ПСТР(R[-4]C[-3];17;8) |
(23, 24)-(23, 29) | =ПСТР(R[-5]C[-3];25;8) |
(24, 24)-(24, 29) | =ПСТР(R[-6]C[-3];33;8) |
Для визуализации полученного результата перенесем полученную битовую комбинацию в шаблон Micro QR Code вер. М2 (рис. 9).
Для перехода ко 2 этапу необходимо перевести полученные 8-битовые комбинации в десятичный вид. Воспользуемся командой =ДВ.В.ДЕС(ссылка на ячейку), получаем последовательность чисел (рис. 10):
233, 197, 7, 206, 96
Диапазон ячеек | Значение |
(20, 30)-(20, 31) | =ДВ.В.ДЕС(RC[-6]) |
(21, 30)-(21, 31) | =ДВ.В.ДЕС(RC[-6]) |
(22, 30)-(22, 31) | =ДВ.В.ДЕС(RC[-6]) |
(23, 30)-(23, 31) | =ДВ.В.ДЕС(RC[-6]) |
(24, 30)-(24, 31) | =ДВ.В.ДЕС(RC[-6]) |
Итак, итоговая комбинация: 233, 197, 7, 206, 96. Можно переходить ко 2 этапу.
Этап 2. Генерация кодовых слов исправления ошибок
Для генерации кодовых слов исправления ошибок необходимо использовать алгоритм Рида-Соломона на поле Галуа GF(28).
Примечание: для самых любопытных, если интересно посмотреть с точки зрения алгебры множеств то, что будет описываться дальше на примере в таблице MS Excel, можно посмотреть/изучить достаточно хороший материал на Хабр:
[2] Кодирование Рида-Соломона для чайников
[3] Арифметика полей Галуа для кодирования информации кодами Рида-Соломона
В данном материале математику изучать не будет, но будем применять во всей красоте магии чисел.
Создаем новый Лист в Книге MS Excel. Забегая вперед, демонстрация результата (рис. 11).
Для деления полиномов будем использовать поле Галуа GF(28) и обратное поле Галуа GF(28) – обязательное требование при работе с QR Code в ГОСТ. Можно просто переписать большую таблицу значений в ячейки, но предполагалась автоматизация. Следовательно, воспользуемся простыми функциями для создания полей.
Поле Галуа GF(28) представляет фиксированный набор из 256 чисел в диапазоне от 0 до 255. Сначала зададим простой ряд натуральных чисел от 0 до 255 в строке 2. В ячейке (2, 2) – 0, в (2, 3) – 1, в (2, 4) – 2 и т.д. до ячейки (2, 257) – 255. Заполняем третью строку. Первая часть идет с простыми значениями:
Ячейка | Значение |
(3, 2) | 1 |
(3, 3) | 2 |
(3, 4) | =RC[-1]*2 |
(3, 5) | =RC[-1]*2 |
(3, 6) | =RC[-1]*2 |
(3, 7) | =RC[-1]*2 |
(3, 8) | =RC[-1]*2 |
(3, 9) | =RC[-1]*2 |
На этом простая часть закончилась, дальше чуть посложнее. Начиная с ячейки (3, 10) необходимо во все последующие ячейки до (3, 257) добавить следующую функцию:
=ЕСЛИ(2*RC[-1]>254;БИТ.ИСКЛИЛИ(2*RC[-1];285);RC[-1]*2)
где добавлено условие: если значение из предыдущей ячейки умноженное на 2 превышает 254, то необходимо выполнить XOR с числом 285. Почему именно 285 описано в статьях по ссылкам выше. Если число меньше 254, то просто оставляем в текущей ячейке умноженное на 2 полученное значение.
Для контроля полученного результата можно воспользоваться рисунком 11.
Обратное поле Галуа GF(28) аналогично представляет фиксированный набор из 256 чисел в диапазоне от 0 до 255. Сначала зададим простой ряд натуральных чисел от 0 до 255 в шестой строке. В ячейке (6, 2) – 0, в (6, 3) – 1, в (6, 4) – 2 и т.д. до ячейки (6, 257) – 255. Заполняем седьмую строку. В ячейке (7, 2) – ставим прочерк. Данного значения не существует. Ячейки (7, 3) – (7, 257) заполняем функцией:
=ИНДЕКС(R2C2:R2C257;ПОИСКПОЗ(R[-1]C;R3C2:R3C257;0))
где производится поиск по индексу шестой строки соответствующего значения в поле Галуа GF(28). Для контроля полученного результата также можно воспользоваться рисунком 11. В результате оба поля должны быть созданы в полном объеме.
Переходим к основному действию – деление полиномов. Сначала необходимо определить уровень корректирующего полинома. На первом этапе получили максимальное количество бит на поле М2 (рис. 4) – 80 бит. Далее определили последовательность бит исходных данных со служебной информацией (рис. 10) – 5 значений по 8 бит (итого – 40). Следовательно, корректирующий код исправления ошибок также должен состоять из 40 бит (80-40=40 бит) или 5 чисел по 8 бит. И здесь начинаются странности с ГОСТ.
Примечание: не ищите в ГОСТ алгоритма определения необходимого количества бит корректирующего кода исправления ошибок. В оригинале ISO тоже нет. Единственный индикатор добавлен в таблицу 9 ГОСТ, столбик «Число кодовых слов исправления ошибок».
Примечание: все необходимые коэффициенты полиномов можно найти в форме степеней в приложении А ГОСТ, таблица А.1. Но в ГОСТ не представлен механизм применения полиномов. Общее описание алгоритма, т.е. то, что должно получиться, приведено в п. 7.5.2. ГОСТ.
Обращаемся к таблице А.1 ГОСТ. Полином 5 уровня имеет коэффициенты 113, 164, 166, 119, 10.
Все необходимые исходные данные для деления полиномов готовы, переходим к практической составляющей.
Примечание: разные комбинации (длина битовой комбинации исходных данных больше длины битовой комбинации корректирующего полинома или длина битовой комбинации исходных данных меньше длины битовой комбинации корректирующего полинома) имеют разные алгоритмы реализации. Далее будет описан алгоритм, когда длины совпадают.
Возвращаемся к битовой комбинации исходных данных (рис. 10). И переносим в ячейки текущего Листа Книги MS Excel (рис. 11):
Ячейка | Значение |
(13, 24) | 233 |
(13, 25) | 197 |
(13, 26) | 7 |
(13, 27) | 206 |
(13, 28) | 96 |
Заполняем 15 строку значениями (коэффициентами) корректирующего полинома (рис. 11):
Ячейка | Значение |
(15, 24) | 113 |
(15, 25) | 164 |
(15, 26) | 166 |
(15, 27) | 119 |
(15, 28) | 10 |
Каждый этап деления будет состоять из 4 последовательных шагов. Каждый шаг будет описан отдельно. Переходим на 16 строку. Ячейка (16, 23):
=ИНДЕКС(R7C2:R7C257;ПОИСКПОЗ(R[-3]C[1];R6C2:R6C257;0))
где ищем значение первого числа исходного кода (233) в обратном поле Галуа GF(28). Получаем результат – 245.
В ячейки (16, 24)-(16, 28) прописываем следующую функцию:
=ОСТАТ(R[-1]C+R16C23;255)
В результате получаем ряд чисел:
103, 154, 156, 109, 0
Переходим к 17 строке. Ячейки (17, 23)-(17, 28) заполняем следующей функцией:
=ИНДЕКС(R3C2:R3C257;ПОИСКПОЗ(R[-1]C;R2C2:R2C257;0))
В результате получаем ряд чисел:
233, 136, 57, 228, 189, 1
Переходим к 18 строке. Ячейки (18, 23)-(18, 28) заполняем следующей функцией:
=R[-5]C[1]
В результате получаем ряд чисел:
233, 197, 7, 206, 96, 0
Переходим к 19 строке. Ячейки (19, 23)-(19, 28) заполняем следующей функцией:
=БИТ.ИСКЛИЛИ(R[-2]C;R[-1]C)
В результате получаем ряд чисел:
0, 77, 62, 42, 221, 1
Первый этап деления выполнен. Все 4 шага описаны. Всего количество этапов будет 5 – по количеству значений исходного кода.
Переходим на 20 строку. Ячейка (20, 23):
=ИНДЕКС(R7C2:R7C257;ПОИСКПОЗ(R[-1]C[1];R6C2:R6C257;0))
где ищем значение первого числа переходного кода (77) в обратном поле Галуа GF(28). Получаем результат – 145.
В ячейки (20, 24)-(20, 28) прописываем следующую функцию:
=ОСТАТ(R15C+R20C23;255)
В результате получаем ряд чисел:
3, 54, 56, 9, 155
Переходим к 21 строке. Ячейки (21, 23)-(21, 28) заполняем следующей функцией:
=ИНДЕКС(R3C2:R3C257;ПОИСКПОЗ(R[-1]C;R2C2:R2C257;0))
В результате получаем ряд чисел:
77, 8, 80, 93, 58, 114
Переходим к 22 строке. Ячейки (22, 23)-(22, 28) заполняем следующей функцией:
=R[-3]C[1]
В результате получаем ряд чисел:
77, 62, 42, 221, 1, 0
Переходим к 23 строке. Ячейки (23, 23)-(23, 28) заполняем следующей функцией:
=БИТ.ИСКЛИЛИ(R[-2]C;R[-1]C)
В результате получаем ряд чисел:
0, 54, 122, 128, 59, 114
Второй этап деления выполнен.
Переходим на 24 строку. Ячейка (24, 23):
=ИНДЕКС(R7C2:R7C257;ПОИСКПОЗ(R[-1]C[1];R6C2:R6C257;0))
где ищем значение первого числа переходного кода (54) в обратном поле Галуа GF(28). Получаем результат – 249.
В ячейки (24, 24)-(24, 28) прописываем следующую функцию:
=ОСТАТ(R15C+RC23;255)
В результате получаем ряд чисел:
107, 158, 160, 113, 4
Переходим к 25 строке. Ячейки (25, 23)-(25, 28) заполняем следующей функцией:
=ИНДЕКС(R3C2:R3C257;ПОИСКПОЗ(R[-1]C;R2C2:R2C257;0))
В результате получаем ряд чисел:
54, 104, 183, 230, 31, 16
Переходим к 26 строке. Ячейки (26, 23)-(26, 28) заполняем следующей функцией:
=R[-3]C[1]
В результате получаем ряд чисел:
54, 122, 128, 59, 114, 0
Переходим к 27 строке. Ячейки (27, 23)-(27, 28) заполняем следующей функцией:
=БИТ.ИСКЛИЛИ(R[-2]C;R[-1]C)
В результате получаем ряд чисел:
0, 18, 55, 221, 109, 16
Третий этап деления выполнен.
Переходим на 28 строку. Ячейка (28, 23):
=ИНДЕКС(R7C2:R7C257;ПОИСКПОЗ(R[-1]C[1];R6C2:R6C257;0))
где ищем значение первого числа переходного кода (18) в обратном поле Галуа GF(28). Получаем результат – 224.
В ячейки (28, 24)-(28, 28) прописываем следующую функцию:
=ОСТАТ(R15C+RC23;255)
В результате получаем ряд чисел:
82, 133, 135, 88, 234
Переходим к 29 строке. Ячейки (29, 23)-(29, 28) заполняем следующей функцией:
=ИНДЕКС(R3C2:R3C257;ПОИСКПОЗ(R[-1]C;R2C2:R2C257;0))
В результате получаем ряд чисел:
18, 211, 109, 169, 254, 251
Переходим к 30 строке. Ячейки (30, 23)-(30, 28) заполняем следующей функцией:
=R[-3]C[1]
В результате получаем ряд чисел:
18, 55, 221, 109, 16, 0
Переходим к 31 строке. Ячейки (31, 23)-(31, 28) заполняем следующей функцией:
=БИТ.ИСКЛИЛИ(R[-2]C;R[-1]C)
В результате получаем ряд чисел:
0, 228, 176, 196, 238, 251
Четвертый этап деления выполнен.
Переходим на 32 строку. Ячейка (32, 23):
=ИНДЕКС(R7C2:R7C257;ПОИСКПОЗ(R[-1]C[1];R6C2:R6C257;0))
где ищем значение первого числа переходного кода (228) в обратном поле Галуа GF(28). Получаем результат – 156.
В ячейки (32, 24)-(32, 28) прописываем следующую функцию:
=ОСТАТ(R15C+RC23;255)
В результате получаем ряд чисел:
14, 65, 67, 20, 166
Переходим к 33 строке. Ячейки (33, 23)-(33, 28) заполняем следующей функцией:
=ИНДЕКС(R3C2:R3C257;ПОИСКПОЗ(R[-1]C;R2C2:R2C257;0))
В результате получаем ряд чисел:
228, 19, 190, 194, 180, 63
Переходим к 34 строке. Ячейки (34, 23)-(34, 28) заполняем следующей функцией:
=R[-3]C[1]
В результате получаем ряд чисел:
228, 176, 196, 238, 251, 0
Переходим к 35 строке. Ячейки (35, 23)-(35, 28) заполняем следующей функцией:
=БИТ.ИСКЛИЛИ(R[-2]C;R[-1]C)
В результате получаем ряд чисел:
0, 163, 122, 44, 79, 63
Заключительный пятый этап деления выполнен.
Итак, вторая часть битовой комбинации кода получена. Далее необходимо первую и вторую часть перевести в двоичную комбинацию и получить итоговую битовую последовательность.
Переносим две исходные последовательности в столбики в ячейки:
Ячейка | Значение | Ячейка | Значение |
(17, 5)-(17, 6) | 233 | (17, 14)-(17, 15) | 163 |
(18, 5)-(18, 6) | 197 | (18, 14)-(18, 15) | 122 |
(19, 5)-(19, 6) | 7 | (19, 14)-(19, 15) | 44 |
(20, 5)-(20, 6) | 206 | (20, 14)-(20, 15) | 79 |
(21, 5)-(21, 6) | 96 | (21, 14)-(21, 15) | 63 |
Получаем два столбика двоичных последовательностей (рис. 11):
Ячейка | Значение | Ячейка | Значение |
(17, 8)-(17, 11) | =ДЕС.В.ДВ(RC[-3];8) | (17, 17)-(17, 20) | =ДЕС.В.ДВ(RC[-3];8) |
(18, 8)-(18, 11) | =ДЕС.В.ДВ(RC[-3];8) | (18, 17)-(18, 20) | =ДЕС.В.ДВ(RC[-3];8) |
(19, 8)-(19, 11) | =ДЕС.В.ДВ(RC[-3];8) | (19, 17)-(19, 20) | =ДЕС.В.ДВ(RC[-3];8) |
(20, 8)-(20, 11) | =ДЕС.В.ДВ(RC[-3];8) | (20, 17)-(20, 20) | =ДЕС.В.ДВ(RC[-3];8) |
(21, 8)-(21, 11) | =ДЕС.В.ДВ(RC[-3];8) | (21, 17)-(21, 20) | =ДЕС.В.ДВ(RC[-3];8) |
В 23 строке объединяем ячейки (23, 5)-(23, 11) и (23, 14)-(23, 20). В ячейку (23, 5) добавляем функцию:
=R[-6]C[3]&R[-5]C[3]&R[-4]C[3]&R[-3]C[3]&R[-2]C[3]
И в ячейку (23, 14) добавляем функцию:
=R[-6]C[3]&R[-5]C[3]&R[-4]C[3]&R[-3]C[3]&R[-2]C[3]
В 25 строке объединяем ячейки (25, 5)-(25, 20). В ячейку (25, 5) добавляем функцию:
=R[-2]C&R[-2]C[9]
Пример итогового варианта представлен на рисунке 12.
Этап 3. Размещение модулей в матрице символа
Шаблон поиска и шаблоны синхронизации размещают в пустой матрице 13×13, а модули в позиции для информации о формате временно оставляют пустыми. Кодовые слова, полученные на этапах 1 и 2 (табл. 5), размещают в матрице в соответствии с п. 7.7.3 ГОСТ, в результате получают символ, приведенный на рис. 13.
Таблица 5 – Кодовые слова
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
Этап 4. Выбор шаблона маски данных
Для выбора наиболее удачного варианта применяются шаблоны маски данных согласно п. 7.8.2 ГОСТ по очереди и оценивают результаты по п. 7.8.3 ГОСТ. Рассмотрим последовательно описанный в пунктах ГОСТ процесс для данного примера. Создаем новый Лист в Книге MS Excel.
На рисунке 22 ГОСТ представлены маски для Micro QR Code, вычисляемые по формулам таблицы 10 ГОСТ (табл. 6).
Таблица 6 – Условия генерации шаблона маски данных
Указатель шаблона маски данных для символов QR Code | Указатель шаблона маски данных для символов Micro QR Code | Условие |
000 |
| (i + j) mod 2 = 0 |
001 | 00 | i mod 2 = 0 |
010 |
| j mod 3 = 0 |
011 |
| (i + j) mod 3 = 0 |
100 | 01 | ((i div 2) + (j div 3)) mod 2 = 0 |
101 |
| (ij) mod 2 + (ij) mod 3 = 0 |
110 | 10 | ((ij) mod 2 + (ij) mod 3) mod 2 = 0 |
111 | 11 | ((i + j) mod 2 + (i + j) mod 3) mod 2 = 0 |
Можно процесс наполнения масок бинарными данными автоматизировать, но в данной постановке решено пропустить этап и заполнить маски вручную. Для любопытных, подсказка, как можно автоматизировать (рис. 14).
Переносим указанные в табл. 6 маски на новый Лист MS Excel (рис. 15).
Примечание: MS Excel не умеет работать с цветами ячеек. Для дальнейшей автоматизации во всех ячейках масок белые биты подписаны нулями (0), черные – единицами (1).
Бинарную матрицу предыдущего этапа (рис. 13) также переводим в бинарный вид (рис. 16).
Имеются 4 маски и исходник по полученным данным. Позиции верхних левых углов:
маска 00 – ячейка (4, 4);
маска 01 – ячейка (4, 20);
маска 10 – ячейка (20, 4);
маска 11 – ячейка (20, 20);
исходные данные – ячейка (4, 36).
Добавляем четыре заготовки для будущих маскированных вариантов (рис. 17). Позиции верхних левых углов заготовок (4, 52), (4, 68), (20, 52) и (20, 68).
Пример полученного результата представлен на рисунке 18.
В ячейку (5, 61) добавляем следующую функцию:
=БИТ.ИСКЛИЛИ(RC[-48];RC[-16])
Если все сделано корректно, то в ячейке должна появиться цифра один (1). Дальше за нижний правый угол выделенной ячейки (магический квадрат MS Excel) заполняем все остальные ячейки матрицы (00).
В ячейку (5, 77) добавляем следующую функцию:
=БИТ.ИСКЛИЛИ(RC[-48];RC[-32])
Если все сделано корректно, то в ячейке должна появиться цифра один (1). Дальше за нижний правый угол выделенной ячейки (магический квадрат MS Excel) заполняем все остальные ячейки матрицы (01).
В ячейку (21, 61) добавляем следующую функцию:
=БИТ.ИСКЛИЛИ(RC[-48];R[-16]C[-16])
Если все сделано корректно, то в ячейке должна появиться цифра один (1). Дальше за нижний правый угол выделенной ячейки (магический квадрат MS Excel) заполняем все остальные ячейки матрицы (10).
В ячейку (21, 77) добавляем следующую функцию:
=БИТ.ИСКЛИЛИ(RC[-48];R[-16]C[-32])
Если все сделано корректно, то в ячейке должна появиться цифра один (0). Дальше за нижний правый угол выделенной ячейки (магический квадрат MS Excel) заполняем все остальные ячейки матрицы (11).
Пример результата маскирования представлен на рисунке 19.
Следующий этап – оценка символов Micro QR Code (п. 7.8.3.2. ГОСТ). После выполнения операции маскирования данных в области кодирования символа с каждым шаблоном маски данных оценивают результат, подсчитывая множество темных модулей в каждой из двух границ, которые не содержат шаблоны синхронизации. Чем меньше число темных модулей, тем менее приемлемым является результат. В таких символах рекомендуется иметь больше темных модулей на границе, чтобы более эффективно отличать свободную зону от области кодирования.
Для каждого шаблона маски данных подсчитывают число темных модулей в правой и нижней границах символа (исключая последний модуль шаблона синхронизации). Оценку результата подсчета производят следующим образом:
если SUM1 <= SUM2;
то оценка = SUM1 x 16 + SUM2;
если SUM1 > SUM2;
то оценка = SUM1 + SUM2 x 16;
где SUM1 – число темных модулей на правой границе;
SUM2 – число темных модулей на нижней границе.
Реализуем данную схему на Листе. Пример полученного результата представлен на рисунке 21.
Заполняем ячейки определения количества единиц (1) в правом столбике и нижней строчки каждой матрицы:
Ячейка | Функция |
(4, 87) | =СЧЁТЕСЛИ(R[1]C[-23]:R[12]C[-23];1) |
(4, 88) | =СЧЁТЕСЛИ(R[12]C[-35]:R[12]C[-24];1) |
(5, 87) | =СЧЁТЕСЛИ(RC[-7]:R[11]C[-7];1) |
(5, 88) | =СЧЁТЕСЛИ(R[11]C[-19]:R[11]C[-8];1) |
(6, 87) | =СЧЁТЕСЛИ(R[15]C[-23]:R[26]C[-23];1) |
(6, 88) | =СЧЁТЕСЛИ(R[26]C[-35]:R[26]C[-24];1) |
(7, 87) | =СЧЁТЕСЛИ(R[14]C[-7]:R[25]C[-7];1) |
(7, 88) | =СЧЁТЕСЛИ(R[25]C[-19]:R[25]C[-8];1) |
Заполняем ячейки определения критерия оценки для каждой матрицы:
Ячейка | Функция |
(4, 89)-(4, 90) | =ЕСЛИ(RC[-1]<RC[-2];RC[-1]*16+RC[-2];RC[-2]*16+RC[-1]) |
(5, 89)-(5, 90) | =ЕСЛИ(RC[-1]<RC[-2];RC[-1]*16+RC[-2];RC[-2]*16+RC[-1]) |
(6, 89)-(6, 90) | =ЕСЛИ(RC[-1]<RC[-2];RC[-1]*16+RC[-2];RC[-2]*16+RC[-1]) |
(7, 89)-(7, 90) | =ЕСЛИ(RC[-1]<RC[-2];RC[-1]*16+RC[-2];RC[-2]*16+RC[-1]) |
Выбирают шаблон маски, имеющий наибольший результат. Находим максимум из полученных вариантов. В ячейку (8,89)-(8,90) добавляем функцию:
=МАКС(R[-4]C:R[-1]C[1])
Проверяем полученный результат с примером на рисунке 21. В результате должно получиться число 88. Т.е. для данного символа рекомендуется использовать шаблон маски данных с обозначением 11 (табл. 10). Применяем выбранный шаблон маски данных к области кодирования в матрице согласно п. 7.8 ГОСТ.
Этап 5. Подготовка информации о формате
В качестве исходных данных используются два показателя:
для символа версии M2-L номер равен 1, что в двоичном виде данных – 001 по таблице 13 ГОСТ (табл. 7);
полученный на 4 этапе шаблон маски – 11.
Таблица 7 – Номер символа для Micro QR Code
Номер символа | Версия | Уровень исправления ошибок | Двоичный индикатор |
0 | М1 | Только обнаружение | 000 |
1 | М2 | L | 001 |
2 | М2 | М | 010 |
3 | М3 | L | 011 |
4 | М3 | М | 100 |
5 | М4 | L | 101 |
6 | М4 | М | 110 |
7 | М4 | Q | 111 |
В результате получают биты данных в информации о формате 001 11:
00111
По таблице С.1 ГОСТ (табл. 8) находим соответствующую битовые последовательности информации о формате. Для данного примера – 101101011110111.
Hidden text
Таблица 8 – Надлежащие битовые последовательности информации о формате
Последовательность до маскирования | Последовательность после маскирования (символы Micro QR Code) | ||
Биты данных | Биты исправления ошибок | Двоичная | Шестнадцатеричная |
00000 | 0000000000 | 100010001000101 | 4445 |
00001 | 0100110111 | 100000101110010 | 4172 |
00010 | 1001101110 | 100111000101011 | 4Е2В |
00011 | 1101011001 | 100101100011100 | 4В1С |
00100 | 0111101011 | 101010110101110 | 55АЕ |
00101 | 0011011100 | 101000010011001 | 5099 |
00110 | 1110000101 | 101111111000000 | 5FC0 |
00111 | 1010110010 | 101101011110111 | 5AF7 |
01000 | 1111010110 | 110011110010011 | 6793 |
01001 | 1011100001 | 110001010100100 | 62А4 |
01010 | 0110111000 | 110110111111101 | 6DFD |
01011 | 0010001111 | 110100011001010 | 68СА |
01100 | 1000111101 | 111011001111000 | 7678 |
01101 | 1100001010 | 111001101001111 | 734F |
01110 | 0001010011 | 111110000010110 | 7С16 |
01111 | 0101100100 | 111100100100001 | 7921 |
10000 | 1010011011 | 000011011011110 | 06DE |
10001 | 1110101100 | 000001111101001 | 03Е9 |
10010 | 0011110101 | 000110010110000 | 0CB0 |
10011 | 0111000010 | 000100110000111 | 0987 |
10100 | 1101110000 | 001011100110101 | 1735 |
10101 | 1001000111 | 001001000000010 | 1202 |
10110 | 0100011110 | 001110101011011 | 1D5B |
10111 | 0000101001 | 001100001101100 | 186С |
11000 | 0101001101 | 010010100001000 | 2508 |
11001 | 0001111010 | 010000000111111 | 203F |
11010 | 1100100011 | 010111101100110 | 2F66 |
11011 | 1000010100 | 010101001010001 | 2А51 |
11100 | 0010100110 | 011010011100011 | 34E3 |
11101 | 0110010001 | 011000111010100 | 31D4 |
11110 | 1011001000 | 011111010001101 | 3E8D |
11111 | 1111111111 | 011101110111010 | ЗВВА |
Этап 6. Заключительное формирование символа
Добавляют модули информации о формате в позиции, зарезервированные на этапе 3, с 14 бита по 0 бит (рис. 22):
14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
В результате получаем завершенный символ, приведенный на рис. 23.
Можно проверить полученный результат на любом онлайн сканере в сети Интернет. Выделяем в MS Excel полученный код и копируем через буфер обмена в MS Word как рисунок. В MS Word сохраняем полученный рисунок как внешний графический файл в формате .png. Загружаем произвольный онлайн сканер (например) и проверяем полученный Micro QR Code.