Методи за откриване на изкривявания в кадри

Друг клас методи за анализ на изкривяванията в кадрите са свързани с установяването на самия факт на изкривяване.

Задачата за определяне на броя на повредените битове е много сложна и следователно, ако вероятността от изкривяване на рамката по време на предаване е ниска (което се случва при използване на медни или оптични комуникационни канали), тогава е по-ефективно от гледна точка на сложността повторното изпращане на повредени рамки: ако получателят на рамката открие изкривяване в тази рамка, той моли подателя да изпрати тази рамка отново.

За да сравните сложността на проблемите с корекцията и откриването на изкривяване, разгледайте следния пример. Нека се знае, че не повече от един бит може да бъде изкривен в рамка. Ако размерът на рамката 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)), ограничен от левия и десния 1 бита.

Означаваме с комбинацията от символи E 1 (x) втория фактор в (8.19).

---