Методи виявлення спотворень у кадрах
Інший клас методів аналізу спотворень у кадрах пов'язаний із встановленням самого факту спотворення.
Завдання визначення номерів спотворених бітів має високу складність, і тому, якщо ймовірність спотворення кадрів при передачі невисока (що має місце при використанні мідних або оптоволоконних каналів зв'язку), то ефективнішим з точки зору складності є повторне посилення спотворених кадрів: якщо одержувач кадру виявляє спотворення у цьому кадрі, він просить відправника надіслати цей кадр ще раз.
Для порівняння складності завдань виправлення спотворень та виявлення спотворень розглянемо наступний приклад. Нехай відомо, що у кадрі може бути спотворено трохи більше одного біта. Якщо розмір кадру n = 1000, то
• для виправлення такого спотворення потрібно 10 контрольних бітів,
• а виявлення такого спотворення потрібен лише 1 контрольний біт, значення якого вважається рівним парності кількості одиниць в інформаційних бітах.
Один із методів кодування з метою виявлення спотворень полягає в наступному:
• кадр ділиться на k частин, і
• у кожній частині призначається один контрольний біт, значення якого вважається рівним парності кількості одиниць у решті біт цієї частини.
Якщо при передачі цього кадру біти спотворюються рівноймовірно та незалежно, то для кожної такої частини кадру ймовірність того, що
• ця частина кадру спотворена, та
• тим не менш, її парність вірна (тобто ми вважаємо її неспотвореною)
менше 1/2, тому ймовірність невиявлення спотворення менше 2 -k.
Іншим методом кодування для виявлення спотворень є поліноміальний код (Cyclic Redundancy Check, CRC).
Цей метод заснований на розглядібітових рядків як багаточленів над полем Z 2 = : бітовий рядок виду
(b k , b k−1 , . . . , b 1 , b 0 )
розглядається як багаточлен
b k · x k + b k−1 · x k−1 +. . . + b 1 · x + b 0
Нехай необхідно передавати кадри розміру m + 1. Кожен такий кадр сприймається як многочлен M(x) ступеня ≤ m.
Для кодування цих кадрів вибираються
x j · (x i−j + 1) = G(x) · Q(x)
З теореми про єдиність розкладання на множники багаточленів над полем випливає, що співвідношення (8.16) спричиняє співвідношення
x i−j + 1 = G(x) · Q 1 (x)
Має місце такий факт: якщо
G(x) = x 15 + x 14 + 1
то кожного k = 1, . . . , 32768 багаточлен x k + 1 не ділиться на G(x) без залишку. Тому утворюючий многочлен(8.18) дозволяє виявити двобітні спотворення кадрах довжини ≤ 32768.
3. Уявимо багаточлен спотворень E(x) у вигляді
E(x) = x j · (x k−1 + . . . + 1)
Число k цього запису називають розміром пакета помилок. Очевидно, що k дорівнює розміру підрядка рядка спотворень (тобто того рядка, якому відповідає многочлен E(x)), обмеженого лівим та правим одиничними бітами.
Позначимо знакосполученням E 1 (x) другий множник (8.19).