УДК 004.056.55

АЛГОРИТМ РЕАЛИЗАЦИИ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ КОДОВ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА В ЦИКЛИЧЕСКИХ КОДАХ

Евразийский национальный университет им. , Астана

Научный руководитель – к. ф-м. н, доцент

Коды БЧХ [1] представляют собой обширный класс кодов, способных исправлять многократных пакетов ошибок и занимают заметное место в теории и практике кодирования. Интерес к кодам БЧХ определяется тем, что они позволяют исправлять любое наперед заданное число ошибок и для них существуют эффективные алгоритмы кодирования и декодирования и обладают оптимальными свойствами.

Порождающий многочлен циклического кода можно представить в следующем виде, где – минимальные многочлены корней.

Пусть элементы— корни порождающего многочлена . Тогда

(1)

В результате получаем уравнений, содержащих только величины, определяемые ошибками и не зависящие от кодового слова. Если эти уравнения можно разрешить относительно, то можно определить многочлен ошибок. Нужно выбрать таким образом, чтобы система уравнений могла быть решена относительно каждый раз, когда не более неизвестных отличны от нуля.

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

(2)

Эти элементы поля отличны от синдромного многочлена , но содержат эквивалентную информацию. Нужно подобрать так, чтобы по можно было найтиошибок. В качестве таких можно взять степени примитивного элемента поля .

Определение 1. Пусть заданы q и m, и пусть – любой элемент поля GF(qm) порядка п. Тогда для любого положительного целого числаt соответствующий код БЧХ является циклическим кодом длины п с порождающим многочленом , где — минимальный многочлен элемента .

НЕ нашли? Не то? Что вы ищете?

Определение 2. БЧХ коды длины называются примитивными.

Таким образом, для того, чтобы построить порождающий многочлен примитивного БЧХ кода нужно задать следующий алгоритм:

1. Задать длину кода и числоошибок, которые необходимо исправлять.

2. Найти неприводимый многочлен степениm и построить поле .

3. Найти примитивный элемент в поле .

4. Найти минимальные многочлены для над

5. Взять в качестве

Алгоритмов декодирования БЧХ-кодов много, но в данной статье был рассмотрен самый эффективный: декодер Питерсона-Горенстейна-Цирлера (ПГЦ), который предполагает обращение двух матриц размера . Пусть – элемент поля , по которому строился код БЧХ, а – количество ошибок, исправляемых кодом. Блок-схема данного алгоритма выглядит следующим образом:

Алгоритм ПГЦ следующий:

1. На вход алгоритму поступает принятое слово .

2. Вычисляем компоненты синдрома

3. Полагаем

4. Строим матрицу

5. Вычисляем определитель матрицы . Если он равен нулю, уменьшаемна единицу и возвращаемся к шагу 4.

6. Обращаем матрицу и вычисляем коэффициенты многочлена :

=

7. Вычисляем корни многочлена . Поскольку число элементов поля конечно, обычно кор­ни ищут процедурой Ченя. Эта процедура заключается в последовательном вычислении для каждогои проверки полученных значений на нуль.

8. Найдя корни, найдем локаторы ошибок(корни многочлена являются обратными к локаторам ошибок).

9. Если код код двоичный, то ошибки известны. В противном случае вычислим их:

=

10. Исправляем в полученном слове ошибки, и получаем на выходе алгоритма кодовое слово.

Литература

1. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.