Пример
Процедура кодирования циклическим кодом
Процедура кодирования записывается следующим образом:
V(x)=U(x)*xn-k Å R(x)
R(x)= U(x)*xn-k mod g(x)
В этом случае старшие k разрядов кодового слова являются информационными. Младшие разряды r=n-k – являются проверочными.
Закодировать информационную последовательность U=0110 циклическим кодом (7,4) с образующим полиномом g(x)= x3+x+1.
U(x)= x2+x, r=n-k=3, U(x)*x3= x5+x4
R(x)=(x5+x4) mod (x3+x+1)=1
V=0110001 ® V(x)= x5+x4+1
Сложение коэффициентов при одинаковых степенях осуществляется по модулю 2.
Деление можно выполнять в двоичном виде.
U(x)*x3= x5+x4 ® 0110000
g(x) ® 1011
R=001®V=0110001
Число проверочных символов в кодовой комбинации всегда равно степени образующего полинома.
В основу принципа декодирования циклического кода положено свойство делимости кодовых слов без остатка на свой образующий полином.
Декодирование с обнаружением ошибок
Если принятая комбинация Y(x) делится без остатка на g(x), то считается, что ошибок нет или произошла не обнаруживаемая кодом ошибка.
|
|
В случае обнаруженной ошибки имеет место ненулевой остаток от деления, который называется синдромом циклического кода.
S(x)=Y(x) mod g(x)=[V(x)+e(x)] mod g(x)=e(x) mod g(x), гдеe(x) – полином ошибки.
Декодирование с исправлением ошибок
Обычно в памяти декодера заданного циклического кода хранится некоторый типовой вектор ошибки и соответствующий ему типовой синдром.
Ошибкевида e0 =1 соответствуетсиндром S0 =1. Назовемих типовыми, так как это соответствие сохраняется для любого циклического кода.
S0(x)=e0(x) mod g(x)
Если вектор ошибки e' получается из e0 путем i циклических сдвигов влево, то есть
e'(x)=e0 (x)*xi mod (xn+1),
то синдром ошибки e' S’ можно определить через типовой синдром S0 по формуле
S'(x)=S0(x)*xi mod g(x),
Тогда S0(x)= S'(x)* x-i mod g(x), то есть типовой синдром образуется в схеме, осуществляющей деление на образующий полином g(x), при циклическом сдвиге S’(x) вправо через i тактов работы после получения S’(x).