Замечание. Формула Мак-Вильямс симметрична; подста новка г/ = (1 - z)/[l -f (g - 1) z] приводит к формуле

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

16.211. Определение. Пусть v, Vj, . . ., v„ - базц пространства GF (g") над GF (g), a скалярное произведение векторо!

п п п

задается равенством ( 2 ii) ( S •) = 2

j=i i=i г=1

Пусть рукописные буквы обозначают подпространства GF (а" над GF(q).

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

Пусть © - прямая сумма и , т. е. элемент х g © однозначно записывается в виде х = у -f- z, где у J, г

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

Таким образом, С другой стороны.

А, дА@\ {А@)А, -L; {А@)А П = А П

16.213. Лемма. Пусть и А - подпространства в GF{q"). над GF(q) размерностей j и к соответственно, § = и = А-% Тогда "

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

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

{ п .) = .-® = .®-

dim (jr © А) = dim jr + dim A- dim (jzr f] .-),

так что

dim(g n .) = ?г -dim jr -dim. -Ldim(ir [] = = A;-/ + dim(r n Ш Доказательство теоремы 16.21. Пусть = 1, . . ., " j j-некоторое фиксированное у-мерное подпространство в GF (g"), состоящее из всех векторов, содержащих нули в и -У фиксированных координатах. Тогда дуальное к подпространство §т состоит ИЗ вокторов, содоржащих нули в дополнительном множестве координат. Если а - некоторый фиксированный вектор веса i из кода А, то а тогда и только тогда, когда множество, состоящее из координат, соответствующих нулям Sm, образует подмножество множества, состоящего из и - i нулевых координат вектора а. Если положить

0, если ат;

1, если а£т>

а П т =

(")

2 аП т=(7)

(")

(16.214) Аналогично,

(16.215) 2 2 ibn.Fmi=2-«(;i;)-

Комбинируя равенства (16.213) - (16.215), получим

(i) С)

(16.216) 2("7)2 2 1« п «1=--2 1- п mi =

i aSAm=l m=l

(") (i)

= ?-2i-« n т\я- 2 2 ь n .F.i=?-2 •« (ni;)-

m=l

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

ss.("-)=-s«*-s(::,>=

i i j i

A-vsS (::;) (1)=2.4,(1+.)"-- =/(frs.(-ir-

Деление всех членов равенства на (l-j-x)" дает равенство

Полагая z=l/(l--x), а:=(1-z)/z, p = (q-i)/q, получаем

2..=.(.- + р.)"2(-гпй)7)- -

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

5 (z) = 1 -t- (2"+i- 2) z--f z2". Следовательно, нумератор весов 1-удлиненного кода Хэмминга pai

(16.22) Л (Z) 2--2П1 + zr[l + (2"--2)(1) + (У[

Формула Мак-Вильямс дает систему п + I уравнений, связывав щих ге -(- 1 коэффициентов функции Л (z) с и + 1 коэффициента» функции В (z). Если функция А (z) известна, то формул Мак-Вильямс позволяет определить В (z), и наоборот. Во мног случаях, однако, бывает трудно определить все коэффициен и А (z) ш В (z), но сравнительно просто определяются некотор из коэффициентов этих многочленов. Например, могут быть из* стны все коэффициенты Aj, за исключением некоторых s коэффицие тов, и Bd,Bi, . . ., В s-1- Тогда формула Мак-Вильямс определ): систему и -f- 1 уравнений относительно s неизвестных коэффициент Aj и п I - S неизвестных коэффициентов Bj. Для решения Э1 системы сначала находятся s уравнений, связывающих s неизвестщ коэффициентов Aj с известными коэффициентами Вд, В, . . ., Bs Это осуществляется с помощью моментно-степенных тождеств, кб рые мы сейчас определим. Эти тождества, введенные Плесе [196

выражают г-е «сдвинутые» моменты величин Aj, {w - jY Aj,

через коэффициенты Bi. Константа w обычно принимается равной О, и/2, {п -Ь 1)/2 или п.

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

il Ajz = (tYBj (g-i + pz)"- {q- - Щ-У. 3=0 ;=0

Умножив обе части равенства на ехр 2wx и полагая z = ехр {-2х), получим

2 4ехр[2(и;-7)х] =

3 = 0

= S 7 [д-1 -f- р ехр (- 2х)Г- [д- - ехр (- 2х)] ехр 2wx. 3 = 0

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

(16.225) 2 {2w-2jY Aj = 2 W>

3=0 3=0

где /() (n) - многочлен от n,

(16.23) F\? (n) = {[g-i + P exp (- 2x)]"- X

X [q~ - q~ exp (- 2x) f exp 2wx) j x=o•

Если r<7, TO F<J)(7i)=0. Это позволяет записать уравнение (16.225) в виде

(16.24) 2 {2w-2jyAjq"" 2 BjF\}n) для всех г.

3=0 3=0

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

(16.241) 2 S {2w-2iYz-Aj = q 2 BjF(n; z),

г=Оэ=0 3=0

(16.242)

F (п; z) - 2 Fr («) z.

Если известны В, В, . . ., Bg-t и не известны точно s коэффициентов Aj, то тождества Плесе (16.24) дают систему «уравнений

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

В общем случае вычисление многочлена F[ (тг) по формуле (16.23) - очень утомительный процесс. Приближенное выражение может быть получено на основе чисел Стирлинга или многочленов Балла, свойства которых указаны Риорданом [1958, стр. 43-49]. В двоичном случае выбор и> = п12 приводит к относительно простой рекурсии. Если w = w/2, g = 2 и р = 1/2, то уравнение (16.23) принимает вид

(16.243)

ch"- X sli

x) .

В большинстве приложений Bj - О для малых положительных /, и поэтому вычисления производятся для / = О, г или г - 2. В случае надобности другие многочлены FJ {п) могут быть выражены чбрез Ро) (fij многими способами. Например, используя ряды Тейлора

th-.= (.-+...) = .-ifi-b...,

ch"x=l++...,

ch"xtha:=x4(-)++ сразу получаем формулы:

(n) = r!, FrHn)=r\(-),

(16.244)

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

/"« {п; 2) = 2 (п)

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

(16.245) Fo {п; z) 1 + 2 ( <h" ),=о =

= 1 + 22

dxr dx2

x) =

1+22

16.3. Ограничения весов г dr

dx-r

[и2 ch" Ж - ;г (и - 1) ch"- a:]=o =

r = 0

= 1-f zW«" (/г; z)-«(/i -l)z2P« («-2; z). Следовательно,

1 , если и - О,

(16.25) F{n;z)=.{ i-.(„-i).2-,o,(„ 2;z) p„„-.

1 22„2 если I.

Оказывается, многочлены F: (n) легче выразить не через степени п, а через производные величины па)=п {п-I) {п - 2). .. .. .(п-т- i - i)- Полагая Fj.(п) =Ег, in, можно при г>0 уравнение (16.245) записать в виде

2 Ег, = «2 2 Ег-2, гПц) - 2 Ег-г, 1Па+2)-

г i i

Применяя тождество = (п - 1 - i) [п - i) + {2i (n - i) + P, получим, что

2 Er, 1Пф = 2 (2i-f 1) Er-2, iUa+i) + 2 iEr-2, iUay

t t i

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

{1, если г = 0 и г = 0,

О, если i = 0 и гфО или 1фО, г = 0,

{2i-1) £г 2, г-1+г остальных случаях.

Очевидно, что £г, г = О для нечетных г. Значения величин Ег, i для г = О, 2, 4, . . ., 12 приведены в табл. 16.2. Производящая функция для i-ro столбца этой таблицы имеет вид

> (Z) = 2 Ег, iz\

Согласно равенству (16.26), Е°Ч)==\, (z) = z2/(l - z2), £(z) = 3zV(l-z2)(l-4z2), E (z) = (2j-l)z2£*-i(z)/(l-iV)

(16.27)

fe= 1

16.3. Ограничения весов

Если не известны только s коэффициентов Aj ж известны В, Bi, . . ., В s-l, то из тождеств Плесе можно определить s неизвестных Aj, а остальные коэффициенты Bj - по формуле Мак-Вильямс.