Підвищення ефективності засобів виявлення помилок передачі даних в комп’ютерних системах і мережах

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

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ ”КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

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

УДК 004.052.42

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

АВТОРЕФЕРАТ

ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗАСОБІВ ВИЯВЛЕННЯ ПОМИЛОК ПЕРЕДАЧІ ДАНИХ В КОМП'ЮТЕРНИХ СИСТЕМАХ І МЕРЕЖАХ

Хазем Мох'д Саід Абдел Маджід Хатамлех

Київ - 2007

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

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

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

Офіційні опоненти: доктор технічних наук, професор Брюхович Євген Іванович, Інститут кібернетики ім.В.М. Глушкова НАН України, завідувач лабораторії кандидат технічних наук, Каліновський Яків Олександрович, Інститут проблем реєстрації інформації НАН України, старший науковий співробітник

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

Захист відбудеться ” 04 ” квітня 2007 р. о 16-00 годині на засіданні спеціалізованої ради Д 26.002.02 у НТУУ ”КПІ” (м. Київ, проспект Перемоги 37, корп.18,ауд.306)

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

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

Автореферат розісланий ” 02 ” березня 2007 р.

Вчений секретар спеціалізованої вченої ради Д 26.002.02 Орлова М.М. кандидат технічних наук, доцент

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

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

Стала тенденція зростання швидкості передачі цифрових даних в шинах обчислювальних систем та лініях комп'ютерних мереж ставить більш жорсткі вимоги до продуктивності засобів контролю помилок: вона має забезпечувати реалізацію обчислювальних операцій, пов'язаних з контролем помилок в темпі передачі даних. Вирішення проблеми забезпечення продуктивності засобів контролю, достатньої для його реалізації в темпі передачі цифрових даних на принциповому рівні може бути досягнуте тільки в рамках розпаралелювання операцій, пов'язаних з виявленням помилок. Обчислювальна процедура найбільш поширеного в комп'ютерних системах контролю помилок за допомогою циклічних надлишкових кодів (CRC - Cyclic Redundancy Codes) має принципово послідовний, побітовий характер і не може бути розпаралелена.

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

Зв'язок роботи з науковими програми, планами, темами. Дисертаційне дослідження проводилось в рамках держбюджетної теми ”Розробка цифрових систем обробки даних з високошвидкісними комутаторами” (номер держреєстрації 0102U000222).

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

Об'єктом дослідження є процеси виявлення помилок в лініях передачі даних комп'ютерних систем та мереж.

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

Основні задачі дослідження у відповідності до поставленої мети полягають у наступному:

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

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

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

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

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

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

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

Наукова новизна одержаних результатів полягає в наступному:

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

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

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

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

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

Особистий внесок здобувача полягає в теоретичному обґрунтуванні одержаних результатів, експериментальній їх перевірці та дослідженні, а також в створенні програмних продуктів для практичного використання одержаних результатів. У роботах, що написані в співавторстві, автору належать: [1] - два способи прискореного контролю помилок передачі цифрових даних за рахунок комбінованого використання циклічних кодів та контрольних сум, [2] - спосіб контролю помилок в мережних лініях з модуляцією цифрових даних, що дозволяє підвищити вірогідність виявлення домінуючих в таких лініях помилок в порівнянні з застосуванням циклічних надлишкових кодів, а також прискорити процедуру контролю за рахунок розпаралелювання відповідних обчислень при апаратній реалізації, [3] - спосіб гарантованого виявлення всіх помилок обмеженої заданим значенням парної кратності за допомогою модифікованої зваженої контрольної суми, для кодування компонент якої використовуються частково-ортогональні коди, [4] - спосіб прискорення виявлення помилок за рахунок комбінованого виявлення контрольної суми та циклічних надлишкових кодів, аналіз ефективності запропонованого способу, [5] - алгоритм отримання частково-ортогональних кодів, за допомогою яких пропонується розширити клас помилок, що гарантовано виявляються при використанні зваженої контрольної суми помилок передачі даних.

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

1. VII Міжнародній науково-технічній конференції студентів, аспірантів та молодих вчених ”Системний аналіз та інформаційні технології”, 28 червня -3 липня 2005 р., м. Київ.

2. VІІ Міжнародній науково-практичній конференції Современные информационные и электронные технологии, 22-26 травня 2006 р. м. Одеса.

3. VIII Міжнародній науково-технічній конференції студентів, аспірантів та молодих вчених ”Системний аналіз та інформаційні технології”, 13-16 вересня 2006 р., м. Київ.

Публікації Основні результати роботи викладені в 5 публікаціях, з них 3 статті в провідних фахових виданнях.

Структура та об'єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та додатків. Загальний обсяг роботи складає 157 сторінки, робота містить 14 малюнків, 10 таблиць та список використаної літератури на 96 найменувань, 2 додатки.

2. ОСНОВНИЙ ЗМІСТ

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

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

При передачі даних в комп'ютерних мережах широко застосовується цифрова модуляція, тобто одночасна передача k бітів, які складають символ, у вигляді одного модулюючого (канального) сигналу. Така модуляція цифрових даних використовується як в високочастотних лініях (телефонні лінії модемів, радіоканали), так і в низькочастотних. Для першого класу ліній, передача символу, що належить алфавіту М, реалізується з використанням спектральної модуляції, найпоширенішим видом якої є квадратурно-амплітудна модуляція (QAM-Quadrature Amplitude Modulation). Цей вид модуляції передбачає передачу символу у вигляді стрибкоподібної зміни фази і амплітуди синусоїдального несучого сигналу. В низькочастотних лініях передачі даних комп'ютерних мереж широко використовується амплітудно-імпульсна модуляція (PAM-Pulse-Amplitude Modulation).

Використання модуляції дозволяє в k разів підвищити швидкість передачі, разом з тим, ускладнюється виявлення помилок, оскільки спотворення при передачі одного сигналу (канального символу) може потенційно призвести до спотворення до k бітів даних. Відповідно, в сучасних системах передачі даних з використанням модуляції, для яких значення k лежить в інтервалі від 4 до 8-ми, навіть одиночна помилка передачі сигналу може призвести до 4-8 бітових спотворень. Проведений аналіз показав, що для модемних ліній кількість виникаючих помилок передачі канальних сигналів практично підпорядкована біноміальному закону розподілу. Це означає, що засоби виявлення помилок мають гарантовано виявляти бітові спотворення, зумовлені помилками при передачі до 2-3-х канальних сигналів.

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

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

Огляд протоколів виявлення помилок передачі даних в комп'ютерних системах і мережах показав, що найбільш поширеними засобами контролю помилок є циклічні надлишкові коди (Cyclic Redundancy Code - CRC), та контрольні суми (Checksum-CS). Значно рідше для виявлення помилок застосовуються коди Хемінга.

При використанні CRC гарантовано виявляються всі помилки непарної кратності, подвійні помилки, а також помилки, локалізовані в межах групи бітів, довжина якої не перевищує ступеню q утворюючого поліному CRC. Для ліній передачі даних комп'ютерних систем помилки останнього типу трапляються достатньо рідко. Інші помилки виявляються при застосуванні CRC з ймовірністю 1-2-q. На практиці, при використання 16-розрядного контрольного коду CRC-16 ймовірність невиявлення 4-кратної помилки при передачі блоку достатньо мала, проте, вважаючи на велику кількість інформації, що передається по лініях комп'ютерних систем, існує реальна можливість того, помилка вказаної кратності не буде виявлена. Тобто, з точки зору достовірності контролю, недоліком CRC є те, що при його застосуванні для ліній, що відповідають моделі двійкового симетричного каналу не гарантується виявлення 4-х кратних помилок. Для ліній з М-арною модуляцією цифрових даних, CRC не гарантує виявлення бітових спотворень, зумовлених 2-3 кратними помилками передачі канальних сигналів. Це дозволяє зробити висновок, що недоліком CRC являється вузький клас помилок, які гарантовано виявляються при його застосуванні.

Інший важливий недолік CRC полягає в тому, він передбачає принципово послідовний характер обробки бітів блоку даних, правильність передачі якого контролюється. Час tCRC формування контрольного коду CRC при передачі m-бітового блоку даних становить tCRC = m(txor + tsh), де txor та tsh - проміжки часу, що потребуються на додавання за модулем 2 та зсув k-розрядного коду, відповідно. Особливо гостро стоїть проблема реалізації обчислення контрольного коду CRC в темпі передачі даних стоїть для паралельних каналів, які складаються з n ліній. В цьому випадку контроль в темпі передачі даних може бути реалізований лише за виконання умови:

,

де -темп передачі n-розрядних символів.

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

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

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

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

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

При передачі m-бітового блоку B = {b1,b2,…,bm},j{1,…,m}:bj{0,1}, і використанні CS, блок розділяється на t=m/n n-бітових символів: Х1,Х2,…,Xt. При використанні звичайної CS контрольний код обчислюється як побітова сума за модулем 2 всіх символів блоку: CS=X1X2…Xt. При цьому клас помилок, що гарантовано виявляється включає лише помилки непарної кратності. Подвійні помилки виявляються з ймовірністю 1-n-1. При зростанні кратності помилок, ймовірність їх виявлення поступово підвищується, асимптотично наближуючись до 1-2-n - рівня, що забезпечується при застосуванні CRC, ступінь утворюючого поліному якого дорівнює n. Таким чином, ймовірність виявлення помилок за допомогою CS найменша для найбільш частого типу помилок парної кратності - двократних. Причиною цього є неефективність кодування домінуючих на практиці одиночних помилок при передачі символу, зумовлена тим, що n-розрядний код різниці контрольних сум передавача і приймача в випадку одиночних помилок при передачі двох символів Хd і Хu, d,u{1,…,t}: не залежить від кодів символів Хd та Хu і може приймати лише n2 значень з 2n можливих.

Для підвищення виявлення домінуючих на практиці парних помилок невеликої кратності за допомогою контрольної суми розроблено ряд її модифікацій, основними з яких є коди Хемінга та зважена CS. Коди Хемінга передбачають спеціальний порядок вибору бітів повідомлення, що входять до кожного з символів, причому, на відміну від традиційної контрольної суми, множини бітів, що входять до кожного з символів перетинаються. Завдяки цьому коди Хемінга забезпечують можливість розширення класу помилок, що виявляються гарантовано. Проте таке розширення виявляє суттєвий недолік кодів Хемінгу: швидке зростання розрядності символу , а відповідно і кількості контрольних розрядів. Так, гарантоване виявлення двократних помилок забезпечується застосуванням двовимірної контрольної суми Хемінга, при цьому розрядність контрольної суми має становити . Для гарантованого виявлення помилок кратністю 4 потрібно використовувати 3-вимірну контрольну суму Хемінга, яка передбачає наявність контрольних розрядів. Наприклад, гарантоване виявлення 4-кратних помилок передачі блоку, довжиною 1 Кбіт з використанням контрольної суми Хемінга потребує 305-ти контрольних розрядів.

Підвищення ймовірності виявлення парних помилок невеликої кратності досягається застосуванням зваженої контрольної суми, базова ідея якої полягає в тому, що компонентами контрольного коду є не самі символи, а результат певного функціонального перетворення над ними. При цьому модифікована контрольна сума обчислюється у вигляді: , де f - функція кодування символу. Основна ціль використання функції f - функції кодування полягає в збільшенні інформації, що міститься в коді різниці відповідних компонент f(XjS) та f(XjR) контрольної суми на передавачеві і приймачеві при виникненні помилки передачі j-то символу Xj. В якості функцій кодування пропонувалося застосовувати булеві функції, що задовольняють критерію лавинного ефекту (Strict Avalanche Criterion-SAC), а також функції, що мають максимальну диференційну ентропію. Використання таких функцій кодування зваженої контрольної суми дозволяє підвищити ймовірність виявлення двократних помилок до рівня 1-2-n. Проте, доведено, що за умови, коли функція f кодування залежить лише від коду символу, принципово неможливо розширити клас помилок, які гарантовано виявляються зваженою контрольною сумою. Для вирішення цієї задачі необхідно застосовувати функцію f кодування, що залежить не тільки від коду Х символу, але й від його номеру в блоці, передача якого контролюється. В рамках цієї ідеї пропонувався варіант зваженої контрольної суми, використання якого забезпечує гарантоване виявлення лише всіх подвійних помилок.

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

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

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

Для гарантованого виявлення помилок парної кратності, яка не перевищує h пропонується спосіб, що являє собою модифікацію зваженої контрольної суми. Сутність способу полягає в тому, що в якості компонент зваженої контрольної суми пропонується використання частково-ортогональних кодів. Частково-ортогональні коди (коди з обмеженою ортогональністю) являють собою множину ?m={U1,U2,…,Um}, яка складається з m k-бітових кодів U1,U2,…,Um таких, що сума за модулем 2 будь-якої їх підмножини , яка включає не більше h кодів не дорівнює нулю.

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

де ah - коефіцієнт, який залежить від h, для h=4 ah 2.3, а для h=6 ah 3.65. Виходячи з того, що для z >m: mz, розроблено ітераційний алгоритм генерації множини m , за допомогою якого побудована таблиця значень частково-ортогональних кодів для h=4. Спираючись на те, що множина m для h=6 - є підмножиною m для h=4- , запропоновано алгоритм генерації множини і побудовано відповідну таблицю частково-ортогональних кодів для h=6. Запропонована модифікація зваженої контрольної суми, яка забезпечує гарантоване виявлення 4-кратних або 6-кратних помилок передбачає використання відповідних таблиць.

Нехай блок В даних складається з m бітів: B={b1,b2,…,bm}, bi{0,1}, i=1,…,m. Для заданої парної кратності h помилок, що мають гарантовано виявлятися завжди можна сформувати множину ?={U1,U2,…,Um} частково-ортогональних кодів. За запропонованим способом модифікована контрольна сума CS формується, як сума за модулем 2 m (k+1)-розрядних компонент W1,W2,…,Wm: CS=W1W2…Wm. Кожна j-та компонента Wj, j{1,…,m}, визначається значенням однойменного біту bj та j-тим частково-ортогональним кодом Uj. При цьому компонента Wj утворюється як конкатенація j-того біту bj блока В та логічного добутку цього біту на кожен з розрядів коду Uj: . Рішення про наявність помилок передачі блоку даних приймається при відмінні від нуля (k+1)-розрядного коду різниці контрольних сум передавача CSS та приймача CSR : , причому компоненти коду визначаються наступним чином:

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

При виникненні помилок парної кратності d h , номери d спотворених утворюють множину : dі. Біт 1 коду різниці контрольних сум передавача та приймача дорівнює нулю в силу того, що d mod 2 = 0, а значення k-бітової компоненти Z коду визначається формулою:

В силу властивості (2) частково-ортогональних кодів Z0, а відповідно і 0. Так, якщо контролюється передача блоку В довжиною 1 Кбіт (m=1024) з гарантованим виявленням помилок парної кратності, яка не перевищує 4 (h=4), то розрядність контрольного коду, згідно (3) дорівнюватиме k+1=24. При виникненні 4-кратної помилки будуть спотворені, наприклад, наступні біти b167,b717,b718,b1016 блоку. Відповідно, Z=(U167 U717 U718 U1016) = (108B0h

360F18h 365869h 85690Ch ) = 8436CDh. Тобто, помилки, парна кратність яких не перевищує наперед заданого порогового значення h >2 гарантовано виявляються при використання запропонованої модифікації зваженої контрольної суми, на відміну від відомих різновидів контрольних сум та CRC. Таким чином, розроблений спосіб формування зваженої контрольної суми забезпечує суттєве розширення класу гарантовано виявляємих помилок в порівнянні з відомими засобами контролю передачі цифрових даних. кодування шифр модифікація спектральний

Доведено, що ймовірність виявленні помилок парної кратності більшої за h визнаяється як 1-2-(k+1), і таким чином, практично співпадає з аналогічним показником CRC за умови однакової кількості контрольних розрядів, тобто, якщо ступінь утворюючого полінома CRC дорівнює k+1.

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

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

Контрольний код V символу Х пропонується формувати з k+1 бітових полів. Кожне і-те з перших k полів, i=1,…,k, пропонується обчислювати як логічний добуток відповідного і-того біту xi символу Х на q- розрядний код Wi : Vi = xi Wi, де q = log2t. Кожний з k кодів, що використовуються при формуванні j-го контрольного коду Vj : Wji = {wji1,wji2,…,wjiq}, wjiy{0,1}, y{1,…,q}, j{1,…,t}, i{1,…,k}, однозначно пов'язаний з номером j символу Xj в блоці. Коди Wj1, Wj2, …, Wjk є відмінними між собою для всіх j{1,…,t}. Одним з можливих варіантів формування вказаних кодів є використання q-розрядного зсувного регістру з періодом повторення t. Останнє, (k+1)-те поле контрольного коду V складається з k бітів символу Х: Vk+1 = X={x1,x2,…xk}. Таким чином, загальна довжина контрольного коду становить LV = LCS = k(log2(m/k) + 1). Наприклад, при довжині блоку в 2048 байтів і використанні 16-QAM (k=4), розрядність контрольної суми становитиме 4(12+1) = 52. Контрольна сума CS також складається з k полів: CS = {CS1,CS2,…,CSk,CSk+1}, кожне з яких являє собою суму за модулем 2 відповідних полів контрольних кодів символів . Код різниці контрольних сум передавача CSs і приймача CSr також складається з k+1 полів: = {1,2,…,k,k+1}: l = CSsl CSrl, l=1,…,k+1.

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

При спотворенні двох символів Xu і Xg вони відрізняються на приймачеві та передавачеві, тобто: Xsu={xsu1,xsu2,…,xsuk} Xru={xru1,xru2,…,xruk} та Xsg={xsg1,xsg2,…,xsgk} Xrg={xrg1,xrg2,…,xrgk}. Код i-того поля i, i{1,…,k) різниці при помилковій передачі Xu і Xg може бути представлений у вигляді:

В силу того, що Wui Wgi, то в усіх випадках, окрім xsui = xrui та xsgi = xrgi, код i-того поля i різниці контрольних сум приймача та передавача не дорівнює нулю: i 0. Проте згадана умова не може одночасно виконуватися для всіх k полів 1,2,…,k, оскільки XsuXru та Xsg Xrg. Таким чином, запропонований спосіб формування контрольної суми забезпечує гарантоване виявлення від 2-х до 2k помилок, зумовлених спотворенням двох модульованого сигналів. Наприклад, якщо використовується модуляція 16-QAM (k=4) і блок складається з 4-х байтів (8-ми символів), то k=4. Якщо послідовність W формується 3-розрядним зсувним регістром з функцією зворотного зв'язку f(W) = w1 w3 w2w3 1, то послідовність W={0,1,2,5,3,7,6,4}. Нехай, в процесі передачі 2-й та 8-мий символи спотворюються: наприклад в 2-му символі змінюються біти х1 і х2, а в 8-му всі 4 біти, тобто вектор помилки має вигляд E=0C000000Fh. Для другого символу W21 = 1, W22 = 0, W23 = 4, W24 = 6. Для восьмого символу: W81 = 4, W82 = 6, W83 = 7, W84 =3. Значення першого поля різниці 1 має вигляд:

Аналогічно:

Таким чином, для наведеного прикладу 0, відповідно помилка передачі двох модулюючих сигналів, яка викликала спотворення 6-ти бітів блоку виявлена на відміну від CRC-16, який ці помилки не виявляє.

При виникненні трикратної помилки передачі модулюючого сигналу потенційно існує можливість спотворення до 3k бітів блоку, проте при використанні запропонованого способу їх виявлення, код різниці контрольних сум передавача і приймача також гарантовано не буде дорівнювати нулю. Нехай, помилково передані символи Xu, Xg, Xe , з номерами в блоці u,g і е. Кожна i-та компонента (k+1)-го поля k+1= {(k+1).1,(k+1).2,…,(k+1).k } коду різниці контрольних сум буде дорівнювати:

Враховуючи, що коди, які входять до кожної із пар <Xsu , Xru >, <Xsg,Xrg> та <Xse, Xre> відмінні між собою, тобто Xsu Xru, Xsg Xrg и Xse Xre , рівність нулю всіх бітових компонент (k+1).1, (k+1).2,…,(k+1).k поля 5 можливо лише за умови існування біту з номером {1,…, k } такого, що його значення відрізняються на передавачеві і приймачеві для пари з кодів Xu, Xg, Xe і в одному з цих кодів співпадають. Без порушення узагальненості можна вважати, що xsu xru, xsg xrg і xse = xre. Тоді поле різниці контрольних сум передавача і приймача може бути представлено в вигляді:

В силу того, що WuWg, то в випадку коли поле k різниці контрольних сум передавача і приймача дорівнює нулю: k = 0, його поле 0, відповідно, 0. Таким чином запропонований спосіб формування зваженої контрольної суми забезпечує гарантоване виявлення всіх бітових спотворень блоку даних, викликаних трьома помилками передачі модулюючих сигналів. Цілком очевидним є те, що використання CRC не забезпечує такої можливості, тобто має меншу достовірність виявлення помилок цього класу.

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

Наприклад, при передачі 2048 байтів і використанні 16-QAM (k=4), t=4096, чисельне значення ймовірності Р4 становить 1.510-8.

Якщо кількість d помилок передачі канальних сигналів більша за 4-х, то вони потенційно можуть бути не виявлені лише тоді, коли спотворені помилками однойменні біти, локалізовані в парній кількості помилкових символів ne, причому d ne4. Доведено, що ймовірність Pd такої ситуації, тобто ймовірність того, що помилка передачі d канальних сигналів (d>4), яка потенційно спотворює від d до dk бит блока, не виявляється запропонованою модифікацією зваженої контрольної суми, визначається згідно з наступною формулою:

В таблиці 1 наведені чисельні значення ймовірностей Pd для різних значень d - кратності помилки канальних символів при передачі 2048 байтів і використання модуляції 16-QAM (k=4), t=4096.

Таблиця 1 - Ймовірність Pd невиявлення d-кратної помилки передачі модулюючого сигналу 16-QAM (k=4) при довжині блоку 2048 байт (t=4096).

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

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

В першому варіанті блок даних поділяється на h q-розрядних субблоків S1,S2,…,Sh, де q=m/h, причому, кожний i-тий субблок Si = {bi,bi+h,…,bm-h+i}, i{1,…,h} включає біти, що відстоять в блоці В один від іншого на h бітових позицій, починаючи з i-того.

Відповідно, біти кожного із субблоків передаються по лінії в темпі /h, тобто в h разів меньшим в порівнянні з темпом передачі бітів блоку В. Для кожного з субблоків S1,S2,…,St незалежно обчислюються k-розрядні залишки від ділення на утворюючий поліном CRC: U1,U2,…,Uh. Крім того, для кожного i-того з субблоків обчислюється біт парності: rj=bibi+h…bm-h+i. Частковий контрольний код кожного i-того субблока Si розрядністю k+1 формується як конкатенація відповідного залишку Ui та біту парності ri : Qi=Ui||ri. Контрольний код DB блока В утворюється як конкатенація k-розрядного коду H і біту парності r0 : DB = H||r0. В свою чергу, коди H и r0 обчислюються як сума за модулем 2 кодів залишків U1,U2,…,Uh і бітів парності r1,r2,…,rh всіх субблоків:

Обчислення часткових контрольних кодів Q1,Q2,…,Qh при апаратній реалізації виконуються незалежно і паралельно. Число h субблоків визначається виходячи з умови реалізації виявлення помилок в темпі передачі даних:

Час tD формування (k+1)-розрядного контрольного коду DB блока в визначається у відповідності з виразом:

Оцінка надійності описаного варіанта комбінованого використання CRC та CS може бути виконана наступним чином. Виходячи з того, що до складу контрольного коду DB блока входить біт парності r0 = r1r2…rh = b1b2…bm, то помилка непарної кратності виявляється гарантовано. Подвійна помилка, яка спотворює два біти одного субблоку Si, в силу властивостей CRC має наслідком зміну однойменного залишку Ui. Відповідно, змінюється і код DB , тобто така помилка також гарантовано виявляється.

Доведено, що всі інші помилки, що виникають при передачі блоку не виявляються з ймовірністю 2-(k+1).

Для гарантованого виявлення всіх подвійних помилок, запропонована схема комбінованого використання CRC і CS може бути модифікована наступним чином. До контрольного коду DB блока додається log2h - розрядне поле L: DB = H||r0||L. Код L являє собою суму за модулем 2 логічних додатків бітів парності субблоків на двійкові коди номерів відповідних субблоків: L = r11r22r33…rhh.

В разі виникнення подвійної помилки, яка спотворює по одному біту різних субблоків, наприклад, l-того і t-того, де l,t {1,…,h},lt, змінюються їх біти парності: rl і rt , відповідно, зміна L коду L являє собою суму за модулем 2 двійкових номерів l та t : L = lt . Цілком очевидно, що сума за модулем 2 двох різних кодів не дорівнює нулю: L0. Таким чином, і різниця контрольних кодів на передавачеві і приймачеві не дорівнює нулю: DB0. Це означає, що подвійна помилка завжди буде гарантовано виявлена. Доведено, що в описаному варіанті, ймовірність того, що помилка парної кратності більша 2-х не буде виявлена становить

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

Сутність другого варіанту комбінованого використання CRC та CS полягає в тому, що над кожним з n-бітових символів X={x1,x2,…,xn} блоку виконується лінійне перетворення, результатом якого є код Y={1(X),2(X)…,s(X)}, розрядністю s=1+log2n. Контрольний код блоку обчислюється шляхом віднаходження залишку від ділення коду V, що є конкатенацією всіх t кодів Y блоку: V=Y1||Y2||…||Yt на утворюючий поліном CRC.

Перші s-1 лінійні функції 1,2,…,s-1 перетворення вибираються таким чином, щоб кожна з двійкових змінних x1,x2,…,xn входила в якості лінійної компоненти хоча б в одну з функцій 1,2,…,s-1 і не існувало пари змінних, що одночасно входять або не входять я якості лінійної компоненти до всіх s-1 функцій 1,2,…,s-1. Вказаній умові задовольняє система log2n функцій двійкового шифратора на n входів. Ще одна, s-та функція s лінійного перетворення являє собою суму за молем 2 всіх змінних x1,x2,…,xk.: s= x1x2…xk .

При спотворенні непарної кількості бітів символу Х зміниться значення старшого, s-того розряду відповідного коду Y в силу того, що зміниться значення функції парності s(Х). У випадку спотворення двох бітів символу Х, змінить своє значення хоча б одна з функцій 1,2,…,s-1 в силу вказаних вище їх властивостей. Таким чином, запропоноване лінійне перетворення забезпечує безумовну зміну коду Y при зміні непарного числа або двох розрядів символу Х. Якщо ступінь k утворюючого поліному CRC більша за розрядність n символу X: k > log2n, то зміна коду Y завжди буде мати наслідком зміну контрольного коду CRC, а, відповідно, різниця контрольних кодів передавача та приймача не буде дорівнювати нулю.

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

Наприклад, при виявленні помилок в 32-бітовій шині РСІ (n=32), час, що витрачається на обчислення, пов'язаних з контролем помилок, зменшується практично в 5 разів порівняно з використанням CRC.

ВИСНОВКИ

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

Основні наукові і практичні результати полягають у наступному:

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

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

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

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

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

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

1. Хазем Мохд Саид Абдель Маджид Хатамлех. Повышение производительности контроля ошибок передачи данных // Вісник Національного технічного університету „КПІ”. Інформатика, управління та обчислювальна техніка.-К.: ВЕК+.-2006.- № 45.-С.67-75.(Дисертантом запропоновано два способи прискорення контролю помилок передачі даних за рахунок комбінованого використання циклічних кодів та контрольних сум, виконано аналіз їх ефективності).

2. Самофалов К.Г., Хазем Мохд Саид Абдель Маджид Хатамлех, Антоненко А.А. Модификация контрольной суммы для эффективного контроля ошибок в каналах передачи данных компьютерных сетей. // Проблеми інформатизації та управління. Збірник наукових праць НАУ, - Київ: НАУ - 2006 - Випуск 1(16).- С.134-141. (Дисертантом запропоновано спосіб контролю помилок в мережових лініях з модуляцією цифрових даних, що дозволяє підвищити вірогідність виявлення домінуючих в таких лініях помилок в порівнянні з застосуванням циклічних надлишкових кодів, а також прискорити процедуру контролю за рахунок розпаралелювання відповідних обчислень при апаратній реалізації).

3. Абу Усбах А.Н., Хазем Мохамед Саид Абдель Маджид Хатамлех, Метлашевская Е.Ю. К проблеме повышения надежности обнаружения ошибок передачи данных методом контрольных сумм // Вісник Національного технічного університету „КПІ”. Інформатика, управління та обчислювальна техніка. № 45,ВЕК+,- 2005.- С.159-166. (Дисертантом запропоновано спосіб гарантовано виявлення всіх помилок обмеженої заданим значенням парної кратності за допомогою модифікованої зваженої контрольної суми, для кодування компонент якої використовуються частково-ортогональні коди).

4. Хазем Мохд Саид Абдель Маджид Хатамлех, Антоненко А.А. Об одном подходе к повышению скорости контроля ошибок цифровых данных// Тезисы 8-й международной конференции ”Системный анализ и информационные технологии”,Киев,- 2006.-С.254-257.(Дисертантом запропоновано спосіб прискорення виявлення помилок за рахунок комбінованого виявлення контрольної суми та циклічних надлишкових кодів, аналіз ефективності запропонованого способу).