Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 16.2. Уравнения Мак-Вильямс - Плесс для нумераторов весов дуальных кодовНумераторы весов кодов с малым числом кодовых слов и кодов с малым числом классов эквивалентности относительно некоторой известной группы подстановок могут быть найдены путем полного перебора классов эквивалентности. Этот подход оказывается весьма эффективным для некоторых классов кодов с малой блоковой длиной или малой скоростью. В частности, нумераторы весов для большинства кодов со скоростью К сожалению, число кодовых слов в большинстве кодов с большой скоростью и умеренной или большой блоковой длиной на много порядков превосходит число всех подстановок, относительно которых код инвариантен. Поэтому нумераторы весов этих кодов не удается определить даже с использованием больших быстродействующих вычислительных машин. Однако, даже если число Если нумератор весов дуального кода известен, то нумератор весов исходного кода может быть определен с помощью замечательной формулы, полученной Мак-Вильямс [1963]. 16.21. Теорема (Мак-Вильямс). Пусть
где Замечание. Формула Мак-Вильямс симметрична; подстановка
Доказательство теоремы Мак-Вильямс основано на лемме 16.213, которая в свою очередь базируется на лемме 16.212 и определении 16.211. 16.211. Определение. Пусть Пусть рукописные буквы обозначают подпространства Пусть Пусть 16.212. Лемма.
Доказательство.
Таким образом,
С другой стороны,
16.213. Лемма. Пусть
Доказательство.
Согласно лемме 16.212,
так что
Доказательство теоремы 16.21. Пусть
то
и
Аналогично,
Комбинируя равенства
Так как
Деление всех членов равенства на
Полагая
Формула Мак-Вильямс позволяет получить распределение весов в любом линейном коде по известному распределению весов дуального ему кода. Например, код, дуальный к
Следовательно, нумератор весов
Формула Мак-Вильямс дает систему выражают Для вычисления
Умножив обе части равенства на
Продифференцируем обе части равенства
где
Если
Уравнения (16.24) называется моментно-степенными тождествами Плесе. Через производящие функции оно записывается так:
где
Если известны с В общем случае вычисление многочлена
В большинстве приложений
сразу получаем формулы:
Для вычисления
используем равенство
Следовательно,
Оказывается, многочлены
Применяя тождество
Таким образом, мы вывели рекурсивную формулу для
Очевидно, что
Согласно равенству (16.26),
и
|
1 |
Оглавление
|