ГЛАВА 9. КОДЫ БОУЗА - ЧОУДХУРИ

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

9.1. Определение

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

являются корнями многочленов называется кодом Боуза — Чоудхури. Особо интересны случаи, когда

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

и, следовательно, длина кода делится на не может быть меньше, чем — порядок элемента а. С другой стороны, если то так что число делится на порядок каждого элемента Поэтому не больше следовательно,

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

Теорема 9.1. Пусть код Боуза — Чоудхури состоит из векторов таких, что корнями многочлена являются элементы

Тогда минимальное кодовое расстояние равно самое меньшее d.

Доказательство. Как указывалось в разд. 8.2, приведенное определение кода Боуза — Чоудхури эквивалентно утверждению, состоящему в том, что код совпадает с нулевым пространством матрицы

Рассмотрим определитель, составленный из любого набора различных столбцов матрицы

Выпося из каждого столбца множитель получим

Это определитель Вандермонда

Справедливость равенства можно проверить либо непосредственными вычислениями, либо с помощью следующего рассуждения. 1) Если определитель равен нулю; отсюда вытекает, что разности входят в качестве сомножителей в левую часть равенства (9.3) для всех следовательно, левая часть равенства должна делиться на правую часть равенства. 2) В обеих частях равенства стоят многочлены одной и той же степени, они могут отличаться друг от друга только на постоянный множитель. 3) Этот постоянный множитель должен быть равен 1, поскольку коэффициент при один и тот же в обеих частях. Таким образом, поскольку в определителе D нет совпадающих столбцов, этот определитель обязательно отличен от нуля, и, следовательно, не существует линейно зависимых комбинаций из или меньшего числа столбцов матрицы . В соответствии со следствием 3.2 код, являющийся нулевым пространством матрицы И, имеет минимальное расстояние, равное самое меньшее d. Ч. т. д.