13.6. Граница Элайеса

циклических или негациклических сдвигов порождающего многочлена, то они имеют равный вес в метрике Ли. Однако при Ф + i констациклические сдвиги порождающего многочлена имеют разные веса в метрике Ли. щ

Для некоторых регистровых кодов максимальной длины теорема 13.52 указывает истинный минимальный вес, больший, чем можно было бы предположить из других соображений. Например, рассмотрим негациклический регистровый код максимальной длины с блоковой длиной 63 над GF (127). (Этот код приведен в табл. 9.1.) Согласно теореме 9.34, код исправляет в метрике Ли 63 ошибки. Однако, согласно теореме 13.52, вес каждого ненулевого слова этого j кода равен 32 X 63. Следовательно, код исправляет в 16 раз больше» ошибок, чем это следует из теоремы 9.34.

По заданному эквидистантному коду с К словами и блоковой! длиной п с помощью простого повторения каждого слова исходного! кода / раз можно построить эквидистантный код с К кодовыми слова-] ми и блоковой длиной jn. Если исходный код был циклическим, то] и результирующий код будет циклическим с тем же проверочным! многочленом.

Над полем GF (2) регистровые коды максимальной длины имеют! блоковую длину п = 2 - i м содержат К = 2" кодовых слов. Для многих других значений К эквидистантные двоичные коды из К слов с блоковой длиной К~\ могут быть построены на основе матр1 Адамара. Матрицей Адамара называется ортогональная {К X К.)-\ матрица, элементами которой являются числа -f-l и -1. Например,f

12 -

- +J

+ + -f + + + + + - + + + - + -

+ - - + -+----

----Y

--+ + -

- + + + -J

Без потери общности можно предположить, что все элементы первой строки и первого столбца матрицы Адамара равны -)-1. Отбрасывая первый столбец {К X Г)-матрицы Адамара, получим К строк длины К - образующих двоичный эквидистантный код. Если К не есть степень числа 2, то получается нелинейный код.

Легко показать, что (К X )-матрицы Адамара существуют только тогда, когда К = 2 или К кратно 4. Не доказана и не опровергнута гипотеза, что для всех таких К существуют матрицы Адамара. Первый контрпример возможен при К = 188; для всех меньших значений К (и многих больших значений) матрицы Адамара могут быть построены с помощью методов, предложенных Холлом [19671 или в более ранних работах Спенсом [1967] и Гёталсом и Зейде-лем [1967].

В то время как полное расстояние произвольного линейного кода равно DKn, где D задается теоремой 13.49, нелинейный код может иметь и меньшее полное расстояние. Нелинейный код может быть эквидистантным даже в тех случаях, когда его кодовое расстояние лежит намного ниже границы Плоткина. Например, двоичный код, словами которого являются строки единичной матрицы, является эквидистантным с расстоянием 2. Хотя этот код является тривиальным, ничего лучшего построить нельзя, если потребовать, чтобы каждый вектор имел вес 1. Вообще, если на вес каждого кодового слова наложить некоторые ограничения, среднее расстояние между парами слов не может быть большим. Это замечание лежит в основе вычисления границы Элайеса, которая выводится в следующем разделе.

13.6. Граница Элайеса

Мы видели, что граница, полученная с помощью сферической упаковки, является точной при больших скоростях передачи и неточной при малых, а граница Плоткина точна при малых скоростях передачи и неточна при больших. Комбинируя эти границы и используя одну высказанную в 1960 г. плодотворную идею Элайеса, можно получить более строгую границу для средних скоростей. Некоторое уточнение этой границы было предложено Вайнером [1965].

Мы выведем границу Элайеса в двух леммах. В лемме 13.61 на основе границы сферической упаковки мы покажем, что код должен содержать критический шар, включающий много кодовых слов. Затем в лемме 13.61 мы покажем, что среднее расстояние между кодовыми словами этого критического шара мало.

13.61. Лемма. Для заданных числа t и кода с блоковой длиной п и скоростью R существует критический шар радиуса t, содержащий К > F<">/gn( 1-R) кодовых слов, с помощью подходящего сдвига кода центр этого критического шара может быть перенесен в точку 0.

(m)t

где 3г,расстояние между г-й и /-й буквами входного алфавита. Полный вес по всем кодовым словам определяется выражение»

2 AD<°P<"",

где D*" = [3)о,о, 3)о,1, Зо ,9-1] - первая

q-ii - ±icjjDci/i строкэ матрицы 3>. Если вес каждого из К кодовых слов не превосходи!

Dxn, то полный вес не превосходит KDxn и 2 KDV™ CKDxni

Р<, Р<", максимин

Найдем теперь вероятностные векторы Р

зирующие сумму 2 PJP" при условии 2 KDV Dxn\

)П=1

Эту задачу будем решать в два этапа. Сначала определим максиму»

р(т)( I (0)р(т)(

(13.63) и

(13.64) = Dxm, где 1 = [1, 1, 1]. в силу этих условий, для отыскания максимума функции Р"3)Р"= 2 2г"Р$"г.у надо рассмотреть

i i

функцию

2 2 pirs);., ч- а {Dxm - 2 з)о. iPT) +5(1-2 Pi"},

i j i i

где A и В - постоянные множители Лагранжа. Для определения стационарной точки этой функции приравняем к нулю ее частную производную но PjK Так как 3)h,h - 0, то для всех к получим

2 Pii, k + 2 рТзп, j-азо, й - 5=о.

или (13.65)

Полагая

,(т)

2Pr3)i,k==A3,,u + B.

1) Иногда его называют критической сферой.- Прим. перев.

6 = [1,0, о, ...,0],

можно проверить, что одним из решений задачи (13.63) - (13.65) является

Р">= + (1-т)6, (13.66) A2{i-Xm),

B = 2XmD,

Согласно разд. 13.4, РЗТ -выпуклая функция вероятностного вектора Р. Следовательно, стационарная точка (13.66) является точкой максимума функции р(™>3)р(" при условиях (13.63) и (13.64).

Для завершения доказательства надо определить ж,, Х2, Хп,

максимизирующие 2 Dxm{2 - Xm) при условии 2 т<-Из сооб-

т=1 4=1

ражений симметрии выберем Хт = х для всех т. Такой выбор задает стационарную точку, а так как ж (2- ж) - выпуклая функция от х, то выбор является правильным.

Доказательство. Каждую из д" точек пространства окружим сферой радиуса t и обозначим через (t = 1, 2, . ; ., g") число кодовых слов в i-M шаре. Так как каждое из д" слов появляет-

СЯ в Vl" шарах, то S = g"F," и Z = max Kt > Fj"Vg(i-«K

i=i i

Шар, содержаш,ий наибольшее число кодовых слов, называется критическим ). Если из каждого кодового слова вычесть центр критического шара, то центр критического шара переместится в о, а минимальное расстояние кода не изменится, щ

Вычислим теперь среднее попарное расстояние между кодовыми словами в критическом шаре. Так как каждое из таких слов находится на расстоянии от центра, то они должны располагаться близко друг к другу. Поэтому среднее попарное расстояние кодовых точек в критическом шаре значительно меньше среднего попарного расстояния кода. Точный подсчет содержится в лемме 13.62.

13.62, Лемма. Если вес каждого из К кодовых слов не превос-

ходит Dxn, где D = 2 о dq-, то расстояние между некоторыми

i=l

парами из этих К кодовых слов не превосходит х{2 - х) Dn /(1 - К~),

Доказательство. Как и в разд. 13.4, di <С dioi/{K-K)M где dtot - полное расстояние для всех упорядоченных пар кодо-1 вых слов. Если через Р"" опять обозначить вектор вероятностейJ описываюш,ий /п-й столбец кода, то

p(m),p(m)( jjpjj условии D<°P" = ZJm, 3 ззтсм выберем максими-

,ЗируЮШ,ие {Хт} при условии 2 тХП.

Согласно ограничениям на искомый максимум,

Таким образом, максимум полного расстояния c?tot = = iC2 2 p(m)p(m)( pjj условии ЬV">Dxn достигается,

m=l m=l

если Xm = x для всех m и P"" задается равенством (13.66). Полное расстояние при этом равно KH{2 - x)Dn, а среднее попарное расстояние между К - К различными словами равно Кх (2 - ж) X xDn/{K-l)K. и

Для эффективного сочетания лемм 13.61 и 13.62 необходимо прежде всего выбрать радиус t критического шара. Такое t должно минимизировать Dxn{2 - x)/{i--K-), где x = t/Dn, а /(Г -наименьшее целое число, большее или равное FIV?""- При больших блоковых длинах объем У(" быстро растет с ростом t, так что хорошо выбранное число t лишь незначительно превышает наименьшее целое число, для которого У1">д"~\

Согласно (13.15) и (13.18),

Следовательно, если отношение t/n становится постоянным, как только его значение превосходит б (i?), то yj"Vg"~ стремится к бесконечности при увеличении п. При этом < 1. Пренебрегая этим членом в знаменателе выражения х (2 - х) Dn/{1 - К~) (из леммы 13.62), получаем следуюш;ую асимптотическую форму границы Элайеса.

13.67. Теорема. При произвольно выбранных е>> О и скорости R для достаточно больших п

<6(i?)

D J

+ е.

где б [К) определяется условиями (13.18) и (13.15), а Z) - теоремой (13.49).*

Сравнение полученной границы с асимптотической формой границы сферической упаковки (уравнение (13.19)) показывает, что граница Элайеса равномерно более точная, хотя с увеличением скорости разница становится практически неощутимой. Для малых скоростей

граница Элайеса стремится к границе Плоткина, так как Иш б (i?) = д-»о

= D. На рис. 13.2 показана асимптотическая граница Элайеса для

двоичного случая.

13.7. Граница Гилберта

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

13.71. Т е о р е м а (Гилберт [1952]). Если

„п(1-Д) Ч 1

то произвольный код с блоковой длиной п, минимальным расстоянием d и скоростью R является собственным подкодом другого кода с тем же минимальным расстоянием.

Доказательство. Каждое из д" кодовых слов окружим сферой радиуса d - \. Объем каждой сферы равен Fl, а полный

объем всех сфер - gF-i- Если полный объем меньше, чем д", то существуют точки, не входящие ни в какую сферу. Расстояние каждой такой точки до произвольной кодовой точки d, так что без уменьшения минимального расстояния кода любая из этих точек может быть добавлена в качестве кодовой, щ

В соответствии с границей Гилберта, к коду с малой скоростью и минимальным расстоянием d можно прибавлять кодовые слова до тех пор, пока скорость не возрастет до 1 - (1/и) loggFdli. Расстояние такого кода будет совпадать с расстоянием исходного кода. Однако, к сожалению, регулярная математическая структура исходного кода при таком расширении может нарушиться. Если к исходному коду применимы алгебраические методы декодирования, то они могут оказаться непригодными для увеличенного кода. Если исходный код -циклический, то расширенный код, вообще говоря, уже не циклический. В общем случае увеличенный код не является линейным, даже если исходный код - линейный. Однако если поступать более осторожно в соответствии с леммой 13.72 и теоремой 13.73, 10 последней неприятности можно избежать.

13.72. Лемма. Для каждого линейного кода, содержащего д" кодовых слов, можно построить расширенный) линейный код из gi+" с.юв, который получается путем присоединения к исходному коду всех ненулевых скалярных кратных слов из некоторого смежного класса исходного кода.

Доказательство. Пусть G - множество слов исходного !.ода, V Ф G - смежный класс, а v - его лидер. Каждое слово класса V имеет вид v + g, g 6 G, а каждое слово из расширенного кода

) См. далее примечание переводчика на стр. 338.