Декодирование информации циклическими кодами

Идея обнаружения ошибок в принятом ЦК заключается в том, что при отсутствии ошибок закодированная кодовая комбинация делится без остатка на образующий полином, при этом контрольные символы отбрасываются. Принятая кодовая последовательность может быть представлена как F¢(x)=F(x)+E(x), где Е(х) – полином ошибок.

Пример: код (7,4); F(x)=1101001; P(x)=1011.

Пусть придет F¢(x)=1101011. Поделим F¢(x)/Р(х).

1101011 | 1011

1011 1111

1011

1011

1011

010=R(x) – наличие остатка свидетельствует об ошибке.

Идея обнаружения и исправления ошибок осуществляется несколькими вариантами декодирования ЦК:

I. Алгоритм декодирования ЦК с использованием весовой оценки остатка при делении F¢(x)/Р(х).

1) Вычисляем R(x)= F¢(x)/Р(х), если R(x)=0, то F¢(x)= F(x)

если R(x)≠0 Þ произошла ошибка и следует процедура исправления.

2) Определяем вес R(x).

Если W_R(x)≤t_испр, то принятая комбинация F¢(x)ÅR(x)=F(x).

Если W_R(x)>t_испр, то производится циклический сдвиг на один цикл влево. Полученную комбинацию снова делим на Р(х). Если теперь W_R(x)≤t_испр, то циклически сдвинутую кодовую последовательность суммируем по модулю два с R(x) и сдвигаем в обратном направлении на один сдвиг и получаем F(x). А если W_R(x)>t_испр, то производим дополнительный сдвиг влево и делим полученную комбинацию на Р(х) и снова проверяем и т.д.

Пример: Q(x)=1001; P(x)=1011; F(x)=1001110; F¢(x)=1101110; t_испр=1 двоичный символ.

1) Вычисляем R(x)= F¢(x)/Р(х)

1101110 | 1011

1011 1111

1011

1011

1011

111=R(x)

2) · Вес R(x) (количество единиц)> t_испр: W_R(x)=3, t_испр=1, W_R(x)>t_испр (3>1)

Произведем циклический сдвиг F¢(x) на один цикл влево F¢¢(x)=F¢(x)×х=1011101

Вычисляем R(x)= F¢¢(x) /Р(х)=1011101/1011=101

· W_R(x)=2>t_испр=1

Произведем циклический сдвиг F¢¢(x) на один цикл влево F¢¢¢(x)=F¢(x)×х²=0111011

Вычисляем R(x)= F¢¢¢(x)/Р(х)= 0111011/1011=001, W_R(x)=1=t_испр.

· Циклически сдвинутую кодовую последовательность F¢¢¢(x) суммируем по модулю два с R(x)

F¢¢¢(x)ÅR(x)=0111011

. 001

· Осуществляем 1-ый циклический сдвиг вправо: 0011101

2-ой циклический сдвиг вправо: 1001110= F(x).

II. Алгоритм декодирования на основе цикличности кода.

При сдвиге разрешенной кодовой комбинации на любое число разрядов влево или вправо также получается разрешенная кодовая комбинация. Это свойство является основным свойством циклического кода.

Рассмотрим алгоритм на примере: F¢(x)=1011111, F(x)=1111111, Р(х)=1011

1) Определим остаток от деления соответствующий наличию ошибки в старшем разряде.

Е₆(х)=1000000

Е₅(х)=0100000

Е₄(х)=0010000

Е₃(х)=0001000

Е₂(х)=0000100

Е₁(х)=0000010

Е₀(х)=0000001

Если ошибка произошла в k-ом символе, то Е_i(х)/Р(х) не зависит от вида переданной информации, а значит от кодовой последовательности и вида передаваемой информации.

R¢(x)=Е₆(х)/Р(х)=1000000 | 1011

1011 1011

1011

1011

101=R₀(х)

2) Определим остаток от деления R₁(х)=F¢(x)/Р(х)

1011111 | 1011

1011 1000

0000

0000

0000

111=R₁(x)

Т.к. R₁≠R₀ Þ сдвигаем F¢(x) влево на одну позицию, получаем F¢¢(x)=0111111

3) Определим остаток от деления R₂(х)=F¢¢(x)/Р(х)

0111111 | 1011

1011 110

1011

0000

101=R₂(x)

R₂=R₀ Þ F(x)=F¢¢(x)ÅЕ(х)=0111111

1000000