Но ДЛЯ большинства кодов первые неизвестные значения Bj соответствуют относительно малым а большинство из и + 1 коэффициентов не известны. Прежде чем применять тождества Плесе для нахождения s коэффициентов Aj, необходимо каким-то иным путем определить п -\- \ - s коэффициентов Aj.

Для некоторых классов кодов известно несколько методов определения некоторых коэффициентов Aj. Очевидно, что Aq = 1. Если удается показать, что минимальное расстояние кода не меньше чем d, то = О для / = 1, 2, 3, . . ., d - 1. Полезными границами для минимального расстояния являются БЧХ-граница (см. разд. 7.4) и граница, указанная в теореме 15.22; в некоторых случаях эти границы могут быть улучшены с помощью сильных методов, развитых Мэттсоном и Соломоном [1961].

16.31. Теорема (Мэттсон - Соломон). Пусть q - степень простого числа и п взаимно просто с q. В любом циклическом коде над GF (q) длины п вес Хэмминга кодового слова С (х) равен п - г, где г - число корней п-й степени из единицы, являющихся корнями многочлена Мэттсона - Соломона (МС-многочлена)

ft о

Здесь Si = С (а) (i = О, 1, . . ., п) - значения степенных симметрических функций на кодовом слове С (х).

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

(16.311) S„ = C (а").

Умножая (16.311) на а~* и суммируя по к, получим

(16.312) 2 Ska- = 2 S а*"*

ft 3 ft

Для любого нечетного / = /г/н. о. д. (тг, к) сумма всех корней из единицы степени / совпадает с коэффициентом при х в многочлене xJ - i и, следовательно, равна 0. С другой стороны, 2l = "»

так что

(16.313) S

ft i

О, если 1ф jmodn, если i = 7.

Из равенств (16.313) и (16.312) вытекает, что

Sua-=Cjn

(16.314)

Уравнение (16.314) называется формулой обращения Рида и выражает коэффициенты кодового слова С {х) через значения многочлена Мэттсона - Соломона на корнях ге-й степени из единицы, щ

16.315. Следствие. Вес каждого ненулевого кодового слова, для которого = = . . . -dgq ~ меньше бчх-

Доказательство. Многочлен Мэттсона - Соломона не может иметь больше корней, чем его степень, которая не превосходит ге - Йбчх-

Следствие 16.315 дает элегантное доказательство БЧХ-границы для минимального расстояния, но, к сожалению, не приводит к осуществимым процедурам декодирования. Тем не менее подход Мэттсона - Соломона иногда позволяет улучшить БЧХ-границу для минимального расстояния. Теорема 16.32 показывает, что для некоторых кодов с малой скоростью вопрос о достижимости БЧХ-границы может быть решен только с помощью вычислений в поле GF (q), а не в расширении этого ноля.

16.32. Теорема (Мэттсон - Соломон - Сервейра). Пусть q - степень простого числа, п кратно (q - I) и взаимно просто с q, а - примитивный корень п-й степени из единицы в расширении поля GF (q), J - множество классов вычетов вида дйвчх mod re для i = 0, 1, 2, . . ., пусть Йбчх - наименьший элемент в J. {Например, если g = 2, п = 23, то Йбчх = 5 ы / = {5, 10, 20, 17, И, 22, 21, 19, 15, 7, 14}.)

Пусть Г (z) = 2 z"~ ad - истинное минимальное расстояние

циклического кода с проверочным многочленом h{x) = {x - i) [[ {х - а).

Если йвчх и п взаимно просты, то d = Йбчх тогда и только тогда, когда существует ненулевой элемент s 6 GF {q), такой, что 1 -\-+ sT (-z) делит 1 - z".

Доказательство. Ненулевое кодовое слово может иметь вес Йбчх тогда и только тогда, когда степень его многочлена Мэттсона - Соломона равна ге - вчх и все корни МС-многочлена - корни ге-й степени из единицы. Согласно предположению, h (х) = {х - 1) X X [] (х - а), так что 5 == О кроме случая t J [} 0. Таким обра-

зом, МС-многочлен для каждого кодового слова имеет вид

So + T{yx)

MS {х) =

где Y Бчх = Sdj. Если 0 = 0, то О - корень МС-многочлена, так что мы предположим, что S О я

п-с(бчх

(16.321) So + T{yx) = S, и {l-lix).

где (так же, как и взаимные к ним) - корни п-ж степени из единицы. Приравняв старшие коэффициенты этих многочленов, получим равенство

"-<БЧХ

Так как все элементы §г - корни п-й степени из единицы, то и их произведение - корень п-ш степени из единицы. Так как S GF (q) и п кратно g - 1, то - корень п-й степени из единицы. Следовательно, (-у)"~БЧх корень п-й степени из единицы. Согласно предположению теоремы, п - Йбчх и п взаимно просты, так что (-у) - также корень п-й степени из единицы. После подстановок 2 = -ух, Рг = -li/y и S = в уравнение (16.321) получим, что

1-Ь5Г(-2)= П (1-М)-

Так как р; - различные корни п-й] степени из единицы, то I -\- sT (-z) делит 1 - z"." I

16.322. Следствие. Пусть п - простое число, т - мультипликативный порядок числа 2 по mod п и Йбчх - ЕЧХ-граница для минимального расстояния двоичного ВЧХ-кода с длиной п и скоростью (т 4- 1)/п. Если Йбчх < тп < га - 1, то Йбчх < d.

Доказательство. Если i -\- Т {х) делит х" -Ь 1, то сте- пень частного равна йвчх. Но степень каждого делителя многочлена (ж" -f 1)/{х -f- 1) кратна числу т, превосходящему вчх- Единствен-пая возможность йвчх = 1 исключается предположением о том, что т <Z п - i. щ

Следствие 16.322 дает другое доказательство того, что минимальное расстояние кода Голея больше пяти. Оно также показывает, что минимальное расстояние двоичного БЧХ-кода длины 43 с 15 информационными и 28 проверочными символами больше БЧХ-границы: для этого кода, равной 7.

Границы для минимальных расстояний облегчают отыскание нуме- раторов весов кодов в двух направлениях: граница для минималь- ного расстояния кода А позволяет исключить некоторые неизве-! стные Aj, а граница для минимального расстояния кода увели- чивает минимальное значение s, для которого не известны Bj, j = i = s, s -Ь 1, ... . Но даже при лучших границах минимальных i расстояний все же часто тождества Плесе не позволяют найти нуме- раторы весов, так как неизвестных коэффициентов Aj оказывается слишком много. Тем не менее иногда удается уменьшить количество; неизвестных Aj с помощью других методов, к рассмотрению которых мы сейчас перейдем.

Если в двоичном коде с нечетной блоковой длиной Л„ = 1, то Aj = An-j для всех /. Так как п - j нечетно при четных / и наоборот, то нумератор весов такого кода можно определить по нумератору весов суженного кода, состоящего из кодовых слов четного веса исходного кода. В суженном коде Aj = О для всех нечетных /.

В таблице 16.1 содержатся несколько кодов (включая суженный код Голея с тг = 23, к = 11), ненулевые веса которых удовлетворяют следующему условию: Л = О не только при / О mod 2, но и при i mod 4.

Используя методы проективной геометрии, Глизон доказал, что этим свойством обладают все КВ-коды с длиной п = -1 mod 8. Этот результат позволяет определить нумераторы весов КВ-кодов с блоковыми длинами 8, 24, 32 и 48 с помощью тождеств Плесе. Например, согласно следствию 15.27, минимальный нечетный вес КВ-кода с длиной 47 не меньше 9. Так как вес каждого кодового слова 1-удлиненного-КВ-кода делится на 4, то неизвестными являются только коэффициенты А = Азе, 16 = 32. 20 = 28 и А. Так как код, дуальный к 1-удлиненному КВ-коду, эквивалентен этому коду, то 5j = О для i = 1, 2, . . ., Ни неизвестные Aj могут быть определены из тождеств Плесе.

Теорема 16.33, доказанная Соломоном и Макэлайсом [1966], обобщает теорему Глизона. Как обычно, через g (х) обозначается многочлен, взаимный к g (х).

16.33. Теорема (Соломон - Макэлайс). Если х" - 1 делится на g (х) g {х), то вес каждого кодового слова двоичного циклического кода, порожденного многочленом g (х), кратен 4.

Доказательство. По предположению теоремы из g (а) Ф Ф О вытекает, что g {аГ) = О и S y = 0. Следовательно,

(16.331) SfeS.ft = О для всех к.

Если С (х) - кодовое слово, то двоичная запись его веса имеет вид

w{C) = Wi (С) 2\

Теорема 16.33 утверждает, что из равенства (16.331) вытекает соотношение (С) = (С) = О для всех кодовых слов С. Для доказательства этого утверждения надо получить выражения для wt через S. Для удобной записи таких выражений Соломон [1962] ввел величины

(16.332) Г;=3 2 ... Зад, ... Cj, (сумма в CP(2)).

il<i2< . .. <ij

Очевидно, что

("j) = S2j • • • 2 «1*2 • • • Ci. (обычная сумма),

n<i2< ... <г.

так ЧТО Tj{C)= "."j mod2. Согласно теореме Лукаса 4.71,

("f ),(Omod2,

так что wi{C) = Vi{C). Теперь надо выразить величины Ti (С) через Su- Из формулы 16.331 ясно, что

В силу (16.332) Г2(0 = SSCгC•. Используя равенство (16.314), получим

(16.333) Г2 (С) = (S Snoi-") (S Sa-) =

h к i<3

Используя разбиение

h К h<K h>K h=K

запипзем соотнопзение (16.333) в виде

(16.334) Го(С) = SSk (a-(ift+W 4 а-(*ВД)4

k<K i < j

Так как допустимы все J) <. сумма i + j при-

нимает каждое из возможных значений по modn точно (и -1)/2 раз. Следовательно,

( О, если кф О, 2 2 а- ="-=12 - bizdll, если /. = 0.

г < 3 J=0 l

и, согласно формуле (16.311),

2 512 2 =- °-

i < 3

Для вычисления других членов в (16.334) заметим, что 22 {а--+> + „-(i/f-f3ft)) = 22 (а-+да) =

= (2 а-") (2 а-) + S

t 3 г

Подставив это выражение в формулу (16.334), в силу соотношения (16.331) получим

Г2 (С) = 2S SkSK = " S SuS-k- 0. .

факт, что при г

Соломон иМакэлайс выразили Г4(6), Fg (С),. . . через Su- Их формула для (С) оказалась очень полезной при определении весов нескольких кодов, но большинство формул для Г,- трудно использовать ввиду их чрезвычайной сложности.

Необходимо в качестве следствия из теоремы 16.33 отметить тот

- вес каждого слова РМ-кода порядка г кратен 4. Для доказательства достаточно только заметить, что если W (/) (число единиц в двоичной записи числа j) не превосходит т/2, то g («О = О, а если w (/) > т/2, то w (2"" - 1 - у) = m - - W {]) т/2, так что g (а") = 0. На самом деле для весов кодовых слов РМ-кода можно доказать выполнимость условия сильной четности. Допустимые значения весов РМ-кода первого порядка исчерпываются величинами О, 2"" и 2"\ Значения васов РМ-кода второго порядка также сильно ограничены, как показывает теорема 16.34.

16.34. Теорема (Казами [1968]). Бес каждого кодового слова любого подкода РЖ-кода второго порядка с блоковой длиной 2*" имеет вид

ц; = 2"-Че2/"+2-\

где fQ, i т (mod 2), а е = 0, -f-1, -1 в зависимости от кодового слова.

Замечание. Согласно теореме 15.34, каждое кодовое слово РМ-кода второго порядка может быть записано в виде

(16.341)

BijXiXj+BtXi + Б,

где Bi, j, Bi п Б GF (2), Xi = С() и XiXj = С() ®С(. Для упрощения выражения (16.341) воспользуемся теоремой 16.35, принадлежащей Диксону [1901]. Доказательство теоремы 16.34 мы проведем после доказательства теоремы Диксона и следствий из нее. Хотя первая сумма в формуле (16.341) - квадратичная форма над GF (2), мы проведем доказательство теоремы Диксона для поля GF (2"), что вызовет лишь незначительные услончнения.

16.35. Теорема (Диксо н). Любая квадратичная форма от I переменных

I I

= S S Bi,jXiXj, Bi,j£GF(2n,

i=l 3=1

С помощью линейного невырожденного преобразования переменных над полем GF (2") может быть приведена к одной из следующих