Методика обнаружения и исправления ошибок в циклическом коде

Матричное представление циклического кода

Как и всякий линейный код ц.к. может быть построен на основе порождающей и проверочных матриц. Для формирования строк порождающей матрицы по второму способу построения ц.к. берется комбинация простого к - разрядного кода, содержащего только одну единицу. Затем они умножаются на одночлен

х^n-k и делятся на порождающий полином; полученные остатки дописываются в n-k последние строки проверочной матрицы.

Пример: построить порождающую матрицу для ц.к. (7,4) в качестве порождающего многочлена выбрать х³+х²+1.

P(7,4)=

Для получения первой строки дополнительной матрицы необходимо первую строку информационной матрицы умножить на х³, а затем разделить на порождающий полином.

0001*х³ = х³ | x³+x²+1

x³+x²+1 1

x²+1 =101

0010*x³ = x⁴ | x³+x²+1

x⁴+x³+x x+1

x³+x

x³+x²+1

x²+x+1 = 111

0100*x³ = x⁵ | x³+x²+1

x⁵+x⁴+x² x²+x+1

x⁴+x²

x⁴+x³+x

x³+x²+x

x³+x²+1

x+1 = 011

1000* x³ = x⁶ | x³+x²+1

x⁶+x⁵+x³ x³+x²+x

x⁵+x³

x⁵+x⁴+x²

x⁴+x³+x²

x⁴+x³+x

x²+x = 110

Чтобы получить проверочную матрицу необходимо определить проверочный полином.

x⁷+1 | x³+x²+1

x⁷+x⁶+x⁴ x⁴+x³+x²+1 = g(x) = 11101

x⁶+x⁴+1

x⁶+x⁵+x³

x⁵+x⁴+x³+1

x⁵+x⁴+x²

x³+x²+1

x³+x²+1

| 0 0 1 1 1 0 1 |

h(p) = | 0 1 1 1 0 1 0 |

| 1 1 1 0 1 0 0 |

Для обнаружения и исправления ошибок в кодограмме, принятой из канала, используется порождающий полином. Если принятая циклическая кодограмма делится без остатка на порождающий полином, то можно сделать вывод – данная кодограмма является разрешенной. Если остаток от деления этой кодограммы отличен от нуля, то в данном случае используется следующая методика обнаружения и исправления ошибок в циклическом коде:

1. Обнаружение и исправление ошибок в циклическом коде производится по остаткам от деления принятой комбинации на порождающий полином. Нулевой остаток свидетельствует о правильности кодограммы. Для того, чтобы найти ошибочный разряд в принятой кодограмме необходимо выполнить следующие действия: Принятую комбинацию делят на порождающий полином.

2. Подсчитывают вес остатка W_ост. Если вес остатка W_ост меньше или равен кратности исправляемых ошибок, то принятую комбинацию складывают по модулю 2 с полученным остатком, Сумма дает исправленную комбинацию.

3. Если W_ост больше кратности исправляемых ошибок, то производят циклический сдвиг принятой комбинации В(х) влево на один разряд. Комбинацию, полученную в результате сдвига, делят на порождающий полином. Если в результате повторного деления окажется, что вес остатка не превосходит кратность исправляемых ошибок, то делимое суммируют с остатком и производят циклический сдвиг вправо на один разряд. Полученная в результате комбинация уже не содержит ошибки.

4. Если после первого циклического сдвига и последующего деления остаток получается с весом W_ост превышающим кратность ошибки, то повторяют операцию по пункту 3 до тех пор, пока не будет его вес меньше или равным кратности исправляемых ошибок. В этом случае полученную в результате последнего циклического сдвига комбинацию суммируют с остатком и производят циклический сдвиг вправо ровно на столько разрядов, на сколько была сдвинута суммарная с последним остатком комбинация относительно принятой комбинации В(х).

Рассмотрим пример декодирования запрещенной кодограммы. Порождающий полином имеет следующий вид

Р(х) = х³+х+1.

Разделим полученную комбинацию 1110010 на порождающий полином, представленный в двоичной виде (1011).

1 1 1 0 0 1 0 1 0 1 1

1 0 1 1

Дата добавления: 2014-01-13