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

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

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

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

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

АВТОРЕФЕРАТ

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

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Мулкі Ахмед Ясін Ал Бадайнех (Йорданія)

Київ 2008

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

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

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

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

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

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

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

Дичка Іван Андрійович,

НТУУ ”КПІ”, декан факультету прикладної математики

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

Мартинова Оксана Петрівна,

Національний авіаційний університет,

доцент Інституту комп'ютерних технологій.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Міжнародній науково-технічній конференції ”Автоматизація: проблеми, ідеї, рішення”, 10 - 15 вересня 2007 р., м. Севастополь.

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

3. Міжнародній науково-технічній конференції ”Комп'ютерні системи та мережні технології”, 17-19 березня 2008 р., м. Київ.

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

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

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

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

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

Послідовні інтерфейси сучасних комп'ютерних систем з точки зору технології передачі даних можна розділити на два класи: на основі низькочастотної імпульсно-кодової модуляції двійкових кодів (COM, USB(Universal Serial Bus), FireWare), а також на основі високочастотної спектральної модуляції (модемні інтерфейси). Інтерфейси першого типу доцільно, в свою чергу, розділяти на інтерфейси з синхронною передачею та асинхронні. Теоретичною моделлю перших, з точки зору виникаючих помилок, є двійковий симетричний канал. Це означає, що бітові спотворення, викликані помилками передачі в таких інтерфейсах, незалежні між собою і проявляються у вигляді зміни значень окремих бітів блоку. Залежність ймовірності бітових спотворень від їх кількості має біноміальний характер. Переважна більшість помилок викликається гаусовим шумом, явищами міжсигнальної інтерференції та зовнішніми завадами.

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

Серед низькочастотних інтерфейсів слід окремо виділити ті, в яких дані передаються побайтно з контрольним бітом парності (СОМ).

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

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

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

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

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

Для більшості частини послідовних інтерфейсів комп'ютерних систем характерним є використання асинхронного кодування даних. Зокрема таке кодування даних має місце в USB та FireWire. Так для кодування даних при передачі в USB використовується метод NRZI(Non Return to Zero Invert) з бітовим стафінгом. Цей метод передбачає зміну потенціалу на лінії при передачі нуля, в той час, як при передачі одиниці напруга не змінюється.

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

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

В результаті порушення синхронізації при передачі серії бітів виникає помилка, яка полягає в зміні їх кількості на приймачеві. Така помилка фактично еквівалента зсуву частини блоку даних, що контролюється. Такий характер спотворення блоку відрізняється від традиційної моделі помилки, яка передбачає зміну одного або декількох бітів, без впливу на інші біти блоку. Найвідоміші методи виявлення помилок, такі як CRC і контрольна сума - CS(Check Sum) зорієнтовані саме на традиційну модель бітових спотворень. Зокрема, передбачений в USB контроль помилок за допомогою CRC забезпечує гарантоване виявлення спотворення двох або непарної кількості бітів. При виникненні навіть однократної помилки синхронізації всі наступні біти блоку змінюють свої позиції. Така помилка не може бути гарантовано виявлена CRC. Наприклад, якщо передається блок даних, що має 16-ричне представлення 4003, то при використанні стандартизованого для USB утворюючого поліному CRC x¹⁶ + x¹⁵ + x² + 1 залишок від ділення 4003 0000 дорівнює 7FF8. Відповідно в лінію інтерфейсу передається код 40037FF8. Якщо припустити, що при передачі 2-ї серії одиниць (що складається з 2-х одиниць) виникла помилка синхронізації, що мала наслідком зміну довжини серії до 3-х одиниць, то на приймач поступає код 80077FF8. Залишок від ділення відповідного поліному на утворюючий поліном CRC дорівнює нулю, що значить, така однократна помилка не виявлена CRC.

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

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

Блок В даних, що передаються складається з m бітів: B={b₁,b₂,…,b_m}, b_l{0,1},l=1,…,m. B блоці виділяються серії однакових бітів, передача яких не синхронізується. Для USB такими серіями є серії одиниць. Через позначимо серію, що має порядковий номер в блоці k та складається біль як з u одиниць. Спосіб передбачає контроль за зміною довжини серій, для яких існує потенційна небезпека порушення синхронізації. Наприклад, для USB доцільним є контроль серій, довжина яких перевищує 1 ((u=1).

Контрольний код V пропонується обчислювати в вигляді зваженої контрольної суми. Для цього, кожній k-тій із серій , що контролюються ставиться у відповідність коефіцієнт W_k, котрий однозначно співвідноситься з порядковим номером k серії в блоці. В процесі передачі (прийому) блоку обчислюється біт парності довжини L_k кожної k-тої серії. Код V зваженої контрольної суми обчислюється на передавачеві та приймачеві, як конкатенація сум за модулем 2 бітів парності довжини серій та суми за модулем 2 добутків біта парності довжини серії на відповідний коефіцієнт ваги:

(1)

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

При W_k=k гарантовано виявляються, крім помилок непарної кратності, всі двократні помилки. Дійсно, якщо зміниться довжина двох, наприклад, q-тої і d-тої серій одиниць в блоці, q,d{1,…,K_u}, то різниця контрольних кодів приймача та передавача буде дорівнювати . Оскільки W_q W_d в силу того, що dq, то 0, а це значить.

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

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

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

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

(2)

В рамках прийнятих припущень можна показати, що середня кількість серій нулів дорівнює середньому числу серій одиниць. З цього, з урахуванням (2) слідує, що середнє значення кількості серій одиниць становить m/4. З них, середнє число _е серій, що містять в собі е одиниць в m-бітовому блоці визначається формулою:

(3)

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

(4)

Кількість s контрольних розрядів залежить від довжини m блоку даних і парної кратності помилок, що гарантовано виявляються. Так, для гарантованого виявлення всіх помилок непарної кратності на подвійних помилок розрядність коефіцієнтів W дорівнює log₂K_e. Зокрема, для послідовних інтерфейсів USB специфікована довжина пакету даних як 1024 байтів (m=8192). При використання бітового стафінгу доцільно контролювати зміну серій, що містять від 1 до 6-ти одиниць. Число K таких серій визначається формулою:

Розрядність коефіцієнтів W становить, відповідно, log₂m-2 = log₂8192 -2 = 11. З урахуванням біту парності кількості одиниць в серіях, загальна розрядність контрольного коду становить 12 біт. Характеристики кількості контрольних розрядів та кратності помилок, що гарантовано виявляються за допомогою запропонованого способу, а також CRC наведені в таблиці 1.

Таблиця 1. Порівняльні характеристики ефективності гарантованого виявлення помилок, зумовлених порушеннями синхронізації в USB.

Метод виявлення помилок	Характеристика помилок, що виявляються гарантовано	Кількість контрольних розрядів
Контроль зміни довжини одиничних серій за допомогою зважених контрольних сум	Всі помилки непарної кратності	1
	Помилки непарної кратності та подвійні помилки	12
	Помилки непарної кратності та парні помилки, кратністю меншою 6-ти	24
CRC	Помилки гарантовано не виявляються	16

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

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

Однократне порушення синхронізації викликає зміну довжини L_Sd d-тої серії одиниць, d{1,…,K_u}. При цьому код містить коефіцієнт W_d, який однозначно співвідноситься з номером d спотвореної серії одиниць. Зокрема, при h=2 коефіцієнт W_d співпадає з номером d. Проте точна локалізація спотвореної серії не дозволяє її відновити, оскільки можливими є два варіанти спотворень - збільшення довжини L_Sd серії і її зменшення.

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

При виникненні однократної помилки синхронізації, що має наслідком зміну довжини d-тої серії код ? = V_S? V_R? має вигляд:

? = (L_Sd mod 4 L_Rd mod 4) || W_d

де L_Sd - довжина d-тої серії одиниць до передачі, L_Rd - довжина d-тої серії після спотворення. На приймачеві, знаючи локалізацію спотвореної серії можна визначити її довжину - L_Rd. За кодами = L_Sd mod 4 L_Rd mod 4 та L_Rd mod 4 можна відновити неспотворену довжину L_Sd d-тої серії одиниць блоку, тобто скорегувати помилку.

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

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

При використанні спектральної модуляції блок B даних, що складається з m бітів B={b₁,b₂,…,b_m}, b_l{0,1},l=1,…,m можна розглядати таким, що містить в собі t = m/k канальних символів: B={X₁,X₂,…,X_t}. Кожен j-тий з цих символів Х_j, j{1,2,…,t} містить k суміжних бітів блоку В, передача якого контролюється: :

В результаті помилок передачі канальних сигналів, відповідні кодові групи ( символи ) змінюються, тобто при виникненні помилки передачі j-то сигналу коди j-то символу X_j на приймачі та передавачі не одинакові: X_sj X_rj. Зрозуміло, що при цьому можуть змінися від одного до k бітів, що складають j-тий символ X_j.

При контролі правильності передачі за допомогою CRC однократна помилка передачі канального символу гарантовано виявляється, оскільки ступінь r утворюючого поліному CRC, як правило, перевищує довжину k двійкового представлення символу: r > k. Проте, подвійна помилка передачі канального сигналу не може бути гарантовано виявлена при використанні CRC. Така помилка гарантовано виявляється за допомогою зваженої контрольної суми. При цьому контрольний код V символу Х формується з k+1 бітових полів. Кожне і-те з перших k полів, i=1,…,k, обчислюється як логічний добуток відповідного і-того біту x_i символу Х на q- розрядний код W_i : V_i = x_i W_i, де q = log₂t. Кожний з k кодів, що використовуються при формуванні j-го контрольного коду V_j : W_ji = {w_ji1,w_ji2,…,w_jiq}, w_jiy{0,1}, y{1,…,q}, j{1,…,t}, i{1,…,k}, однозначно пов'язаний з номером j символу X_j в блоці. Коди W_j1, W_j2, …, W_jk є відмінними між собою для всіх j{1,…,t}. Останнє, (k+1)-те поле контрольного коду V складається з k бітів символу Х: V_k+1 = X={x₁,x₂,…x_k}. Таким чином, загальна довжина контрольного коду становить:

(5)

Наприклад, при довжині блоку в 2048 байтів і використанні 16-QAM (k=4), розрядність контрольної суми становитиме 4(12+1) = 52. Зважена контрольна сума WCS також складається з k полів: WCS = {WCS₁,WCS₂,…,WCS_k,WCS_k+1}, кожне з яких являє собою суму за модулем 2 відповідних полів контрольних кодів символів . Код різниці зважених контрольних сум передавача WCS_s і приймача WCS_r також складається з k+1 полів: = {₁,₂,…,_k,_k+1}: _l = WCS_sl WCS_rl, l=1,…,k+1.

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

При спотворенні двох символів X_u і X_g вони відрізняються на приймачеві та передавачеві, тобто: X_su={x_su1,x_su2,…,x_suk} X_ru={x_ru1,x_ru2,…,x_ruk} та X_sg={x_sg1,x_sg2,…,x_sgk} X_rg={x_rg1,x_rg2,…,x_rgk}. Код i-того поля _i, i{1,…,k) різниці при помилковій передачі X_u і X_g може бути представлений у вигляді:

В силу того, що W_ui W_gi, то в усіх випадках, окрім x_sui = x_rui та x_sgi = x_rgi, код i-того поля _i різниці контрольних сум приймача та передавача не дорівнює нулю: _i 0. Проте згадана умова не може одночасно виконуватися для всіх k полів ₁,₂,…,_k, оскільки X_suX_ru та X_sg X_rg. Таким чином, запропонований спосіб формування контрольної суми забезпечує гарантоване виявлення від 2-х до 2k помилок, зумовлених спотворенням двох канальних модульованого сигналів.

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

Для підвищення ефективності вказаного класу помилок пропонується модифікація зваженої контрольної суми. В цій модифікації пропонується в якості коефіцієнтів ваги застосувати взаємно-прості числа W₁,W₂,…,W_t, кожне наступне з яких більше за попереднє: W₁<W₂<…<W_t-1<W_t.

Кожному j-му символу X_j блоку В співставляється k-розрядне двійкове число z_j : . Контрольний код Y_j j-го символу X_j обчислюється як медулярний арифметичний добуток z_j на відповідний коефіцієнт W_j : . Модифікована контрольна сума блоку - MCS обчислюється як арифметична сума контрольних кодів символів блоку:

. (6)

причому, значення модуля R має задовольняти умові :

(7)

На практиці, для спрощення виконання модулярних операцій R являє собою найменший ступінь 2, для якого виконується умова (7):

(8)

За умови (8) при виконанні операцій, передбачених виразом (6) враховуються лише молодших n розрядів проміжних та кінцевих результатів. Відповідно, розрядність контрольної суми MCS дорівнює n.

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

Припустимо, що помилки трапилися при передачі u-того та q-того канальних сигналів, що викликає спотворення символів X_u і X_q, а також зміну відповідних їм чисел так, що числа z_Su і z_Sq на передавачеві відрізняються від чисел z_Ru та z_Rq на приймачеві. Якщо позначити через z_u = z_Ru- z_Su та z_q = z_Rq- z_Sq, то очевидно, що контрольні суми передавача і приймача відрізняються на величину _CS = (z_uW_u + z_qW_q) mod R. Покажемо, що абсолютна величина _CS не може дорівнювати нулю.

Оцінимо спочатку можливість виконання умови z_uW_u + z_qW_q =0. Для цього має виконуватися

(9)

Покажемо, що права частина (9) не може бути цілим числом. Якщо z_q і W_u не мають подільників, то оскільки W_q та W_u також не мають подільників, то чисельник і знаменник правої части являють собою взаємно-прості числа, тому ця частина не може бути цілим числом. Якщо z_q і W_u мають спільний подільник , тобто : z_q = и W_u = , де , и - цілі числа, причому і є взаємно-простими, причому > тому, що W_u > 2^k-1 > z_q. Так як W_q і W_u є взаємно-простими, то такими ж являються і W_q та , причому > 1. Таким чином, і цьому випадку, відмінний від одиниці знаменник та чисельник правої частини (9) не мають спільних подільників. Це значить, що права частина (9) не може бути цілим числом. З цього випливає, що умова (9) не виконується. Проте _CS = (z_uW_u + z_qW_q) mod R може дорівнювати, якщо справедливо:

(10)

де - ціле число. Покажемо, що умова (10) також не може бути виконана. Дійсно, значення k-розрядних чисел z_u і z_q не перевищують 2^k-1. Оскільки W_uW_t та W_qW_t, причому W_uW_q, то W_u+W_qW_t-1+W_t . Враховуючи (7) це означає, що завжди справедливо:

(11)

З (11) слідує, що рівняння (9) не виконується.

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

Використання запропонованої модифікації зваженої контрольної суми може бути ілюстроване на прикладі. Нехай передається блок даних об'ємом 32 біти ( m=32), що складається з 8-ми (t=8) 4-х бітових (k=4) символів: X₁=<0001>,X₂=<1001>,X₃=<0110>,X₄=<0100>, Х₅=<0011>, X₆=<1111>, X₇=<0111>, X₈=<1010>. Цим символам відповідають 4-розрядні числа z₁=1, z₂=9, z₃=6, z₄=4, z₅=3, z₆=15, z₇=7, z₈=10. Оскільки 2^k-1 =15, коефіцієнти W₁,W₂,…,W₈ є взаємно-простими, більшими за 15: W₁=16, W₂=17, W₃=19, W₄=21, W₅=23, W₆=25,W₇=29,W₈=31. Значення R визначається у відповідності (3.7) як 2¹⁰ > (2^k-1)(W₇+W₈) = 15(29+31)= 900. Зважена контрольна сума MCS_S на передавачеві обчислюється у вигляді: MCS_S = (116 + 917 + 619 + 421 + 223 + 1525 + 729 + 1031) mod 1024 = 1324 mod 1024 = 300.

Якщо припустити, що з помилками передані 4-й (u=4) та 7-й (q=7) канальні сигнали; при цьому 4-й символ декодовано як X_4R =<1110>, а 7-й як X_7R=<0000>. Декодованим символам відповідають числа z_4R=14 та z_7R=0. Контрольна сума MCS_R на приймачеві обчислюється у вигляді: MCS_R = (116 + 917 + 619 + 1421 + 223 + 1525 + 029 + 1031) mod 1024 = 1331 mod 1024 = 307. Так як MCS_S MCS_R, то викликане подвійною помилкою передачі канальних сигналів спотворення 7-ми бітів блоку виявлено.

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

Розрядність n контрольної суми залежить від кількості n_W двійкових розрядів W_t і визнається за формулою:

(12)

Значення n_W може бути обчислене з використанням функції (y), яка визначає кількість простих чисел, менших за y. При великих значеннях y кількість (y) взаємно-простих чисел, менших за y практично дорівнює (y): (y)(y). Значення функції (y) визначається за відомою формулою:

(13)

Враховуючи, що кількість простих чисел менших або рівних W_t становить

t + (2^k-1), то формулу (3.12) можна конкретизувати у вигляді:

(14)

Формула (3.14) може бути використана для обчислення значення n_W.

Порівняльний аналіз формули (14) кількості контрольних розрядів для розробленої модифікації контрольної суми та формули (6) для відомого способу доводить на підвищення ефективності гарантованого виявлення подвійних помилок за рахунок зменшення кількості контрольних розрядів.

В таблиці 2 наведено значення розрядності контрольного коду для відомого варіанту контрольної суми (L), та розрядності (n) розробленої контрольної суми, а також їх співвідношення (L/n).

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

Характеристики зважених контрольних сум	k = 4	k = 8
	Число символів t в блоці	Число символів t в блоці
	128	256	512	1024	128	256	512	1024
Wt-1	751	1663	3701	8209	1087	2039	4099	8647
Wt	757	1667	3709	8219	1091	2053	4111	8663
n	15	16	17	18	20	20	21	23
L	32	36	40	44	64	72	80	88
L/n	2.1	2.25	2.35	2.44	3.2	3.6	3.8	3.82

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

1. Мулки Ахмед Яссин Ал Бадайнех. Исправление ошибок с использованием дифференциально-кодированной суммы // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2005.-№ 43.- С.64-72.

2. Самофалов К.Г. Марковский А.П., Мулки Ахмед Яссин Ал Бадайнех. Обнаружение и исправление ошибок передачи данных с использованием взвешенных контрольных сумм // Проблеми інформатизації та управління. Збірник наукових праць.- К.:НАУ.- 2008.- Випуск 3(14).- С.121-128. (Дисертантом запропоновано підхід до підвищення ефективності виявлення двократних помилок за рахунок зменшення кількості контрольних розрядів, а також спосіб виправлення виявлених помилок шляхом часткової повторної передачі блоку, виконано аналіз ефективності запропонованого способу виправлення помилок ).

3. Марковский А.П., Мулки Ахмед Яссин Ал Бадайнех, Пуя Солеймани Нежадиан. Об одном подходе к повышению эффективности обнаружения и исправления ошибок передачи данных // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2007.-№ 47.- С.62-74 (Дисертантом запропоновано вдосконалення способу виявлення та виправлення помилок за допомогою двовимірної контрольної суми, зокрема застосування зваженої контрольної суми в стовпцях матриці даних, що контролюється, а також виконано аналіз ефективності вдосконаленого способу).

...