16.4. Нумераторы весов Казами для некоторых подкодов РМ-кода второго порядка

16.41. Приведение тождеств Плесс. В случае подкодов РМ-кода второго порядка теорема Казами 16.34 утверждает, что все ненулевые коэффициенты совпадают с где При тождества Плесс принимают вид

где во избежание путаницы с блоковой длиной -укороченных кодов блоковая длина обозначена через Если предположить, что то для всех Так как единичный вектор задает общую проверку на четность для дуального кода, то для всех нечетных Заменяя на и на перепишем (16.411) в виде

Положим

Используя (16.413) при запишем равенство (16.412) в виде

Умножая (16.414) на и суммируя по от 1 до получаем, что

Используя равенство (16.242) и табл. 16.2, можно показать, что

Для того чтобы исключить из уравнения (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.

Доказательство. Согласно теореме -удлиненный код инвариантен относительно транзитивной аффинной группы подстановок. Значит, по теореме 10.38 .

16.46. Теорема (Велч [1967]). Уравнение имеет точно решений в

Доказательство. Пусть базис над Тогда

Последнее равенство дает квадратичную форму от переменных Согласно теореме Диксона 16.35, существует такой базис такое число и такой элемент что

или

В первом случае не зависит от координат, а во втором — от координат. Для определения с надо найти такое число что для всех

Имеем

Это равенство не зависит от тогда и только тогда, когда Если то так что Следовательно, для всех тогда и только

тогда, когда Так как не зависит от 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 не все корни лежат в поле . В этом случае фиксирует отказ от декодирования, обнаруживая тем самым существование не менее трех ошибок. Если предположить, что произошли три ошибки с локаторами то, согласно проверочным уравнениям для получим

Полагая и исключая приходим к равенствам

Возведем первое уравнение в куб, прибавим его ко второму и разделим сумму на первое. Тогда получим

Элементы удовлетворяют уравнению

Это уравнение разрешимо в поле тогда и только тогда, когда

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

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

16.481. Полный алгоритм декодирования для двоичных БЧХ-кодов с исправлением двух ошибок. Вычисляем

Если то полагаем

Если то полагаем

Если или то полагаем и

Число возможных выборов их, зависит от числа ненулевых кубов и некубов с нулевым следом в поле Согласно теореме Велча 16.46, число ненулевых кубов с нулевым следом равно

число ненулевых кубов с единичным следом равно

число некубов с нулевым следом равно

число некубов с единичным следом равно

Здесь В любом случае недоразумений не произойдет, так как неправильный выбор знака приведет к элементу, не являющемуся целым числом. Используя этот результат, можно дать классификацию смежных классов двоичного БЧХ-кода длины исправляющего две ошибки, как показано в табл. 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] показал, что величины должны делиться на следовательно, если то для всех Это условие выполняется для всех . В этих случаях величины можно определить из

уравнений Согласно Это уравнение доказано для и представляется очень правдоподобным, что оно справедливо для всех Гипотетическая формула для эквивалентна предположению о том, что для всех Доказательство любой из этих гипотез дает доказательство гипотетической формулы для нумератора весов кода, дуального к -удлиненному БЧХ-коду с исправлением трех ошибок. Нам представляется, что эту формулу для можно доказать с помощью нумераторов смежных классов для БЧХ-кода с исправлением трех ошибок аналогично тому, как это сделано в разд. 16.48. Однако такое вычисление будет достаточно запутанным, и возможно, что существует более непосредственное доказательство.