„Київський політехнічний інститут”

Дичка Іван Андрійович

УДК 681.3

МЕТОДИ І ЗАСОБИ ДЛЯ РЕАЛІЗАЦІЇ ЗБЕРІГАННЯ, ОБРОБКИ

ТА ВВОДУ ГРАФІЧНОКОДОВАНОЇ ІНФОРМАЦІЇ

Спеціальність 05.13.13 – Обчислювальні машини, системи та мережі

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

Київ – 2004

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” Міністерства освіти і науки України.

Науковий консультант- доктор технічних наук, професор

Тарасенко Володимир Петрович,

Національний технічний університет України “Київський політехнічний інститут”, завідувач кафедри спеціалізованих комп’ютерних систем.

Офіційні опоненти: доктор технічних наук, заслужений винахідник України

Боюн Віталій Петрович,

Інститут кібернетики ім. В.М.Глушкова НАН України, завідувач відділу керуючих машин і систем,

доктор технічних наук, професор

Бузовський Олег Володимирович,

Національний технічний університет України “Київський

політехнічний інститут”, професор кафедри обчислювальної техніки,

доктор технічних наук, старший науковий співробітник

Мохор Володимир Володимирович,

Інститут проблем моделювання в енергетиці НАН України, завідувач відділу спеціалізованих засобів моделювання.

Провідна установа: Інститут проблем реєстрації інформації НАН України,

відділ спеціалізованих засобів моделювання.

Захист відбудеться “_17_”___травня___2004 р. о _14:00_годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України “Київський політехнічний інститут”, м. Київ, проспект Перемоги, 37, корп. 18, ауд. 306.

Відзиви на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 03056, м. Київ, проспект Перемоги, 37, вченому секретарю НТУУ “КПІ”.

З дисертацією можна ознайомитись у бібліотеці Національного технічного університету України “Київський політехнічний інститут”, м. Київ, проспект Перемоги, 37.

Автореферат розісланий “_15_”_квітня__2004 р.

Вчений секретар

спеціалізованої вченої ради Орлова М.М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА роботи

Актуальність теми. Одним із напрямів підвищення швидкості, надійності та ефективності вводу інформації в ЕОМ є графічне кодування інформації.

Графічне кодування – це спосіб подання та зберігання інформації із застосуванням дискретних графічних форм. Особливої уваги заслуговує графічне кодування, що використовує прості (елементарні) графічні форми: круг, квадрат, прямокутник, штрих (прямий, косий (з нахилом вліво-вправо), многокутник (наприклад, шести-, восьмикутник) тощо. Метою графічного кодування є автоматичне введення в обчислювальну систему великих обсягів інформації із застосуванням нескладних та недорогих технічних засобів.

Графічне кодування передбачає оптичний спосіб зчитування інформації, у тому числі й на відстані.

Графічнокодована інформація конструктивно та візуально подається у вигляді графічного коду. Графічний код (ГК) – це одно- або двомірний масив дискретних різнокольорових графічних елементів, оформлених як єдине ціле. Конструктивне оформлення такого масиву називатимемо графічнокодовою позначкою (ГК-позначкою).

У ГК інформація подається комбінаціями (поєднанням) елементів з різним забарвленням.

Якщо елементарними графічними формами є прямокутник або штрих, а кількість кольорів, використовуваних для їх забарвлення, – два (зазвичай чорний та білий), то такі графічні коди називають штриховими кодами. Штриховий код є окремим випадком графічного коду.

Аналіз відомих графічних кодів, зокрема штрихових, як засобу зберігання інформації з метою автоматичного введення даних в обчислювальну систему свідчить про те, що в графічнокодованому вигляді зберігаються невеликі обсяги інформації. У переважній більшості випадків інформація, що зберігається у вигляді ГК, є лише ключем доступу до більш повної інформації про об’єкт, яка зберігається (у файлі або базі даних) окремо від об’єкта, а внаслідок використання лише двох кольорів – як правило, чорного та білого – існуючі ГК мають низьку інформаційну щільність, що не дозволяє на заданій площі носія зберігати необхідні обсяги інформації.

При створенні сучасних обчислювальних систем реального часу до ГК як засобу зберігання та вводу інформації пред’являються вимоги: 1) мініатюризації ГК-позначок (для нанесення ГК-позначки на об’єкт обліку, управління виділяється обмежена площа); 2) іс-тотного зростання ємності ГК-позначок без зміни їх геометричних розмірів; 3) надання ГК-позначці рис бази даних (ГК-позначка має містити повну інформацію про об’єкт обліку, управління, а не ключ доступу до інформації); 4) обробка ГК-позначок має здійснюватися з високою швидкістю та надійністю в реальному часі.

Невиконання цих вимог створює труднощі в організації систем збору та обробки графічнокодованої інформації в реальному часі та перешкоджає подальшому розвитку графічного кодування.

Подолання зазначених труднощів, що виникли в даній ситуації, засобами наявних знань, накопичених у галузі графічного кодування як технології зберігання і вводу інформації, є неможливим.

Таким чином, існує важлива науково-технічна проблема організації надійного зберігання на обмеженій площі носія великих обсягів інформації, поданої у графічнокодованому вигляді, та її обробки в реальному часі з метою автоматичного вводу в обчислювальну систему.

Теоретичне підгрунтя виконаних у роботі досліджень було закладене в працях українських вчених, які займалися питаннями нетрадиційного подання, кодування та обробки інформації Березюка М.Т., Боюна В.П., Брюховича Є.І., Бузовського О.В., Додонова О.Г., Євдокимова В.Ф., Забари С.С., Кузьміна І.В., Луцького Г.М., Петрова В.В., Романкевича О.М., Самофалова К.Г., Сінькова М.В., Широчина В.П., вчених країн СНД Крайзмера Л.П., Арманда В.А., Желєзнова В.В., Пузанкова Д.В., Хетагурова Я.А. та країн далекого зарубіжжя Берлекемпа Е., Пітерсона У., Блейхута Р., Селлерса Ф., Касамі Т., Уелдона Е.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках плану наукових досліджень, що провадяться кафедрою спеціалізованих комп’ютерних систем Національного технічного університету України “Київський політехнічний інститут” за госпдоговірними темами:

- НДР “Дослідження шляхів підвищення ефективності введення інформації на основі кольорових лінійних штрихових кодів” (номер державної реєстрації 0103U003930), замовник – Державне науково-виробниче підприємство “Електронмаш”, м. Київ;

- НДР “Дослідження шляхів ефективного застосування високощільних штрихових кодів у поштовій підгалузі” (номер державної реєстрації 0103U003931), замовник – Українське державне підприємство поштового зв’язку “Укрпошта”, м. Київ;

- НДР “Розробка теоретичних основ багатокольорових матричних штрихових кодів та дослідження шляхів їх ефективного застосування на машинобудівному підприємстві” (номер державної реєстрації 0104U000585), замовник – Державна акціонерна

холдингова компанія “Артем”, м. Київ.

У зазначених науково-дослідних роботах автор – науковий керівник робіт.

Мета і задачі дослідження. Метою роботи є підвищення щільності та завадостійкості зберігання великих обсягів графічнокодованої інформації, ефективності її обробки та вводу.

Мета досягається за рахунок зберігання інформації у вигляді багатокольорових графічних кодів (БГК), що забезпечує зростання інформаційної щільності зберігання даних, і, як наслідок, продуктивності вводу.

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

Для досягнення поставленої мети необхідно вирішити такі задачі:

- з’ясувати ступінь впливу багатокольоровості ГК на інформаційну щільність зберігання даних;

- розробити методи зберігання інформації на основі багатокольорових лінійних, стекових та матричних графічних кодів;

- розробити методи ущільнення інформації при її зберіганні у вигляді БГК;

- розробити методи та засоби забезпечення надійного зберігання та вводу інформації, поданої у вигляді БГК;

- створити апаратне та програмне забезпечення процесів обробки БГК у реальному часі;

- розробити архітектури спеціалізованих і проблемно-орієнтованих процесорів та обчислювальних систем для обробки БГК у реальному часі.

Об’єктом дослідження є процеси перетворення, зберігання, обробки та вводу інформації, поданої у графічнокодованому вигляді, які породжують проблему підвищення щільності та надійності зберігання на обмеженій площі носія великих обсягів графічнокодованої інформації, її ефективної обробки та вводу.

Предметом дослідження є методи та засоби, які забезпечують організацію перетворення, зберігання, обробки та вводу інформації, поданої у вигляді БГК.

Методи дослідження. Для створення теоретичних основ зберігання та обробки інформації на основі БГК використовуються положення теорії інформації і кодування, комбінаторики, теорії множин. Розробка методів ущільнення інформації при її зберіганні у вигляді БГК ґрунтується на застосуванні теорії чисел та теорії інформації. Забезпечення надійного зберігання, обробки та введення інформації, поданої у вигляді БГК, базується на використанні теорії скінченних полів, теорії ймовірностей, завадостійкого кодування та теорії надійності. Розробка засобів обробки БГК ґрунтується на застосуванні теорії алгоритмів, операційних пристроїв, методів схемо- та системотехніки.

Наукова новизна одержаних результатів. У дисертації дістала розвиток теорія графічного кодування внаслідок її поширення на випадок многозначного алфавіту (багатокольоровості графічного коду).

У рамках цього одержано такі наукові результати:

1. Вперше виконано теоретичне обґрунтування доцільності зберігання та обробки інформації, поданої у вигляді багатокольорових лінійних, стекових та матричних ГК, що порівняно з відомими чорно-білими ГК дозволяє завдяки істотному зростанню інформаційної щільності даних (у 2 – 10 разів) на обмеженій площі носія подавати у графічнокодованому вигляді великі обсяги інформації та створювати високопродуктивні системи автоматичного вводу інформації.

2. Розроблено математичні моделі для аналізу впливу багатокольоровості на інформаційну щільність зберігання даних у графічнокодованому вигляді, які дозволяють кількісно оцінювати ступінь зростання інформаційної щільності БГК від числа використовуваних кольорів та здійснювати за заданими параметрами вибір методу побудови ГК з найкращим за заданих умов показником інформаційної щільності.

3. Розроблено метод побудови символік БГК, графічнокодові знаки (ГК-знаки) яких мають властивість завадостійкості, що забезпечує під час обробки ГК-позначок можливість правильного відтворення інформації у випадку ушкоджень графічнокодових елементів (ГК-елементів). Метод ґрунтується на тому, що вектор ГК-знака є кодовим словом многозначного коректувального коду, який здатний виправляти помилки.

4. Розроблено метод підвищення надійності зберігання інформації у вигляді матричного БГК великої ємності, який ґрунтується на спільному застосуванні дворівневої системи завадостійкості та розсіювання сусідніх ГК-знаків у межах ГК-позначки, що забезпечує надійне зчитування та відтворення інформації навіть в умовах, коли кількість ушкоджених ГК-знаків перевищує коректувальну здатність коректувального коду. Перший (нижній) рівень завдостійкості – рівень ГК-знаків, коли ГК-знаки символіки наділені властивістю виправляти 1- або 2-кратні спотворення ГК-елементів; другий (верхній) рівень – рівень ГК-позначки, коли для послідовності ГК-знаків застосовується многозначний коректувальний код, здатний виправляти багатократні спотворення (помилки і стирання).

5. Запропоновано організацію та апаратну реалізацію обчислень в полях Галуа, що дозволяє зводити складні обчислення до операцій над цілими числами без знаку малої розрядності і за рахунок цього будувати для обробки БГК спеціалізовані процесори малої розрядності зі спрощеною архітектурою і системою команд та високою продуктивністю.

6. Запропоновано методологію побудови спеціалізованих та проблемно-орієнтованих обчислювальних систем реального часу для обробки БГК, що порівняно з універсальними обчислювальними засобами забезпечує більш високу продуктивність та ефективність обробки.

Практичне значення одержаних результатів:

- запропоновано систему показників, які дозволяють кількісно оцінювати ГК, виконувати їх порівняння та здійснювати вибір ГК, який найбільш повно відповідає заданим параметрам;

- виконано класифікацію ГК та способів зберігання інформації у графічнокодованому вигляді, що дозволяє здійснювати пошук нових ГК з покращеними характеристиками порівняно з відомими кодами;

- розроблено способи та методики побудови символік БГК, які дозволяють користувачеві за заданими параметрами проектувати власні графічні коди з метою захисту інформації;

- створено програмні засоби, які дозволяють вивчати властивості БГК, створювати нові коди, здійснювати вибір найбільш оптимального методу побудови ГК з метою зберігання інформації залежно від вхідних параметрів;

- розроблено способи побудови символік БГК з можливістю виправлення помилок у ГК-знаках, а також алгоритми декодування та структури апаратних декодерів, які забезпечують на практиці зберігання інформації з підвищеними показниками надійності;

- розроблено алгоритмічне забезпечення процесу обробки матричних БГК, яке дозволяє створювати високоефективні програмні засоби з обробки та декодування ГК-позначок;

- запропоновано структури операційних пристроїв для реалізації операцій в полях Галуа, які дозволяють будувати високопродуктивні спеціалізовані та проблемно-орієнтовані процесори для обробки БГК.

Теоретичні і практичні результати дисертаційної роботи використані та впроваджені:

- на Державному науково-виробничому підприємстві “Електронмаш”, м. Київ, у системі автоматизованого вводу інформації, поданої у графічнокодованому вигляді;

- на Українському підприємстві поштового зв’язку “Укрпошта”, м. Київ, у системі формування графічнокодованих щоденних звітів від касових апаратів;

- у Державній акціонерній холдинговій компанії “Артем”, м. Київ, у системі контролю документообігу та перепускній системі;

- у ТОВ “Боедем”, м. Київ, при виготовленні високощільних ГК-позначок лінійних ГК;

- у навчальному процесі кафедри СКС НТУУ “КПІ”, зокрема під час дипломного проектування,

що підтверджено відповідними актами про впровадження.

Особистий внесок здобувача. У наукових працях, опублікованих у співавторстві, здобувачеві належать: [12, 34, 35] – ідеї запровадження числових показників для оцінювання лінійних, стекових, матричних ГК з метою їх порівняння та вибору оптимального ГК за заданими параметрами; [13, 15, 16, 19, 25, 32, 33] – ідеї побудови завадостійких ГК-знаків багатокольорових лінійних, стекових, матричних ГК, наділених здатністю виправляти асиметричні та незалежні помилки; [14, 21] – алгоритмічне забезпечення процесу обробки ГК-позначок; [17, 20, 44] – ідеї числового перетворення текстової інформації, що підлягає зберіганню у графічнокодованому вигляді, для підвищення інформаційної щільності зберігання даних; [18, 45] – ідеї побудови неструктурованих лінійних ГК; [22, 23, 39, 40] – ідеї підвищення ефективності систем управління за рахунок графічнокодованого подання інформації; [24, 26-28, 42] – ідеї зберігання інформації у вигляді високощільних двомірних ГК; [29, 30, 36, 37] – ідеї забезпечення завадостійкості ГК-позначок багатокольорових двомірних ГК за рахунок застосування коректувального коду Ріда-Соломона з виправленням як помилок, так і стирань; [31] – ідея підвищення завадостійкості ГК-позначок багатокольорових матричних ГК за рахунок спільного застосування коректувального коду, здатного виправляти багатократні спотворення, та розсіювання сусідніх ГК-знаків у межах ГК-позначки.

Апробація результатів дисертації. Результати досліджень, що включені до дисертації, оприлюднено на: Науково-технічному семінарі “Передача та обробка даних в системах керування та мережах ЕОМ” (Київ, 1989); Першій українській конференції з автоматичного керування “Автоматика-94” (Київ, 1994); Науково-практичній конференції “Наукоємні технології подвійного призначення” (Київ, 1994); Третій українській конференції з автоматичного керування “Автоматика-96” (Севастополь, 1996); Міжнародній конференції “Комп’ютерні системи і технології” – КомпСисТех’2000 (Болгарія, Софія, 2000); Міжнародній науково-практичній конференції “Проблеми впровадження інформаційних технологій в економіці та бізнесі” (Ірпінь, 2000); Міжнародній конференції “Комп’ютерні системи і технології” – КомпСисТех’2001 (Болгарія, Софія, 2001); Другій міжнародній науково-практичній конференції “Проблеми впровадження інформаційних технологій в економіці та бізнесі” (Ірпінь, 2001); Міжнародній науково-практичній конференції “Автоматизація виробничих процесів МНПК АВТ-2002 (Хмельницький, 2002); I міжнародному радіоелектронному форумі “Прикладна радіоелектроніка. Стан і перспективи розвитку” – МРФ-2002 (Харків, 2002); VII міжнародній конференції “Досвід проектування і застосування САПР в мікроелектроніці CADSM 2003” (Львів-Славсько, 2003); Міжнародній науково-практичній конференції “Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” (Хмельницький, 2003).

Публікації. Результати дисертації опубліковані в монографії, 34 статтях у наукових журналах та збірнику наукових праць, 10 матеріалах і тезах конференцій.

Структура та обсяг дисертації. Дисертація складається із вступу, восьми розділів, висновків, списку використаних літературних джерел з 317 найменувань і тринадцяти додатків. Повний обсяг дисертації становить 425 сторінок, 124 ілюстрації, 51 таблицю, 86 сторінок додатків, 26 сторінок використаних літературних джерел.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі розкрито сутність і стан наукової проблеми, обґрунтовано актуальність її вирішення та необхідність проведення дослідження, сформульовано мету роботи і задачі, які необхідно вирішити для досягнення поставленої мети, сформульовано наукову новизну та показано практичне значення одержаних результатів.

У першому розділі дано загальні відомості про чорно-білі ГК, наведено галузі застосування графічного кодування інформації, проаналізовано існуючі апаратно-програмні засоби створення та обробки ГК-позначок, окреслено основні етапи розвитку наукової думки у галузі графічного кодування інформації як технології зберігання даних з метою автоматичного вводу в обчислювальну систему.

Проаналізовано різновиди ГК та структури ГК-позначок, виділено елементарні структурні одиниці ГК-позначок – ГК-знаки та ГК-елементи.

Далі для спрощення розглядаються ГК, що використовують елементарні графічні форми – прямокутник та квадрат, але пропоновані методи та отримувані результати справедливі для будь-яких дискретних графічних форм.

ГК-знаки багатокольорових лінійних та стекових ГК складаються з послідовності різнокольорових смужок різної ширини (рис. 1). Вважається, що смужка найменшої ширини у ГК має розмір один модуль (1 мод). Модуль – безрозмірна відносна величина, якій кратні розміри всіх елементів ГК. ГК-знак багатокольорового матричного ГК є квадратною або прямокутною матрицею розмірністю aM  bM (2Ч2, 3Ч2, 3Ч3, 4Ч4), ?лементами якої є різнокольорові комірки; розмір комірки 1мод х 1мод.

ГК-знак зазвичай подає один символ алфавіту (букву, цифру тощо). Повний набір ГК-знаків, використовуваних у даному ГК, кожному з яких поставлено у відповідність символ алфавіту, називається символікою ГК.

Лінійні та стекові ГК використовують горизонтальний спосіб побудови, сканування та декодування ГК-знаків даних; по вертикалі інформація не подається. Стекові ГК дозволяють досягти більшої щільності зберігання інформації порівняно з лінійними ГК лише за рахунок зменшення висоти елементів; вони зчитуються за допомогою багаторазового одноосьового сканування, що досягається переміщенням пристрою зчитування відносно ГК-позначки по вертикалі.

У матричних ГК інформація подається із застосуванням двох ортогональних осей. Наслідком цього є збільшення інформаційної щільності зберігання даних порівняно зі стековими ГК.

Запропоновано систему показників, яка дозволяє оцінити ГК, виконати порівняння ГК між собою, вибрати ГК, що найбільш повно відповідає заданим параметрам.

Показано, що відомі ГК мають недоліки: використання лише двох кольорів не дозволяє на заданій площі носія зберігати потрібні обсяги інформації; у багатьох випадках (зокрема лінійних ГК) ГК є лише ключем доступу до більш повної інформації про об’єкт.

Потреби сучасних систем обробки інформації вимагають переходу від ГК як ключа доступу до інформації до ГК як бази даних, що дозволяє будувати автономні системи, які могли б працювати на віддалі від центральної ЕОМ та центральної бази даних. Розширення сфер застосування графічного кодування інформації часто вимагає зменшення розмірів ГК-позначок (мініатюризації), часу обробки, підвищення їх завадостійкості.

Зроблено висновок про необхідність здійснювати пошук методів підвищення інформаційної щільності ГК без зміни геометричних розмірів елементів, збільшення ємності ГК-позначок та можливість їх обробки в реальному часі, що дозволило б за сеанс автоматичного зчитування вводити в обчислювальну систему більші обсяги інформації з потрібним рівнем надійності.

У другому розділі розглянуто побудову високощільних багатокольорових лінійних ГК.

Запропоновано два принципово різні підходи до побудови ГК-позначок багатокольорових лінійних ГК. Перший ґрунтується на тому, що кожному символу алфавіту, використовуваному для подання текстової інформації, що підлягає зберіганню у вигляді ГК, має відповідати ГК-знак. У цьому випадку ГК-позначка складається з послідовності ГК-знаків. Таку позначку називатимемо структурованою (див. рис.1).

Другий підхід до побудови ГК-позначок полягає в тому, що вихідну текстову послідовність перетворюють у числову форму з використанням q-кової системи числення, де q – кількість використовуваних кольорів, а потім кожній цифрі одержаної цифрової послідовності ставлять у відповідність ГК-елемент завширшки 1 мод відповідного кольору (а не ГК-знак). Така ГК-позначка є неструктурованою (беззнаковою).

Для побудови структурованого багатокольорового лінійного ГК потрібно задати: структуру ГК-знаків (кількість R елементів (смужок) і/або ширину m ГК-знака в модулях); кількість градацій ширини елементів (L); кількість використовуваних кольорів (q); потрібну потужність символіки (N).

Ознакою виділення ГК-знаків із ГК-позначки може бути однакова ширина ГК-знаків і/або однакова кількість елементів у ГК-знаку. Відповідно сформульовано дві задачі:

1) побудова багатокольорових лінійних ГК із заданими параметрами за умови, що виділення ГК-знаків з ГК-позначки здійснюють за двома ознаками – сталістю ширини m ГК-знаків та сталістю кіль-кості R елементів у ГК-знаках.

2) побудова багатокольорових лінійних ГК із заданими параметрами за умови, що виділення ГК-знаків з ГК-позначки здійснюють за однією ознакою – сталістю кількості R елементів у ГК-знаках (ГК-знаки можуть мати різну ширину m).

Узагальнено поняття типу лінійного ГК – неперервного та дискретного. У неперервному лінійному ГК ГК-знаки в ГК-позначці розміщують один до одного впритул без розділових проміжків; у дискретному – ГК-знаки в ГК-позначці відділяють один від одного розділовим проміжком.

У чорно-білих лінійних ГК тип коду задається значенням R: якщо R непарне, то ГК – дискретний, якщо R парне – неперервний. Показано, що у багатокольорових лінійних ГК тип коду задається не значенням R, а способом розфарбовування ГК-знаків, і в цьому випадку слід розрізняти не два, а три типи коду – неперервний (Н), дискретний без використання кольору носія (фону) (Д) та дискретний з використанням фону (Дф).

Запропоновано три алгоритми розфарбовування ГК-знаків, кожний з яких забезпечує отримання відповідного типу коду: Н, Д, Дф.

Символіка багатокольорового лінійного ГК зі сталою шириною ГК-знаків та сталою кількістю елементів у ГК-знаках задається п’ятіркою S = {L, q, R, m, N}, де N – потужність символіки.

Задача побудови символіки потужністю N ГК-знаків такого ГК за заданих L, q зводиться до генерування N ГК-знаків якнайменшої ширини m.

Аналітично задача знаходження m зводиться до знаходження такого мінімального значення m, за якого виконується нерівність N = CL(q, R, m), де CL(q, R, m) – максимально можлива кількість ГК-знаків завширшки m модулів, які складаються з R ГК-елементів, що розфарбовані q кольорами.

Для обчислення CL(q, R, m) знайдено аналітичний вираз, що є рекурентною формулою. Показано, що за фіксованих L та q значення CL(q, R, m) при різних R можна розмістити у вигляді трикутника, який названо узагальненим (L,q)-арифметичним трикутником (рис. 2).

Для заданого типу багатокольорового лінійного ГК – Н, Д і Дф при різних L та q можна побудувати множину узагальнених (L, q)-арифметичних трикутників, які замінюють складне обчислення значення CL(q, R, m) пошуком елемента в трикутнику з координатами (R, m), де R – номер рядка, а m – порядковий номер елемента у рядку (нумерація в рядку починається зі значення R (див. рис. 2).

Алгоритм знаходження m:

1) побудувати узагальнений (L, q)-арифметичний трикутник;

2) зафіксувати рядки, у яких є найближче більше або рівне N значення CL(q, R, m). Для кожного такого значення записати його (R, m)_коорди-нати;

3) в одержаному масиві (R, m)-координат: (Ri, mi), (Rj, mj), ..., (Rt, mt) – залишити ті пари, які мають найменше m (решту пар викреслити), а потім серед пар, що залишилися, вибрати пару з найменшим R; отримана таким чином пара (R, m) дасть шукане m (а також R).

4) знаючи четвірку L, q, R, m з узагальненого (L, q)-арифметичного трикутника знаходимо потужність CL(q, R, m) повної символіки та генеруємо кольорові ГК-знаки;

5) викреслюванням будь-яких CL(q, R, m) – N ГК-знаків (наприклад, ос-танніх) отримуємо символіку потужності N (табл.1).

Символіка багатокольорового лінійного ГК зі сталою кількістю елементів у ГК-знаках та змінною шириною ГК-знаків задається четвіркою V {L, q, R, N}.

Задача побудови символіки потужністю N ГК-знаків такого ГК за заданих L, q зводиться до генерування N ГК-знаків, які мають однакову кількість R елементів та якомога меншу ширину (при цьому m – змінна). Запропоновано алгоритм розв’язування цієї задачі з використанням узагальненого (L, q)-арифметичного трикутника.

Запропоновано інформаційну щільність (біт/мод) структурованих багатокольорових лінійних ГК обчислювати за формулою

де =log2N – кількість інформації, яку передає один ГК-знак ГК з символікою потужністю N; mсер середня ширина ГК-знаків символіки; mр – ширина розділового елемента.

У випадку неперервного лінійного ГК mр=0; у дискретних ГК зазвичай mр=1мод.

Інформаційна щільність неструктурованої ГК-позначки, біт/мод, дорівнює

де I – кількість інформації, яку передає один символ (ti) вихідної послідовності T =  tntn – 1...t1, n – довжина послідовності, – довжина цифрової послідовності після перетворення T в q-кову систему числення.

Порівнюючи інформаційну щільність JНС неструктурованих лінійних ГК з аналогічним показником структурованих ГК зроблено висновок, що неструктуровані лінійні ГК у багатьох випадках мають перевагу над структурованими, якщо q = 3.

Виконано порівняння чорно-білих та багатокольорових лінійних ГК. Показано, що інформаційна щільність зберігання даних у вигляді багатокольорових лінійних ГК порівняно з чорно-білими кодами зростає в 1,5 – 4 рази.

У третьому розділі запропоновано узагальнення двох структурних методів підвищення інформаційної щільності зберігання даних у вигляді багатокольорових лінійних ГК – методу поділу алфавіту на набори символів та методу поділу символіки ГК на набори ГК-знаків.

У загальному випадку потужність NA алфавіту А, за допомогою якого подають вихідні текстові послідовності, не збігається або може не збігатися з потужністю NЩ символіки Щ ГК, за допомогою якої ці текстові послідовності подають у графічнокодованому вигляді.

Якщо NA> NЩ, то можливе застосування методу поділу алфавіту А на набори символів розмірністю NЩ; якщо ж NA<NЩ/2 – то методу поділу символіки Щ на набори ГК-знаків розмірністю NA.

У першому випадку (NA> NЩ) набори слід сформувати так, щоб кількість переходів між ними при поданні текстових послідовностей була якомога меншою.

Ефект від застосування даного методу полягає в тому, що завдяки меншій ширині ГК-знаків символіки Щ порівняно з ГК-знаками у випадку прямого подання інформації (для цього потрібна символіка потужності NA) сумарна ширина ГК-позначки є меншою, ніж при прямому поданні інформації.

Метод поділу символіки Щ на набори ГК-знаків застосовують при зберіганні у графічнокодованому вигляді алфавітно-цифрових повідомлень фіксованої довжини, якщо NA= NЩ/2; він забезпечує неявне кодування символів.

Нехай символіку Щ поділено на v наборів, де v = N NA. Оскільки кожний символ текс-тового повідомлення завдовжки r можна подати ГК-знаком, що може належати до будь-якого з v на-борів, то існує vr варіантів подання фіксованого r-символьного текстового повідомлення за допомогою ГК-знаків символіки ?. Якщо ці варіанти (комбінації номерів наборів ГК-знаків) пронумерувати (наприклад, від 0 до vr– 1), то це дозволить

символів текстового повідомлення не подавати у вигляді ГК-знаків – їх буде закодовано неявно.

Отже, ГК-позначка, до складу якої входить r ГК-знаків, подаватиме r+n'=n символів, n' з яких буде подано неявно, де n' – номер комбінації наборів ГК-знаків.

Після зчитування ГК-позначки, що містить r = n – n' ГК-знаків, зна-ходять r символів текстової послідовності. Але, фіксуючи комбінацію наборів ГК-знаків, до яких належать зчитані ГК-знаки, одержують її номер, а отже, додатково n' символів, які є цифрами цього номера, і долучають їх до r текстових символів, отримуючи n символів.

Запропоновано методику проектування високощільних багатокольорових лінійних ГК. При проектуванні беруться до уваги:

1) алфавіт А, за допомогою якого подають вихідні текстові повідомлення;

2) параметри NA, L, q: NA – потужність алфавіту; L – кількість градацій ширини елементів; q – кількість кольорів, які розрізняє пристрій зчитування ГК;

3) кольорову гаму – перелік використовуваних кольорів;

4) спеціальні вимоги, наприклад, вимоги до надійності (звичайні, підвищені);

5) особливості: колір носія (фону), довжину текстових повідомлень (фіксовану, змінну), максимальну довжину повідомлень.

Проектування полягає в тому, щоб, проаналізувавши задані умови 1 – , вибрати такий метод побудови ГК, який забезпечував би максимальну щільність зберігання даних.

Метод слід вибирати з урахуванням типу ГК – Н, Д, Дф. Для цього, порівнюючи задану кольорову гаму з кольором фону, потріб-но проаналізувати можливість використання кольору фону як додатково-го. Якщо це можливо, то можна побудувати багатокольоровий лінійний ГК з типом Дф, інакше – лише ГК з типом Н або Д.

Методику реалізовано у вигляді програмної моделі, яка за заданими параметрами користувача на підставі обчислення показника інформаційної щільності пропонує вибір такого методу побудови ГК та тип коду, який забезпечує за заданих умов максимально можливу інформаційну щільність зберігання даних.

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

У багатокольорових лінійних ГК слід враховувати не лише можливі зміни ширини ГК-елементів, але й можливу зміну кольорів ушкоджених елементів. Ця специфіка позначається на виборі засобів забезпечення завадостійкості ГК.

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

Показано, що для побудови символіки багатокольорового лінійного ГК з параметрами N, L, q, в ГК-знаках якої під час відтворення інформації можливе виникнення однократних помилок, доцільно використовувати узагальнений код Хемінга, який дозволяє виправляти однократні помилки в q-кових словах, оскільки компоненти векторів ГК-знаків належать множині

Q {0, 1, 2, q – }.

Узагальнений код Хемінга можна побудувати для таких q, які є простим числом або степенем простого числа.

Ідея побудови завадостійких ГК-знаків багатокольорового ГК полягає в тому, що вектор ГК-знака має бути кодовим словом узагальненого многозначного коректувального (n,k)- коду (табл. 2).

Якщо аналіз особливостей середовища використання багатокольорового ГК свідчить про те, що в ГК-знаках можливе виникнення двократних помилок, то символіку ГК слід будувати так, щоб у ГК-знаках забезпечувалось виправлення двократних помилок. Для цієї мети доцільно використовувати узагальнений коректувальний код Боуза-Чоудхурі-Хоквінгема (БЧХ) з коректувальною здатністю t=2, і вектори ГК-знаків символіки мають бути кодовими словами узагальненого БЧХ.

Твірний многочлен G(x) q-кового коду БЧХ з t =2 та довжиною n визначають як найменше спільне кратне мінімальних многочленів М(1)(х), М(2)(х), М(3)(х), М(4)(х) елементів б, б2, б3, б4 відповідно: G(x)= HCK(М(1)(х), М(2)(х), М(3)(х), М(4)(х)), де б – примітивний елемент GF(q) і б GF(qm); m – степінь мінімальних многочленів. Поле GF(q) називають полем символів, а GF(qm)– полем локаторів.

Твірному многочлену – відповідає твірна матриця G розмірністю k  n, де k=nr, n= qm 1.

Кодування інформації зводиться до множення многочлена степеня k  1, який відповідає k-розрядному q_ковому інформаційному слову А=(а0, а1,…, аk–1), на твірний многочлен степеня r (на матрицю G): C(x) A(x)G(x), де – многочлен степеня n  , що відповідає n-розрядному кодовому слову С.

Для отримання завадостійкої символіки багатокольорового лінійного ГК із заданими параметрами N, L, q, де N – потужність символіки, L – кількість градацій ширини ГК-елементів, q – кількість кольорів, в ГК-знаках якої виправляють 2-кратні помилки, потрібно виконати такі дії.

1. Отримати всі кодові слова q-кового (n, k)-коду БЧХ , використовуючи твірну матрицю G коду.

2. З множини кодових слів вибрати ті кодові слова, які відповідають структурі ГК-знаків.

3. Змінюючи параметри n, k отримати кількість кодових слів потрібної структури – не меншу ніж N.

Використовуючи спроектовану в такий спосіб символіку, створюють ГК-позначки багатокольорового лінійного ГК.

Під час зчитування ГК-позначок визначають межі інформаційних ГК_зна-ків завширшки n модулів. Перетворивши ширини елементів ГК_зна-ка та їх кольори в цифрову форму, отримують q-ковий n_розрядний вектор, який декодують за правилами q-кового коду БЧХ з t , використовуючи перевірну матрицю Н:

Спочатку обчислюють синдром S= с'HT, де с' – вектор зчитаного ГК-знака.

Якщо S=0, то ГК-знак не містить помилок, інакше:

1) формують матрицю ;

2) обчислюють визначник матриці М: якщо det M? 0 (це означає, що в слові с' – дві помилки), то обчислюють коефіцієнти 1, 2 многочлена локаторів помилок (х) 

, якщо det M=0 (це означаєб що в слові с' – одна помилка) – коефіцієнт

1 –S2/S1 (2=0);

3) у полі GF(qm) розв’язують рівняння 2х21х =0 (або 1х =0 – якщо det M=0), розв’язки подають у вигляді степеня примітивного елемента поля: х1 =, х2=;

4) знаходять локатори помилок (слід взяти до уваги, що в полі GF(qm) =1);

5) обчислюють значення Y1, Y2 помилок:

; якщо в слові с' одна помилка, то Y1 Х (Х2=0, Y2=0);

6) відновлюють значення символів в розрядах n – і1 та n – і2: , .

Показано, що надання завадостійких властивостей ГК-знакам символіки істотно підвищує надійність зберігання інформації.

У п’ятому розділі розглянуто питання зберігання інформації у вигляді багатокольорових стекових ГК.

При побудові символік багатокольорових стекових ГК з метою досягнення якнайменшої ширини ГК-знаків слід застосовувати структурний метод підвищення щільності зберігання даних – поділ алфавіту на набори символів.

Крім використання понад двох кольорів для розфарбовування ГК-знаків, підвищити інформаційну щіль-ність двомірних ГК (як стекових, так і матричних) можна застосуванням спеціального методу ущільнення даних, ідея якого полягає в тому, що групі з р сусідніх символів текстового повідом-лення, яке має зберігатися у вигляді багатокольорового двомірного ГК, ставиться у відповідність група з pш ГК-знаків, де pш < p. Характерна особливість методу – відмова від однозначної відповідності “символ ГК-знак” так, щоб один ГК_знак подавав більше, ніж один символ алфавіту.

За цього методу ущільнення (метод пакування символів) використовувані символи алфавіту поділяють на набори (рис. 3): “КВ” – набір, що містить великі літери кирилиці, “КМ” – малі літери кирилиці, “ЛВ” – великі латинські літери, “ЛМ” – малі латинські літери, “СС” – спеціальні символи (цифри, керувальні символи ASCII: CR, HT, LF тощо), “РС” – розділові символи (можливі й інші варіанти поділу).

Для переходів з одного набору до іншого використовують спеціальні службові символи переходів – перемикачі (виконують перехід до іншого набору, і цей перехід триває до кінця текстового повідомлення або до по-яви іншого символу-перемикача) та зсувачі (виконують перехід до відпо-відного набору тільки для подання одного символу з поверненням до по-точного набору): КВП – перехід з поточного набору в набір “КВ”, КМП – у набір “КМ”, ЛВП – у набір “ЛВ”, ЛМП – у набір “ЛМ”, ССП – у набір “СС”, РСП – у набір “РС”; КВЗ – зсув у набір “КВ”, ЛВЗ – зсув у набір “ЛВ”, РСЗ – зсув у набір “РС” (у загальному випадку можливі й інші перемикачі та зсувачі).

Розглянуто три режими пакування даних:

1) пакування текстових символів – текстовий режим (TXР);

2) пакування символів ASCII (байтів) – байтовий режим (БТР);

3) пакування цифрових даних – цифровий режим (ЦФР).

У текстовому режимі двом суміжним алфавітно-цифровим символам ставиться у відповідність один ГК-знак. Для кожної пари символів обчислюється значення d кодовектора: d = ans + b, де a – числове значення лівого (старшого) символу пари; b – правого (молодшого) символу; ns – потужність кожного з наборів символів; a, b 0, 1, 2, …, ns 1. Кодовектору ставиться у відпо-відність ГК-знак.

Під час розпаковування даних, знаючи значення d кодовектора, спочат-ку знаходять значення a старшого (лівого) символу пари: a = int(d/ns), а потім – молодшого: b = d ans.

Для подання можливих двосимвольних пар у режимі ТХР потрібно мати ns2 ГК-знаків.

Загальна кількість N ГК-знаків, необхідна для реалізації режимів ущіль-нення даних, має становити не менше N = + nд, де nд – кількість допоміжних символів, потрібних для переходів між режимами ущільнення даних.

Допоміжними символами, що забезпечують переходи між режимами пакування даних, можуть бути: ТР – перехід з поточного режиму в текстовий режим, БР – перехід з поточного режиму в байтовий режим, БРР – перехід з поточного режиму в байтовий режим (використовується інакше, ніж допоміжний символ БР), ЦРД – перехід з поточного режиму в цифровий режим для подання десяткових даних, ЦРШ – перехід з поточного режиму в цифровий режим для подання шістнадцяткових даних, ТРЗ – зсув у текстовий режим (для подання однієї пари текстових символів) з поверненням у поточний режим, БРЗ – зсув у байтовий режим (для подання одного символу ASCII) з поверненням у поточний режим та інші.

Показано, що в режимі ТХР порівняно з прямим поданням даних ущільнення даних буде найбільш ефективним у разі застосування q=4 кольорів.

Режим БТР дозволяє пакування символів ASCII і використовується тоді, коли текстове повідомлення містить символи, які відсутні в символіці двомірного ГК.

Послідовності символів ASCII завдовжки ставиться у відповідність кодовекторів (), де , визначають із співвідношення , де bі – числове значення символу ASCII (0, 1.., 255), dj – значення кодовектора (0, 1,..., – 1). Значення та слід вибирати так, щоб відношення / було якнайбільшим.

Наприклад, якщо ns=38, = ns2=1444, то найбільше ущільнення досягається за таких відношень між та : 5 4 (/ = 1,25); 9 7 (/ ,29); 13 10 (/ = 1,3); 17 13 (/ = 1,31). З огляду на найбільш імовірні значення довжини послідовностей символів ASCII доцільно п’ять ( = 5) символів ASCII подавати за допомогою чотирьох ( = 4) кодовекторів (ГК-знаків) або дев’ять ( = 9) символів ASCII подавати за допомогою семи

( = 7) кодовекторів (ГК-знаків).

Режим ЦФР використовується для кодування довгих цифрових (десяткових або шістнадцяткових) послідовностей, які зустрічаються в текстовому повідомленні.

Мета режиму ЦФР – досягти більшої щільності пакування цифрових даних, ніж у режимі ТХР.

Десятковій цифровій послідовності завдовжки x розрядів можна поста-вити у відповідність у кодослів (x > y), де x, y визначають із співвідно-шення

де аі – значення десяткової цифри; dj – значення кодовектора (від 0 до 1).

Величини x та y необхідно вибрати так, щоб відношення x/y було якнайбільшим.

Наприклад, якщо = 1444, то найбільше ущільнення досягається за таких значень x та y: 22 7 (групі з 22 цифр ставлять у відповідність 7 кодовекторів (ГК-знаків), при цьому x/y = 3,14); 41 13 (x/y = 3,15); 60  (x/y = 3,16).

Якщо = 1444, то у разі пакування шістнадцяткових послідовностей найбільш доцільними є такі значення z та u: 18 7 ( групі з 18 символів ставлять у відповідність 7 кодовекторів (ГК-знаків), при цьому z/u ,57); 26 10 (z/u = 2,6); 34 13