318 Гл. 13. Скорость передачи инфор.чации для оптима.гьных кодов

Используя аналогичные рассуждения для дуального кода Синглтон [1964] показал, что

(13.34) если d=re + l-А;<?г - 1, то q п + i - к.

Из соотношения (13.33) следует, что уравнение (13.32) не выполняется ни для одного двоичного кода, за исключением случаев /с = 1 (двоичный код с повторением) и d = 2 (код с одной проверкой на четность). Однако для больших алфавитов известны нетривиальные коды, для которых выполняется равенство d = ге -(- 1 - к. Один из классов таких кодов дает теорема 13.35.

13.35. Теорема. Расстояние, блоковая длина и число информационных позиций любого кода Рида - Соломона (БЧХ-кО(9а с q = = и -j- 1) связаны соотношением d - п - к ~\~ i.

Доказательство. Порождающий многочлен БЧХ-кода

НО определению равен g (х) = Ц () где М<*) (х) - минимальный многочлен элемента а% а а - примитивный корень ге-й степени из единицы в расширении поля GF (q). Для РС-кодов а GF (q), М(*) (х) = X - и deg g (х) = d - i. щ

Другие классы кодов с достижимым максимальным расстоянием были предложены Синглтоном [1964]. В разд. 16.5 будет показано, что для этих кодов удается полностью определить их весовую структуру-

13.4. Граница Плоткина для малых скоростей (граница среднего расстояния)

Минимальное расстояние между любыми двумя кодовыми слова- ми не может превышать среднего расстояния по всевозможным f парам кодовых слов. Это замечание, принадлежащее Плоткину, лежит Щ в основе вывода другой границы для минимального расстояния. Для метрики Ли эта граница впервые была получена Грэхемом и Вай- ; пером [1968].

Предположим, что код состоит из К слов С, С, С", С, где 6*= [С**), С(*>, C(j*)J. Тогда полное расстояние по всем

Словами кода, дуального к линейному коду, являются векторы пространства строк его проверочной матрицы. Легко проверить, что дуальным к дуальному коду является сам исходный код.

13.4. Граница Плоткина для .малых скоростей 319

парам кодовых слов задается формулой

<tot = ] Sd(C<,c<>)-

i=l j = 1 m=0

=V S I d(ac(i)).

m-O t l 3 = 1

Обозначим через ""(/ = 0, 1, 2, . . ., q-1) число появлений 1-й буквы алфавита среди букв С\ С(3) qw. Тогда вероят-

ностный вектор P">=irj"\ Jf\ . .., Ц1\]/К характеризует т-ю координату случайно выбранного из кода слова. Имеем

1 S d (cwco)) 2 РГРГЗ)1. J =

i- 1 i~ 1 i=0 i=0

где 31, j - элемент на пересечении г-й строки и ;-го столбца в матрице 3) расстояний между буквами входного алфавита. Например, для g = 5 в метрике Ли

ГО 1 2 2 Г

10 12 2 3 = 2 10 12 2 2 10 1 Л 2 2 1 Oj

а в метрике Хэмминга

0 1111 10 111 110 11 1110 1

Ll 1 1 1 oJ

В любом случае полное расстояние задается формулой

dtot=-K 2 P<"SJP">.

вых г.п« г1 Р™™" содержит сумму по всем К парам кодовых слов. Среди них К нар содержат одинаковые слова, а К -К пар - различные слова. Среднее расстояние по всем К (К - i)

парам различных кодовых слов удовлетворяет соотношению

2 P"5)P<"><j--PSP,

где Р - «лучший» из возможных векторов РС"), т = О, i, . . ., п - 1. Так как минимальное расстояние не превышает среднего расстояния, то

(13.41) d.„< PSP.

Соотношение (13.41) называется границей Плоткина для минимального расстояния.

Из соображений симметрии естественно предположить, что наилучший из возможных вероятностных векторов задается равенством Р = l/q = [1, 1, . . ., l]/q. Однако сухцествуют симметричные матрицы 3, для которых i/q не является наилучшим вектором. В общем случае вопрос об оптимальности вектора l/q для данной матрицы 3 может быть решен с помощью ее собственных чисел. В случае аддитивного шума по mod q для матрицы 3 выполняется условие j = =3h, т при I - j = к - т mod q. В этом случае собственные векторы матрицы 3 равны р) == [1, efe/?, е4лШд . . .],где к = О, 1,

2, . . ., q -\, i = У -I; я = 3,14159. . ., е = 2,71828 При

fc == О получаем собственный вектор рС) = 1. Собственное число,

соответствующее собственному вектору р*"), равно.А= 3o,je".

Легко проверить, что Sp( = ,ftp( )для всех /с = О, 1, 2, ..., q- 1. Легко также проверяется ортогональность собственных векторов, т. е. тот факт, что р()р*() = О, если / Ф к. (Здесь р*() ~ вектор, комплексно сопряженный с р).)

В общем случае величина = q-ft комплексно сопряжена с Х/,. Если 3 - симметричная матрица, то все ее собственные числа вещественны. В этом случае вместо комплексно сопряженных собственных векторов pt) и р(~) можно использовать вещественные! собственные векторы р() -f рС") и i (р(*) - р*")), но это дает; весьма малые преимущества.

Собственные числа матрицы 3 легко вычислить и в случае метри- ки Хэмминга, и в случае метрики Ли. Полагая и = е2л?/д g случав метрики Хэмминга, получим, что при к Ф О

(13.42)

(13.43)

9- 1

Xk = 2jU --5-= -1

9-1 3=1

(13.44)

3=1 3=0 5=0

г [(ге+1)гп(г -l) (zn+l l)] ~ (=1)2

d z"+l-1

г -1

При нечетных q неглавные собственные числа матрицы 3 в мет-

„ (9-1)/2

рике Ли задаются формулой h = 2Re{ j /V), где и = е2лШ5,

Так как «/ = (-1)= и иЧ-и-Ч. = 2isinA, топриАО, исполь-зуя (13.44), получим

(13.45) Яй=2Ке

1 + Ф (-1)" 2i sin --(-l)ft (cos + г sin f)

- 4sin2 (nk/q) -1 + l)ftcos (nk/q) 2 sin2 (лк/д)

Главное собственное число равно

(13.46)

(9-1)/2

q-ig+i g-i

Для четных q неглавные собственные числа матрицы 3 в метрике Ли определяются формулой

(9-2)/2

(13.47) A,.Re(r./2 + 2 =

= Ве = Не

tnf9(A)k I 2[l + (g/2)(-l)fe(l-»-l) ( l)ftn

-4sin2(n/c/g)-] =

2-2(-l)ft+(g/2)(-l)ft («-и-1)-- 4sin2(n/(;/g)

-i-K-i)ft

2sin2(n/c/g)

tllZT е. собственное число с макси-

мальным модулем.

Для вычисления в метрике Ли рассмотрим сумму

а главное собственное число - формулой

(д-2)/2

(13.48) K=i + 2 2 /-1 + 1 = -

Из равенств (13.42), (13.45) и (13.47) следует, что все неглавные собственные числа матрицы 3) неположительны и в метрике Хэмминга, и в метрике Ли. Поэтому квадратичная форма PSP - выпуклая функция от вектора Р, т. е., если а>0, 6>0, а + Ь=1, 1Р = 1, 1Q = 1, то

(аР -f bQ) 3 (аР + bQ) > aPSP ± bQSQ. Для доказательства этого факта выразим Р и Q через вещественные соб-

q-i ?-1

ственные векторы матрицы 3. Полагая Р= 2 уР*- <?= S QjP

3=0 3=0

получим

(аР + ЬО) 3 (аР + bQ) = g 2 (« + Qj)

g-i 9-1

aP3P+bq3q = aq 2 ?7i + bg 2 .-f-

j=o 3=0

Так как собственные векторы ортогональный 1P = 1Q=1, то PoQo = aPo + bQo=i/g и K{aPo+bQo) = aloPl-\-bKQl- Предно--ложение о выпуклости квадратичной формы при этом сводится к утверждению, что

2 h iPj f bQjr > 2* h {aP] + bQ.

3=1 3=1

Так как a; -выпуклая функция от х, то {аРj-bQjYKaP]-TbQ)l для всех у. Так как все собственные числа, кроме главного, нено- ложительны, то

Х{аР \-bQjf>kj{aP] + bQ;):

для всех / > 1 и Р.25Р - выпуклая функция вектора Р.

В силу выпуклости квадратичной формы стационарная точка: является точкой абсолютного максимума, а ввиду симметрии векто1Й Р = ilq задает стациоларпую точку. Таким образом, наибольше значение функции VЗV из (13.41) можно определить из уравнен ПИЙ (13.43), (13.46) и (13.48). Мы получили:

13.49. Теорема. Минимальное расстояние dain произвольного кода с блоковой длиной п и К кодовыми словами над алфавитом из буке удовлетворяет неравенству

где постоянная Z) = 2 о, i/Ч задается формулой 1=1

для метрики Хэмминга,

для метрики Ли и нечетного q, J- для метрики Ли и четного q.

*13.5. Эквидистантные коды

Для того чтобы код достигал границы, указанной в теореме 13.49, его минимальное расстояние должно совпадать со средним расстоянием. Это возможно только тогда, когда расстояние между любыми двумя различными кодовыми словами одно и то же (такой код называется эквидистантным).

Наиболее важный класс эквидистантных кодов описывается определением 13.51 и теоремой 13.52.

13.51. Определение. Регистровым кодом максимальной длины называется циклический, негациклический или констациклический код, проверочный многочлен h (х) которого является примитивным многочленом степени к над полем GF (q). Если п - блоковая длина кода, то h (х) делит х - , где I OF (q) и порядок равен (д" - i)/n.

13.52. Теорема. Каждое ненулевое кодовое слово циклического, негациклического или констациклического регистрового кода максимальной длины является циклическим, негациклическим или констациклическим сдвигом любого другого ненулевого кодового слова. Таким образом, в метрике Хэмминга все регистровые коды максимальной длины, а в метрике Ли все циклические и негациклические регистровые коды максимальной длины являются эквидистантными.

Доказательство. Код содержит q - 1 ненулевых кодо-Bi.Tx слов, каждое из которых кратно порождающему многочлену ц (.г) = {х - l)/h (х). Достаточно показать, что д - 1 констацикли-ческих сдвигов порождающего многочлена дают различные значения. Если это не так, то xg (х) = x™g (х) mod (ж"- I) и существует число i = т - i, i <:q - 1, такое, что .(ж -~\) g {х) = 0 mod [х - I). Так как х" - I = g (х) h [х), то У - 1 = О mod h (х). Но примитивный многочлен h (х) делит х - i только когда j кратно д - 1. (Следовательно, д*" - 1 ненулевых слов кода получаются путем кон-стациклических .сдвигов порождающего многочлена и имеют один и тот же вес Хэмминга. Если кодовые слова получаются путем