Харківський національний університет радіоелектроніки

Бережна Ольга Володимирівна

УДК 004.04:519.72

МЕТОДИ ТА АЛГОРИТМИ АДАПТИВНОГО

РІВНОВАЖНОГО КОДУВАННЯ

НА ОСНОВІ БІНОМІАЛЬНИХ ЧИСЕЛ

ДЛЯ ІНФОРМАЦІЙНИХ СИСТЕМ

05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології

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

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

Харків - 2002

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

Робота виконана в Сумському державному університеті,

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

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

Сумський державний університет,

завідувач кафедри промислової електроніки

Офіційні опоненти:

- доктор технічних наук, професор Горбенко Іван Дмитрович, Харківський національний університет радіоелектроніки, завідувач кафедри безпеки інформаційних технологій;

- кандидат технічних наук, доцент Приходько Сергій Іванович, Харківський військовий університет, начальник кафедри систем бойового управління та зв'язку

Провідна установа - Національний технічний університет України "Київський політехнічний інститут", кафедра технічної кібернетики, Міністерство освіти і науки України, м. Київ

Захист відбудеться " 27 " листопада 2002 р. о 1500 год. на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел. (0572) 40-91-13.

З дисертацією можна ознайомитись в бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий " 25 " жовтня 2002 р.

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

спеціалізованої вченої ради В. І. Саєнко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Розвиток і впровадження інформаційних технологій управління є необхідною умовою науково-технічного прогресу суспільства. Україна як частина світової суспільно-економічної системи також увійшла до процесу інформатизації. В інформаційних підсистемах автоматизованих систем управління (АСУ) будь-якого призначення, наприклад, у сферах державного управління, банківської діяльності, управ-ління технологічними процесами на підприємствах, управління транспортними засобами та інших, постійно зростає обсяг інформації, що передається, та її цінність. Тому велике значення мають швидкість та інформаційна надій-ність передачі даних, які визначають ефективність інформаційних систем. З цієї причини, незважаючи на значні успіхи в теорії та практиці передачі дискретної інформації, задача підвищення ефективності передачі даних залишається актуальною і в наш час. На практиці в інформаційних системах інтенсивність завад має змінний характер. Підвищення ефективності передачі даних досягається шляхом змінювання швидкості передачі дискретних повідомлень залежно від рівня завад, так, щоб вона була максимальною з додержанням необхідних обмежень на вірогідність інформації, яка надається споживачам. Цим визначається сутність задачі оптимізації процесу передачі даних за швидкодією при обмеженні на допустимий рівень інформаційної надійності. При змінному рівні завад задача оптимізації вирішується в адаптивних системах передачі даних (СПД). Одним із шляхів вирішення пробле-ми підвищення ефективності передачі даних в інформаційних системах є розроблення та застосування методів адаптивного кодування. Значний внесок у розроблення теоретичних та практичних питань ефективного кодування зробили У.У. Пітерсон, Р.Дж. Галагер, О.О. Харкевич та інші.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась згідно з планом науково-дослідних робіт Сумського державного університету в рамках держбюджетних тем: № 0194U009663 "Разработка и исследование биномиальных систем счисления и цифровых устройств на их основе" та № 0197U016602 "Разработка алгоритмов синтеза и обработки двумерных изображений на основе метода срезов и локальных окон с использованием биномиальных систем счисления", над якими автор працював, обіймаючи посаду наукового співробітника.

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

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

Основні задачі дослідження, що визначаються метою і загальною задачею роботи:

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

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

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

Об'єкт дослідження - системи завадостійкого кодування для інформаційних задач АСУ.

Предмет дослідження - методи і алгоритми адаптивного рівноважного кодування для інформаційних систем.

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

Наукова новизна одержаних результатів. У ході вирішення поставлених задач були отримані такі результати:

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

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

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

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

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

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

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

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

Алгоритми адаптивного рівноважного кодування на основі біноміальних чисел застосовані науково-виробничим колективним підприємством "Преобразователь" (м. Суми) у проекті автоматизованої системи управління, контролю та обліку електроенергії та прийняті ВАТ "Сумське МНВО ім. М.В.Фрунзе" для застосування в комп'ютеризованих системах управління технологічних комплексів і в АСУ об'єднання. Розроблені алгоритми та програми використовуються в навчальному процесі Сумського державного університету.

Особистий внесок здобувача. Усі результати роботи одержані автором самостійно. В наукових працях, опублікованих у співавторстві, йому належать: процедури рівноважного кодування і декодування дискретних повідомлень на основі нерівномірних біноміальних чисел [2]; структурна схема апаратного пристрою декодування [3]; формулювання та докази виразів імовірностей П, V і Z відповідно до правильної передачі рівноважної кодової комбінації по каналу зв'язку, невиявлення і виявлення помилок при kЈn/2 [4]; декомпозиція задачі адаптивного вибору параметрів рівноважного коду на послідовно розв'язувані задачі визначення мінімально допустимого значення параметра n, аналізу можливості розв'язання задачі з визначенням початкових значень параметрів n і k, максимізації швидкості передачі повідомлень шляхом корекції значень параметрів коду з одержанням їх оптимальних значень [7]; застосування рівноважних кодів та біноміальних чисел для оброблення результатів фізичних експериментів [9]; пристрій нумерації рівноважних кодів із застосуванням біноміальних чисел та алгоритм раціонального обчислювання біноміальних коефіцієнтів [10]; застосування біноміальних кодів для завадостійкого адаптивного кодування телевізійної інформації [11]; розроблення моделі процесу кодування-декодування в адаптивній системі передачі даних та визначення принципів адаптивного завадостійкого кодування [12]; розроблення алгоритмів та синтез пристроїв адаптивного рівноважного кодування і декодування [13]; розроблення алгоритму вибору параметрів рівноважного коду [14].

Апробація результатів дисертації. Основні положення дисертації і результати досліджень доповідалися на науково-технічній конференції "Техника и физика электронных систем и устройств" (м. Суми, 1995); науково-технічних конференціях викладачів, співробітників і студентів фізико-технічного факультету Сумського державного університету (м. Суми, 1997, 1998, 1999, 2000); ІІ Міжнародній конференції MPSL'96 (м. Суми, 1996); науково-методичній конференції "Применение компьютерных технологий в учебном процессе" (м. Харків, 1997); науково-технічних конференціях Кременчуцького державного політехнічного інституту "Проблемы создания новых машин и технологий" (м. Кременчук, 1999, 2000); ІV Міжнародному форумі "Радиоэлектроника и молодежь в XXI веке" (м. Харків, 2000).

Публікації. Результати дисертації опубліковані в 14 наукових працях (6 наукових статей у виданнях, перелік яких затверджений ВАКом України, та 8 тез доповідей на науково-технічних конференціях).

Структура та обсяг дисертації. Робота складається зі вступу, 4 розділів, загальних висновків, 8 додатків. Загальний обсяг дисертації - 146 сторінок. Список використаних джерел містить 120 найменувань. Кількість рисунків і таблиць - відповідно 32 і 8.

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

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

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

До вихідних положень і понять відносять такі. У процесі передачі повідомлення по тракту прямого зв'язку інформаційного каналу (ІК) вихідне повідомлення у вигляді двійкової кодової комбінації X=(x1,...,xm) кодується завадостійким кодом з результатом у вигляді вхідної послідовності каналу Xк=(xк1,...,xкn). На вихід каналу зв'язку (КЗ) надходить кодова комбінація Yк=(yк1,...,yкn). Якщо перехід Xк?Yк (одноразова передача) відбувся правильно, то Yк=Xк, а у випадку неправильного переходу (через вплив завад) Yк?Xк. Після виявлення помилок і перепитувань вихідна послідовність Yк каналу декодується з результатом у вигляді кодової комбінації Y=(y1,...,ym), що видається споживачу. Рівність Y=X вказує на правильну передачу.

Для оцінки результатів передачі повідомлень X споживачу використовуються імовірності Pп, Pош, Pоо і Pно відповідно до правильної, неправильної, виявленої та невиявленої помилкових передач [5]. Для оцінки результатів одноразової передачі по КЗ рівноважних кодових комбінацій Xк (без виправлення помилок) використовуються імовірності П і W, Z і V відповідно до правильної та неправильної передач, виявлення і невиявлення помилок [4].

Аналіз характеру помилок і причин їх виникнення в КЗ показує, що стан КЗ часто характеризується різними значеннями імовірностей p10 і p01 перекручення значень відповідно до одиничних і нульових розрядів, тобто КЗ може бути асиметричним. На основі розгляду різних моделей КЗ в роботі прийнята модель нестаціонарного асиметричного КЗ з незалежними помилками. Таким чином вважається, що імовірності p10 і p01 відомі та не залежать від розміщення одиничних розрядів у кодовій комбінації Xк.

Для СПД, що працюють у режимі виявлення помилок, задача підвищення ефективності передачі даних інтерпретується як задача максимізації швидкості Rс передачі повідомлень від джерела споживачу при обмеженні за максимально допустимим значенням Vmax імовірності невиявлення помилок [7]:

(1)

У зв'язку з тим, що стан КЗ може непередбачено змінюватись, розв'язання задачі (1) можливо лише в адаптивних СПД, в яких максимізація швидкості Rс досягається за рахунок мінімізації довжини n послідовностей Xк та імовірності Z за умови утримання імовірності V на допустимому рівні. Сутність процедури розв'язання задачі (1) методом адаптивного кодування полягає в зміні значень параметрів застосованого коду їз зміною стану КЗ. Розроблення цієї процедури входить до елементів предмета дослідження.

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

Другий розділ присвячений вдосконаленню методу оцінки завадостійкості рівноважних кодів з метою забезпечення можливості обчислювання імовірностей П, W, Z і V та прогнозування їх змінювання при варіації параметрів n і k рівноважного коду, що необхідно для визначення підходу до розробки методу адаптивного вибору цих параметрів.

Міркування базуються на положеннях теорії нероздільних кодів. Множина Qп вихідних повідомлень має потужність Мп. Повідомлення XjОQп, j=, видається джерелом з імовірністю Pj і перетворюється в завадостійку вхідну послідовність каналу XкjОQр, j=, з множини Qр кодових комбінацій застосованого нероздільного коду. Вважається, що виконується умова

(2)

здійсненності кодування будь-якої кодової комбінації XjОQп.

У процесі передавання по КЗ кодова комбінація Xкj перетворюється в одну з двійкових послідовностей YкіОQдв, де Qдв - множина елементів двійкового коду потужністю Мдв=2n. Множина Qдв упорядкована так: елементи Yкі=Xкj, i=j=, складають множину Qр дозволених, а елементи Yкі, і= - множину Qз заборонених кодових комбінацій YкіОQдв. Виявлений помилковий перехід Xкj®Yкі відбувається з імовірністю і має результат YкіОQз. Правильний і невиявлений помилковий переходи відбуваються з імовірностями й і мають результат YкіОQр. Множина Qр упорядкована так: кодовим комбінаціям Xкj, j=, відповідають повідомлення XjОQп, j=, а кодові комбінації Xкj, j=, видаються кодером з імовірністю Pj= 0.

Потужність рівноважного коду

, 1=k=n-1, n=2. (3)

Оскільки виявлення помилок у кодових комбінаціях YкіОQр здійснюється шляхом перевірки їхньої належності рівноважному коду з параметрами n і k, то невиявленими є лише помилки зсуву, що не приводять до зміни ваги k кодових комбінацій. Максимально можлива кількість помилок зсуву в будь-якій кодовій комбінації Yкі, i=, дорівнює

(4)

На основі відомих виразів імовірностей П, V, Z і W для нероздільних кодів з урахуванням (4) одержані [4,5] вирази імовірностей П, V, Z і W для рівноважного коду:

, (5)

(6)

(7)

, (8)

де l= - кратність помилки зсуву в кодовій комбінації Yкі; р11=1-р10; р00=1-р01. За умови р10=р01 вирази (5-8) перетворюються у відомі вирази імовірностей П, V, Z і W для симетричного КЗ.

Розглянуто приклади графіків залежностей П(k), V(k), Z(k) і W(k) за умови незмінних значень n, р10, р01, один з яких при асиметрії КЗ вигляду р10<р01 наведений на рис.1. На основі аналізу прикладів сформульовані при-пущення про закономірності впливу параметрів n і k на імовірності П, V, Z та W і проведений доказ їхньої об'єктивності для різних станів КЗ відносно його асиметрії. На підставі теоретичного дослідження сформульовані такі виснов-ки та рекомендації, що мають принципове значення для вироблення підходу до розв'язання задачі (1) методом адаптивного рівноважного кодування [6].

Рис. 1. Діаграми залежностей П(k), W(k), V(k) і Z(k)

при n=20, p10=0,005, p01=0,015

Незалежно від стану КЗ імовірності П і W є відповідно спадною та зростаючою функціями параметра n при незмінності параметра k. У зв'язку з цим у процедурі адаптивного вибору параметрів рівноважного коду слід задавати початкове значення nпоч параметра n таким, що дорівнює його мінімально допустимому значенню nmin за умови (2) здійсненності кодування.

При стані КЗ, що характеризується співвідношенням p10іp01, імовір-ності П і W є відповідно незростаючою і неспадною, а при p10<p01 - зростаючою й спадною функціями параметра k при незмінності значень n, p10 і p01.

Незалежно від стану КЗ імовірність V має унімодальний характер змінювання залежно від параметра k при незмінності значень n, p10 та p01 і від параметра n за умови незмінності значень k, p10 і p01 за наявності єдиного локального максимуму.

При p10<p01 межові значення імовірностей V і Z в діапазоні (3) значень параметра k знаходяться у співвідношеннях

V(1)<V(n-1), Z(1)>Z(n-1), (9)

а при p10іp01 - у співвідношеннях

V(1)іV(n-1), Z(1)ЈZ(n-1), 10)

причому при p10=p01 співвідношення (10) перетворюються в рівності. У про-цедурі адаптивного вибору параметрів рівноважного коду слід задавати початкове значення kпоч параметра k таким, що дорівнює максимально допустимому значенню kmax при p10іp01 і мінімально допустимому значенню kmin при p10<p01 за умови (2) здійсненності кодування для обраного початкового значення n=nпоч.

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

У третьому розділі розглядаються питання розробки методу адаптивного вибору параметрів рівноважного коду як способу розв'язання задачі (1).

При розв'язанні задачі (1) оптимізації методом адаптивного кодування вводиться додаткове обмеження на діапазон допустимих значень параметра n, у результаті чого задача (1) трансформується в задачу адаптивного вибору параметрів рівноважного коду [6] у постановленні

(11)

де nmax - задане максимально допустиме значення параметра n.

Зроблено декомпозицію задачі (11) на задачі визначення мінімально допустимого значення nmin параметра n, аналізу можливості розв'язання задачі (11) з видачею початкових значень nпоч і kпоч параметрів n і k, корекції значень n і k з видачею їх оптимальних значень nопт і kопт [7].

Мінімально допустиме значення nmin параметра n, а також граничні значення kmin та kmax параметра k при nіnmin визначаються умовою (2) здій-сненності кодування будь-якого вихідного повідомлення XОQп. Розроблені алгоритми обчислення значень nmin, kmin і kmax та їх програмне забезпечення [1].

У зв'язку з обмеженням nЈnmax може виявитись, що розв'язати задачу (11) неможливо. Сутність процедури перевірки можливості розв'язання задачі (11) полягає в пошуку найменшого значення nпоч параметра n у діапазоні його допустимих значень, при якому забезпечується виконання обмеження VЈVmax хоча б для одного значення k у діапазоні від kmin(nпоч) до kmax(nпоч).

На підставі співвідношень (9) і (10) доведено [6], що задачу (11) можливо розв'язати при p10іp01, якщо дійсне співвідношення

(12)

і при p10<p01, якщо

(13)

Весь діапазон допустимих значень параметра n поділяється на піддіа-пазони постійних значень kmin=kmin(nmin), kmin(nmin)-1,...,1. Доведено [6], що глобально мінімальні значення V(kmax(n)) і V(kmin(n)) імовірності V змінюють-ся непередбачено при зміні значення n у будь-якому з цих піддіапазонів. Тому пошук значення nпоч параметра n здійснюється шляхом послідовного перебору значень n у допустимому діапазоні, починаючи від n=nmin, і перевірки виконання умови (12) або (13) для кожного чергового значення n. Після визначення nпоч параметра kпоч присвоюється значення kmax(nпоч) або kmin(nпоч) відповідно при p10іp01 і p10<p01. Розроблено алгоритм [6] перевірки можливості розв'язання задачі (11) і його програмне забезпечення.

Чергова задача полягає в тому, щоб шляхом варіації параметрів n і k у межах nпочЈnЈnmax і kmin(n)Јk(n)Јkmax(n) максимізувати швидкість Rc передачі повідомлень без порушення умови VЈVmax. Враховуючи, що збільшення значення n відносно вихідного значення n=nпоч приводить до зниження швидкості Rc через збільшення довжини n вхідних послідовностей Xк каналу і, можливо, через збільшення імовірності Z виявлення помилок, оптимальне значення параметра n береться таким, що дорівнює nопт=nпоч [6].

Оптимізація параметра k здійснюється таким чином. При р10<p01, з огляду на спадний характер залежності W(k), здійснюється спроба переходу з висхідної гілки залежності V(k) на її спадну гілку зі збереженням значення n=nопт шляхом присвоєння параметру k значення kmax(nопт). У випадку дотримання умови (12) буде досягнуто мінімум імовірності W і, можливо, мінімум імовірності Z. Тоді можна спробувати ще більше підвищити швидкість Rc, зменшуючи значення k і спостерігаючи за зміною імовірності Z та дотриманням умови VЈVmax. Процес декрементування параметра k слід припинити і повернутися до попереднього значення k, якщо виявляється збільшення імовірності Z чи порушення умови VЈVmax. Якщо перехід на спадну гілку залежності V(k) виявляється неможливим через порушення умови VЈVmax, то слід відновити значення k=kmin(nопт) і почати спроби інкрементування параметра k, спостерігаючи за зміною імовірності Z і дотриманням умови VЈVmax. У кінці виконання описаної ітераційної процедури буде визначено значення kопт. Аналогічно виконується процедура оптимізації параметра k при р10іp01, що проілюстрована на рис.2. У процесі оптимізації значення k здійснювався послідовний перехід на діаграмах залежностей V(k), Z(k) і П(k) з початкових точок V1 і Z1 у точки V2 і Z2, потім - у точки V3 і Z3 і, нарешті, у точки оптимального режиму V2 і Z2.

Рис. 2. Діаграми залежностей V(k), Z(k) і П(k) при Мп=8000,

p10=0,1, p01=0,095, Vmax=0,12, nопт =23, kпоч=19, kопт=4

Розроблено [6] алгоритми оптимізації параметрів n і k, розв'язання задачі адаптивного вибору параметрів коду в цілому та їхнє програмне забезпечення. Проведено моделювання процесів передачі даних у СПД з перепитуваннями, в якій протягом кінцевих тимчасових інтервалів мають місце спів-відношення р10>p01, р10<p01 і р10=p01. Результати моделювання підтвердили працездатність алгоритму адаптивного вибору параметрів рівноважного коду в реальних умовах і можливість підвищення швидкості передачі.

Розглянуто питання про перспективність використання рівноважних кодів, параметри яких адаптивно змінюються за допомогою розробленого ме-тоду, на прикладі комп'ютеризованої системи управління обладнанням трубоелектрозварювального стану ТЕС 20-89 виробництва ВАТ "Сумське МНВО ім. М.В. Фрунзе". АСУ технологічним процесом виконана на базі мережі з трьох програмованих контролерів типу TSX Premium PLCs. Тип ліній зв'язку- екранована вита пара. Імовірності р10 і p01 можуть набувати будь-яких зна-чень від 10-3 до 10-6. У таких системах інформація швидко знецінюється й оновлюється з високою частотою, тому вимоги до інформаційної надійності невисокі (Vmax порядку 10-4). Аналітичним моделюванням процесів передачі даних при варіації р10 і p01 у зазначеному діапазоні встановлено, що адаптив-не рівноважне кодування у цій інформаційній системі дає можливість підви-щити швидкість передачі на 20-30% з дотриманням вимог до інформаційної надійності. На підставі результатів проведеного аналізу запропонований метод прийнятий ВАТ "Сумське МНВО ім. М.В. Фрунзе" для використання в автоматизованих системах управління технологічними об'єктами для підвищення швидкості передачі даних в нестаціонарних інформаційних каналах.

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

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

У біноміальній системі числення з параметрами n і k будь-яке біноміальне число подається двійковою кодовою комбінацією А=аr-1,...,aj,...,a0 довжиною r і задовольняє умови q0=k, r<n або q0<k, r-q0=n-k, де q0 - кількість одиничних розрядів. Кількісний еквівалент біноміального числа А визначається за функцією

, (14)

де ; ; ; .

На основі формули (14) будуються алгоритми перетворення двійкового числа у нерівномірне біноміальне та взаємно однозначного йому зворотного перетворення. Перетворення А®Xк здійснюється доповненням послідовності А молодшими одиничними або нульовими розрядами, а перетворення Yк®А - виключенням надлишкових молодших розрядів. Розроблено алгоритми [2] рівноважного кодування і декодування на основі нерівномірних біноміальних чисел. Доведено їхню перевагу відносно алгоритмічної складності порівняно з алгоритмами, побудованими на основі рівномірних біноміальних чисел.

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

Алгоритми рівноважного кодування і декодування на основі біноміальних чисел використані підприємством "Преобразователь" (м. Суми) в проекті автоматизованої інформаційно-вимірювальної системи управління, кон-тролю та обліку електроенергії для ВАТ "Сумське МНВО ім. М.В. Фрунзе". У цій системі засереджена інформаційна підсистема передачі команд телеуправління для здійснення керуючих впливів на високовольтні комутаційні аппарати і апаратуру релейного захисту та автоматики. Для передачі даних передбачається використання існуючих телефонних ліній, які характеризуються високим рівнем завад (порядку 10-4), високим ступенем асиметрії та нестаціонарності. Відповідно до діючих стандартів передачу команд телеуправління необхідно здійснювати з обмеженням Vmax=10-14.

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

У додатках наведені докази тверджень, приклади діаграм залежностей П(k), V(k), Z(k) і W(k), приклади виконання процедур вибору параметрів рівноважного коду, кодування і декодування, виведення формул для обчислення імовірноcтей Pп, Pош, Pо.о і Pн.о при моделюванні, документи про використання результатів роботи.

ВИСНОВКИ

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

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

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

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

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

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

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

7. Алгоритми адаптивного рівноважного кодування на основі біномі-альних чисел застосовані науково-виробничим колективним підприємством "Преобразователь" (м.Суми) в проекті автоматизованої системі управління, контролю і обліку електроенергії та прийняті ВАТ "Сумське МНВО ім. М.В. Фрунзе" до використання в комп'ютеризованих системах управління технологічних комплексів і в АСУ об'єднання. Розроблені програми і алгоритми використовуються в навчальному процесі Сумського державного університету.

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

1. Бережная О.В. О допустимых значениях параметров равновесного кода в системе передачи данных //Автоматика. Автоматизация. Электротехнические комплексы и системы. - Херсон: ХГТУ. - 1999. - №1. - C. 58-64.

2. Соловей В.А., Бережная О.В. Нумерация равновесных кодов на основе биномиальных чисел //Вісник Сумського державного університету. - 1994. - №2. - C. 74-77.

3. Борисенко А.А., Бережная О.В., Кулик И.А. Устройство помехоустойчивого кодирования на основе биномиальных кодов //Вісник Сумського державного університету. - 1997. - №2(8). - C. 93-96.

4. Борисенко А.А., Бережная О.В., Кулик И. А. Оценка помехоустойчивости системы передачи данных на основе равновесных кодов //Вісник Сумського державного університету. - 1999. - №1. - C. 79-82.

5. Бережная О.В. Наблюдаемость статистических характеристик процесса передачи дискретных сообщений в системе передачи данных с переспросами при использовании равновесного кода //Проблемы создания новых машин и технологий: Научные труды КГПИ. - Кременчуг: КГПИ, 1999. - Вып.1. - C. 31-36.

6. Бережная О.В. О разрешимости задачи минимизации длины равновесных кодовых комбинаций //Проблемы создания новых машин и технологий: Научные труды КГПИ. - Кременчуг: КГПИ, 2000. - Вып. 1/2000(8). - C. 353-358.

7. Бережная О.В., Борисенко А.А. Оптимизация параметров равновесного кода в адаптивной системе передачи данных //4-й Международный форум "Радиоэлектроника и молодежь в XXI веке": Научные труды ХГТУРЭ. - Харьков. - 2000. - C. 165-166.

8. Бережная О.В. Алгоритм нумерации двоичных последовательностей на основе биномиальных чисел //Научно-техническая конференция "Техника и физика электронных систем и устройств".-Сумы: СумГУ.-1995.- С. 152-153.

9. Kulik I.A., Berezhnaya O.V., Arbuzov V.V. High-speed compression methods for physical experimental results //Book of Abstracts of Second International Conference MPSL'96. - Sumy (Ukraine). - 1996. - P. 68.

10. Бережная О.В., Онанченко Ю.Е. Устройство нумерации равновесных кодов //Научно-техническая конференция преподавателей, сотрудников, аспирантов и студентов физико-технического факультета. - Сумы: СумГУ. - 1997. - С. 57.

11. Арбузов В.В., Бережная О.В. О повышении качества передачи телевизионной информации //Науково-методична конференція "Використання комп'ютерних технологій у навчальному процесі". - Харків: ХДТУРЕ. - 1997.- С. 198-199.

12. Бережная О.В., Новиков В.Б. Имитационное моделирование процесса передачи данных в адаптивных системах //Научно-техническая конференция преподавателей, сотрудников, аспирантов и студентов физико-технического факультета. - Сумы: СумГУ. - 1998. - С. 44-45.

13. Бережная О.В., Линник В.Н., Солдатенко А.В., Солдатенко О.М. Адаптивная система связи на основе равновесных кодов //Научно-техническая конференция преподавателей, сотрудников, аспирантов и студентов физико-технического факультета. - Сумы: СумГУ. - 1999. - С. 100.

14. Бережная О.В., Козачек А.В., Малярчук А.С. Алгоритм выбора параметров равновесного кода //Научно-техническая конференция преподавателей, сотрудников, аспирантов и студентов физико-технического факультета. - Сумы: СумГУ. - 2000. - С. 29.

АНОТАЦІЯ

Бережна Ольга Володимирівна. Методи та алгоритми адаптивного рівноважного кодування на основі біноміальних чисел для інформаційних систем. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології. - Харківський національний університет радіоелектроніки, Харків, 2002.

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

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

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Харьковский национальный университет радиоэлектроники, Харьков, 2002.

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

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

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

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

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

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

ABSTRACT

Berezhnaya Olga Vladimirovna. Methods and algorithms of adaptive equiponderant coding on the basis of binomial numbers for information systems. – Manuscript.

Thesis for a candidate degree of technical sciences by speciality 05.13.06 – automation control systems and progressive information technologies. – Kharkov national university of radioelectronics, Kharkov, 2002.

The dissertation is devoted to developing methods of adaptive equiponderant coding of discrete messages on the basis of binomial numbers. The method orients itself on using into information systems under circumstances of a variable noise level. On the basis of analyzing probable characteristics of noise-immunity of equiponderant codes method of adaptive selection of equiponderant code parameters is developed. Algorithms, programs and structures of devices of equiponderant coding on the basis of binomial numbers are developed. In comparison with the known ones they have less algorithmic and circuitry complexity as well are able to work at adaptively changeable parameters of an equiponderant code.

Key words: information channel, efficiency, adaptation, discrete message, equiponderant code, probability, binomial number.

Відповідальний за випуск Левикін В.М.

Підп. до друку 07.10.02 р.