9.9. ГРАНИЦА КАРЛИЦА—УШИЯМЫ

Теорема 18. Предположим, что двоичный код БЧХ длины с конструктивным расстоянием где

Тогда вес любого ненулевого слова кода заключен в границах

Заметим, что вес должен быть четным.

Доказательство. Идея доказательства состоит в следующем. Разность между числом нулей кодового слова и числом его единиц равна Используя многочлен Мэттсона-Соломона, эту величину можно записать в виде показательной функции от следа Затем, опираясь на глубокий результат Карлица и Ушиямы, мы показываем, что эта сумма мала. Следовательно, число нулей кодового слова примерно равно числу его единиц, а вес, грубо говоря, равен

Нули кода лежат в циклотомических классах условия (9.28) и следствия 8 вытекает, что все эти

классы различны и мощность их равна Согласно § 7.5 классы образуют ненули кода Поэтому согласно § 8.6 МС-многочлен вектора равен:

где степень многочлена равна

Далее, используя теорему 20 гл. 8, запишем разность между числом нулей и числом единиц кодового слова а в виде

Воспользуемся теперь без доказательства следующим результатом.

Теорема 19. (Карлиц и Ушияма.) Если многочлен над степени такой, что ни для одного многочлена над и ни для одной постоянной константы то

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

откуда вытекает (9.29).

Следствие 20. Пусть двоичный код БЧХ длины с конструктивным расстоянием Тогда минимальное расстояние кода равно по меньшей мере

Доказательство. Если то результат следует из теоремы 18. А если то выражение (9.31) становится отрицательным.

Примеры. При является симплексным кодом, все ненулевые веса которого равны это совпадает с (9.29), так как при следует, что При из (9.29) имеем: что согласуется с рис. 15.3 и 15.4.

В качестве заключительного примера рассмотрим код БЧХ длины 127 с конструктивным расстоянием 11. Как видно из рис. 4.4, код имеет 15 последовательных нулей и, следовательно, согласно границе БЧХ (теорема 8 гл. 7) его минимальное расстояние не меньше 16, 16. Однако согласно теореме и так как должно быть четным, то 20.

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

Задача (нерешенная). (9.5). Можно ли усилить утверждение теоремы 18, записав границы в виде

Более простая граница для минимального расстояния кода, дуального коду БЧХ, дается следующей теоремой.

Теорема 21. (Сидельников.) Пусть двоичный код БЧХ длины и конструктивным расстоянием Тогда минимальное расстояние кода удовлетворяет условию

Доказательство. МС-многочлен вектора записывается в виде

где пробегает все различные представители смежных классов С], Двоичное разложение любого такого имеет вид

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

Так как 0 — корень многочлена то по теореме 26 гл. 8 имеем: