автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Способы и средства помехоустойчивого штрихового кодирования-декодирования алфавитно-цифровой информации

КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

РГВ

~5 СЕ Г щ

од

На правах рукописи

Али К. Абуд Аль-Амери < Ирак)

УДК 681.3.04

СПОСОБЫ И СРЕДСТВА ПОМЕХОУСТОЙЧИВОГО ШТРИХОВОГО КОДИРОВАНИЯ-ДЕКОДИРОВАНИЯ АЛФАВИТНО-ЦИФРОВОЙ ИНФОРМАЦИИ

Специальность 05.13.05 - Элементы и устройства

вычислительной техники и систем управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Киев - 1994 г.

Работой является рукопись.

Работа выполнена на кафедре специализированных компыогернь систем Киевского политехнического института.

Научный руководитель - кандидат технических наук.

Официальные оппоненты - доктор технических наук,

профессор Муратовекий Ю. П., - кандидат технических наук Селигей A.M.

Ведущая организация - Институт проблем регистрации

Зашита состоится " 1Я " сентября 1994 г. в /т часе на заседании специализированного совета Д 068.14.09 Киевског политехнического института по адресу: 252056, г.Киев, проспек Победы, 37, корп. 18, ауд.306.

Отзывы на автореферат (в двух экземплярах) , заверенные пе чатыо учреждения, просим направлять по адресу: 252056, г.- Киев 56, проспект Победы, 37, КПИ, Ученому секретарю.

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

Автореферат разослан " 11 " о1густа_1994 р.

■ Ученый секретарь _ ■ .

специализированного совета доктор технических наук.

доцент Дичка И. А.

информации НАН Украины.

профессор

О. В. Вузовски

АННОТАЦИЯ

Целью диссертационной работы является обеспечение помехо-стойчивог.о считывания алфавитно-цифровой информации, представ-:енной в виде штриховых кодов. ■

Для достижения указанной цели в диссертации решаются сле-упцие задачи:

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

2. Разработка методики построения многозначного кода Хем-инга , ориентированной на применение в существующих стандартах триховых кодов с целью коррекции ошибок.

3. Разработка способов повышения достоверности считывания триховых изображений с помощью сканера в виде оптического арандаша за счет использования многозначных корректирующих одов.

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

5. Разработка структуры декодера штриховых кодов и алгорит-ов их помехоустойчивого декодирования.

Автор защищает следующие положения и результаты:

- способы обеспечения помехоустойчивого считывания штрихо-ух изображений, основанных на совместном использовании штрихо-ах и корректирукшх кодов;

. - методику построения многозначного кода Хемминга, ориен-ированную на применение в штриховых кодах и обеспечивашую жокую. скорость преобразований в случае ее программной реали-ации;

- алгоритмы помехоустойчивого декодирования штриховых ко-

эв;

- методику построения бинарных штриховых кодов и алгоритмы < декодирования;

- структурную организацию устройства считывания и декоди-эвания штриховых кодов.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Интенсивное развитие средств вычж

лительной техники и их широкое внедрение в народное хозяйст) заставляют по новому рассмотреть некоторые вопросы, связанные процедурой ввода информации в вычислительную систему.

Процедура ввода является наиболее узким местом в автомат! эированных системах обработки информации, где необходимо вводи' в ЭВМ большие объемы информации. Ввод информации'вручную помощью клавиатуры требует больших затрат, поскольку зависит I внимания и сосредоточенности оператора , часто приводит к оши кам. Такая технология ввода информации в ЭВМ является огранни вашим фактором в развитии современных автоматизированных сист обработки информации.

Одним из способов повышения скорости , надежности и эффе тивности ввода информации в ЭВМ является использование штрихов го кодирования вводимой информации. Сущность штрихового кодир вания состоит в том , что данные , подлежащие вводу в ЭВ представляются в виде чередующихся темных (штрихов) и светл (пробелов) полос разной ширины, информацию при этом несут отн ситеяьнда ширины светлых и темных, полос и их сочетания. Штрих вые изображения с помощью специальных недорогих сканируют устройств (оптический карандаш, ПЗС-сканер, лазерный пистоле с большой скоростью вводят в ЭВМ.

Однако в связи с расширением сферы применения штриховс кодирования одной из проблем является обеспечение надлежаще уровня достоверности вводимой информации. Дело в том , I существующие технические средства, несмотря на их относителы простоту , надежно обеспечивают ввод информации только в слу1 нанесения штрихового кода на высококачественную поверхнос:

В связи с этим возникает задача разработки таких. штрихо; кодов, которые обеспечили бы надежный ввод информации в слу1 нанесения штрихового изображения на поверхность обычного ка> ства. Разработка таких помехоустойчивых кодов, а также спосо< и средств их считывания и декодирования , позволила бы , первых, снизить требования к качеству носителя штриховой инФ мации , и во-вторых, значительно расширила бы область примене

трихового кодирования.

Методы исследования. При решении поставленных задач были

спользованы аппарат теории корректирующих кодов, теории вероят-остей, теории конечных полей. Для подтверждения основных теоре-ических результатов применялся эксперимент и моделирование на Вк1.

Научная новизна выполненных исследований заклшается в сле-ущем:

-разработана система числовых показателей, позволяющая оце-ивать штриховые коды и сравнивать их с целью выбора штрихового :ода, наиболее полно удовлетворяющего заданным требованиям;

-предложена методика построения многозначного кода Хемминга, >риентированная на применение в штриховых кодах с целью коррек-т ошибок считывания, отличающаяся высокой скоростью декодирования;

-разработан способ повышения достоверности считывания штри-овых изображений за счет совместного использования штриховых :одов и корректирующих кодов, исправляющих блочные ошибки; '

-разработано семейство бинарных штриховых кодов, ориентиро-¡анных на совместное использование с корректирующими кодами, ¡справляющими блочные ошибки, что обеспечивает высокую помехоус-ойчивость считывания штриховых изображений и позволяет строить |Ысоконадежные устройства считывания и декодирования штриховых адов.

Практическая ценность работы. Использование предложенных

:пособов и средств, а также разработанных программ обеспечивает юстоверное считывание как существующих, так и вновь разрабаты-¡аемых штриховых кодов , что позволяет строить аппаратные деко-[еры штриховых кодов и на их основе - системы автоматической щентификации.

Апробация работы. Основные результаты диссертационной

>аботы докладывались и обсуждались на научно-технических конфе->енциях «Применение вычисли?ельной техники и математических (етодов в научных исследованиях» {Львов, 1992 г.), «Проблемы по-¡троения цифровых сетей интегрального обслуживания» (Киев, .993 г.) , на 1-й Украинской конференции по автоматическому

управлению «Автоматика-94» (Киев, 1994 г.).

Публикации. Результаты выполненных исследований отражены ; 8 публикациях.

Структура и объем работы. Диссертационная работа состоит и;

введения , четырех глав , заключения , списка литературы из 14( наименований и 7 приложений. Работа содержит 200 страниц машино писного текста , включая 77 рисунков и 27 таблиц , приложена включают 120 страниц.

Во введении обоснован выбор темы, ее актуальность, сформу лирована цель исследований, приведено краткое содержание работ] по главам и перечислены основные результаты , выносимые Hi защиту.

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

Во второй главе рассмотрен способ повышения достоверност] считывания штриховых изображений за счет использования в извест ных стандартах штриховых кодов .корректирующих кодов , исправля юших блочные ошибки. - В-частности предложена,методика построени. многозначного кода Хемминга , ориентированная на применение : известных штриховых кодах с целью коррекции ошибок, а также рас смотрены вопросы совместного использования многозначного код; Хемминга с штриховыми кодами EAN и ITF.

В третьей главе предложена методика построения бинарны штриховых кодов и способ обеспечения помехоустойчивости считыва ния штриховых изображений з& счет совместного ■ использовани выбранного бинарного штрихового кода и многозначного код Хемминга.

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

В заключении сформулированы основные результаты диссертации.

В приложениях приведены тексты программ считывания извест-■шх, а также разработанных штриховых кодов.

СОДЕРЖАНИЕ РАБОТУ

Штриховой код (ПК) представляет собой последовательность итрихов и пробелов, образующих изображение прямоугольной формы. Птриховое изображение состоит из знаков , знак - совокупность итрихов и пробелов , несущих закодированную информацию об одном символе отображаемого алфавита. Ширина знака измеряется в модулях, модуль - минимальный по ширине элемент (штрих или пробел), <оторому кратны все элементы изображения ПК.

В первой главе рассмотрены наиболее широко известные ШК--JAN < European Article Numbering - Европейская товарная нумерация), ITF (interllved two of five - код Z из 5 с чередованием), соды 39, 93, 128, Кодабар и др., - способы их построения, считы-зания и декодирования , а также аппаратно-программные средства считывания и обработки информации , представленной в виде ШК. выполнена классификация ШК и их сравнение.

Для сравнения различных ШК введены числовые показатели; F -1Исло информационных символов в алфавите кода; п - длина знака в одулях; к - количество информации , передаваемое одним знаком ПК , k = llog Ft ; ß - информационная плотность знаков ШК 3 = к/п ; и - избыточность знаков ШК, ц= (n-k)/n , - позволяющие женить отдельно взятый ШК, а также выбрать из некоторого множества ШК штриховой код , наиболее полно удовлетворяющий заданным требованиям.

В результате выполненного анализа ШК сделаны следующие вы-

ЗОДЫ:

-недостатком всех существующих ШК является то , что с их томошью можно кодировать только незначительные объемы информации. Следовательно, необходимо разрабатывать новые ШК, которые з течение одного цикла чтения обеспечивали бы автоматический звод в ЭВМ массива информации (в ближайшем будущем хотя бы I Кбайт). Для этого очевидно необходимо перейти от линейной структуры ШК к двумерной;

Z-4-39S8

-другой недостаток состоит в отсутствии достаточно универ сального ШК, который имел бы широкую область применения. Сущест вуюшие ШК, к сожалению , достаточно специализированы. Поэтом предложенные числовые показатели позволяют выбрать из множеств ШК наиболее экономична* код , а также дают . асимптотически границы, в которых следует .вести поиск новых, более универсаль ных ШК; '■

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

Существующие. ШК обладает только обнаруживающей способ ностькх Отсутствие в ШК способности исправлять' возникающие ошуб ки ограничивает сферу применения ЩК. Вследствие этого одной и главных задач при. обработке информации , представленной в вид Ж, является обеспечение высокой достоверности считывания ивфор мации -за счет коррекции ошибок в считываемых словах' информации Разработка ШК , обладающих кроме обнаруживающий свойств способ ностью исправлять ошибки, обеспечила бы расширение "области, при менения Ж , повышение технологичности обработки изделий , дл маркировки которых .применяется ШК, снижение Требований к. качест ву поверхности носителя ИК , создание новых автоматизировании комплексов для автосканировачия Движущихся упаковок маркирован ных с помощью ШК. •

Возможны., два подхода к обеспечению помехоустойчивости ШК.

1. Использование в существующих ШК известных методов коррек ции информации на основе классических корректирующих кодов, на пример , кода Хемминга, БЧХ, Рида-Соломона, кс^д'ов, испра^ляюши ошибки типа «вставка символа» и. «выпадение символами др.

2. Создание принципиал£но -новых ШК, обладающих',как обнаружи вающей, так и корректирующей способностью.

• Первый подход основывается на"том, что примитивные элемент ШК - штрих и пробел минимальной ширины рассматриваются как дво ичные символы 1 и 0, а вся" последовательность знаков ШК, вклк чая ограничительные и разделительные знаки- как двоичное слово

соторое может быть закодировано некоторым помехоустойчивым ко-юм , исправляющим ошибки. • Этот подход обеспечивает придание известным Ж , обладающим свойством только обнаруживать ошибки, корректирующих свойств за счет добавления к словам контрольных символов.

Особенностью второго подхода является то , что структура знаков вновь создаваемых ШК максимально ориентирована на особен-■юсти построения корректирующих кодов, исправляющих ошибки, что ■ значительно упрощает алгоритмы построения ШК, ускоряет их деко-шрование, а также повышает корректирующую способность.

В диссертации реализованы оба указанных подхода.

Во второй главе предложен способ повышения достоверности считывания ШК за счет использования в ШК корректирующих кодов, исправляющих блочные ошибки , в частности за счет использования многозначного кода Хемминга.

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

Разбив двоичное слово, соответствующее штриховому изображению, на т-разрядные (т=2, 3, 4, _____ 8) двоичные слоги, получим

3 = £т-ичное слово а1 аг...ак, где а ем» {0, 1, 2, ...,2т-1>, 1 = 1, ..., к , которое можно закодировать корректирующим кодом, исправляющим q-ичный искаженный символ. В результате получим

кодовое слово а а2 — ак ____ су , где а - информационные

символы , () = 1, ... , V) - контрольные символы , ^ <5 м. Корректирующий код , исправляющий один искаженный а = г^-ичный символ в принятом слове , называют многозначным кодом Хемминга (МКХ). МКХ представляет собой обобщение известного двоичного кода Хемминга на случай произвольного конечного алфавита (Ф>2). Искажение ч-ичного символа в кодовом слове назовем двоичной блочной ошибкой, она представляет собой частный случай двоичной пакетной ошибки.

Проверочная матрица Н q-ичнoгo кода Хемминга в общем случае состоит из V строк и к+у столбцов,' элементы матрицы принадлежат множеству М , а к и V связаны между собой соотношением

k+v s (qv-l)/(cH>. столбцами матрицы H являются q-ичные набор! длины v , содержащие единицу в качестве первой ненулевой компо ненты. При кодировании информации МКХ необходимо выполнять one рации сложения и умножения элементов. пйля GF(2m). Сложение дву: элементов поля GP( Zw) осуществляется как поразрядное сложени< по модулю два ш-разрядных двоичных чисел, соответствующих скла дываемым элементам поля. Умножение двух элементов поля представляет собой умножение многочленов, соответствующих перемножаемы) элементам , по модулю неприводимого многочлена Q степени т.

т

Контрольные символы вычисляют по формулам:

где , 1 = 1, 2, ....V , 1г. - элемент матрицы Н, находящийся на пересечении 1-строки и J~гo столбца , и . « М.

При декодировании (к+у)-разрядного принятого словг а4- ... а^ с^ ... су находят синдром Э = з4 ... по формулам:

Если Б=0, то считают, что ошибки в считанном слове отсутствуют. Иначе (БгО), рассматривая синдром как вектор-столбец, находят по специальному алгоритму величину ошибки и местоположение искаженного символа в декодируемом коде, используя операши сложения, умножения и деления элементов поля Ш 2"). Искаженны; символ восстанавливают , прибавляя к нему по той С) величин;,

Я)

ошибки. В диссертации предложен отличный от известного спосоС декодирования МКХ, отличающийся тем, что для определения величины ошибки и местоположения искаженного символа используют« только операции сложения и умножения. Исключение операции деления, приводит к ускорению процесса декодирования, реализуемое программно и выполняемого в реальном времени,

' Далее предложен способ обеспечения помехоустойчивости считывания и декодирования известных 111К за счет дополнительное кодирования штрихового изображения многозначным корректируюнр кодом, исправляющим блочную ошибку.

к

j -1

к

mod G

m

В качестве примера рассматривается совместное использование ШК ЕАН-13, ЕАН-8 с 16- (т=4) и 256-ичным (т=8) кодом Хемминга. ШК ЕАМ-13 имеет следующую структуру:

^ Ъ.

Ч Ч

ь. ь.

"1 ~г "з ч 5 страна код предприятия

^ ь

Ъ г, Ъ 10 11 12

код товара

контрольный символ

где Ъ (1=1,.. .,13) - десятичные символы. 12 символов (Ъ - Ъ > отображаются в виде знаков ШК, Ъ кодируется неявно и в штриховом изображении отсутствует. Структура штрихового изображения ЕАИ-13 имеет вид (- штриховой знак десятичного символа ^ , К - штриховой знак контрольного символа й ):

В'

знак ограничительного символа

знак разделительного

символа

I

2г 2э V2

□ □□□□□

ч ч ч ч ч ч

Т 1 т т т т

о

3

- знак информационного символа

Ч Ч Чо Ч1 Ч, Чз

Т Т Т I 1 т

'О

символы кодового слова ЕАН-13

Рис.1. Структура ШК ЕАН-13.

Длина знака информационного символа - 7 модулей, разделительного - 3 и ограничительного - 5 модулей. Следовательно, штриховому изображению ЕАИ-13 соответствует 95-битовое двоичное слово. Разбив его на тетрады и дополняя неполную тетраду справа нулем получим 24-разрядное 16-ичное слово, которое кодируем 16-ичным кодом Хемминга. В результате получим 3 16-ичных контрольных символа, которым ставим в соответствие штриховые знаки Ц, I , Ц. Указанные знаки можно расположить несколькими способами, на рис.2 представлено 2 способа расположения.

Структуры ШК, представленные на рис. 2 назовем модифицированным ШК ЕАН-13 (МЕАН-13). Вариант а) полностью сохраняет структуру ЕАН-13; вариант б) минимизирует длину штрихового изображения, в этом случае десятичный символ Х>д предлагается кодировать неявно.

1ю а □ □ □ сшп □ а □ □ сшсюа

ъ г, I, Ь г, й Ъ Ъ Ъ Ь 1 Ъ

1 г 3 4 5 6 7 О 9 10 11 12 1

а)

П2г 2з ц п г9 г19 г1г ц ц п

ъ ъ г. г г ъ ГСП г 1, ъ г

1 г 3 4 5 О 7 ) 8 I 9 10 11 12

0)

Рис.2. Варианты расположения контрольных символов 16-ичного кода Хеммига в ШК ЕАЯ-13.

Например, десятичный товарный код 574010010211 , представленный МЕАЬЫЗ по варианту а) , будет выглядеть следующим образом:

Рис.3. Изображение десятичного слова 574010010211 ШК ЕАМ-13 с 16-ичным МКХ по варианту а). ,

При считывании МЕАН-13 получаем двоичное слово, и, если оно содержит 4-битовую блочную ошибку, то она исправляется 16-ичным кодом Хемминга. Затем скорректированное слово декодируем в соответствии с правилами. ШК ЕАЬЫЗ. Если разбить двоичное слово на 8-разрядные слоги, то используя 256-ичный код Хемминга, можно обеспечить коррекцию байтовой блочной ошибки.

Недостатком предложенного способа придания корректирующих свойств известным штриховым кодам является отсутствие прямого соответствия между контрольными символами МКХ, имеющими двоичную природу (ч=2®), и знаками известных ШК, ориентированных на представление десятичных цифр либо дополнительно на представление символов латинского алфавита. В результате для штрихового представления контрольных символов МКХ приходится использовать знаки

0611201048045

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

Для построения ШК предлагается использовать два элементарных знака (рис.4) , с помощью которых можно.представить любую двоичную последовательность. ШК, для построения которых используются г указанных элементарных знака, названы бинарными штриховыми кодами (БШК). В зависимости от количества (а) двоичных разрядов , . используемых для представления символов , можно получить семейство Ж : при а = 2 можно построить ШК, с помощью которого можно кодировать 4 символа (0, 1, 2, 3 - как и в 4-ичной системе счисления) (QBC - Quadruple Ваг Code - четверичный ШК) ," а при а=3 , 4 и 8 можно получить ШК , с помощью которых можно кодировать 8 (QBC - Octal Ваг Code - 8-ичный ШК) , 16 (НВС - Hexadecimal Bar. Code - 16-ичный Ж) и 256 (ASC1IBC -ASCII Ваг Code - Ж ASCII) символов соответственно.

Рис.4. Изображение символов двоичной системы счисления в вйде штрихов и пробелов.

Знаки ВЖ НЁС показаны в табл. 1.

Длина знаков равна 12 модулей , знаку соответствует его 4-разряяный двоичный эквивалент , знак состоит из 4 штрихов и 4 пробелов. Если отдельно рассматривать состояние штрихов, то оно повторяет двоичное значение символа, а состояние пробелов является инверсией этого значения. Следовательно имеет.место двойное кодирование - прямым* и инверсным 4-разрядными кодами. Такой способ представления символов обеспечивает высокую достоверность считывания, *ак как имеется дополнительная возможность контроля считываемых знаков.

_ 1 о _

Таблица. 1

Таблица знаков штрихового кода НВС'

символ знак символа двоичное зна- состояние состояние номер

чение символа штрихов пробелов символа

0 1 в в в 0 и 0 0 0 о о 0 1 1 1 1 0

1 В в в в 0 0 0 1 0 0 0 1 1 1 1 0 1

2 1 в в в 0 0 1 0 0 0 1 0 1 1 0 1 2

3 Н в в в 0 0 1 1 0 0 1 1 1 1 0 0 3

4 1 в в в 0 1 0 0 0 1 0 0 1 0 1 1 4

5 В т Б га 0 1 0 1 0 1 "0 1 1 0 1 0 5

6 в в ш В 0 1 1 0 0 1 1 0 1 0 0 1 6

7 в в в в 0 1 1 1 0 1 1 1 1 0 0 0 ?

е ш в в в 1 0 0 0 1 0 0 0 0 1 1 1 8

9 ш в в в 1 0 0 1 1 0 0 1 0 1 1 0 9

А Ё ш в 1 0 1 0 1 0 1 0 0 1 0 1 10

В в в цд в 1 0 1 1 1 0 1 1 0 1 0 0 И

С в т в в 1 1 0 0 1 1 0 0 0 0 1 1 12

С о в в в 1 1 0 1 1 1 0 1 0 0 1 0 13

Е О! в в в 1 1 1 0 1 1 1 0 0 0 0 1 14

Р Ш в в в 1 1 1 1 1 1 1 1 0 0 0 0 15

СТАРТ В 0 0 1

СТОП в о - 0 1 0

Например , десятичное значение 574010010211 (85А5А9АА63 после преобразования в 16-ичный вид) , представленное с помощью БШК НВС и 16-ичного кода Хемминга выглядит следующим образом^

85А5А9АА634Р

Рис.5. Штрихкодовое изображение номера 85А5А9АА63. представленное с помощью БШК НВС совместно с 1о-ичным МКХ.

БШК можно использовать самостоятельно, и в этом смысле они не уступают существующим ШК (см. табл.2) , однако их главное предназначение - совместное использование с многозначными корректирующими кодащ.

Таблица. 2

Числовые показатели известных ШК и БШК НВС

ШК Р 11 к А Ц

код 39 43 12 5,42В 0,452 0,547

код 32 32 12 5,000 0,416 0,583

код 93 47 9 5,555 0,617 0,382 -

код 128 103 И 6,687 0,607 0,392

Кодабар 16 9 4,000 0,444 0,555

код 2/5 10 12 3,333 0,277 0,722

код С1Р 10 12 3,333 0,277 0,722

код ИР 10 14 3,333 0,476 0,523

коды 10 7 3,333 0,476 0,523

ЕАН, ЦРС

НВС .16 12 . 4,000 0,333 0,666

В диссертации предложен способ исправления оиибок при считывании штриховых изображений , представленных с помощью БШК за счет использования многозначных корректирующих кодов.

Если необходимо представлять в виде ШК 10-ичную информацию, то алгоритм кодирования может быть следующим--

1.Преобразуем Исходное 10-ичное число в 2а-ичную (например, 16-ичную) систему счисления. Пусть длина 2а-ичного числа равна к.

2.Строим проверочную матрицу 2а-ичного МКХ, обеспечивающую кодирование к-разрядных 2а-ичных чисел.

3. Вычисляем Контрольные разряды в соответствии с правилами 2а-ичного кода.Хемминга.

4. Ставим- в соответствие символам 2а-ичного кодового слова штриховые знаки соответствующего БШК и ограничиваем полученную последовательность знаков символами СТАРТ-СТОП.

Обратное преобразований - получение 2а-ичного числа исходя

из штрихового изображения , - выполняем в соответствии со следующим алгоритмом;

1. Считываем штриховое изображение и находим соответствующее ему г^-ичное число.

2. Декодируем полученное 2а-ичное слово по правилам 2а-ичного кода Кемминга.

3. Если синдром не равен нулю, то исправляем 2а-ичньй искаженный символ принятого слова или формируем сообщение «ошибка», если в-слове искажены два или более символа.

4. Преобразуем скорректированное 2а-ичное число в десятичное.

Совместное использование БШК и многозначных корректирующих кодов обеспечивает более высокую корректирующую способность, чем использование последних с существующими стандартами 111К (табл.3).

Таблица. 3

Сравнение ВПК НВС-12 с ШК EAN-13

Код Количество контрольных знаков длина штрихового изображения, модулей длина двоичного слова, би*г Корректируюшая-способность

EAN-13 1 96 96 обнаружение

НВС-12 1 139 46 обнаружение

EAN-13+MKX 3 117 117 исправление ошибки длиной .4 модуля

НВС-12+МКХ 2 151 50 исправление ошибки длиной 12 модулей

Это вызвано тем, что при преобразовании штрихового изображения в двоичный вид в известных ШК двоичный бит соответствует минимальному элементу шк (штриху или пробелу) длиной 1 модуль, а в БШК бит соответствует элементу длиной 3 модуля (рис.4).

В диссертации разработан обобщенный алгоритм и программа считывания штриховых изображений, распознавания и декодирования известных штриховых, кодов, а также программные средства декодирования помехоустойчивых ШК (ЕАН+МКХ, БШК+МКХ), Кроме того, разработана структура аппаратного декодера ШК и его функциональная

схема в случае реализации с помощью однокристального микроконтроллера К1816ВЕ51.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1.Исследованы и классифицированы штриховые коды , технические средства их считывания и декодирования. Показано, что для повышения достоверности считывания штриховых изображений необходимо совместно с ШК - использовать многозначные корректирующие коды.

2.Разработана методика построения 2т-ичных (т=2, 3, .... 8) кодов Хемминга, отличающаяся простотой лрограммной реализации и высоким быстродействием, ориентированная на применение совместно

с ШК.

3.Разработан способ придания корректирующих свойств известным стандартам ШК за счет их совместного использования с многозначными корректирующими кодами, позволяющий повысить достоверность считывания и декодирования штриховых изображений.

4. Предложена методика построения бинарных штриховых кодов, обеспечивающая создание ШК с заданной размерностью алфавита , их считывания и обработки , отличающаяся простотой реализации и обеспечивающая помехоустойчивое считывание штриховых изображений.

5. Показано , что совместное использование бинарных ШК совместно с многозначными корректирующими кодами обеспечивает более высокую корректирующую способность, чем их совместное использование с известными стандартами ШК.

6. Разработаны эффективные алгоритмы и программы считывания и обработки штриховых кодов , что позволяет строить системы идентификации, реализующие информационную технологию, базирующуюся на применении штриховых кодов.

7. Предложена структура устройства считывания и декодирования штриховых кодов.

Основные результаты диссертации • опубликованы в следующих

работах;

1. Дичка И. А. , Али Кадум Абуд . Ввод информации в ЭВМ с помощью штриховых кодов // Вестн. Киев, политехи, ин-та. Автоматика и электроприборостроение. - 1993. - Вып. 30 .С. 84-91.

2. Дичка И. А. , Али Кадум Абуд . Повышение достоверности считывания штриховых кодов за счет использования обобщенного кода Хемминга // Вестн. Киев, политехи, ин-та. Автоматика и электроприборостроение. - 1993. - Вып. 30 .С. 91-99.

3. Дичка И. А., Али Кадум Абуд . Применение штриховых кодов в области автоматизации и систем управления // 1-а Укра1нська конференШя з автоматичного керування «АВТ0МАТИКА-94» :' Тез. допов. наук. - техн. конф., 18-23 травня 1994р./ - Ки1в, 1994,-С. 231-232.

4. Дичка И. А., Али Кадум Абуд. Совместимость цифровых сетей интегрального обслуживания с сетью БАИГОМ // Проблемы построения цифровых сетей интегрального обслуживания •• Тез. докл. научн. -техн. конф., 20-22 апреля 1992г./ - Киев, 1992,- С. 49-51.

5. Дичка И. А. , Али Кадум Абуд. Управление товародвижением на основе использования штрихового кодирования товаров // Киев, 1994 - 16 с. Деп. в ГНТБ Украины, N 972-Ук 94.

6. Дичка И.А., Али Кадум Абуд . Аппаратно-програмшые средства считывания и декодирования штриховых кодов // Киев, 1994 - 14 с. Деп. в ГНТБ Украины, N 971-Ук 94.

7. Дичка И.А., Али Кадум Абуд . Применение бинарных штриховых кодов для исправления ошибок при считывании штрихкодовых из-ображений//Киев, 1994 - 19 с. Деп. в ГНТБ Украины, N 1211-Ук 94.

8. Дичка И.А., Али Кадум Абуд . Бинарные штриховые коды // Киев, 1994 - 15 с. Деп. в ГНТБ Украины, N 1210-Ук 94.

Али К. Абуд Аль-Амери

Способы и средства помехоустойчивого штрихового кодирования-декодирования алфавитно-цифровой информации.

Работой является рукопись на соискание ученой степени кандидата технических наук по специальности 05.13.05. - Элементы и устройства вычислительной техники и систем управления.

г.Киев, 1994г.

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

исправляющих блочные ошибки, а также предложено семейство бинарных штриховых кодов , обеспечивающих совместно с корректирующими кодами высокую достоверность считывания штриховых изображений. Кроме того разработаны программно-аппаратные средства, обеспечивающие помехоустойчивое считывание и декодирование пггриховых

All К. Aboud Al-Ahmmry

Manners and means for erorr corrected barcoding-decoding of alphabet-numerical data.

This scientific work is a manuscript to submit one's thesis for candidate's scientific degree in technical scienses in speciality 05.13.05. - Elements and units of computer technique and control systems.

The aim of the thesis is to provide an erorr corrected reading of bar code data. For this aim achievement in the thesis a manner have been developed for reading the bar code description, by the conjointly use of the bar and block-erorr correction codes. As far as it have been developed a binary bar code family , which in conjointly with correction codes provides a high reliability bar code description reading. Aside from it have been developed so many programme . which provide an erorr corrected reading and decoding of bar code description.

клшов1 слова:

штриховий код, б1нарний пггриховий код, завадост1йк1сть, коректу-вальний код , многозначний код Хем1нга , пггрихове зображення, кодування-декодування 1нформаи11.

кодов.

ук. № 5 - Cnoci6 друку офсетний. Умовн. друк. ар] Умовн. фарбо-в(Дб. . Обл.-вид. арк.

Тираж 'foО • Зам. М • Безплатно.

Ф1рма «В1ПОЛ» 252151, Ки?в, пул. Волияська, 60.

ч