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

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

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

(Йорданія)

УДК 004.052.42

ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗАСОБІВ ВИЯВЛЕННЯ

ПОМИЛОК ПЕРЕДАЧІ ДАНИХ В КОМП’ЮТЕРНИХ

СИСТЕМАХ І МЕРЕЖАХ

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

АВТОРЕФЕРАТ

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

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

Київ 2007

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

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

Науковий керівник – член –кореспондент Національної Академії Наук

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

Самофалов Костянтин Григорович,

НТУУ ”КПІ”, радник ректора

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

Брюхович Євген Іванович,

Інститут кібернетики ім.В.М.Глушкова НАН

України, завідувач лабораторії

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

Каліновський Яків Олександрович,

Інститут проблем реєстрації інформації

НАН України, старший науковий співробітник

Провідна установа: Інститут проблем моделювання в енергетиці

ім. Г.Є.Пухова НАН України, відділ

математичного і економетричного моделювання

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

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

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

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

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

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

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

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

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

Стала тенденція зростання швидкості передачі цифрових даних в шинах обчислювальних систем та лініях комп’ютерних мереж ставить більш жорсткі вимоги до продуктивності засобів контролю помилок: вона має забезпечувати реалізацію обчислювальних операцій, пов’язаних з контролем помилок в темпі передачі даних. Вирішення проблеми забезпечення продуктивності засобів контролю, достатньої для його реалізації в темпі передачі цифрових даних на принциповому рівні може бути досягнуте тільки в рамках розпаралелювання операцій, пов’язаних з виявленням помилок. Обчислювальна процедура найбільш поширеного в комп’ютерних системах контролю помилок за допомо-гою циклічних надлишкових кодів (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 додатки.

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

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

У першому розділі дисертації виконано аналіз сучасного стану проблеми забезпечення надійності передачі даних в шинах комп’ютерних систем та лініях мереж. Більшість ліній передачі інформації комп’ютерних систем можна розглядати як низькочастотний канал з імпульсно-кодовою модуляцією двій-кових кодів. З точки зору характеру виникнення помилок, теоретичною модел-лю таких ліній є двійковий симетричний канал з відносно невеликою інтенсив-ністю помилок. Вважаючи на відносно невелику інтенсивність виникнення помилок, для забезпечення надійності передачі в комп’ютерних системах переважно вико-рис-товують виявлення помилок і їх виправлення шляхом пов-тор-ної передачі на противагу корегуючим кодам, застосування яких при малій інтенсивності помилок малоефективне. Виходячи з теоретичної моделі двій-кового симетричного каналу помилки передачі даних в таких лініях можна розглядати як незалежні одна від одної, а кількість помилок, що виникає при передачі блоку даних підпорядкована біноміальному закону розподілу. З цього випливає, що найбільш важливим при організації контролю правильності передачі в таких лініях, є гарантоване виявлення помилок відносно малої кратності (до 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 ліній. В цьому випадку контроль в темпі передачі даних може бути реалізований лише за виконання умови:

(1)

де -темп передачі 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=X1X2Xt. При цьому клас помилок, що гарантовано виявляється включає лише помилки непарної кратності. Подвійні помилки виявляються з ймовірністю 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 кодів не дорівнює нулю.

(2)

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

(3)

де 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=W1W2Wm. Кожна 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).

d | Pd | d | Pd | 5 | 8.510-12 | 6 | 2.010-11 7 | 2.410-12 | 8 | 8.910-13 9 | 2.610-13 | 10 | 7.610-14

Аналіз наведених в таблиці 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, а, відповідно,