Контроль правильності передачі
Контроль правильності передачі При передачі інформації по неякісних та/або каналах зв'язку, що розділяються, можливі помилки, тобто спотворення інформації, що передається. Ці помилки необхідно виявляти та виправляти.
Контроль приймачем інформації може бути побайтним та пакетним. Побайтний метод передбачає, кожен переданий байт доповнюється бітом парності (чи непарності), тобто у разі, коли кількість одиниць в переданому інформаційному байті парне, то біт дорівнює "0", а якщо непарне - то "1". Метод може застосовуватися як при байтовій передачі, так і пакетної передачі. Імовірність того, що помилка не буде виявлена досить велика. До цього може призвести наявність парної кількості помилок в інформаційних бітах, а також одночасне спотворення інформаційного та контрольного бітів.
Пакетний метод зводиться до того, що в кінці кожного пакета, що передається, додається контрольна сума (довжиною 8, 16 або 32 біта), яка включає в себе інформацію про всі інформаційні біти пакета. Метод підрахунку контрольної суми вибирається те щоб, з одного боку, її було обчислити, з другого боку, щоб вона досить надійно виявляла помилки. Зазвичай використовуються контрольні суми трьох видів.
a) Сума за модулем 2 всіх байтів (слів) пакета, тобто. обчислення йде за правилами: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0. При цьому одноразові помилки (тобто одна помилка на пакет) виявляються з ймовірністю 100%, дворазові (дві помилки на пакет) – з ймовірністю 7/8 (оскільки у випадку, коли дві помилки потрапляють в той самий розряд, вони не можуть бути виявлені). Потрібно також врахувати, що бувають ще й пачки помилок (спотворення кількох бітів), які цим методом виявляються досить погано. Така сума легко та швидко вважаєтьсяпрограмним шляхом, тому що відповідна команда обчислення суми за модулем 2 є практично у всіх процесорів.
b) Арифметична сума всіх байтів (або слів) пакета. При її обчисленні відкидаються старші розряди задля збереження заданої розрядності контрольної суми (зазвичай 8 чи 16). Одноразові помилки виявляються із ймовірністю 100%. Імовірність невиявлення дворазових помилок у найгіршому випадку становить 1/8*1/4 = 1/32. Така найгірша ситуація спостерігається, коли в кожному з 8 розрядів всіх байт пакета або в кожному з 16 розрядів усіх слів пакета є половина логічних одиниць і половина логічних нулів. При цьому дворазові помилки не виявляються, коли в одному розряді один з бітів із "0" переходить внаслідок помилки в "1", а інший біт у цьому ж розряді з "1" переходить у "0", що не змінює загальної суми. Арифметична сума також легко та швидко обчислюється програмно.
c) Циклічна контрольна сума. Її застосування викликане прагненням підвищити якість контролю, тобто збільшити ймовірність виявлення помилок. Цю суму не можна так само просто, як попередні обчислити програмно, проте надійність даного методу контролю незмірно вища. Цей метод часто називають "циклічним контролем надмірності" (скорочено CRC - Cyclic Redundancy Check). Сенс його полягає у наступному.
Циклічна контрольна сума.
Весь пакет розглядається як N-розрядне двійкове число, де N - кількість бітів у пакеті. Для обчислення контрольної суми це число ділиться на деяке постійне число, обране спеціальним чином (але ділиться не просто, а модулем 2). Приватне від цього поділу відкидається, а залишок використовується як контрольна сума.
Як бачимо, цей метод не такий простий, як попередні два.Але ми не заглиблюватимемося в його математичне обґрунтування. Даний метод виявляє одноразові помилки з ймовірністю 100%, а будь-яка інша кількість помилок з ймовірністю приблизно P = (1 - 2^-n), де n - кількість розрядів контрольної суми (проте це вірно лише за умови, що N> ). Наприклад, при n = 8 дана ймовірність становитиме P = 0.996, для n = 16 вона буде P = 0.999985.
А тепер коротко пояснимо, що таке поділ за модулем 2. Нехай пакет (послідовність біт) має такий вигляд: 101111001110 (для простоти беремо невелику розрядність). Як дільник (називається зазвичай поліномом) візьмемо 10011. Як він вибирається? Це число має ділитися без залишку тільки на одиницю і на себе (тобто це має бути просте число в сенсі розподілу по модулю 2). Розрядність полінома береться на одиницю більша, ніж потрібна розрядність контрольної суми (залишку від розподілу). Так, щоб був 8-розрядний залишок, треба брати 9-розрядний поліном. У нашому випадку поліном 5-розрядний, отже залишок буде 4-розрядний. Для отримання 8-розрядного залишку можна використовувати поліноми 100011101=4358, а також 5438, 5518, 7278.