Контроль парності - комп’ютерні мережі

контроль парності

Можливо, найпростіша форма виявлення помилок полягає у використанні одного біта парності. Припустимо, що на рис. 5.4 передані дані D мають довжину d розрядів. При перевірці на парність відправник просто додає до даних один біт, значення якого обчислюється як сума всіх d розрядів даних по модулю 2. У цьому випадку кількість одиниць в отримують в результаті числі завжди буде парних. Застосовуються також схеми, в яких контрольний біт інвертується, в результаті чого кількість одиниць в отримують в результаті числі завжди буде непарним. На рис. 5.5 зображена схема перевірки на парність, а єдиний біт парності зберігається в окремому полі.

Дії, що виконуються одержувачем при використанні такої схеми, також дуже прості. Одержувач повинен всього лише порахувати кількість одиниць в отриманих d + 1 розрядах. Якщо при перевірці на парність одержувач виявляє, що в прийнятих ним даних непарна кількість одиничних розрядів, він розуміє, що сталася помилка, щонайменше, в одному розряді. У загальному випадку це означає, що в отриманих даних інвертовану непарна кількість розрядів (сталася помилка непарної кратності).

Що станеться, якщо в отриманому пакеті даних відбудеться парна кількість однобітових помилок? У цьому випадку одержувач не зможе виявити помилку. Якщо ймовірність помилки в одному розряді мала і можна припустити, що помилки в окремих розрядах виникають незалежно один від одного, тоді ймовірність кількох помилок в одному пакеті вкрай мала. В такому випадку єдиного біта парності може бути досить. Однак практичні спостереження показали, що в дійсності помилки не є незалежними, а часто групуються в пакети помилок. У разі пакетних помилок ймовірність того, що одержувач не виявить помилку в пакеті, може наблизитися до величини 50%. Очевидно, в такій ситуації потрібно більш надійна схема виявлення помилок! Але перш ніж перейти до вивчення схем виявлення помилок, що застосовуються на практиці, розглянемо просту схему, яка узагальнює попередню схему однорозрядного контролю парності і допомагає зрозуміти принцип роботи методів виправлення помилок.

На рис. 5.6 показано двомірне узагальнення однорозрядною схеми перевірки на парність. В даній схемі d розрядів пакета даних поділяються на г рядків і j стовпців, утворюючи прямокутну матрицю. Значення парності обчислюється для кожного рядка і кожного стовпця. Що виходять в результаті i + j +1 бітів парності утворюють розряди виявлення помилок кадру канального рівня.

Припустимо тепер, що в початковому блоці даних з d розрядів відбувається одноразова помилка. У такій двомірної схемою контролю парності про помилку будуть одночасно сигналізувати контрольні розряди рядки і стовпці. Таким чином, одержувач зможе не тільки виявити сам факт помилки, але і за номерами рядка і стовпця знайти пошкоджений біт даних і виправити його! На малюнку показаний приклад, в якому пошкоджений біт в позиції (2, 2) - він змінив своє значення з 1 на 0. Таку одиночну помилку одержувач може не тільки виявити, але і виправити. Хоча нас, в першу чергу, цікавить виявлення та виправлення помилок у вихідних d розрядах, дана схема дозволяє також виявляти і виправляти поодинокі помилки в самих бітах парності. Крім того, дана двомірна схема контролю парності дозволяє виявляти (але не виправляти!) Будь-які комбінації з двох одиночних помилок (тобто подвійні помилки) в пакеті.

Дана система може виявляти і виправляти помилки іноді називають прямим виправленням помилок (Forward Error Correction, FEC). Подібні прийоми широко застосовуються в пристроях зберігання і відтворення звуку, наприклад на лазерних компакт-дисках. У мережах методи виявлення і виправлення помилок можуть використовуватися самі по собі, а також в поєднанні з автоматичними запитами на повторну передачу, які ми розглядали в розділі 3. Методи виявлення та виправлення помилок дуже корисні, оскільки дозволяють знизити необхідну кількість повторних передач. Крім того (що, можливо, навіть важливіше), ці методи дозволяють одержувачу негайно виправляти помилки. Таким чином, одержувач даних може не чекати, поки відправник отримає його повідомлення про помилку і вишле пакет ще раз, що може бути істотною перевагою в мережевих додатках реального часу.

Мій блог знаходять за такими фразами

Відповідальність, за все зміни, внесені в систему за порадами даної статті, Ви берете на себе.