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

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

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

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

1101011 | 1011

10111111

1100

1011

1111

1011

1001

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

10111111

1101

1011

1101

1011

1100

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

0111010

 Осуществляем 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

10111011

1100

1011

1110

1011

101=R₀(х)

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

1011111 | 1011

10111000

0001

0000

0011

0000

0111

0000

111=R₁(x)

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

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

0111111 | 1011

1011110

1001

1011

0101

0000

101=R₂(x)

R₂=R₀F(x)=F(x)Е(х)=0111111

1000000

1111111