Для того чтобы исключить
из уравнения (16.415), можно умножить (16.415) на
и приравнять коэффициенты при
Например, если умножить на
равенство (16.415), то в силу формулы (16.244)
Приравняв коэффициенты при
получим
Это третье уравнение, приведенное в таблице 16.3. Аналогичные выкладки позволяют получить все уравнения табл. 16.3. Эти уравнения представляют собой тождества Плесс (16.414), приведенные к треугольному виду.
16.42. Нечетное
некоторые
коды с малой скоростью. Начнем с РМ-кода первого порядка, отмеченного в первой строке таблицы 16.4. Распределение весов для этого кода было известно еще Риду и Маллеру.
-укороченный РМ-код первого порядка — циклический. Корнями его проверочного многочлена являются
или, что то же самое,
где
Как показано в первом столбце табл. 16.4, двоичные записи логарифмов этих корней по основанию а образуют циклические сдвиги последовательности
Этот циклический код представляет собой суженный БЧХ-код со скоростью
который в свою очередь является
-укорочен-ным РМ-кодом первого порядка. Хорошо известно, что распределение весов РМ-кода первою порядка имеет вид
Рассмотрим теперь
-удлиненный БЧХ-код со скоростью
приведенный во второй строке табл. 16.4. Распределение весов для этого кода впервые было найдено Казани. Проверочный многочлен суженного БЧХ-кода имеет
корней. Двоичная запись логарифмов по основанию а получается циклическими сдвигами последовательностей
содержащихся в первом
столбце таблицы. В соответствии с БЧХ-границей минимальное расстояние
-удлиненного БЧХ-кода со скоростью
больше или равно
так что
для всех
Так как этот код содержит РМ-код первого порядка, то дуальный к нему код образует подкод кода, дуального к РМ-коду первого порядка. Так как на предыдущей линии таблицы
то, таким образом, дуальный к РМ-коду первого порядка (последний, на самом деле, есть
-удлиненный код Хэмминга) не имеет кодовых слов веса 2, так что код, дуальный к
-удлиненному БЧХ-коду со скоростью
тоже не содержит кодовых слов веса 2. Другими словами,
Это позволяет определить
непосредственно из уравнения
из уравнения
табл. 16.3. Согласно уравнению
и мы заключаем, что
Прежде чем переходить к БЧХ-коду с большей скоростью, заметим, что для достаточно больших
имеется много
-удлиненных БЧХ-кодов с малыми скоростями, представляющих собой подкоды РМ-кода второго порядка. Ясно, что каждая двоичная последовательность длины
содержащая не менее трех нулей, имеет циклический сдвиг, который начинается с 0 и содержит следующий 0 не позже, чем в
-й позиции. Например, если
то крайний случай дает последовательность
Пусть
Образуем
двоичных последовательностей длины
Тогда они и все их циклические сдвиги должны превосходить по меньшей мере один циклический сдвиг любой двоичной последовательности длины
содержащей не менее трех нулей. Следовательно, если
нечетно, то
-удлиненный двоичный БЧХ-код со скоростью
подкод РМ-кода второго порядка.
Рассмотрим теперь приведенный в третьей строке табл.
-удлиненный БЧХ-код со скоростью
Согласно БЧХ-границе, минимальное расстояние этого кода больше или равно
так что
для всех
Так как данный код содержит
-удлиненный БЧХ-код со скоростью
то дуальный к нему код является подкодом дуального к
-удлиненному БЧХ-коду со скоростью
Так как на предыдущей линии таблицы
то, следовательно, опять получаем
Это позволяет определить
из уравнения
из уравнения
из уравнения
Согласно
откуда заключаем, что
Рассмотрим далее
-удлиненный БЧХ-код со скоростью
Согласно БЧХ-границе,
для всех
В силу предыдущих рассмотрений
. Следовательно, можно определить
из уравнения
из
из
Согласно
откуда можно найти
Рассмотрим теперь
-удлиненный БЧХ-код со скоростью
Согласно БЧX границе)
для всех
Согласно предыдущему
. С другой стороны, этот код является подкодом РМ-кода второго порядка, и поэтому дуальный к нему код есть надкод для кода, дуального к РМ-коду второго порядка. Этот дуальный код, согласно теореме 15.329, содержит точно
кодовых слов веса 8. Поэтому
Затем вычисляем
из уравнения
из
из
из
из
Согласно уравнению
48)] -
откуда
Наконец, рассмотрим
-удлиненный БЧХ-код со скоростью
Согласно БЧХ-границе,
для
. В силу предыдущих рассмотрений
Следовательно, можно определить
из уравнения
из
Для каждого кода этой последовательности вычисляется следующее
Благодаря чрезвычайно благоприятному стечению обстоятельств каждое
оказывается равным числу слов веса
в коде, дуальном к РМ-коду второго порядка. Тот факт, что для каждого следующего кода величина
оказывается ограниченной сверху и снизу двумя равными величинами, позволяет продолжать вычисления и определять нумераторы весов последовательности БЧХ-кодов
малыми скоростями. Наши вычисления заканчивались на БЧХ-коде со скоростью
не потому, что мы не хотим дальше искушать судьбу, а потому, что это достаточно однообразное занятие. Конечно, мы не беремся наверняка утверждать, что благоприятные условия, сопутствовавшие нам пять раз, должны выполняться и впредь. Но можно сделать
16.43. Предположение. Если
то число слое веса
в коде, дуальном к
-удлиненному
со скоростью
равно числу слов с весом
в коде, дуальном к РМ-коду второго порядка.
Из этого предположения вытекает, что для нечетных
нумераторы весов последовательности тех БЧХ-кодов с низкими скоростями, которые являются подкодами РМ-кода второго порядка, могут быть вычислены с использованием только тождеств Плесс. Будучи оптимистом, автор надеется не только на доказательство предположения 16.43, но и на вывод простых точных формул для нумераторов.
Согласно табл. 16.4, число кодовых слов наименьшего ненулевого веса в
-удлиненном БЧХ-коде со скоростью
для нечетных
очевидно, задается равенством
где
Хотелось бы найти прямое доказательство этой формулы. Хотелось бы также найти характеристики кодовых слов малого веса, аналогичные теореме 15.329.
16.44.
- нечетное;
коды с большими скоростями. При фиксированном
только три из
-удлинен-ных БЧХ-кодов имеют дуальные коды, содержащиеся в РМ-коде второго порядка, — это БЧХ-коды с исправлением одной, двух и трех ошибок. Если 4, то код, дуальный к
-удлиненному БЧХ-коду с исправлением
ошибок, не является подкодом РМ-кода второго порядка, так как
корень порождающего многочлена БЧХ-кода, а двоичная запись 111 числа 7 — слово веса 3.
При нечетном
нумераторы весов кодов, дуальных к
-удлинен-ным БЧХ-кодам с исправлением двух и трех ошибок, могут быть определены по формулам, приведенным в табл. 16.3. Для дуального к коду с исправлением двух ошибок
согласно БЧХ-границе,
Уравнение
при этом принимает вид
Так как
для всех нечетных
то для этих
для всех
Это позволяет теперь определить
из уравнения
из уравнения
Теперь рассмотрим код, дуальный к
-удлиненному БЧХ-коду с исправлением трех ошибок. Так как, согласно БЧХ-границе,
то уравнение
можно записать в виде
нечетн
Отсюда следует, что
для всех
Затем определим величины
из уравнений
Результаты приведены в табл. 16.5.
Найденное распределение весов для кодов, дуальных к
-удли-ненным БЧХ-кодам с исправлением двух и трех ошибок, позволяет вычислить распределение весов в
-удлиненных БЧХ-кодах с исправлением двух и трех ошибок на основании формулы Мак-Вильямс (16.21). Мы опускаем эти непосредственные, но утомительные выкладки.
Для нечетных
вывод нумераторов весов
-удлиненных двоичных БЧХ-кодов (являющихся подкодами РМ-кодов порядка 2 или
дуальных к ним кодов) значительно упрощается благодаря членам
соответственно в уравнениях
и
Аналогичные уравнения для четных
не содержат этих членов, и это значительно усложняет вычисление нумераторов весов. Здесь решение найдено для очень малого числа случаев, а полученные результаты могут служить лишь основой для дальнейшего изучения кодов. К таким результатам относятся теоремы 16.45 и 16.46. Как и в разд. 4.7, через
будем обозначать минимальный многочлен элемента а.
16.45. Теорема (Казами). Двоичный циклический код с блоковой длиной
и порождающим многочленом
содержит точно
кодовых слов веса 3, где н. о. д. - наибольший общий делитель
и всех
Доказательство. Так как циклический код инвариантен относительно транзитивной циклической группы подстановок, то число кодовых слов веса 3 в
раз больше числа кодовых слов веса 3, содержащих единицу в позиции с локатором
Если 1, х и у — локаторы трех единиц в кодовом слове веса 3, то
и
Подставляя равенство (16.451) в (16.452), получаем, что для всех
Отсюда
Таким образом, имеется точно
выборов упорядоченных пар элементов
и
способов для неупорядоченных пар.
16.453. Следствие. Код с блоковой длиной
полученный как
-удлинение кода из теоремы 16.45, содержит точно
кодовых слов всех 4.
тогда, когда
Так как
не зависит от 2а координат, то
задается формулой (16.462), а не (16.461).
Согласно равенству (16.354), число
способов выбора
двоичных чисел
удовлетворяющих уравнению
задается равенствами
Следовательно, если
то уравнение
имеет в
решений; если
то уравнение
имеет в
решений. Чтобы определить, равен ли элемент Я нулю или единице, заметим, что число ненулевых решений уравнения
должно быть кратно
Следовательно,
и
Так как
то отсюда получаем
16.47. Четное
;
-удлиненные БЧХ-коды с малой скоростью. Рассмотрим теперь приведенный в табл. 16.5 1-удлиненный двоичный БЧХ-код со скоростью
Так как, согласно БЧХ-границе, минимальное расстояние этого кода равно по меньшей мере
то
для всех
Так как рассматриваемый код содержит РМ-код первого порядка, то дуальный к нему код — подкод кода Хэмминга, и
Величины
и определяются соответственно из уравнений
таблицы 16.3 при
Рассмотрим далее
-удлиненный двоичный БЧХ-код со скоростью
В соответствии с БЧХ-границей,
для всех
Так как наибольший общий делитель чисел
равен 1, то по следствию
Величины
определяются из уравнений
при
Распределения весов для двоичных БЧХ-кодов со скоростями
к сожалению, не известны.
16.48. Четное
-удлиненные БЧХ-код исправляющие две ошибки. Для определения распределения весов в БЧХ-кодах, исправляющих две ошибки, выберем: относительно обходный путь. Сначала рассмотрим полный алгоритм: декодирования для этих кодов. Это позволит вычислить число слов, веса 3 в смежных классах веса 2 и 3. Отсюда легко найти число кодовых слов веса 5 в (циклическом) БЧХ-коде с блоковой длиной
Оказывается, этой информации уже достаточно для вычисления нумератора весов по формулам таблицы 16.3. Казами дал более прямой метод вычисления нумератора весов БЧХ-кодов с исправлением двух ошибок. Однако полный алгоритм декодирования и нумераторы для смежного класса представляют существенный самостоятельный интерес, и поэтому мы предпочли более обходный путь.
Если произошло не более двух ошибок, то, согласно разд. 1.4 (или алгоритму 7.4), многочлен локаторов ошибок для БЧХ-кода,. исправляющего две ошибки, задается равенством
Здесь
Если
по теореме 6.695 не все корни
лежат в поле
. В этом случае
фиксирует отказ от декодирования, обнаруживая тем самым существование не менее трех ошибок. Если предположить, что произошли три ошибки с локаторами
то, согласно проверочным уравнениям для
получим
Полагая
и исключая
приходим к равенствам
Возведем первое уравнение в куб, прибавим его ко второму и разделим сумму на первое. Тогда получим
число ненулевых кубов с единичным следом равно
число некубов с нулевым следом равно
число некубов с единичным следом равно
Здесь
В любом случае недоразумений не произойдет, так как неправильный выбор знака приведет к элементу, не являющемуся целым числом. Используя этот результат, можно дать классификацию смежных классов двоичного БЧХ-кода длины
исправляющего две ошибки, как показано в табл. 16.6.
Например, рассмотрим случай, когда
некуб, такой, что
Всего имеется
способов выбора и столько способов выбора
сколько существует способов выбора элемента
некуба с единичным следом. Как мы видели, в поле
содержится
таких элементов. Эта величина отмечена в столбце «Число смежных классов в типе». Вес смежных классов этого типа, очевидно, равен 3.
Сколькими способами смежный класс может быть декодирован в вектор шума веса 3? Сначала надо выбрать элемент и с нулевым следом, для которого в поле существует кубический корень из
Всего в
имеется
некубов с нулевым следом. Так как квадрат недопустимого элементам также недопустим и наоборот, то точно половина этих
некубов с нулевым весом недопустима в качестве элемента и. Следовательно, и может быть выбрано
различными способами. Хотя имеется три выбора
в качестве кубического корня из
каждому кубическому многочлену ошибки также соответствуют три различных выбора
(не обязательно при одном и том же выборе
). Таким образом, происходит сокращение этих двух троек и число слов веса 3 в каждом смежном классе рассматриваемого типа равно
Эта величина внесена в столбец «Кратность элементов минимального веса в смежном классе» таблицы 16.6. Остальные члены этой таблицы могут быть получены аналогичным образом.
Заметим, что ни один смежный класс не имеет веса
Этот факт впервые был отмечен Горенстейном, Питерсоном и Цирлером [1960], которые доказали, что при четном
двоичный БЧХ-код длины
исправляющий две ошибки, является квазисовершенным
(см. разд. 13.2). Из алгоритма 16.481 видно, что при нечетном
двоичный БЧХ-код с блоковой длиной
также квазисовершенен.
Остается еще несколько вопросов. Сколько слов веса 3 принадлежат смежным классам веса 3? Ответ дает следующая формула:
Общее число всех слов веса 3 во всех смежных классах равно
Тогда число слов веса 3, принадлежащих смежным классам веса 2, равно
Для каждого кодового слова веса 5 имеется
векторов ошибок в смежных классах веса 2, так что код должен содержать
кодовых слов веса 5.
Так как БЧХ-код с исправлением двух ошибок содержит
кодовых слов веса 5, то, согласно теореме
-удлиненный БЧХ-код содержит
кодовых слов веса 6. Уравнение
из табл. 16.3 соответственно принимает вид
откуда следует, что
для всех
Величины
определяются затем из
Соответствующие результаты приведены в табл. 16.5.
16.49. Четное та;
-удлиненные
-коды с исправлением трех ошибок. В заключение раздела рассмотрим код, дуальный к
-удлиненному БЧХ-коду с исправлением трех ошибок при
Согласно БЧХ-границе,
. В силу (Т8)
или
Казами [1968] показал, что величины
должны делиться на
следовательно, если
то
для всех
Это условие выполняется для всех
. В этих случаях величины
можно определить из