Методи виявлення помилок

Усі методи виявлення помилок засновані на передачі у складі кадру даних службової надлишкової інформації, за якою можна судити з деяким ступенем ймовірності про вірогідність прийнятих даних. Цю службову інформацію прийнято називати контрольною сумою (чи послідовністю контролю кадру - Frame Check Sequence, FCS). Контрольна сума обчислюється як функція від основної інформації, причому необов’язково лише шляхом підсумовування. Адресат повторно обчислює контрольну суму кадру за відомим алгоритмом і у випадку її збігу з контрольною сумою, обчисленою передавачем, робить висновок про те, що дані були передані мережею коректно [1, 4, 11].

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

Контроль за паритетом є найпростішим методом контролю даних. У той же час це найменш потужний алгоритм контролю, оскільки за його допомогою можна знайти тільки одиночні помилки у даних, що перевіряються. Метод полягає у підсумовуванні за модулем 2 усіх біт контрольованої інформації. Наприклад, для даних 100101011 результатом контрольного підсумовування буде значення 1. Результат підсумовування також є один біт даних, що пересилається разом з контрольованою інформацією. При спотворенні під час пересилання будь-якого одного біта вихідних даних результат підсумовування буде відрізнятися від прийнятого контрольного розряду, що говорить про помилку. Однак подвійна помилка, наприклад 110101010, буде невірно прийнята за коректні дані. Тому контроль за паритетом застосовується до невеликих порцій даних, як правило, до кожного байта, що дає коефіцієнт надмірності для цього методу 1/8. Метод рідко застосовується в КМ внаслідок великої надмірності і невисоких діагностичних здібностей.

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

Циклічний надлишковий контроль (Cyclic Redundancy Check, CRC) зраз є найпопулярнішим методом контролю в КМ (і не тільки в мережах, наприклад, цей метод широко застосовується при записі даних на диски та дискети). Метод заснований на розгляді множини вихідних даних як одного багаторозрядного двійкового числа. Наприклад, кадр стандарту Ethernet розміром 1024 байт, буде розглядатись як одне 8192-бітне число. Як контрольна інформація розглядається залишок від ділення цього числа на відомий дільник R. Зазвичай, як дільник вибирається число, що має 17 або 33 розряди, щоб залишок від ділення мав довжину 16 або 32 розряди. При одержанні кадру даних знову обчислюється залишок від ділення на той же дільник R, але при цьому до даних кадру додається і контрольна сума, що міститься в ньому. Якщо залишок від ділення на R дорівнює нулю (є дещо модифікована процедура обчислення залишку, що приводить до одержання у випадку відсутності помилок відомого ненульового залишку, що є більш надійним показником коректності) - то робиться висновок про відсутність помилок в отриманому кадрі, в протилежному випадку кадр вважається спотвореним [1].

Цей метод має більш високу обчислювальну складність, але його діагностичні можливості набагато вище, ніж у методів контролю за паритетом. Метод CRC виявляє усі одиночні помилки, подвійні помилки та помилки у непарному числі біт. Метод має також невисокий ступінь надмірності (наприклад, для кадру Ethernet розміром у 1024 байт контрольна інформація довжиною у 4 байти складає тільки 0,4 %).