для любой последовательности {gi 6 GF (q)}. Отсюда вытекает, что

giVGF (q)

для любой последовательности {gi 6 GF (q)}, кроме случая, когдч все gi равны.

Таким образом, когда / = 3, то iV = 4, если многочлен f (z - г1 имеет неприводимый делитель четвертой степени с линейно незави-i симыми корнями, и iV = 6, если многочлен J{z - г) имеет непривс димый делитель четвертой степени с линейно независимыми корнями

и неприводимый квадратный делитель, корнями которого являются V + vq + и и v + + и, ueGF (q). Если iV 4 и N фЦ то TV = 25 + ЗС, В, С > 1, и можно найти iV корней многочлену J (z - г) среди корней В неприводимых квадратных многочлене! и С неприводимых кубических многочленов.

Относительно легко определить вероятность того, что все Kopi случайно выбранного аффинного многочлена будут лежать в основ ном ноле. Число аффинных многочленов любой заданной степет в точности совпадает с числом способов выбора их коэффициентов Число многочленов, все корни которых лежат в основном поле описывается следующей теоремой, известной еще Ландсбергу [18931

11.52. Теорема. Число к-мерных подпространств поля GF над GF (q) задается формулой

h-i k-l m-h-l

qm-i - l yj qm-i - i

nh-i-l

qm-h-i 1

t=0 i=0

Число к-мерных аффинных подпространств поля GF {q) на GF (q) задается формулой

qm-i 1 q-i-i

Доказательство. Сколькими способами можно выбра! упорядоченные совокупности из к линейно независимых (над GF (qj элементов ноля GF (д"*)?

Если i линейно независимых векторов уже выбраны, то oi порождают пространство размерности г, содержащее векторе! Тогда (i + 1)-й вектор может быть выбран (q - q) способами

Таким образом, имеется (q" - 1) (g"" - q) {q" - q) . . . (g-™ - g""* способов выбора упорядоченного множества к линейно независим! элементов ноля GF {q). Так как каждое подпространство разме! ности к имеет - \) {q - q) . . . {ф - ) различных базисо!

число различных /с-мерных подпространств задается формулой, участвующей в формулировкетеоремы. Каждое /с-мерное[нодпростран-ство имеет д""** сдвигов, приводящих к аффинному подпространству, и каждое аффинное подпространство является сдвигом линейного подпространства, щ

11.6. Кодовые слова с малым весом в некоторых кодах

Существует много способов задания кодовых слов и векторов ошибок. В некоторых случаях наиболее удобно представлять кодовые слова непосредственно в виде последовательности символов, передающихся по каналу, С = [Со, Cj, . . ., C.J. Вектор ошибок может быть представлен при этом как последовательность аддитивных шумовых символов, Е = [£о, i, . . ., En-i]. Однако для целей декодирования вектор ошибок удобнее представлять в виде многочлена локаторов ошибок

(7.21) o(z)= П (i-XiZ).

j-локаторы ошибок

В случае двоичных циклических кодов и недвоичных негацикличееких кодов с метрикой Ли многочлен локаторов ошибок полностью определяет вектор ошибок, а в случае недвоичных кодов с метрикой Хэмминга вектор ошибок зависит как от многочлена локаторов ошибок, так и от многочлена значений ошибок со (z) = о (z) + + S zYtXt П (1 - Xjz). Если все ошибки равны 1, то со (z) =

= ст (z) - zo (z). Существенное преимущество представления вектора ошибок через многочлен локаторов ошибок о (z), а не в виде

многочлена ошибок Е (х) = 2 EiX, состоит в том, что многочлен

о (z) точно отражает вес вектора ошибок: deg а (z) = вес Е.

Хотя мы до сих пор и не пользовались этим, каждое кодовое слово можно описать с помощью многочлена локаторов кодового слова

o(z) =

{i-Xiz).

j.-локаторы ненулевых коэффициентов многочлена С(х)

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

соответствующее кодовоеслово удовлетворяет всем проверочным! уравнениям. Для циклических кодов такими проверочными уравне-! ПИЯМИ являются взвешенные степенные симметрические функции от взаимных корней многочлена о (z).

В случае метрики Ли степенные симметрические функции от взаимных корней многочлена локаторов о (z) могут быть вычислены! с помощью тождеств Ньютона:

(9.32)

5(z) = -

-za (2)

a(z)

Эта формула остается справедливой и в случае метрики Хэмминга,! если величины всех ошибок равны 1. I

Покажем теперь, что если некоторые коэффициенты многочлена! а (z) равны нулю, то некоторые коэффициенты многочлена S (z) также равны нулю.

11.61. Теорема. Пусть о (z) = L (z) - и, где L (z)

= 2 i2«\ Пусть

S{z) =

- za (z) a(z)

= B,jZuJ,

к J

где Вк, j - константы, зависящие только от коэффициентов много члена L (z). Определим w {К), вес числа К, с помощью равенств( w (К) = Kj, где Kj - коэффициенты q-ичного представления чис

К; К ==j] Kjq\ О < Kj <q. Тогда

Bk,j = О,

за исключением случая, когда выполняются оба неравенства (11.611) wiK)k(q-i) +w{J)k{q-l)

/ + 1 < ( + !)• Доказательство

o(z)--= - м+ 2 LiZ\ Lk = i, ft

o(z) = -az9+ 2 LiZi-i",

a (z) = Lo{q-1) z = - Lozs"",

(11.612)

S{z) = -

11.6. Кодовые слова с малым весом в некоторых кодах -za (z)

a{z)

ft-i

l+-LiZ-4-uz

= LoZ«-i2 (uz-ZLi-Т-

N=0 1=0

Разлагая N в ряд по степеням q, N=Njq\ получим, что

ft-i

S (z) = Lo 2 z«-i {uzч- 2 L.z-)

ft-1

= Lo 2 z-n П {иЛя- 2 Ьф-я) .

N=0 i m=l i=0

Рассмотрим произведение

i m=l

- ~ i=0

Запись этого произведения в виде степенного ряда может содержать

член с u-f только тогда, когда / = 2 где О < Nj. Иными

словами, каждая цифра в д-ичном представлении числа / не должна превосходить соответствующей цифры д-ичного представления числа N. Разложение произведения в ряд может содержать член с zu- только тогда, когда

Nj i m=i

где i - функция от / и т, принимающая значения О, 1, 2, . . ., /с - 1 или оо, причем i (j, т) = - оо только для Jj различных значений т. (суммируя сначала только по тем значениям т, для которых i (J, т) = ~ -оо, получим

K=q-i+{JsqJ 2 g+-gU.

3 m=l

= - 1 + 9" + S S (?"+ -gi+*0-. -)),

где i (j, m) = 0, 1, . . ., /с - 1. Следовательно, Z > g - 1 + qJ. Это доказывает соотношение (11.612).

Можно также записать

3 т

д"-1-igTv-л:+2 S•

Э тп

Так как для любого множества чисел {а,} справедливо неравенств qN) <w{K) + Jiw (qi+iO. m-)) =

i m

=w{K)+w{N-J)=w{K)+w(N)-w{J). Подстановка w {( - I + qN) = к (q - I) -{ w (N) дает к (q - i) + w (N) (К) + (TV) - w (/),

w(K)k{q - I) +w (/).

Это доказывает соотношение (11.611) и теорему.

Теорема 11.61 позволяет выделить слова малого веса во многв циклических кодах с блоковой длиной q" - I. Например, в циклв ческом двоичном коде с блоковой длиной 31 координаты могут быт занумерованы как 1, а, а, а, а*, . . ., а", где а* + + 1 =

Каждый элемент поля GF (2) может быть записан в виде 2 •гИ

Восемь элементов, координаты которых удовлетворяют уравнение Zq + Zj + = О, Zj -f Zg = 1, образуют трехмерное аффинне подпространство над GF (2). Это аффинное подпространство элеме! тов а, а, а**, а*, а, а, а, а*, являюн];ихся корнями аффинног многочлена а (z) = z* + aV + az + a*z + a. Согласно теорв ме 11.61, для всех К, таких, что w (К) 3, симметрические фунг ции степени К от этих восьми элементов равны нулю. В частноств Si = S, = = О, так

что о (z) = 1 + ai*z* + az" + a*z + az* - многочлен локаторов кодового слова с весом 8 из двоич ного БЧХ-кода с блоковой длиной 31, исправляюш,его три ошибкв Соответствующим кодовым словом является

С =- [0001010000000000100101100001100]. Так .как Sq = О, то это кодовое слово, Дополненное нулем, нринадлеЛ жит расширенному БЧХ-коду с блоковой длиной 32. Этот приме обобщается теоремой 11.62, вытекающей сразу из теоремы 11.61

11.62. Теорема (Казами, Лин и Питерсон [1966[ и Камьо [1966, 1968]). Если а - примитивный элемент поля GF (д"*),

) Доказательство этого соотношения мождо найти в лемме 15.575»

{-удлиненный циклический код с блоковой длиной N = q" над GF (q) и порождающим многочленом g (х) содержит кодовые слова веса ф {как в метрике Хэмминга, так и в метрике Ли), за исключением сгучая, когда существует такое К, для которого и> (К) к (q - i) и g (аК) = 0.

11.63. Следствие. Частный i-удлиненный ВЧХ-код с конструктивным расстоянием ) q над GF (q) содержит кодовые слова веса q.

Доказательство следствия 11.63. Корни порождающего многочлена циклического БЧХ-кода с конструктивным расстоянием q совпадают с элементами а", а, а, . . ., а?- п сопряженными с ними. Если К <,q - , io w (К) <.к (q - 1). Если а- - элемент, сопряженный с а, то w (J) = w (К). Следовательно, g-(а*) =5 О, за исключением случая и> (К) <к (q - I). щ

Теорема 11.62 описывает кодовые слова малого веса, локаторы ненулевых координат которых лежат в аффинном подпространстве пространства GF (д") над GF (д). В некоторых кодах все слова малого веса являются словами такого типа. Такие коды описываются теоремой 11.64, являющейся обобщением теоремы Питерсона.

11.64. Теорема. Пусть g (х) - порождающий многочлен кода с блоковой длиной п = д™ - 1, U пусть w (К) - сумма цифр q-ичного представления числа К. Если

g{a) = 0 w(K)<ik{q-l)

w(K)<k{q-i), I

<2g

g{a) = 0.

11.641. Локаторы ненулевых координат произвольного кодового с.чова веса q из 1-удлиненного кода образуют аффинное подпространство размерности к над GF (q).

11.642. Ненулевые координаты любого фиксированного слова веса ц совпадают.

Доказательство утверждения 11.641. Пусть о (z) - локатор кодового слова с весом Хэмминга ф, и пусть и (z) - многочлен величин координат для этого кодового слова. Тогда

(11.643)

q(2) 2j •

К=1

) Конструктивным расстоянием д-ичного БЧХ-кода называется такое число d, что а, а, . . ., ad- являются корнями порождающего многочлена кода.- Прим. перев.