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

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

Мулкі Ахмед Ясін Ал Бадайнех

(Йорданія)

УДК 004.052.42

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

ТА ВИПРАВЛЕННЯ ПОМИЛОК В ПОСЛІДОВНИХ

ІНТЕРФЕЙСАХ КОМП’ЮТЕРНИХ СИСТЕМ

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

АВТОРЕФЕРАТ

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

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

Київ 2008

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

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

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

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

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

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

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

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

НТУУ ”КПІ”, декан факультету

прикладної математики

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

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

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

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

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

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

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

Автореферат розісланий ”15” травня 2008 р.

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

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

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

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

Актуальність теми. Передача цифрових даних являє собою один з найменш надійних компонент систем комп’ютерної обробки інформації. Труднощі забезпечення високої достовірності передачі даних зумовлені складною природою фізичних процесів проходження сигналів в довгих лініях, їх взаємним впливом (міжсигнальна інтерференція) та впливом зовнішніх перешкод. Саме тому, з кінця 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 x16 + x15 + x2 + 1 залишок від ділення 4003 0000 дорівнює 7FF8. Відповідно в лінію інтерфейсу передається код 40037FF8. Якщо припустити, що при пере-дачі 2-ї серії одиниць (що складається з 2-х одиниць) виникла помилка синхро-нізації, що мала наслідком зміну довжини серії до 3-х одиниць, то на приймач пос-тупає код 80077FF8. Залишок від ділення відповідного поліному на утворюючий поліном CRC дорівнює нулю, що значить, така однократна помилка не виявлена CRC.

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

(3)

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

(4)

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

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

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

Метод виявлення помилок | Характеристика помилок, що виявляються гарантовано | Кількість контрольних розрядів

Контроль зміни довжини одиничних серій за допомогою зважених контрольних сум | Всі помилки непарної кратності | 1

Помилки непарної кратності та подвійні помилки | 12

Помилки непарної кратності та парні помилки, кратністю меншою 6-ти | 24

CRC | Помилки гарантовано не виявляються | 16

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

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

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

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

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

? = (LSd mod 4 LRd mod 4) || Wd

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

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

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

При використанні спектральної модуляції блок B даних, що складається з m бітів B={b1,b2,…,bm}, bl{0,1},l=1,…,m можна розглядати таким, що містить в собі t = m/k канальних символів: B={X1,X2,…,Xt}. Кожен j-тий з цих символів Хj, j{1,2,…,t} містить k суміжних бітів блоку В, передача якого контролюється: :

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

При контролі правильності передачі за допомогою CRC однократна помилка передачі канального символу гарантовано виявляється, оскільки ступінь r утворюючого поліному CRC, як правило, перевищує довжину k двійкового представлення символу: r > k. Проте, подвійна помилка передачі канального сигналу не може бути гарантовано виявлена при використанні CRC. Така помилка гарантовано виявляється за допомогою зваженої контрольної суми. При цьому контрольний код 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}. Останнє, (k+1)-те поле контрольного коду V складається з k бітів символу Х: Vk+1 = X={x1,x2,…xk}. Таким чином, загальна довжина контрольного коду становить:

(5)

Наприклад, при довжині блоку в 2048 байтів і використанні 16-QAM (k=4), розрядність контрольної суми стано-витиме 4(12+1) = 52. Зважена контрольна сума WCS також складається з k полів: WCS = {WCS1,WCS2,…,WCSk,WCSk+1}, кожне з яких являє собою суму за модулем 2 відповідних полів контрольних кодів символів . Код різниці зважених контрольних сум передавача WCSs і приймача WCSr також складається з k+1 полів: = {1,2,…,k,k+1}: l = WCSsl WCSrl, 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 помилок, зумовлених спотворенням двох канальних модульованого сигналів.

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

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

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

. (6)

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

(7)

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

(8)

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

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

Припустимо, що помилки трапилися при передачі u–того та q–того канальних сигналів, що викликає спотворення символів Xu і Xq, а також зміну відповідних їм чисел так, що числа zSu і zSq на передавачеві відрізняються від чисел zRu та zRq на приймачеві. Якщо позначити через zu = zRu- zSu та zq = zRq- zSq, то очевидно, що контрольні суми передавача і приймача відрізняються на величину CS = (zuWu + zqWq) mod R. Покажемо, що абсолютна величина CS не може дорівнювати нулю.

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

(9)

Покажемо, що права частина (9) не може бути цілим числом. Якщо zq і Wu не мають подільників, то оскільки Wq та Wu також не мають подільників, то чисельник і знаменник правої части являють собою взаємно-прості числа, тому ця частина не може бути цілим числом. Якщо zq і Wu мають спільний подільник , тобто : zq = и Wu = , де , и - цілі числа, причому і є взаємно-простими, причому > тому, що Wu > 2k-1 > zq. Так як Wq і Wu є взаємно-простими, то такими ж являються і Wq та , причому > 1. Таким чином, і цьому випадку, відмінний від одиниці знаменник та чисельник правої частини (9) не мають спільних подільників. Це значить, що права частина (9) не може бути цілим числом. З цього випливає, що умова (9) не виконується. Проте CS = (zuWu + zqWq) mod R може дорівнювати, якщо справедливо:

(10)

де - ціле число. Покажемо, що умова (10) також не може бути виконана. Дійсно, значення k–розрядних чисел zu і zq не перевищують 2k-1. Оскільки WuWt та WqWt, причому WuWq, то Wu+WqWt-1+Wt . Враховуючи (7) це означає, що завжди справедливо:

(11)

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

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

Використання запропонованої модифікації зваженої контрольної суми може бути ілюстроване на прикладі. Нехай передається блок даних об’ємом 32 біти ( m=32), що складається з 8-ми (t=8) 4-х бітових (k=4) символів: X1=<0001>,X2=<1001>,X3=<0110>,X4=<0100>, Х5=<0011>, X6=<1111>, X7=<0111>, X8=<1010>. Цим символам відповідають 4-розрядні числа z1=1, z2=9, z3=6, z4=4, z5=3, z6=15, z7=7, z8=10. Оскільки 2k-1 =15, коефіцієнти W1,W2,…,W8 є взаємно-простими, більшими за 15: W1=16, W2=17, W3=19, W4=21, W5=23, W6=25,W7=29,W8=31. Значення R визначається у відповідності (3.7) як 210 > (2k-1)(W7+W8) = 15(29+31)= 900. Зважена контрольна сума MCSS на передавачеві обчислюється у вигляді: MCSS = (116 + 917 + 619 + 421 + 223 + 1525 + 729 + 1031) mod 1024 = 1324 mod 1024 = 300.

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

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

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

(12)

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

(13)

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

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

(14)

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

Порівняльний аналіз формули (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. Проведено аналіз особливостей