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

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

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

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

Алі Тауфік Окла Аль-Хавальді

(Йорданія)

УДК 004.052.42

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

ЗАСТОСУВАННЯ КОНТРОЛЬНИХ СУМ, ЕХОПЛЕКСУ ТА

ЦИКЛІЧНИХ КОДІВ ДЛЯ ВИЯВЛЕННЯ ПОМИЛОК ПЕРЕДАЧІ

ДАНИХ В КОМП'ЮТЕРНИХ СИСТЕМАХ І МЕРЕЖАХ

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

АВТОРЕФЕРАТ

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

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

Київ 2006

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

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

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

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

доктор технічних наук, професор Зайченко Юрій Петрович, НТУУ ”КПІ”, професор кафедри математичних методів системного аналізу Інституту прикладного системного аналізу при НТУУ ”КПІ”

кандидат технічних наук, Селігей Олександр Минович, Кременчуцький державний політехнічний університет, доцент кафедри комп'ютерних та інформаційних систем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. V Міжнародній науково-практичній конференції ” Современные информационные и электронные технологии, 17-21 травня 2004 р. м. Одеса.

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

3. V Міжнародній науково-практичній конференції Проблеми впровадження інформаційних технологій в економіці, 13-14 травня 2004 р. м. Ірпінь.

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

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

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

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

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

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

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

де р - ймовірність полки при передачі одного біту.

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

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

Основними чинниками ефективності засобів контролю помилок є надійність їх виявлення та продуктивність реалізації обчислень, пов'язаних з контролем. Проведений аналіз тенденцій розвитку засобів передачі інформації в системах та мережах обчислювальної техніки показав, що по мірі зростання швидкості передачі даних збільшується значимість фактору продуктивності контролю, який для більшості використань має виконуватися в темпі передачі інформації. Виконаний огляд засобів контролю помилок показав, що цим чинником суттєво знижується ефективність найпоширенішого на практиці способу виявлення помилок за допомогою циклічних надлишкових кодів (Cyclic Redundancy Code -CRC), процедура обчислювальної реалізації якого має принципово послідовний характер. CRC широко використовується для виявлення помилок передачі даних в послідовних (USB) та паралельних (PCI) шинах комп'ютерних систем. Застосування CRC дозволяє виявляти всі помилки непарної кратності, а також двократні помилки, тобто забезпечує гарантоване виявлення домінуючих в лініях передачі даних комп'ютерів помилок. Суттєвим недоліком в сучасних умовах є принципово послідовний характер обчислень, необхідних для визначення контрольного коду CRC, як залишку від ділення поліномів. Традиційна схема апаратного обчислення контрольного коду CRC на основі зсувного регістру дозволяє лише побітову обробку блоку цифрових даних. Особливо критичною є послідовний характер обчислення контрольного коду CRC для паралельних шин передачі даних комп'ютерних систем, зокрема для РСІ.

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

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

Для бінарного симетричного каналу ймовірність того, що двократна помилка не буде виявлена з використанням традиційної контрольної суми визначається виходячи з наступних міркувань: загальна кількість вариантів локалізації двох помилок при передачі m-бітового блоку B складає m(m-1)/2, в то час, як кількість варіантів локалізації пари помилок в однойменних розрядах символів - m(m/n-1)/2. Таким чином, ймовірність Р₂₀ того, що двократна помилка не буде виявлена з використанням традиційної контрольної суми визначається наступним чином:

Причиною достатньо високої ймовірності невиявлення двократних помилок традиційною контрольною сумою є неефективність кодування домінуючих на практиці одиночних помилок при передачі символу, зумовлена тим, що n-розрядний код різниці контрольних сум передавача і приймача для одного символу Х: не залежить від коду символу Х і може приймати лише n+1 значень з 2ⁿ можливих. Разом з тим, традиційна контрольна сума в достатній мірі ефективно кодує помилки великої кратності, що виникають при передачі одного символу. Аналіз показав, що надійність виявлення таких помилок контрольною сумою близька до надійності їх виявлення з використанням CRC. Проте такий тип помилок рідко зустрічається на практиці. Таким чином, низька надійність виявлення помилок, що домінують в реальних лініях передачі даних зумовлена малою ефективністю кодування компонентів контрольної суми.

Для підвищення ефективності кодування компонентами контрольної суми домінуючого типу помилок доцільно застосовувати спеціальні функції кодування. Зокрема, відомо про використання в якості функцій кодування контрольної суми систем функцій, що задовольняють критерію лавинного ефекту (Strict Avalanche Criterion-SAC). При використанні таких функцій кодування ймовірність P_2f того, що двократна помилка не буде явлена визначається формулою:

При використанні SAC-функцій для кодування компонентів контрольної суми та за умови виникнення подвійної помилки, код приймає n!/((n/2)!)² різних значень і, відповідно, ймовірність невиявлення двократної помилки суттєво зменшується в порівнянні зі звичайною контрольною сумою. Проте, при цьому число варіантів - n!/((n/2)!)² кодування двократної помилки суттєво менше теоретично можливого числа варіантів коду - 2ⁿ. Це означає, що при використанні для кодування SAC-функцій не достягається оптимізація кодування компонент контрольної суми. Використання такого кодування не забезпечує виявлення всіх двократних помилок, що гарантовано при застосуванні для контролю CRC.

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

Засобом оперативного виявлення помилок в дуплексних лініях передачі є ехоплекс, використання якого регламентується стандартом ITU-T ISDN.

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

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

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



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

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

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

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

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

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

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

Оптимізація кодування одиночної помилки досягається, якщо булеві функції f₁,f₂,…,f_m, що складають диференційне перетворення можуть бути представлені у вигляді двох підмножин _{1 і 2}. Перша з них ₁ включає n-1 функцій f₁,f₂,…,f_n-1 таких, що їх диференціали за будь-якою із змінних утворюють ортогональну систему:

Ця властивість забезпечує оптимальність кодування помилки в кожному біті символу, тобто однозначну залежність коду помилки від значень всіх інших розрядів символу, що не змінилися в процесі передачі. Для ефективного кодування номеру спотвореного розряду, диференціал булевих функцій, що складають другу підмножину ₂={f_n, f_n+1, …, f_m} має однозначно визначати цей номер. Вказана умова забезпечується, якщо і двійковий код, утворений диференціалом функцій по j-тій змінній x_j дорівнює j-1:

Нижче наведено приклад системи булевих функцій від 8-ми змінних (n=8), яка задовольняє сформульованим вище вимогам:

Диференціали по будь-якій з 8-ми змінних перших 7-ми функцій, що становлять підмножину ₁ утворюють систему ортогональних булевих функцій від змінних, що не змінилися. Наприклад, диференціали по 4-й змінній х₄ утворюють систему лінійних функцій від всіх змінних крім х₄:

Диференціали функцій f₈, f₉, f₁₀ по булевій змінній x₄ дорівнюють:

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

x₄: j-1=011₂=3.

Для гарантованого виявлення помилок непарної кратності представляється доцільним ввести до складу контрольного коду V біт v₁ парності. Цей біт формується як сума за модулем 2 всіх розрядів коду символу Х: v₁ = x₁ x₂…x_n. Відповідний біт s₁ контрольної суми обчислюється у вигляді:

,

тобто являє собою суму за модулем 2 всіх бітів контрольованого блоку В. Таким чином, біт s₁ дозволяє виявити будь-яку кількість непарних помилок передачі.

Двократна помилка може виникнути або у вигляді однобітового спотворення двох символів, або у вигляді спотворення двох розрядів одного символу.

Для гарантованого виявлення помилок першого типу пропонується використання в контрольному коді поля з q = log₂t контрольних розрядів, що позначаються як v₂,v₃,…,v_q+1, кожен i-тий, i{2,…,q+1} з яких являє собою логічний добуток біту v₁ на (i-1)-й біт двійкового представлення номера W={w₁,w₂,…,w_q} символу в блоці: . Кожний i-тий біт контрольної суми обчислюється як: . Відповідний i-тий розряд коду різниці контрольних сум формується у вигляді:

.

При виникненні помилки передачі будь-якого одного біту j-го символу X_j та одного биту g-го символу X_g: . Відповідно, кожний і-тий розряд _і коду трансформується до вигляду: . Оскільки

та j g,

то u{2,…q+1}: ,

тобто серед розрядів з 2-го по (q+1)-тий: ₂, ₃,…,_q+1 коду буде хоча б один, який не дорівнює нулю. Це означає, що двократна помилка, яка виникла у вигляді однобітових помилок при передачі двох різних символів буде гарантовано виявлена.

Гарантоване виявлення двократної помилки, що виникає у вигляді спотворення двох розрядів одного символу пропонується реалізувати шляхом введення до складу контрольного коду додаткової групи з h=log₂n бітів, які позначаються як v_q+2, v_q+3, …,v_q+h+1. Ці біти являють собою лінійні функції ₁,₂,…,_h, що визначені на множині бітів коду символу Х={x₁,x₂,…,x_n}: v_q+2=₁(X), v_q+3=₂(X),…,v_q+h+1=_n(X). Система ₁,₂,…,_h вибирається таким чином, щоб не існувало пари змінних таких, що вони обоє входять, або обоє не входять в якості лінійних компонент до всіх з h лінійних функцій ₁,₂,…,_h. Цим умовам задовольняють функції двійкового шифратора на n входів.

При виникненні двократної помилки, яка має наслідком спотворення двох бітів x_N та x_R символу Х, біти _q+2, _q+3, …,_q+h+1 коду різниці контрольних сум передавача і приймача, утворюють двійковий код, який дорівнює сумі за модулем 2 номерів спотворених бітів в символі:

.

В силу того, що обидва біти x_N та x_R не входять в якості лінійних компонент всіх лінійних функцій ₁,₂,…,_h, то сума диференціалів по змінним x_N та x_R хоча б для однієї з лінійних функцій не дорівнює нулю. Це означає, що хоча б один з бітів _q+2, _q+3, …,_q+h+1 коду різниці контрольних сум не дорівнює нулю і, відповідно, двократна помилка цього типу буде безумовно виявлена.

Наприклад, якщо символ є байтом X={x₁,x₂,…,x₈} (n=8) і кількість байтів в блоці дорівнює 2048, то відповідно t=2048, q = log₂t = 11, h=log₂n =3. Розрядність контрольного коду становить 15. Для формування контрольних бітів v₁₃,v₁₄,v₁₅ можуть використовуватися лінійні булеві функції двійкового шифратора на 3 входи: ₁=x₂x₄x₆x₈ , ₂=x₃x₄x₇x₈, ₃=x₅x₆x₇x₈. При виникненні помилок передачі двох бітів символу, наприклад, 3-го (N=3) та 7-го (N=3) біти ₁₃, ₁₄, ₁₅ різниці контрольних кодів передавача та приймача формуються у вигляді:

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

Таким чином, доведено, що запропонований спосіб кодування компонент контрольної суми розрядністю 1 + log₂t + log₂n забезпечує гарантоване виявлення всіх помилок непарної кратності та всіх двократних помилок.

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

Наприклад, якщо символ є байтом (n=8), а блок складається з 2048 байт (t = 2048, m=20488), то розрядність контрольної суми дорівнює 15, а ймовірність Р^е₄ того, що 4-кратна помилка не буде виявлена становить . Це практично співпадає з ймовірністю того, що така ж помилка не виявляється при використанні CRC з розрядністю утворюючого поліному 15.

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

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

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

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

При кодуванні ехокоду передавач виконує функціональне перетворення F(X) над n-бітовим символом X={x₁,x₂,…,x_n} x_j{0,1} j{1,…,n}. Приймач виконує таке ж перетворення над прийнятим символом X E_D и відсилає результат F(XE_D) передавачеві. Останній обчислює вектор помилки у вигляді: = F(X) F(X E_D) E_R, де E_D та E_R - вектори помилок при прямій та зворотній передачі, відповідно. Якщо кількість одиниць вектору ={₁,₂,…,_n}, _j{0,1} j{1,…,n} перевищує порогове значення , то вважається, що символ передано з помилками. Код може бути представлений у вигляді:

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

Для надійного виявлення помилок необхідно, щоб код диференціалу F(X) для будь-якого вектору E_D не залежав від змінних, що відповідають нульовим компонентам E_D: . Це означає, що кожна з булевих функцій перетворення F(X)={f₁(X),f₂(X),…,f_n(X)} має бути лінійною, а сама система F(X) має бути ортогональною, тобто може бути представлена у вигляді:



де a_ij{0,1} i,j{1,…,n}.

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

Для надійного виявлення однократних помилок, потрібно, щоб кожна із n змінних входила в якості доданка не менше ніж в n/2 функцій F(X) :

Для надійного виявлення двократних помилок, потрібно, щоб Хемінгова вага диференціалу F(X) по двом змінним була не меншою за n/2. Для цього необхідно, щоб для будь-якої пари змінних х₁,…,х_n виконувалася умова:

Для надійного виявлення трьохкратних помилок, потрібно, щоб Хемінгова вага диференціалу F(X) по трьом змінним була не меншою за n/4:

Для n=8 система F(X), що відповідає наведеним вимогам має вигляд:



Надійність виявлення помилки та ймовірність хибного її виявлення залежать від значення порогового параметру . При =2 використання одержаної системи F(X) забезпечує гарантоване виявлення помилок прямої передачі та виключення хибного виявлення помилок за умови, що кратність помилки при передачі байту не перевищує 2-х.

В лініях передачі цифрових даних зі спектральною модуляцією при передачі кожного канального сигналу передається k бітів. Відповідно, при виникненні помилки передачі канального сигналу потенційно можуть бути спотворені k бітів (групова помилка). На прикладі передачі байту в лінії з квадратурно-амплітудною модуляцією при k=4 (QAM-4) показано запропонований спосіб одержання ефективної функції F(X) кодування контрольного коду ехоплексу для каналів зі спектральною модуляцією. Для зменшення ймовірності маскування групової помилки при прямій передачі груповою помилкою під час зворотної передачі, диференціал функціонального перетворення для E_D ( - множина можливих групових помилок, локалізованих в одній тетраді) має містити одиничні компоненти в обох тетрадах байту - в цьому випадку маскування можливе лише за умови виникнення двократної помилки передачі канального символу, що малоймовірно.

Необхідною умовою ефективного кодування контрольного коду ехоплексу є симетричність матриці коефіцієнтів системи F(X) лінійних булевих функцій відносно головної та побічної діагоналей:

Нижче наведена система F(X) лінійних функцій, яка забезпечує ефективне виявлення помилок ехоплексом при передачі байту в лініях з квадратурно-амплітудною модуляцією:

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

Аналіз наведеної формули показує, що ймовірність виникнення помилки, що не виявляється розробленою модифікацією ехоплексу в порівнянні з традиційним ехоплексом знижується в 15/p_b разів, що становить для p_b 10^-3 - 10^-5, чотири-шість порядків.

В четвертому розділі роботи розроблюються структури апаратних засобів для високопродуктивної реалізації операцій контролю, зокрема структура для швидкого обчислення контрольному коду при використанні CRC. Для блоку В, що складається з m біт: B={b₁,b₂,…,b_m}, b_l{0,1}, l=1,…,m потрібно обчислити код CRC з утворюючим поліномом G(x) степені g. Позначимо через Q⁽¹⁾ = {b₁,b₂,…,b_p} послідовність, що складається з перших р бітів блоку В (p<m). На наступних кроках ітераційного обчислення коду CRC при k>1 послідовність Q^(k) утворюється q бітами блоку В:

Через P^(k) позначимо бітову послідовність, що складається з р бітів блоку В і буде використовуватися для обчислення коду CRC на k-тій ітерації, причому спочатку P⁽¹⁾= Q⁽¹⁾. В подальшому, для наступних ітерацій при k>1 послідовність P^(k) утворюється як конкатенація послідовності Q^(k) (q молодших бітів) та обчисленого на попередній ітерації коду залишку R^(k) (q старших біти):

.

Для обчислення залишку поділимо послідовність P^(k) на u фрагментів P^(k)_u (i=1..u), кожен з яких складається з p_i бітів. Введено зміщення o_i для кожного з фрагментів P^(k)_i (i=1..u): . Позначимо залишки від ділення P_i^(k) на G(x) відповідно через R_i^(k) для i=1..u: . Згідно з відомими властивостями ділення поліномів залишок R^(k) для послідовності P^(k) визначається як сума за модулем 2 залишків його фрагментів:

.

Ітераційний процес обчислення коду CRC складається з ітерацій, кожна з яких включає обчислення залишку R^(k) як суми за модулем 2 залишків фрагментів P^(k)_i (i=1..u) та формування коду P^(k+1) ,як конкатенації попереднього залишку та послідовності Q^(k+1). Залишок R^(N) дорівнює коду CRC для блоку В.

Для апаратної реалізації викладеного підходу до обчислення коду CRC пропонується структура, яка включає u паралельно працюючих обчислювачів , i=1..u. Кожен з цих обчислювачів являє собою комбінаційну схему на р/u входів та q виходів. Розрядні виходи обчислювачів підключено до однойменних входів q- входових суматорів за модулем 2. Розглядається два варіанти реалізації обчислювачів: у вигляді блоків табличної постійної пам'яті та на ПЛІС. В останньому варіанті кожна з булевих функцій являє собою багатовходовий суматор за модулем 2. Кількість рівнів при його реалізації на 2-входових суматорах за модулем 2 дорівнює log₂q.

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

1. Али Тауфик Окла Аль-Хавальди. Оптимизация кодирования эхокода при контроле передачи данных методом эхоплекса // Вісник Національного технічного університету України ”KПI”. Інформатика, управління та обчислювальна техніка,- Київ: ВЕК+. - 2005.-№ 43. - С.181-195. (Дисертантом запропоновано кодування ехокоду, яке дозволяє виявляти всі однократні помилки передачі сигналів в каналах комп'ютерних мереж з амплітудно-фазовою модуляцією).

2. Самофалов К.Г., Али Тауфик Окла Аль-Хавальди, Лазученков Д.В. Оптимизация кодирования контрольных сумм при передаче и хранении цифровой информации // Проблеми інформатизації та управління. Збірник наукових праць НАУ,-Київ: НАУ.-2005. - Випуск 4(15). - С.144-151. (Дисертантом запропоновано метод кодування компонент контрольної суми, який забезпечує гарантоване виявлення всіх двохкратних помилок та помилок непарної кратності).

3. Марковский А.П., Аль-Хавальди Али, Драгунов Н.В. Использование дифференциального кодирования для повышения надежности контроля передачи данных // Вісник Національного технічного університету України ”KПI” Інформатика, управління та обчислювальна техніка, - Київ: ВЕК+ - 2004 - № 42. - С.198-205. (Дисертантом запропоновано метод диференційного кодування компонент контрольної суми, який забезпечує значне підвищення надійності виявлення багатократних помилок передачі даних в лініях та шинах, що відповідають моделі двійкового симетричного каналу)

4. Орлова М.Н., Аль-Хавальди Али, Зохре Каримзаде. Метод синтеза управляемых генераторов балансных SAC-функций // Вісник Національного технічного університету України ”KПI” Інформатика, управління та обчислювальна техніка, - Київ: ВЕК+. - 2004. - № 41.- С.155-164. (Дисертантом запропоновані структури апаратних засобів паралельного обчислення булевих функціональних перетворень, використанням яких пропонується підвищити надійність виявлення помилок контрольними сумами ).

5. Марковский А.П., Али Тауфик Окла Аль-Хавальди. Повышение эффективности контрольной суммы для обнаружения ошибок передачи данных.// Труды 7-й Международной конференции Современные информационные и электронные технологии-2006. - 2006. - С. 148-149. (Дисертантом запропоновано спосіб кодування компонент контрольної суми, що дозволяє підвищити надійність виявлення помилок та структури апаратних засобів для паралельного обчислення модифікованої контрольної суми).

6. Аль-Хавальди Али, Янчук С.В. Использование лавинных преобразований для повышения надежности обнаружения ошибок в каналах связи // Тези 6-ї міжнародної конференції ”Системний аналіз та інформаційні технології”. К. ННК ”ІПСА”.- 2005.- С.172. (Дисертантом запропоновано модифікацію методу ехоплексу, яка забезпечує гарантоване виявлення всіх однократних помилок, а також виключення можливості помилкового виявлення помилки в лініях та шинах, що відповідають моделі двійкового симетричного каналу).

АНОТАЦІЇ

Алі Тауфік Окла Аль-Хавальді. Методи та засоби підвищення ефективності застосування контрольних сум, ехоплексу та циклічних кодів для виявлення помилок передачі даних в компютерних системах і мережах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - Обчислювальні машини, системи та мережі. - Національний технічний університет України ”Київський політехнічний інститут”, Київ, 2006.

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

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

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

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

Ключові слова: виявлення помилок, кодування помилок, контрольні суми, ехоплекс, комп'ютерні мережі, периферійні пристрої ЕОМ.

Али Тауфик Окла Аль-Хавальди. Методы и средства повышения эффективности использования контрольных сумм, эхоплекса и циклических кодов для обнаружения ошибок передачи данных в компьютерных системах и сетях. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - Вычислительные машины, системы и сети.- Национальный технический университет Украины ”Киевский политехнический институт”, Киев, 2006.

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

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

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

...