4. Важнейшие коды

4.1. Коды Боуза — Чоудхури — Хоквингема

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

Теорема 4.1. Если порождающий многочлен циклического кода длины имеет своими корнями где некоторое целое число, то минимальное расстояние этого кода не меньше чем

Доказательство. Если в (3.24) положить то

Определитель любой подматрицы из столбцов матрицы в левой части (4.1) имеет следующий вид:

Определитель в правой части последнего равенства известен как определитель Вандермонда [4, 5], который, как известно, равен и в данном случае отличен от нуля, поскольку Отсюда и из первой части теоремы 3.1 следует справедливость теоремы 4.1.

Расстояние гарантируемое этой теоремой, называется нижней БЧХ-границей минимального расстояния. Циклические коды с минимальной степенью или, что то же самое, с минимальным числом проверочных символов, удовлетворяющие указанным в этой теореме условиям при заданных называются БЧХ-кодами. Другими словами, БЧХ-код — это циклический код, корнями порождающего многочлена которого являются элементы где пробегает все числа из -циклов, содержащих и только они. Чтобы теорема 4.1 гарантировала исправление кодом ошибок веса следует положить Так как, согласно теореме 2.13, длина каждого цикла, содержащего число равна или некоторому делителю то степень т. е. число проверочных символов кода, не превосходит Если оба элемента не являются корнями то называют конструктивным расстоянием данного БЧХ-кода. В частном случае БЧХ-коды называют также примитивными БЧХ-кодами (или БЧХ-кодами в узком смысле). В случае эти коды представляют собой не что иное, как циклические коды Хэмминга. В табл. помещенной в приложении, для приведены возможные значения конструктивного расстояния БЧХ-кодов, соответствующие им числа информационных символов и, когда это известно, фактическое минимальное расстояние и разность между фактическим и конструктивным минимальными расстояниями. Один из алгебраических методов нахождения числа информационных символов БЧХ-кодов описан в работе [3]. Как показано в примере 4.6, нижняя БЧХ-граница может быть несколько обобщена.

Пример 4.1. Рассмотрим примитивный БЧХ-код с параметрами . В этом случае -циклами, содержащими числа 1, 2, 3, 4, 5, 6, являются следующие множества: Следовательно, рассматриваемый код имеет 10 проверочных символов. Конструктивное расстояние этого кода равно 7. Выбирая в качестве корень многочлена и основываясь на задаче 2.60, находим

Пример 4.2. Пусть Минимальное целое число такое, что согласно табл. равно 11.

Совокупность чисел в данном случае содержится в Следовательно, рассматриваемый код имеет 11 проверочных символов и конструктивное расстояние, равное 5. Если в качестве взять корень неприводимого многочлена с показателем 23, то, как следует из задачи будет порождающим многочленом кода. Вместо в качестве порождающего многочлена можно также взять Этот код имеет минимальное расстояние 7 (см. пример 4.11), которое не совпадает с конструктивным расстоянием, равным 5. Прейндж показал, что этот код эквивалентен двоичному совершенному -коду Голея [7]. Поскольку то порождающим многочленом кода, двойственного к этому циклическому коду Голея, является Следовательно, минимальный вес двойственного кода равен 8.

Пример 4.3. Пусть элемент порядка 11 поля (так как делится на 11, то такой элемент существует). В данном случае -циклом, содержащим 1, является множество нижняя БЧХ-граница равна 4. Однако, как известно [3, 4], минимальное расстояние получающегося кода в действительности равно 5, и этот код эквивалентен троичному -коду Голея. Поскольку многочлены являются неприводимыми многочленами над степени 5 с показателем 11 (см. табл. то любой из них может быть взят в качестве порождающего многочлена.

Утверждение 4.1. Пусть минимальное целое число, такое, что Тогда число проверочных символов двоичного БЧХ-кода длины с конструктивным расстоянием не превосходит

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

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

Краткое доказательство. Так как элемент также является корнем то, согласно теореме 4.1, минимальное

расстояние кода С не меньше 3. Так как этот код лежит на границе Хэмминга, то он является совершенным.

Пример 4.4. БЧХ-коды, для которых называются кодами Рида — Соломона [8]. Точнее, коды Рида — Соломона — это -ичные циклические коды длины с порождающим многочленом где один из примитивных элементов поля . В этом случае минимальное расстояние а число информационных символов . В то же время, согласно следствию Следовательно, для кодов Рида — Соломона

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

так Следовательно, минимальное расстояние двойственного кода равно Коды Рида — Соломона используются для построения кодов Юстесена (разд. 4.6) и кодов, исправляющих пачки ошибок (разд. 4.8).

Пример 4.5. Рассмотрим БЧХ-коды с параметрами Так как то Кроме того, заметим, что Отсюда следует, что для всех . А именно если то -циклом, содержащим является множество Тогда, если один из элементов порядка в поле то

— многочлен над являющийся порождающим многочленом рассматриваемого БЧХ-кода. Как и в примере 4.4, из следствия 3.1 получаем, что этот код является разделимым кодом с максимально достижимым расстоянием Этот код имеет на два информационных символа больше, чем код Рида — Соломона с теми же параметрами [51]

Задача 4.3. Проверить, что аналогичный ревультат можно получить, если в примере 4.5 положить

Утверждение 4.4 [4]. Пусть неприводимый многочлен степени удовлетворяющий условию Тогда минимальное расстояние циклического -кода, где показатель с порождающим многочленом не меньше 6.

Краткое доказательство. Пусть — один из корней Так как то также корень Из того, что следует, что а следовательно, и также будут корнями Таким образом, имеет своими корнями так что, согласно теореме 4.1, минимальное расстояние рассматриваемого кода не меньше 6. По табл. А.2 можно установить, что многочлен является неприводимым и имеет показатель 17. Если рассмотреть циклический -код с порождающим многочленом то из верхней границы Хэмминга будет следовать, что минимальный вес этого кода не может быть больше. Следовательно,

Утверждение 4.5. 1) Минимальное целое число I, такое, что равно Минимальное расстояние циклического -кода С, порождающим многочленом которого является неприводимый многочлен степени над с показателем не меньше 5.

Краткое доказательство. Если то 24- 1 не делится на поскольку Это означает, что существует по крайней мере один неприводимый многочлен, указанный в утверждении 4.5. Если один из его корней, то порядок должен быть равен так что Таким образом, корни это элементы Следовательно, Согласно утверждению 4.4, минимальный вес четного подкода кода С не меньше 6. Если допустить, что минимальный вес кода не больше 4, то вес четного подкода также будет не больше 4, что противоречит доказанному выше.

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

минимальное расстояния БЧХ-кодов различаются редко, но тем не менее существует бесконечно много примитивных БЧХ-кодов, минимальное расстояние которых больше конструктивного расстояния (см. табл. Известно несколько достаточных условий того, что минимальное и конструктивное расстояния совпадают [3, 4, 10—13]. Одно из таких условий дает приведенное ниже утверждение 4.14. А именно из утверждения 4.14 следует, что минимальное расстояние -ичного БЧХ-кода длины и конструктивным расстоянием равно конструктивному расстоянию. Рассмотрим произвольный -ичный БЧХ-код с параметрами Пусть конструктивное расстояние этого кода. Если А — минимальное целое число вида такое, что то Поскольку минимальное расстояние этого БЧХ-кода не может быть больше минимального веса БЧХ-кода той же длины с конструктивным расстоянием то

Для примитивных кодов последняя граница может быть несколько улучшена [13]:

Существует гипотеза, что эта оценка является не очень хорошей. Для примитивных БЧХ-кодов при фиксированной скорости имеют место следующие асимптотические равенства: обозначение натурального логарифма) [52]. Следовательно, при фиксированной скорости отношение стремится к нулю.

С помощью описанного в следующем разделе алгебраического алгоритма декодирования можно исправить все конфигурации ошибок, исправление которых гарантируется конструктивным расстоянием (но не минимальным расстоянием). Для бесконечного числа наборов значений параметров в работе [9] показано существование циклических кодов, минимальное расстояние которых несколько больше минимального расстояния БЧХ-кодов с теми же параметрами Однако, поскольку при длинах до нескольких тысяч параметры БЧХ-кодов не хуже параметров других кодов, для которых известны конструктивные методы построения, а кроме того, благодаря существованию эффективного алгоритма декодирования БЧХ-коды являются одим из важнейших классов блоковых кодов.

Пример 4.6 [14]. Пусть 0 — элемент порядка поля и С представляет собой -ичныи циклический код длины с минимальным расстоянием и порождающим многочленом

Пусть Тогда

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

где Положим и введем величины

Если

поскольку Кроме того, положим

Так как то Следовательно, . С другой стороны,

Так как то приведенное выше выражение равно но это противоречит тому, что Поэтому Положив найдем нижнюю БЧХ-границу. Это показывает, что полученная выше граница является обобщением нижней БЧХ-границы. Известен также ряд других обобщений БЧХ-границы [14].