Штрихове кодування є одним з видів автоматичної ідентифікації. За свою понад 60-річну історію розвитку штрихові коди (ШК) пройшли певну еволюцію: лінійні ШК, стекові, матричні, багатоколірні ШК. Протягом останнього десятиліття спостерігається стійка тенденція до розширення сфери застосування багатоколірних ШК, оскільки багатоколірність дозволяє у декілька разів підвищити інформаційну щільність подання даних без зміни геометричних розмірів елементів штрихкодового зображення порівняно з чорно-білими ШК. Однак, як зазначають дослідники, при застосуванні багатоколірних ШК ускладнюються процеси декодування штрихкодових зображень [1-3]. Тому, для надійного зчитування багатоколірних ШК необхідно додатково забезпечувати завадостійкість штрихкодових зображень.
Структурно штрихкодова позначка (ШК-позначка) має форму прямокутника або квадрата та складається з масиву штрихкодових знаків (ШК-знаків), які є мінімальними структурними одиницями зображення. Окремо взятий ШК-знак подає один символ комп’ютерного алфавіту або певну комбінацію символів. В існуючих ШК застосовують однорівневу систему забезпечення завадостійкості ― масив ШК-знаків кодують коректувальним кодом Ріда-Соломона. Для забезпечення належного рівня надійності зчитування даних пропонується додатково застосовувати завадостійке кодування в межах кожного ШК-знака. Для цієї мети доцільно використовувати многозначний (недвійковий) коректувальний код БЧХ (код Боуза-Чоудхурі-Хоквінгема), який здатний виправляти двократні помилки в ШК-знаках.
Нехай ШК-знак складається з s елементів (чарунок), а для розфарбовування елементів використовують q кольорів, q>2. Якщо використовувані кольори позначити цифрами 0, 1, 2, …, q-1, то ШК-знаку поставимо у відповідність цифровий еквівалент ― вектор ШК-знака Z = (z0z1, … zs-1), де zi є {0, 1, 2, …, q-1}. Для того щоб ШК-знак був завадостійким, його вектор Z має бути кодовим словом q-кового коду БЧХ. Тому, необхідно вирішити задачу побудови символіки багатоколірного ШК з можливістю виправлення одно- або двократних помилок у зчитуваних ШК-знаках, а також виявлення помилок (спотворень) більшої кратності. Символікою ШК є набір (множина) ШК-знаків, з допомогою яких формують ШК-позначку.
Код БЧХ є циклічним коректувальним кодом, у якому кодування інформації зводиться до множення многочлена  степеня u-1, який відповідає q-ковому u-розрядному інформаційному слову B = (b 0b 1…b u-1) на твірний (генераторний) многочлен  степеня v:
де  ― многочлен степеня s-1, що відповідає s-розрядному q-ковому слову Z = (z 0z 1…z s-1), який є цифровим еквівалентом ШК-знака: s = u + v: b i, g i, z i ϵ GF(q) [4].
Якщо відомий твірний многочлен g(x), то твірну матрицю G(x, u) (s, u)- коду БЧХ подають у вигляді:
вона має розмірність u x s.
Твірний многочлен g(x) q-кового (s,u)-коду БЧХ з мінімальною кодовою відстанню dmin = 5, здатного виправляти дві помилки, визначають як найменше спільне кратне мінімальних многочленів M(1)(x), M(2)(x), M(3)(x), M(4)(x) елементів α1, α2, α3, α4 поля GF(qm), де αi ― корінь незвідного многочлена M(i)(x), тобто M(i)( αi) = 0:
α є GF(qm), m ― степінь мінімальних многочленів [2].
GF(q) називають полем символів, GF(qm) ― полем локаторів.
Код БЧХ називають повним, якщо s = qm-1.
Деякі q-кові (q>2) повні коди БЧХ з dmin = 5, що придатні для вирішуваної задачі, наведено в табл. 1.
Таблиця 1
Деякі повні q-кові (s,u)-код БЧХ
Нехай q = 5 (випадок п’ятиколірного ШК). Розглянемо, наприклад, п’ятірковий (24,16)-код БЧХ. Для побудови такого коду використовують два поля GF(5) ― поле символів (рис. 1) та поле локаторів (табл. 2), яке є розширенням над GF(5). Побудову GF(52) виконано на основі незвідного многочлена p(x) = x2 + x +2.
Кожному елементу αi поля GF(52), i >= 1 відповідає мінімальний многочлен M(i)(x) (табл. 3).
Рис. 1. Виконання операцій в полі GF(5).
У полі GF(52) αi = αi -24, α-i = α24 – i, α24 = α-24 = α0 = 1.
Таблиця 2
Елементи поля GF(52)
Таблиця 3
Мінімальні многочлени перших чотирьох елементів поля GF(52)
Знайдемо твірний многочлен п’ятіркового (24,16)-коду БЧХ з використанням табл. 3:
g(x) = HCK(M(1)(x), M(2)(x), M(3)(x), M(4)(x)) = HCK(x2 + x + 2, x2 + 3x +4, x2 + 3, x2 + 4x +1) = (x2 + x + 2)( x2 + 3x +4)( x2 + 3)( x2 + 4x +1) = x8 + 3x7 +4x6 + 4x5 + 2x3 + 4x2 + x +4 => g0 g1 ... g8 = 4 1 4 2 0 4 4 3 1.
Твірному многочлену g(x) відповідає твірна матриця G(24,16) (рис. 2).
Рис. 2. Твірна матриця п’ятіркового (24,16)-коду БЧХ
Декодування q-кового (s,u)-коду БЧХ з dmin = 5 здійснюють на основі перевірної матриці, яку подають у вигляді:
де αi ― елементи поля GF(qm), які при формуванні матриці подають у векторному вигляді (наприклад, елементу α3 поля відповідає вектор (24) ― див. табл. 2).
Для побудови завадостійких символік різної потужності багатоколірних ШК потрібні коди БЧХ, довжина кодових слів яких має бути відмінна від qm – 1, тобто необхідні скорочені (неповні) коди. Скороченим називають код утворений шляхом викреслювання потрібної кількості стовпців і рядків у твірній та перевірній матрицях повного коду. Якщо в G(24,16) викреслити, наприклад, 10 стовпців справа (z14 – z23) та 10 нижніх рядків, а в перевірній матриці H(24,16) ― стовпці Z,14 –Z,23 то отримаємо твірну G(14,6) та відповідно перевірну H(14,6) матриці скороченого п’ятіркового (14,6)-коду БЧХ (рис. 3). Добуток матриці G(14, 6) на транспоновану матрицю H(14,6) дорівнює нулю.
Отже, виконуючи скорочення матриць можна отримувати коди БЧХ різної довжини, пристосовуючи їх таким чином до потреб вирішуваної задачі.
На основі твірної матриці G(s,u)-коду БЧХ можна побудувати символіку завадостійкого штрихового коду з можливістю корекції одно- або двократних спотворень елементів (помилок) у ШК-знаках. Для цього u-розрядне інформаційне q-кове слово B = (b0, b1 ... bu-1) необхідно перетворити на s-розрядне слово Z = (z0, z1 ... zs-1), яке є вектором (цифровим еквівалентом) ШК-знака, тобто слово В закодувати (s,u)-кодом БЧХ, а тоді Z поставити у відповідність ШК-знак. Операцію кодування задають рівнянням Z = B • G(s,u) та виконують за правилом поля GF(q).
Нехай B = (2 3 0 4 1 3), тоді Z = (3 4 1 2 4 2 0 2 3 3 3 4 0 3), кодування Z = B • G(14,6) виконано за модулем 5. ШК-знак, що відповідає Z, показано на рис. 5б.
Рис. 3. Скорочення твірної (G) та перевірної (H) матриць п’ятіркового повного (24,16)-коду БЧХ з метою отримання (14, 6)-коду
Рис. 4. Твірна (G) та перевірна (H) матриці п’ятіркового скороченого
(24,6)-коду БЧХ
Рис. 5. Створення п’ятиколірного ШК-знака:
а ― порядок заповнення ШК-знака; б ― розфарбування ШК-знака
Беручи всі можливі значення вектора В – від (000000) до (444444) та застосовуючи до кожного слова процедуру кодування отримаємо 56 = 15625 ШК-знаків, які утворюють символіку Ω завадостійкого п’ятиколірного ШК, в якому в межах кожного ШК-знака можливе виправлення одно- або двократної помилки. Символіці Ω можна поставити у відповідність числову множину
Ω = {0,1, 2, ..., 15624}. Алфавітно-цифрову послідовність, яка підлягає поданню у штрихкодовому вигляді, перетворюють у числову форму, елементами якої є числа з діапазону 0 - 15624, а потім кожному числу ставлять у відповідність ШК-знак з символіки Ω. Далі, ШК-знаки наносять на носій, формуючи ШК-позначку.
Під час зчитування ШК-позначки послідовно виділяють ШК-знаки, кожному з яких ставлять у відповідність цифровий еквівалент ― s-розрядний вектор Z'=(Z'0,Z'0,Z'0, ... , Z's-1 , який декодують за правилами (s,u)-коду БЧХ з dmin = 5.
Нехай на носій було нанесено ШК-знак, вектор якого дорівнював Z = (3 4 1 2 4 2 0 2 3 3 3 4 0 3), а під час зчитування цього знака отримано вектор Z' = (3 4 3 2 4 2 4 2 3 3 3 4 0 3), який містить дві помилки (підкреслені розряди).
Позиціям (розрядам) вектора Z' відповідають степені примітивного елемента поля GF(52), які виконують роль нумератора рядків:
Декодування вектора Z' виконаємо за наступним алгоритмом,
1. Обчислимо синдром помилки S = (S1S2S3S4) як S=Z'·HT (14,6), зокрема
За аналогією S2 = α, S3 = α0, S4 = α17.
2. Сформуємо матрицю  та обчислимо її дискримінант:
Оскільки detM ≠ 0, то слово Z' містить дві помилки.
3. Знайдемо коефіцієнти σ2, σ 2 многочлена локаторів помилок
4. Розв’яжемо рівняння α8x2 + αx + 1 = 0 в полі GF(52) за процедурою Ченя [4]:
Отже, коренями рівняння є x1 = α18, x2 = α22. Тоді локаторами помилок є X1=x1-1= α-18 =α6; X2=x2-1= α-22 =α2. Це означає, що помилки мають місце в розрядах z'6 та z'2 (локатор α2 відповідає розряду z'2, а локатор α6 - розряду z'6.
5. Обчислимо величини Y2, Y1 помилок на основі рівняння
Отже, Y2 = 4, Y1 = 2.
6. Виправимо помилки:
Отже, правильным вектором є
Z = 3 4 1* 2 4 2 0* 2 3 3 3 4 0 3,
де * - виправлені розряди.
Двократну помилку в ШК-знаку виправлено.
На основі многозначних скорочених кодів БЧХ можна створювати символіки завадостійких багатоколірних ШК різної потужності.
На основі розробленого програмного продукту для дослідження коректувальної здатності кодів БЧХ отримано статичні дані, що характеризують можливість многозначних кодів БЧХ виявляти та виправляти багатократні помилки. Досліджено здатність виявляти (3 - 7)-кратні помилки для 18-ти кодів БЧХ ― 8 трійкових, 6-п’ятіркових та 4-сімкових. Наприклад, показано, що трійкові коди БЧХ дозволяють виявити (46,4 - 93,8)% 3-кратних помилок та (34,1 - 92,1)% (4 - 7)-кратних помилок, а п’ятіркові коди БЧХ ― відповідно (70,7 - 96,0)% 3-кратних помилок та (67,9 - 93,8)% (4 - 7)-кратних помилок.
На нижньому рівні забезпечення завадостійкості багатоколірного штрихкодового зображення одно- та двократні помилки виправляються кодом БЧХ в межах кожного ШК-знака, а виявлені помилки, що мають кратність понад два, виправляються кодом Ріда-Соломона. Наслідком застосування двох коректувальних кодів: БЧХ ― на нижньому, та Ріда-Соломона ― на верхньому рівні, для забезпечення завадостійкості багатоколірних штрихкодових зображень є істотне зростання захищеності штрихкодових даних.
1. Parikh D., Jancke G. Localization and Segmentation of a 2D High Capacity Color Barcode // Proc. Of the 2008 IEEE Workshop on Application of Computer Vision (WACV`08). ― 2008. ― P. 1-6. https://doi.org/10.1109/WACW.2008.4544033.
2. Wang F., Manduchi R. Color-constant information embedding // Trends and Topics in Computer Vision. – Springer, 2012. – P. 13-26.
3. Bagherinia H., Manduchi R. High information rate and efficient color barcode decoding // Proc. of the 12th International Conference on Computer Vision. – 2012. – Vol. 2. – P. 482-491. https://doi.org/10.1007/978-3-642-33868-7-48.
4. Blahut R. E. Theory and Practice of Error Control Codes. ― Addіson ― Wesley, 1983. ―576 p.
________________________
Науковий керівник: Сулема Євгенія Станіславівна; доктор технічних наук, доцент, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
|
Голосування 
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter