Дичка Іван Андрійович. Методи і засоби для реалізації зберігання, обробки та вводу графічнокодованої інформації

brief description

Дичка Іван Андрійович. Методи і засоби для реалізації зберігання, обробки та вводу графічнокодованої інформації: дис... д-ра техн. наук: 05.13.13 / Національний технічний ун-т України "Київський політехнічний ін- т". - К., 2004. , табл.

Дичка І. А. Методи і засоби для реалізації зберігання, обробки та вводу графічнокодованої інформації. Рукопис.
Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.13 обчислювальні машини, системи та мережі. Національний технічний університет України Київський політехнічний інститут”, Київ, 2004.
Дисертація присвячена розвитку теоретичних основ перетворення, зберігання та обробки інформації, поданої у вигляді багатокольорових графічних кодів. Запропоновано узагальнення теорії графічного кодування як технології зберігання інформації з метою її подальшого вводу в обчислювальну систему на випадок многозначного алфавіту (багатокольоровості графічного коду).
Розроблено методи зберігання алфавітно-цифрової інформації у вигляді багатокольорових графічних кодів лінійних, стекових, матричних з високими показниками інформаційної щільності.
Розроблено методи надійного зберігання інформації у вигляді двомірних багатокольорових графічних кодів великої ємності, які ґрунтуються на побудові графічнокодових знаків, що мають властивість виправляти помилки, та застосуванні для послідовності графічнокодових знаків многозначних коректувальних кодів, здатних виправляти багатократні спотворення двох видів помилок і стирань.
Запропоновано узагальнення методу ущільнення алфавітно-цифрової інформації при її зберіганні у вигляді двомірних багатокольорових графічних кодів. Метод забезпечує зберігання на обмеженій площі носія у графічнокодованому вигляді великих обсягів інформації.
Запропоновано організацію та архітектуру спеціалізованої обчислювальної системи та проблемно-орієнтованого процесора для обробки графічнокодованих зображень у реальному часі, які ґрунтуються на виконанні операцій в полях Галуа.

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

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

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

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

Показано, що в багатокольорових лінійних ГК інформаційна щільність зростає в 1,51 (приq=3) 4 (приq=8) рази порівняно з чорно-білими графічними кодами, а в багатокольорових матричних ГК приq=3 у 2 4 рази, а приq=8 у 4 11 разів.

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

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

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

Наприклад, якщо при створенні ГК-позначки задати інформаційну надлишковість 50%, то інформацію буде відтворено правильно при пошкоджені до 25% площі ГК-позначки.

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

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

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

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

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