Існує три найпоширеніші знаряддя боротьби з помилками в процесі передачі даних:
· коди виявлення помилок;
· коди з корекцією помилок, називані також схемами прямої корекції помилок (Forward Error Correction - FEC);
· протоколи з автоматичним запитом повторної передачі (Automatic Repeat Request - ARQ).
Код виявлення помилок дозволяє досить легко встановити наявність помилки. Як правило, подібні коди використовуються разом з певними протоколами канального або транспортного рівнів, що мають схему ARQ. У схемі ARQ приймач попросту відхиляє блок даних, у якому була виявлена помилка, після чого передавач передає цей блок повторно. Коди із прямою корекцією помилок дозволяють не тільки виявити помилки, але й виправити їх, не прибігаючи до повторної передачі. Схеми FEC часто використовуються в безпроводовій передачі, де повторна передача вкрай неефективна, а рівень помилок досить високий.
1) Методи виявлення помилок
Методи виявлення помилок засновані на передачі в складі блоку даних надлишкової службової інформації, за якою можна судити з деяким ступенем імовірності про вірогідність прийнятих даних.
Надлишкову службову інформацію прийнято називати контрольною сумою, або контрольною послідовністю кадру (Frame Check Sequence, FCS). Контрольна сума обчислюється як функція від основної інформації, причому не обов'язково шляхом підсумовування. Приймаюча сторона повторно обчислює контрольну суму кадру за відомим алгоритмом й у випадку її збігу з контрольною сумою, обчисленою передавальною стороною, робить висновок про те, що дані були передані через мережу коректно. Розглянемо кілька розповсюджених алгоритмів обчислення контрольної суми, що відрізняються обчислювальною складністю й здатністю виявляти помилки в даних.
Контроль за паритетом являє собою найбільш простий метод контролю даних. У той же час це найменш потужний алгоритм контролю, тому що з його допомогою можна виявити тільки одиночні помилки в даних, що перевіряються. Метод полягає в підсумовуванні за модулем 2 всіх біт контрольованої інформації. Неважко помітити, що для інформації, що складає з непарного числа одиниць, контрольна сума завжди дорівнює 1, а при парному числі одиниць - 0. Наприклад, для даних 100101011 результатом контрольного підсумовування буде значення 1. Результат підсумовування також являє собою один додатковий біт даних, що пересилається разом з контрольованою інформацією. При перекручуванні в процесі пересилання будь-якого біта вихідних даних (або контрольного розряду) результат підсумовування буде відрізнятися від прийнятого контрольного розряду, що говорить про помилку. Однак подвійна помилка, наприклад 110101010, буде невірно прийнята за коректні дані. Тому контроль за паритетом застосовується до невеликих порцій даних, як правило, до кожного байта, що дає коефіцієнт надмірності для цього методу 1/8. Метод рідко застосовується в комп'ютерних мережах через значну надмірність і невисокі діагностичні здатності.
Вертикальний і горизонтальний контроль за паритетом являє собою модифікацію описаного вище методу. Його відмінність полягає в тому, що вихідні дані розглядаються у вигляді матриці, рядки якої становлять байти даних. Контрольний розряд підраховується окремо для кожного рядка й для кожного стовпця матриці. Цей метод виявляє значну частину подвійних помилок, однак має ще більшу надмірність. Він зараз також майже не застосовується при передачі інформації в мережі.
Циклічний надлишковий контроль (Cyclic Redundancy Check - CRC) є в наш час найбільш популярним методом контролю в обчислювальних мережах (і не тільки в мережах; зокрема, цей метод широко застосовується при записі даних на гнучкі й жорсткі диски). Метод заснований на розгляді вихідних даних у вигляді одного багаторозрядного двійкового числа. Наприклад, кадр стандарту Ethernet, що складає з 1024 байт, буде розглядатися як одне число, що складається з 8192 біт. Контрольною інформацією вважається залишок від поділу цього числа на відомий дільник R. Звичайно як дільник вибирається сімнадцяти- або тридцятитрьохрозрядне число, щоб залишок від поділу мав довжину 16 розрядів (2 байт) або 32 розряду (4 байт). При одержанні кадру даних знову обчислюється залишок від поділу на той же дільник R, але при цьому до даних кадру додається й контрольна сума, що втримується в ньому. Якщо залишок від поділу на R дорівнює нулю, то робиться висновок про відсутність помилок в отриманому кадрі, у противному випадку кадр уважається перекрученим.
Цей метод має більш високу обчислювальну складність, але його діагностичні можливості набагато ширше, ніж у методів контролю за паритетом. Метод CRC виявляє всі одиночні помилки, подвійні помилки й помилки в непарному числі біт. Метод також має невисокий ступінь надмірності. Наприклад, для кадру Ethernet розміром 1024 байта контрольна інформація довжиною 4 байти становить тільки 0,4 %.
2) Методи корекції помилок
Техніка кодування, що дозволяє приймачу не тільки зрозуміти, що прислані дані містять помилки, але й виправити їх, називається прямою корекцією помилок (Forward Error Correction - FEC). Коди, що забезпечують пряму корекцію помилок, вимагають введення більшої надмірності в передані дані, ніж коди, які тільки виявляють помилки.
При застосуванні будь-якого надлишкового коду не всі комбінації кодів є дозволеними. Наприклад, контроль за паритетом робить дозволеними тільки половину кодів. Якщо ми контролюємо три інформаційних біти, то дозволеними 4-бітними кодами з доповненням до непарної кількості одиниць будуть: 0001, 0010, 0100, 0111, 1000, 1011, 1101, 1110, тобто всього 8 кодів з 16 можливих.
Для того щоб оцінити кількість додаткових біт, необхідних для виправлення помилок, потрібно знати так звану відстань Хеммінга між дозволеними комбінаціями коду. Відстанню Хеммінга називається мінімальне число бітових розрядів, у яких відрізняється будь-яка пара дозволених кодів. Для схем контролю за паритетом відстань Хеммінга дорівнює 2.
Можна довести, що якщо ми сконструювали надлишковий код з відстанню Хеммінга, рівним n, такий код зможе розпізнавати (n-1)-кратні помилки й виправляти (n-1)/ 2-кратні помилки. Тому що коди з контролем за паритетом мають відстань Хеммінга, рівну 2, вони можуть тільки виявляти однократні помилки й не можуть виправляти помилки.
Коди Хеммінга ефективно виявляють і виправляють ізольовані помилки, тобто окремі перекручені біти, які розділені більшою кількістю коректних біт. Однак з появою довгої послідовності перекручених біт (пульсації помилок) коди Хеммінга не працюють.
Найбільш часто в сучасних системах зв'язку застосовується тип кодування, реалізований згортковим пристроєм, що кодує (Сonvolutional coder), тому що таке кодування нескладно реалізувати апаратно з використанням ліній затримки (delay) і суматорів. На відміну від розглянутого вище коду, що належить до блокових кодів без пам'яті, згортковий код належить до кодів з кінцевою пам'яттю (Finite memory code); це означає, що вихідна послідовність кодеру є функцією не тільки поточного вхідного сигналу, але також декількох із числа останніх попередніх біт. Довжина кодового обмеження (Constraint length of a code) показує, як багато вихідних елементів виходить із системи в перерахуванні на один вхідний. Коди часто характеризуються їхнім ефективним ступенем (або коефіцієнтом) кодування (Code rate). Вам може зустрітися згортковий код з коефіцієнтом кодування 1/2. Цей коефіцієнт указує, що на кожний вхідний біт доводиться два вихідних. При порівнянні кодів звертайте увагу на те, що, хоча коди з більш високим ефективним ступенем кодування дозволяють передавати дані з більш високою швидкістю, вони, відповідно, більш чутливі до шуму.
У безпроводових системах із блоковими кодами широко використовується метод чергування блоків. Перевага чергування полягає в тому, що приймач розподіляє пакет помилок, що спотворив деяку послідовність біт, за великою кількістю блоків, завдяки чому стає можливим виправлення помилок. Чергування виконується за допомогою читання й запису даних у різному порядку. Якщо під час передачі пакет перешкод впливає на деяку послідовність біт, то всі ці біти виявляються рознесеними по різних блоках. Отже, від будь-якої контрольної послідовності потрібна можливість виправити лише невелику частину від загальної кількості інвертованих біт.
3) Методи автоматичного запиту повторної передачі
У найпростішому випадку захист від помилок полягає тільки в їхньому виявленні. Система повинна попередити передавач про виявлення помилки й необхідності повторної передачі. Такі процедури захисту від помилок відомі як методи автоматичного запиту повторної передачі (Automatic Repeat Request - ARQ). У безпроводових локальних мережах застосовується процедура "запит ARQ із зупинками" (stop-and-wait ARQ).
Рис. 2.14. Процедура запит ARQ із зупинками
У цьому випадку джерело, що послало кадр, очікує одержання підтвердження (Acknowledgement - ACK), або, як ще його називають, квитанції, від приймача й тільки після цього посилає наступний кадр. Якщо ж підтвердження не приходить протягом тайм-ауту, то кадр (або підтвердження) уважається загубленим і його передача повторюється. На рис. 2.14 видно, що в цьому випадку продуктивність обміну даними нижче потенційно можливої; хоча передавач і міг би послати наступний кадр відразу ж після відправлення попереднього, він зобов'язаний чекати приходу підтвердження.