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

Способ декодирования с обнаружением ошибок

Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования основана на использовании свойства делимости без остатка кодового многочлена Р(x) циклического (n,m)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом F¢(x) на g(x), вычисление и анализ остатка R(x). Если R(x)=0, то принятое кодовое слово считается неискаженным. Если R(x)¹0, то принятое кодовое слово стирается и формируется сигнал "ошибка".

Способ декодирования с исправлением ошибок

Декодирование заключается в определении номера искаженного разряда и его автоматического исправления. А также отделения информационных разрядов от контрольных.

Рассмотрим три методики декодирования

Определение искаженного разряда с помощью матрицы ошибок.

Матрица одиночных ошибок имеет вид

,
где - единичная матрица; - прямоугольная проверочная матрица.

Строки матрицы определяются из выражений

- остаток от деления на образующий полином ,

где - значение i-той строки матрицы ;

i - номер строки матрицы .

Для определения искаженного разряда необходимо определить остаток от деления принятой кодовой комбинации на порождающий многочлен . Далее находится строка в проверочной матрице с полученным остатком (синдромом). Искаженный разряд – это разряд в строке (соответствующая строке проверочной матрицы) единичной матрицы, в которой стоит «1». Искаженный разряд исправляется посредством сложения строки единичной матрицы с полученной комбинацией.

Свойства циклических кодов по обнаружению ошибок

Свойства циклических кодов полностью определяются выбранным порождающим (образующим) многочленом .

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

2. Циклический код с порождающим многочленом обнаруживает все нечетные ошибки. Используя правила построения проверочной матрицы для , получим . При такой проверочной матрице остаток определяется суммой по модулю 2 всех элементов принятой кодовой комбинации (проверка на четность). Поэтому все искажения на нечетном количестве позиций будут обнаружены.

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

4. Циклический код с многочленом степени обнаруживает все групповые ошибки длительностью в разрядов и менее. Любая групповая ошибка в разрядов описывается многочленом степени , т.е. . Многочлен же степени на многочлен степени не делится и, таким образом, ошибка обнаруживается.

5. Циклический код с порождающим многочленом степени не обнаруживает часть ошибок -й кратности.

6. Циклический код с порождающим многочленом степени не обнаруживает часть ошибок более -й кратности.

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

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

или , при длине кодовой комбинации ;

, при длине кодовой комбинации .

Разработан ряд методик по выбору порождающего многочлена . В литературе коды называют по фамилиям ученых, предложивших ту или иную методику. Так получили свое название коды Боуза-Чоудхури-Хоквингема (БЧХ), коды Рида-Соломона, коды Файра и др.

Не нашли, что искали? Воспользуйтесь поиском по сайту: