16.2. Уравнения Мак-Вильямс - Плесс для нумераторов весов дуальных кодов

Нумераторы весов кодов с малым числом кодовых слов и кодов с малым числом классов эквивалентности относительно некоторой известной группы подстановок могут быть найдены путем полного перебора классов эквивалентности. Этот подход оказывается весьма эффективным для некоторых классов кодов с малой блоковой длиной или малой скоростью. В частности, нумераторы весов для большинства кодов со скоростью приведенные в табл. 16.1, были впервые получены этим способом путем использования циклической группы подстановок и группы подстановок вида (следствие 5.82).

К сожалению, число кодовых слов в большинстве кодов с большой скоростью и умеренной или большой блоковой длиной на много порядков превосходит число всех подстановок, относительно которых код инвариантен. Поэтому нумераторы весов этих кодов не удается определить даже с использованием больших быстродействующих вычислительных машин. Однако, даже если число велико, число быть относительно мало. Таким образом, может оказаться, что нумератор весов дуального кода, кодовые слова которого образуют проверки исходного кода, вычисляется сравнительно просто. Например, если скорость исходного кода то вообще легче вычислить нумератор весов дуального кода, так как он инвариантен относительно той же группы подстановок, что и исходный код. В частности, код, дуальный к циклическому коду с порождающим многочленом есть циклический код с порождающим многочленом где многочлен, взаимный к Аналогично, если не делится на то код, дуальный к -удлиненному циклическому коду с порождающим многочленом есть -удлиненный циклический код, порожденный многочленом, взаимным к многочлену

Если нумератор весов дуального кода известен, то нумератор весов исходного кода может быть определен с помощью замечательной формулы, полученной Мак-Вильямс [1963].

16.21. Теорема (Мак-Вильямс). Пусть линейный код размерности к над с нумератором весов Хэмминга и пусть 98 — его дуальный код снумератором весов Хэмминга Тогда

где

Замечание. Формула Мак-Вильямс симметрична; подстановка приводит к формуле

Доказательство теоремы Мак-Вильямс основано на лемме 16.213, которая в свою очередь базируется на лемме 16.212 и определении 16.211.

16.211. Определение. Пусть базис пространства над а скалярное произведение векторов задается равенством (2 2 1

Пусть рукописные буквы обозначают подпространства над

Пусть подпространство, дуальное к т. е. тогда и только тогда, когда для всех

Пусть прямая сумма т. е. элемент однозначно записывается в виде где

16.212. Лемма.

Доказательство.

Таким образом,

С другой стороны,

16.213. Лемма. Пусть и А — подпространства в размерностей и к соответственно, Тогда

Доказательство.

Согласно лемме 16.212,

так что

Доказательство теоремы 16.21. Пусть некоторое фиксированное -мерное подпространство в состоящее из всех векторов, содержащих нули в фиксированных координатах. Тогда дуальное подпространство состоит из векторов, содержащих нули в дополнительном множестве координат. Если а — некоторый фиксированный вектор веса из кода то а тогда и только тогда, когда множество, состоящее из координат, соответствующих нулям образует подмножество множества, состоящего из нулевых координат вектора а. Если положить

то

и

Аналогично,

Комбинируя равенства получим

Так как произвольно, то равенство (16.216) выполняется при любом Умножив его на и суммируя по получим, что

Деление всех членов равенства на дает равенство

Полагая получаем

Формула Мак-Вильямс позволяет получить распределение весов в любом линейном коде по известному распределению весов дуального ему кода. Например, код, дуальный к -удлиненному двоичному коду Хэмминга длины есть РМ-код первого порядка. Нумератор весов последнего, очевидно, равен

Следовательно, нумератор весов -удлиненного кода Хэмминга равен

Формула Мак-Вильямс дает систему уравнений, связывающих коэффициентов функции коэффициентами функции Если функция известна, то формула Мак-Вильямс позволяет определить и наоборот. Во многих случаях, однако, бывает трудно определить все коэффициенты и и но сравнительно просто определяются некоторые из коэффициентов этих многочленов. Например, могут быть известны все коэффициенты за исключением некоторых коэффициентов, и Тогда формула Мак-Вильямс определяет систему уравнений относительно неизвестных коэффициентов неизвестных коэффициентов Для решения этой системы сначала находятся уравнений, связывающих неизвестных коэффициентов с известными коэффициентами Это осуществляется с помощью моментно-степенных тождеств, которые мы сейчас определим. Эти тождества, введенные Плесс [1963],

выражают «сдвинутые» моменты величин через коэффициенты Константа обычно принимается равной или

Для вычисления сдвинутого момента перепишем формулу Мак-Вильямс в виде

Умножив обе части равенства на и полагая получим

Продифференцируем обе части равенства раз и положим Тогда

где многочлен от

Если то Это позволяет записать уравнение (16.225) в виде

Уравнения (16.24) называется моментно-степенными тождествами Плесе. Через производящие функции оно записывается так:

где

Если известны и не известны точно коэффициентов то тождества Плесс (16.24) дают систему уравнений

с неизвестными. Эти уравнения в точности совпадают с уравнениями разд. 10.1, причем числа соответствуют известным локаторам ошибок, а неизвестные неизвестным значениям ошибок. Следовательно, (10.14) — решения уравнения (16.24). Как будет показано в разд. 16.4, в некоторых случаях уравнение (16.24) удается привести к еще более простому виду.

В общем случае вычисление многочлена по формуле (16.23) — очень утомительный процесс. Приближенное выражение может быть получено на основе чисел Стирлинга или многочленов Бэлла, свойства которых указаны Риорданом [1958, стр. 43—49]. В двоичном случае выбор приводит к относительно простой рекурсии. Если то уравнение (16.23) принимает вид

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

сразу получаем формулы:

Для вычисления

используем равенство

Следовательно,

Оказывается, многочлены легче выразить не через степени , а через производные величины Полагая можно при уравнение (16.245) записать в виде

Применяя тождество получим, что

Таким образом, мы вывели рекурсивную формулу для

Очевидно, что для нечетных Значения величин для приведены в табл. 16.2. Производящая функция для столбца этой таблицы имеет вид

Согласно равенству (16.26),

и