Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

9.1 Граница БЧХ

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

Теорема 9.1. Пусть g(x) - порождающий многочлен циклического кода длины n = 2m-1 и a - примитивный элемент поля GF(2m). Если a, ..., ad-1 суть корни многочлена g(x), то кодовое расстояние кода, порожденного многочленом g(x), не меньше d.

Доказательство. Рассмотрим проверочную матрицу кода

.

Для того чтобы показать, что расстояние кода не меньше d, достаточно показать, что любая совокупность из (d-1) столбцов матрицы линейно независима. Выберем произвольную совокупность столбцов матрицы с номерами jd-1, ...,j1 и составим из них соответствующий определитель:

.


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

.

Последний определитель можно вычислить как определитель Вандермонда, если положить xi = , i = jd-1, ..., j1. Таким образом,

∆ = П(xi - xk).
                              i>k  

Поскольку a примитивный элемент, то xi = не равно xk = , и следовательно ∆ ≠ 0. Поэтому столбцы определителя линейно независимы, т. е. любая совокупность из (d-1) столбцов матрицы линейно независима, и кодовое расстояние не меньше d.