Synthesis of the symbologies of multicolor interference-resistant bar codes on the base of multi-valued BCH codes

Abstract

EN: Context. The problem of constructing a set of barcode patterns for multicolor barcodes that are resistant to distortions of one or two elements within each pattern is considered. Objective. The goal of the work is ensuring the reliability of the reading of multi-color barcode images. Method. A multicolor barcode pattern has the property of interference immunity if its digital equivalent (vector) is a codeword of a multi-valued (non-binary) correcting code capable to correct errors (distortions of the pattern elements). It is shown that the construction of barcode patterns should be performed on the basis of a multi-valued correcting BCH code capable to correct two errors. A method is proposed for constructing a set of interference-resistant barcode patterns of a given capacity, which ensure reliable reproduction of data when they are read from a carrier. A procedure for encoding data with a multi-valued BCH code based on the generator matrix of the code using operations by the modulo of a prime number has been developed. A new method of constructing the check matrix of the multivalued BCH code based on the vector representation of the elements of the finite field is proposed. A generalized algorithm for generating symbologies of a multi-color barcode with the possibility of correcting double errors in barcode patterns has been developed. The method also makes it possible to build symbology of a given capacity based on shortened BCH codes. A method of reducing the generator and check matrices of a multi-valued full BCH code to obtain a shortened code of a given length is proposed. It is shown that, in addition to correction double errors, multi-valued BCH codes also make it possible to detect errors of higher multiplicity – this property is enhanced when using shortened BCH codes. The method provides for the construction of a family of multicolor noise-immune barcodes. Results. On the basis of the developed software tools, statistical data were obtained that characterize the ability of multi-valued BCH codes to detect and correct errors, and on their basis to design multi-color interference-resistant bar codes. Conclusions. The conducted experiments have confirmed the operability of the proposed algorithmic tools and allow to recommend it for use in practice for developing interference-resistant multi-color barcodes in automatic identification systems. UK: Актуальність. Розглянуто задачу побудови набору (символіки) штрихкодових знаків для багатоколірних штрихових кодів, стійких до ушкодження одного або двох елементів у межах кожного знака. Мета. Забезпечення надійності зчитування багатоколірних штрихкодових зображень. Метод. Багатоколірний штрихкодовий знак має властивість завадостійкості, якщо його цифровий еквівалент (вектор) є кодовим словом многозначного (недвійкового) коректувального коду, здатного виправляти помилки (спотворення елементів знака). Показано, що побудову штрихкодових знаків слід виконувати на основі многозначного коректувального коду БЧХ, здатного виправляти дві помилки. Запропоновано метод побудови множини завадостійких штрихкодових знаків заданої потужності, які забезпечують достовірне відтворення даних при їх зчитуванні з носія. Розроблено процедуру кодування даних многозначним кодом БЧХ на основі твірної матриці коду з використанням операцій за модулем простого числа. Запропоновано новий спосіб побудови перевірної матриці многозначного коду БЧХ на основі векторного подання елементів скінченного поля. Розроблено узагальнений алгоритм генерування символіки багатоколірного штрихового коду з можливістю корекції двократних помилок у штрихкодових знаках. Метод також дозволяє будувати символіки заданої потужності на основі скорочених кодів БЧХ. Запропоновано спосіб скорочення твірної та перевірної матриць многозначного повного коду БЧХ для отримання скороченого коду заданої довжини. Показано, що крім виправлення двократних помилок, многозначні коди БЧХ дозволяють також виявляти помилки більшої кратності; ця властивість посилюється при використанні скорочених кодів БЧХ. Метод забезпечує побудову сімейства багатоколірних завадостійких штрихових кодів. Результати. На основі розробленого програмного забезпечення отримані статистичні дані, що характеризують здатність многозначних кодів БХЧ виявляти та виправляти помилки, і на їх основі проєктувати багатоколірні завадостійкі штрихові коди. Висновки. Проведені експерименти підтвердили працездатність розробленого алгоритмічного забезпечення і дозволяють рекомендувати його для використання на практиці при проєктуванні завадостійких багатоколірних штрихових кодів у системах автоматичної ідентифікації.