Циклическая контрольная сумма.

Помехоустойчивое кодирование предполагает введение в

передаваемое сообщение, наряду с информационными, так называемых

проверочных разрядов, формируемых в устройствах защиты от ошибок

(кодерах на передающем конце, декодерах – на приемном).

Избыточность позволяет отличить разрешенную и запрещенную

(искаженную за счет ошибок) комбинации при приеме, иначе одна

разрешенная комбинация переходила бы в другую.

Помехоустойчивый код характеризуется тройкой чисел (n, k, d0), где

n – общее число разрядов в передаваемом сообщении, включая

проверочные (г), k=n-r – число информационных разрядов, d0 –

минимальное кодовое расстояние между разрешенными кодовыми

комбинациями, определяемое как минимальное число различающихся

бит в этих комбинациях. Число обнаруживаемых (tо) и (или)

исправляемых (tи) ошибок (разрядов) связано с параметром d0

соотношениями:

d0 ≥ tо +1,

d0 ≥ 2tи +1,

d0 ≥ tо + tи+ 1

Иногда используются дополнительные показатели

избыточности, производные от приведенных выше характеристик n, k: R

= г / n – относительная избыточность, v = k / n – относительная

скорость передачи.

Рис. 1.3. Классификация помехоустойчивых кодов

Циклические коды (CRC)

Циклические коды – это семейство помехоустойчивых кодов,

включающее в себя в качестве одной из разновидностей коды Хэмминга.

В целом оно обеспечивает большую гибкость с точки зрения

возможности реализации кодов с необходимой способностью

обнаружения и исправления ошибок, определяемой параметром d0, по

сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Широкое

использование циклических кодов на практике обусловлено также

простотой реализации соответствующих кодеров и декодеров.

Основные свойства и само название циклических кодов связаны с

тем, что все разрешенные комбинации бит в передаваемом сообщении

(кодовые слова) могут быть получены путем операции циклического

сдвига некоторого исходного кодового слова:

(a0a1…an-2an-1);

(an-1a0a1…an-2);

……………………….

Циклические коды задаются с помощью так называемых

порождающих полиномов (многочленов) g(x) или их корней.

Порождающий полином имеет вид

G(x)=gr xr + gr-1 xr-1 + … + g0

где gi={0, 1}, x=2. Кроме того, вводятся полином исходного

cообщения

u(x) = uk-1 xk-1 + uk-2 xk-2 + … +u0

и кодированного сообщения

A(x) = an-1 xn-1 + an-2 xn-2 + … + a0

Для этих полиномов, представляющих собой по существу

альтернативную запись чисел в двоичной системе счисления,

определяются операции сложения, умножения и деления, необходимые

для организации кодирования и декодирования сообщения. Все

операции выполняются по модулю 2.

Последовательность кодирования на примере циклического кода

(7, 4, 3), имеющего g(x) = x3 + x + 1, следующая:

1) информационная часть сообщения записывается в виде

полинома:

u(x) = uk-1 xk-1 + uk-2 xk-2 + … +u0

В рассматриваемом примере k=4 и для сообщения 0111 получается

u(x) = x2 + x + 1

2) u(x) умножается xr, что соответствует циклическому сдвигу

исходного сообщения на r разрядов влево:

u(x) x3 = (x2 + x + 1) x3 = x5 + x4 + x3

3) полученный многочлен делится на g(x):

u(x)·xr/q(x) = c(x) ⊕ R(x)/q(x)

где c(x) – полином-частное с максимальной степенью (k—1);

R(x) – полином-остаток с максимальной степенью (r-1);

⊕ – обозначение поразрядной операции суммирования по модулю 2

(исключающее ИЛИ). Кодированное сообщение представляется в виде

A(x)=u(x)xr ⊕ R(x)

Таким образом, в этом случае

A(x) = (x5 + x4 + x3) ⊕ x = x5 + x4 + x3 + x

Передаваемое кодированное сообщение в обычной двоичной форме

имеет вид

0111 010

↔ ↔

k – бит r – бит