Размещено на http://www.allbest.ru/

Національний університет “Львівська політехніка”

ВЕЛИКА ОКСАНА ТАРАСІВНА

УДК 681.325:519.15

алгебро-графові моделі синтезу числових кодів з кільцевою структурою

01.05.02 - Математичне моделювання та обчислювальні методи

Автореферат

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

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

Львів 2006

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

Робота виконана у Національному університеті “Львівська політехніка”

Міністерства освіти і науки України

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

Різник Володимир Васильович,

Національний університет “Львівська політехніка”, професор кафедри “Автоматизовані системи управління”.

Офіційні опоненти: доктор фізико-математичних наук, професор

Слоньовський Роман Володимирович,

Національний університет “Львівська політехніка”, професор кафедри “Прикладна математика.», кандидат технічних наук, старший науковий співробітник алгебричний метод синтез числовий код

Хавалко Віктор Михайлович,

Львівський коледж Державного університету інформаційно-комунікаційних технологій, м. Львів, завідувач відділення.

Провідна установа - Державний науково-дослідний інститут інформаційної інфраструктури Держкомзв'язку та інформатизації

України і НАН України, м.Львів, відділ Інформаційних технологій і систем.

Захист відбудеться “12 ”квітня 2006 р. о 16 год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” за адресою: 79013, м. Львів-13, вул. Ст. Бандери, 12.

З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська політехніка” за адресою: 79013, м. Львів-13, вул. Професорська 1.

Автореферат розісланий “ 10” березня 2006р.

Загальна характеристика роботи

Актуальність теми. Ефективність управління та контролю виробництва в ринкових умовах господарювання українських підприємств стало однією з необхідних умов їх успішного функціонування. Прийняття ефективних рішень неможливе без надійного захисту інформації, на основі якої здійснюється виконання керівних функцій у системі. Оперативність управління, надійність, своєчасність та повнота повідомлень, що надходять каналами зв'язку, і швидке пересилання директив до нижчих ланок системи для їх своєчасного виконання, високі вимоги до рівня захищеності даних від несанкціонованого доступу обумовлюють важливість впровадження в науково-виробничу практику математичних моделей і обчислювальних методів. Тому важливим і актуальним слід вважати дослідження комбінаторних конфігурацій як математичних моделей дискретних сигналів з поліпшеними властивостями щодо кодування, пересилання та перетворення інформації в каналах зв'язку. Визначний вклад у розвиток комбінаторних методів синтезу та дослідження кодів внесли: Боуз Р.Ч., Глушков В.М., Голей М.Дж.Е., Голомб С., Плоткін М., Петерсон У., Райзер Г.Дж., Слоан Н.Дж., Хемінг Р.У., Холл М., Шеннон К. та ряд інших дослідників.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в рамках пріоритетних напрямів розвитку науки і техніки в Україні. Тематика роботи відповідає основному напряму наукових досліджень кафедри “Автоматизовані системи управління” Національного університету „Львівська політехніка”, а саме: „Розробка математичних методів та моделей інформаційних програмних та технічних засобів автоматизованих систем обробки інформації та управління”.

Робота виконана в рамках госпдоговірної теми: № 7174 „Модернізація конструкції пресформи виготовлення реографічного електрода” (від 01.02.2005р., номер держреєстрації 0105U007574), що виконувалась у Національному університеті „Львівська політехніка”, основним учасником якої був автор.

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

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

— провести всебічний системний аналіз алгебричних методів синтезу числових кодів з кільцевою структурою, обґрунтувати їх переваги та недоліки;

— розробити алгебро-графову модель числових кодів з кільцевою структурою;

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

— розробити методику синтезу та обчислення повних сімей числових кодів з кільцевою структурою;

— розробити комплекс програм для синтезу ІКВ-кодів з кільцевою структурою та рекомендації щодо використання запропонованих методик для проектування систем і пристроїв інформаційно-обчислювальної техніки.

Об'єкт дослідження - числові коди з кільцевою структурою.

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

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

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

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

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

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

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

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

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

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

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

Розроблені в дисертаційній роботі методи і рекомендації використовуються у навчальному процесі на кафедрі автоматизованих систем управління Національного університету „Львівська політехніка” при викладанні курсу „Математичні моделі синтезу та оптимізації систем” для студентів базового напряму 6.08.04 „Комп'ютерні науки” за фахом 8.080.401 „Інформаційні управляючі системи та технології”.

Проведені автором дослідження та розробки використовувались у науково-дослідній роботі під час виконання госпдоговірної теми „Модернізація конструкції пресформи виготовлення реографічного електрода”, яка виконувалась у Національному університеті „Львівська політехніка”, а також у виробництві ДП „Електрон-механік” ВАТ „Концерн- Електрон” для підвищення рівня захисту каналу зв'язку під час керування виробничими процесами.

Особистий внесок здобувача. Всі основні результати роботи отримано автором самостійно. У працях, опублікованих у співавторстві, здобувачу особисто належать: [1,5-8,10] - дослідження теоретичних взаємозв'язків між алгебричними моделями різних типів; [13] - дослідження методів алгебричних перетворень в задачах моделювання нелінійних процесів; [11,12] - розроблення методики побудови алгебро-графових моделей числових кодів на ідеальних кільцевих в'язанках; [9] - побудова алгоритму синтезу ІКВ-кодів на базі комбінованих алгебро-графових моделей; [4] - розроблення вдосконаленого алгоритму синтезу ідеальних кільцевих вязанок на основі методу супровідних матриць поліномів та відповідних алгебричних перетворень з урахуванням властивостей циклічних груп в розширених полях Галуа; [2,4,9] - розроблення комплексу програм для синтезу ІКВ-кодів і рекомендації щодо використання запропонованих методик.

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

– East West Fuzzy Colloquium 2000 (Zittau, Germany, 2000);

– Міжнародній конференції „Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій” (м. Євпаторія, 2005);

– конференції молодих учених із сучасних проблем механіки і математики імені академіка Я.С. Підстригача (м. Львів, 2005 ).

В повному обсязі дисертаційна робота доповідалась кафедрі „Автоматизовані системи управління” Національного університету „Львівська політехніка”.

Публікації. За темою дисертації опубліковано 13 наукових праць, із яких 8 статей у наукових фахових виданнях, 1 стаття у науково-технічному журналі, 3 - у матеріалах конференцій.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, переліку літератури та п'яти додатків. Робота містить 25 рисунків, 23 таблиці. Список використаних джерел складається з 90 назв. Загальний обсяг дисертації складає 179 сторінок, в тому числі 123 сторінки основного тексту.

Основний зміст роботи

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

У першому розділі здійснено короткий аналіз ефективності існуючих кодів та викладена суть проблеми „ідеального групування” однойменних символів при кодуванні інформації. Ця проблема зводиться до пошуку такого упорядкованого набору вагових розрядів, при якому будь-яке натуральне число можна представити фіксованим числом способів у монолітному коді. Монолітним називається двійковий код, дозволені комбінації якого утворюються зі щонайбільше двох блоків однойменних символів, наприклад: 00001, 00011, 00111,... Однак число таких комбінацій не дає змоги отримати достатньо великої кількості дозволених кодових комбінацій. Для збільшення числа кодових комбінацій доцільно перейти від ланцюжкових послідовностей до кільцевого розміщення упорядкованого набору вагових розрядів. При цьому потужність коду зростає майже вдвічі, що випливає з наступних розрахунків. Для ланцюжкового коду з фіксованим числом розрядів максимально можливе число комбінацій дорівнює числу способів заповнення розрядного ланцюжка одиничними символами так, щоб між ними не було „нулів”. Очевидно, що число таких способів є:

До цього слід додати комбінацію з усіх „нулів”

Число таких способів для послідовностей з кільцевим розміщенням вагових розрядів включно з „нульовою” комбінацією обчислюється залежністю:

Порівнюючи між собою формули (1) і (2), легко побачити, що потужність „кільцевого” коду практично вдвічі перевищує потужність ланцюжкового.

Основною перевагою кільцевого монолітного коду (КМК) є простота і висока швидкість виявлення та виправлення помилок. На помилку у кодовій комбінації вказує поява хоча б одного символу „1” серед нулів, або символу „0” серед одиниць. Якщо в КМК з'являються хибні символи, то всі символи, або частина їх зразу ж виявляються.

Досліджуючи особливості кодування чисел в монолітному кільцевому коді, виникає проблема оптимального розподілу вагових розрядів, суть якої полягає в тому, щоб множині кодових комбінацій монолітного коду взаємно однозначно відповідала множина чисел натурального ряду. Поставлена задача розв'язується за допомогою правил розміщення елементів в ідеальних кільцевих в'язанках (ІКВ). Приклад розв'язку цієї задачі на основі ІКВ (1,3,2,7) наведено в табл. 1.

Таблиця 1. Кодові комбінації ваг розрядів КМК, утворені на ІКВ (1,3,2,7)

Ваги розрядів	Кодові комбінації
	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	0	0	1	0	1	0	1	0	1	1	0	1
3	0	0	1	1	1	1	0	0	0	0	1	1	1
2	0	1	0	0	1	1	0	0	1	1	0	1	1
7	0	0	0	0	0	0	1	1	1	1	1	1	1

З табл. 1 легко бачити, що всі числа від 1 до 13 можна подати єдиним способом представлення одного, двох, трьох або чотирьох суміжних вагових розрядів ІКВ (1,3,2,7).

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

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

Побудова таких моделей базується на використанні деяких властивостей розширених полів Ґалуа та геометрій над ними. Наприклад, для побудови алгебро-гафової моделі монолітного коду з параметрами (W_n - потужність кільцевого монолітного коду, n - кількість розрядів кодових слів; кодові слова з однаковими сумами ваг розрядів відсутні (N=0)), необхідно знайти деякий незвідний над полем поліном, визначити первісний елемент цього поля з максимально можливим періодом згаданого елемента і обчислити всі його степені, які повинні “пробігати” значення ненульових елементів. Далі слід дослідити отриману алгебричну структуру з метою визначення значень вагових розрядів кодових комбінацій ІКМК.

Так, наприклад, вибравши поліном, який є незвідним у полі, отримуємо всі степені первісного елемента в за модулем (3,):

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

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

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

Алгоритм побудови алгебро-графової моделі ІКМ-коду передбачає наступні операції:

1) за вхідними параметрами монолітного коду обрати первісний незвідний над полем Ґалуа поліном відповідного степеня;

2) обчислити усі ненульові елементи цього поля;

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

4) на побудованому графі необхідно обрати ті вершини, яким відповідають однакові значення коефіцієнтів при будь-якому з фіксованих степенів ;

5) сполучивши усі сусідні пари вершин ребрами, отримуємо алгебро-графову модель ІКМ-коду.

Для прикладу побудуємо алгебро-графову модель ІКМК з параметрами, . У цьому випадку, ,. Обчислюємо усі ненульові елементи поля за модулем (3,):

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

Подібним способом можна знаходити інші варіанти ІКМК за умови попереднього знаходження відповідного незвідного полінома, причому ІКВ-кодам з однаковими наборами вагових розрядів можуть відповідати різні первісні поліноми. В результаті побудови алгебро-графових моделей можна побачити, що кожній вершині , і,..., відповідає певний елемент поля, степінь якого не перевищує степеня незвідного полінома над цим полем. Алгебро-графові моделі дозволяють розширити уяву про теоретичні зв'язки між ідеальними кільцевими вязанками, комбінаторними конфігураціями та розширеними полями Ґалуа.

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

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

На основі використання комбінаторних властивостей ідеальних кільцевих монолітних кодів досліджено алгоритм побудови ІКМК з допомогою ІКВ методом циклічних переміщень вагових розрядів.

Запропоновано швидкісний метод побудови ІКМК на основі твірних елементів, розроблено вдосконалений алгоритм і програму для його реалізації.

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

Суть швидкісного методу побудови ІКМК полягає в знаходженні відповідних твірних елементів і всіх їх степенів за модулем , які після відповідного впорядкування і обчислення визначають вагові розряди коду.

Метод побудови ІКМК на основі твірних елементів дозволяє відносно просто і швидко обчислити значення ваг цифрових розрядів цього коду.

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

Метод графових перетворень циклічних груп полів Ґалуа дає змогу генерувати повні сім'ї ІКМК за наявності хоча б одного із варіантів ІКМК.

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

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

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

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

Блок-схема алгоритму синтезу монолітних кодів зображена на рис.5.

Результати дослідження залежності тривалості обчислення вагових розрядів ІКВ для наведені в табл. 2.

Таблиця 2. Тривалість обчислення ІКВ для

Порядок ІКМК	108	138	200	212	228	240
Час, с	1	2	5	5	6	7

Залежність тривалості обчислення від числа розрядів ІКМК дає підстави стверджувати, що розроблений на основі методу супровідних матриць алгоритм синтезу ідеальних кільцевих монолітних кодів дозволяє генерувати ІКМК з числом розрядів до 100 протягом часу, що не перевищує однієї секунди, а з числом розрядів до 200 - не більше п'яти секунд (AMD Athlon (TM) XP 2000+1,67 ГГц, RAM 256 МБ).

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

Результати імітаційного моделювання зашумленого каналу передачі даних з використанням кільцевого монолітного коду підтверджують його високу ефективність щодо виявлення помилок, яка забезпечує можливість виявлення від 99,7 до 100% дво- і багатократних помилок для монолітного коду з числом розрядів більше 30, причому його висока захищеність зберігається зі збільшенням кратності помилок. Встановлено, що при зростанні числа розрядів монолітного коду спостерігається експоненційна залежність зростання кількості виправлених помилок.

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

Для здійснення процесу перетворення чисел в монолітний код на основі ІКВ достатньо розмістити ваги розрядів (для систем кодування зі зваженими розрядами), або кількість одиничних розрядів по групах (для систем кодування в одиничному коді) за кільцевою схемою, впорядкувати ваги або кількість розрядів згідно послідовності елементів ІКВ та реалізувати схему перетворення чисел в монолітний код.

Слід зазначити, що сучасні досягнення в області інтегральної техніки та мікроелектроніки відкривають широкі можливості проектування пристроїв перетворення сигналів на одиничному коді. Такі пристрої забезпечують високу надійність перетворення сигналів, завдяки властивостям ІКМК, які базуються на дослідженні алгебричних структур.

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

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

Висновки

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

З виконаних досліджень випливають такі висновки:

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

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Бандирська О.В., Бичківський Р.В., Велика О.Т. Оптимальні набори мір на різницевих множинах // Автоматика, вимірювання та керування: Вісник Державного університету “Львівська політехніка”.- 1998.- № 348. - С.124-127.

2. Бандирська О., Велика О., Садов'як Б., Різник В. Дослідження кільцевого монолітного коду методом імітаційного моделювання // Комп'ютерна інженерія та інформаційні технології: Вісник Національного університету “Львівська політехніка”.- 2003.- № 481. - С.110-115.

3. Велика О.Т. Комбіновані алгебро-графові моделі монолітних кодів на ідеальних кільцевих в'язанках // Комп'ютерна інженерія та інформаційні технології: Вісник Національного університету “Львівська політехніка”. -2004. -№521. -С.129 -133.

4. Велика О., Міщенко М., Різник В. Синтез ідеальних кільцевих в'язанок методом супровідних матриць. // Інформаційні системи та мережі: Вісник Національного університету “Львівська політехніка”.- 2004.- № 519. - С.38-44.

5. Велика О.Т., Парамуд Н.Я., Різник В.В., Соломко М.Т. Синтез циклічних блок-схем за допомогою ідеальних кільцевих в'язанок // Прикладна математика: Вісник Державного університету “Львівська політехніка”.- 1999.- № 364. - С.187-189.

6. Різник В., Бандирська О., Велика О. Досконалі комбінаторні конструкції на ідеальних кільцевих в'язанках // Інформаційні системи та мережі: Вісник Державного університету “Львівська політехніка”.- 1999.- № 383. - С.207-212.

7 Різник В., Бандирська О., Велика О. Оптимальні структурні пропорції в інформаційних системах і задачах стандартизації // Інформаційні системи та мережі: Вісник Національного університету “Львівська політехніка”.- 2002.- №464.- С.278-284.

8. Різник В., Бандирська О., Велика О. Використання арифметики ідеальних кільцевих в'язанок в комп'ютерних технологіях // Комп'ютерні технології друкарства: Зб. наук. пр.- Львів, 2000.- № 4.- С. 158-165.

9. Велика О., Різник В., Дзера І., Носалик Н., Якимів О. Дослідження та синтез монолітних кодів на комбінованих алгебро-графових моделях // Технічні вісті.-2005.-№1(20),2(21).-С.58-61.

10. Бандирська О.В., Велика О.Т. Застосування оптимальних комбінаторних конфігурацій для вдосконалення наборів мір // Збірка наукових праць Міжнародної конференції „Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій”.-Том 1.- Євпаторія, Крим, 2005.-С. 38-40.

11. Велика О.Т., Топільницький В.Г. Алгоритм побудови алгебро-графової моделі монолітного коду на ідеальній кільцевій вязанці // Тези доповідей конференції молодих учених із сучасних проблем механіки і математики імені академіка Я.С.Підстригача.- Львів, 2005.-С. 232-233.

12. Дурняк Б., Різник В., Різник О., Велика О. Захист бланків цінних паперів методом комбінаторної конфігурації // Збірка наукових праць Міжнародної конференції „Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій”.-Том 4.- Євпаторія, Крим, 2005.-С.108-109.

13. Riznyk V., Jablonski W., Velyka O., Riznyk M. Perfect distribution phenomenon and modeling of non-linear processes // Proc. East West Fuzzy Colloquium. Zittau, Germany, 2000.- p.364-367.

АНОТАЦІЯ

Велика О.Т. Алгебро-графові моделі синтезу числових кодів з кільцевою структурою. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - Математичне моделювання та обчислювальні методи-Національний університет “Львівська політехніка”, Львів, 2006.

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

Ключові слова: математичне моделювання, ідеальна кільцева в'язанка, ідеальний кільцевий монолітний код, алгебро-графова модель, синтез.

SUMMARY

Velyka O.T. Algebraic and graph models of synthesis of numerical codes with the ring structure. - Manuscript.

The thesis for scientific degree of the candidate of technical science by specialty 01.05.02 - Mathematical modeling and calculating methods. - Lviv National Polytechnic University, Lviv, 2006.

Dissertation is devoted to research of numerical codes with the ring structure. A method of construction of mathematical models of monolithic codes is developed in work on the base of some properties of extended fields of Galois and geometry above them. A combined algebraic and graph model of monolithic ring code is built, that allowed to extend imagination about the theoretical copulas between ideal ring bundles, by the combinatorial configurations and extended fields of Galois. Algorithms of synthesis of monolithic codes are explored with the circular structure. A software package is developed for the synthesis of ideal monolithic codes with the circular structure and recommendation in relation to the use of offered methods for creation the systems and devices of calculation technique.

Keywords: mathematical modeling, ideal ring bundle, ideal ring monolithic code, combined algebraic and graph model, synthesis.

АННОТАЦИЯ

Велика О.Т. Алгебро-графовые модели синтеза числовых кодов с кольцевой структурой. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - Математическое моделирование и вычислительные методы. - Национальный университет “Львивська политэхника”, Львов, 2006.

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

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

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

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

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

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

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

Ключевые слова: математическое моделирование, идеальная кольцевая вязанка, идеальный кольцевой монолитный код, алгебро-графовая модель, синтез.

Размещено на Allbest.ru