7.6. КОДЫ БЧХ, ИСПРАВЛЯЮЩИЕ t ОШИБОК

Теорема 8. (Граница БЧХ.) Пусть — циклический код с таким порождающим многочленом что для некоторых целых чисел и 61 выполняется равенство

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

Доказательство. Если -кодовый вектор из то

так что выполняется равенство где

(Заметим, что матрица не обязательно должна быть полной проверочной матрицей кода

Идея доказательства состоит в том, чтобы показать, что любые 8—1 или менее столбцов являются линейно независимыми. Предположим, что вес вектора с удовлетворяет условию т. е. что если и только если Тогда из равенства вытекает, что

Следовательно, определитель левой матрицы равен нулю. Но этот определитель равен произведению на определитель

который является определителем Вандермонда и согласно лемме 17 гл. 4 отличен от нуля. Получаем противоречие. 9 Примеры. Порождающим многочленом двоичного кода Хэмминга является (см. § 7.3). Так как по свойству гл. то код имеет пару последовательных нулей: Следовательно, по теореме 8 минимальное расстояние кода не меньше 3.

Порождающий многочлен двоичного кода БЧХ с исправлением двух ошибок равен Но Следовательно, код имеет четыре последовательных нуля: так что что совпадает с результатом гл. 3.

На самом деле минимальное расстояние кода может быть и больше чем так как при замене элементов матрицы соответствующими им -векторами над GF(q) может оказаться, что больше чем столбцов матрицы линейно независимы.

Следствие 9. Минимальное расстояние циклического кода длины с нулями где числа взаимно просты, равно по меньшей мере

Доказательство. Пусть Так как взаимно просты, то также является примитивным корнем степени из единицы. Следовательно, найдется такое что и код имеет последовательных нулей: Дальнейшее доказательство совпадает с доказательством теоремы 8 с заменой а на

Коды БЧХ. Определение. Циклический код длины над GF(q) называется кодом БЧХ с конструктивным расстоянием если для некоторого целого числа его порождающий многочлен равен:

Иными словами, нормированный многочлен над GF(q) наименьшей степени такой, что элементы являются его корнями. Следовательно, с — кодовый вектор тогда и только тогда, когда

Таким образом, точно последовательных степеней элемента а представляют собой нули кода. Из теоремы 8 заключаем, что минимальное расстояние кода больше или равно конструктивному расстоянию

Равенство (7.17) означает, что проверочная матрица кода равна:

где каждый элемент должен быть заменен на соответствующий столбец из элементов над GF(q).

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

Теорема 10. Код БЧХ над длины с конструктивным расстоянием имеет минимальное расстояние а его размерность не меньше чем (Число определено в § 7.5.)

Размерность больше этой нижней границы в том случае, когда строки матрицы выписанной над GF(q), линейно зависимы, или (что эквивалентно) когда степень многочлена, стоящего в правой части равенства (7.17), меньше чем Примеры такой ситуации приводятся ниже.

Уравнения (7.1) и (7.9) задают соответственно порождающую матрицу и одну из форм проверочной матрицы кода.

Замечания. (1). Коды при иногда называют кодами БЧХ в узком смысле. При коды называются примитивными, так как в этом случае — примитивный элемент поля (а не только примитивный корень степени из единицы).

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

(2). При фиксированном коды БЧХ вложены друг в друга так, что код с конструктивным расстоянием содержит код с конструктивным расстоянием 62 в том и только в том случае, когда

(3). В общем случае дуальный коду БЧХ кодом БЧХ не является.

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

Таким образом, и размерность кода не менее Проверочная матрица кода равна:

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

Примеры. Начнем с перечисления на рис. 7.2 и 7.3 всех (в узком смысле примитивных) двоичных кодов БЧХ длины 15 и 31. К счастью, минимальные многочлены элементов полей и GF(32) уже были выписаны в § 4.4.

Рис. 7.2. Коды БЧХ длины 15

Рис. 7.3. Коды БЧХ длины 31

Заметим, что коды с конструктивным расстоянием 9 и 11 совпадают. Это происходит по следующей причине. Порождающий многочлен последнего кода равен:

Но и поэтому элементы имеют один и тот же минимальный многочлен Следовательно,

что совпадает с порождающим многочленом для кода с конструктивным расстоянием 9.

Этот пример показывает, что код БЧХ с конструктивным расстоянием 6 может совпадать с кодом БЧХ с конструктивным расстоянием где Наибольшее возможное такое называется расстоянием Боуза. Согласно границе БЧХ истинное минимальное расстояние кода равно по меньшей мере но, как показывает следующий пример, может быть и больше.

На рис. 7.4. приведены двоичные (непримитивные) коды БЧХ длины Циклотомические классы имеют вид:

Так как то мультипликативный порядок 23 по модулю 2 равен 11 (см. § 7.5). Таким образом, распадается на линейные множители — примитивный корень степени 23 из единицы в

Над многочлен согласно таблице на рис. 7.1 имеет следующее разложение:

где

Порождающим многочленом кода БЧХ с конструктивным расстоянием при является

Но Следовательно, и проверочная матрица кода где каждый элемент представляется двоичным столбцом длины 11. Размерность кода равна

Согласно рис. 7.4 расстояние Боуза этого кода также равно 5. Однако, как мы увидим в гл. 20, этот код БЧХ эквивалентен коду Голея § 23, и его минимальное расстояние равно 7. Таким образом, минимальное расстояние этого кода больше его конструктивного расстояния, и это иллюстрирует тот факт, что граница БЧХ не является точной.

Рис. 7.4 Коды БЧХ длины 23

Мы вернемся к кодам БЧХ в гл. 9.

Упражнения. (22). Используя таблицу циклотомических классов для найти размерности кодов БЧХ для 9, 11. То же самое проделать для

(23). Используя границу БЧХ, показать, что минимальное расстояние симплексного -кода с проверочным многочленом равно

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

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

Упражнения. (25). Доказать, что код и конструктивным расстоянием является реверсивным.

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

(27). Доказать, что если —1 равна некоторой степени по модулю то каждый циклический код над GF(q) длины реверсивен.

(28). Коды Меласа, исправляющие две ошибки Используя упражнение (24), показать, что если нечетно, то минимальное расстояние двоичного реверсивного -кода с порождающим многочленом не меньше 5.

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

(30). (Коржик). Показать, что если делится на то минимальное расстояние не может быть больше чем