где Вц. равно единице, если I Ф I, и нулю в противном случае. Значения А,/11 нам неизвестны, но мы знаем, что они удовлетворяют двум следующим ограничениям:

q-1 д~\ п-1

2I£ = 1 И TiY!ih\i = t.

1=0 г=11=0

Так как %щ неизвестны, рассмотрим наихудший случай, выбрав их значения так, чтобы при одновременном выполнении указанных ограничений величина в правой части формулы для dtot была бы как можно больше. Если предварительно доказано, что максимальная функция является выпуклой функцией вероятностного вектора , то один из методов решения задачи состоит в использовании множителей Лагранжа. Чтобы упростить доказательство, воспользуемся вместо этого элементарным приемом: сначала укажем, какие значения А,; являются максимизирующими, а затем докажем, что они в самом деле таковы.

Лемма 14!4.6. Я/сть F (А) = 2г 2/,/-л Лгм где Оц,

равно единице, если I Ф I, и нулю в противном случае. Если для % имеют место ограничения

q-\ Q-\ n-I

S / I 1 = 1 И H S i = /.

l=\ i=0

L<?-l

Доказательство. Прежде всего заметим, что из указанных ограничений вытекает соотношение

Yi Aoi = n-t.

Пусть

/1 i

1 - tin, I == 0,

[{tln)l{q-\),

при всех i. Убедимся, что эти значения максимизируют F (А). Заметим, что

Поэтому при всех %, которые удовлетворяют нашим ограничениям, включая к = к*,

п-1 (7-1 С- 1

1.0 /=0 1=0

<?-1 п-1

Г=1 1=0

Раскрыв скобки и проведя упрощения в левой части этого равенства, получим

= 2 Zj (Zl iZ I Z - iZ* I i) Dw i Z, I

Достаточно показать, что величина в левой части этого равенства неположительна. Введем обозначение

cz I (• = {h I z-t) и заметим, что Jz Cz i z = 0. Необходимо доказать, что при любом i

И (ci I iCi I i) Dir < 0.

Z, I

Ho при любом i

H Cz I iCri zAz == Ij Cz I iCr z - Ц d 1 z = 0 - Ц C? < 0. Z, Z Z, Z z z

Доказательство леммы завершается вычислением значения F □

Теорема 14.4.7 Сграница Элайса). Пусть

T = q-in-k)g iy (;),

/ произвольно. Если Т > U то любой код над GF (q) со скоростью R и длиной п содержит пару кодовых слов, расстояние d между которыми удовлетворяет неравенству

T-l [<?-! (<?- 1) « J *

Доказательство. Выберем величину t в теореме 14.4.5 так, чтобы Т, было больше единицы. Тогда существует сфера, на 17*

1 + JQ-JY t

которой число кодовых слов Т больше единицы. Среднее расстояние между этими кодовыми словами удовлетворяет неравенству

rfav < [ТЦТ - 1)] I, Y%i ihliDu: i l.r

Для завершения доказательства необходимо применить лемму 14.4.6 и воспользоваться тем, что хотя бы два кодовых слова должны располагаться друг от друга"на расстоянии, не меньшем среднего. □

Следствие 14.4.8 (граница Элайса). В двоичных кодах со скоростью R относительное минимальное расстояние асимптотически удовлетворяет неравенству

" diR) 2р (1 - р)

при любых р, для которых 1 - Яь (р) > R.

Доказательство. Положим в теореме 14.4.7 q = 2, t/n = р

и перепишем неравенство теоремьР 14.4.7 в виде

< 1 2р(1-р),

Г = 2-6+0 0) и е = Яь(р)-1 + 7?.

По условиям следствия величина fi положительна; поэтому Т/{Т - 1) стремится к единице, когда п стремится к бесконечности.. Следствие доказано. □

14.5. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ СВЕРТОЧНЫХ КОДОВ

Минимальное /-е расстояние dt для сверточного кода с длиной блока п = (т -\- \) Hq определяется как минимальное расстояние Хэмминга среди всех пар начальных сегментов кодовых слов длины т 4- 1 кадров, у которых первые кадры различны. Минимальное расстояние d* сверточного кода равно dm+i> а свободное расстояние определяется соотношением

doo = maxd*.

В этом параграфе мы найдем границы типа границ Гилберта и Элайса для d* и doo.

Очевидно, что любой сверточный кс.- можно усечь до длины и получить блоковый код длины Л; этот блоковый код не может быть лучше наилучшего блокового кода длины Л. Целью настоящего параграфа является изучение поведения расстояния в зависимости от других мер длины кода, таких, как длина блока и