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

13.1. Граница сферической упаковки Хэминга - Рао для больших скоростей

Как метрика Хэмминга, так и метрика Ли определяют расстояния между точками в ге-мерном пространстве слов над алфавитом из q букв. В любой из этих метрик шар радиуса t с центром С определяется как множество всех точек, расстояние от которых до точки С не превосходит t. Поверхность этого шара [сфера радиуса t) - множество точек, расстояние которых до центра С равно точно t; число точек на сфере обозначается через По определению число точек,

принадлежащих шару, называется объемом FJ" шара. Ясно, что

Неравенство (13.11) называется границей по объему или границей сферической упаковки. Это неравенство появилось в работе Рао [1947] по экспериментальным конструкциям. К кодам с исправлением ошибок его впервые применил Хэмминг [1950].

Одним из приложений границы сферической упаковки является теорема 13.12, согласно которой двоичный БЧХ-код с большой скоростью передачи не хуже любого другого кода с той же скоростью и той же блоковой длиной.

13.12. Теорема. Если {« + 1)! ,

то любой код с блоковой длиной q-1 и скоростью i?>l-- содержит кодовые слова с весом Хэмминга •<2f-t-2.

Доказательство. Мы утверждаем, что F"* > >

>g">g"~ Единственной нетривиальной частью этого утвер-

yin) 2 Пусть {Z) = A{\\ Так как расстояние I "Д™ является неравенство >>g™. Так как

является аддитивной функцией на множестве координат, то производящая функция А (z) на множестве координат мультипликативна и поэтому (z) = [Л (z)]". Значит, в метрике Хэмминга

Л" (Z) = [1 + (д- 1) z]

а в метрике Ли

г (l + 2z + 2z2-f ...+2z(9-i>/2)«, если g нечетно;

" (2)= (l+2z-f 2z2+• • •+2z(?-2)/2+z5/2)", если q четно.

В любом случае можно определить At с помощью разложения Л" (г) в степенной ряд по z. Для метрики Хэмминга Л*" (z)=

= [1 +( 1) z]" = 2 (") 1) /lS"=(;)(g-l).

Для метрики Ли аналогичная формула имеет значительно более сложный вид.

Если расстояние между любыми двумя кодовыми словами 2t -- 1, то любая точка находится на расстоянии не более чем от одной кодовой точки. Если R - скорость передачи кода, то он содержит q" кодовых слов. Все сферы радиуса <i с центрами в кодовых словах не пересекаются. Следовательно, дКп*")

<г>=(7 г/)((?-1)+\

А(1 (gm l)(,m 2)(g™ 3) ... (дп-г-1)

<+1

(13.11)

г=1 г=1 W ;

(согласно предположению теоремы 13.12). Следовательно, Л1~>

>д", так что Fj+r* > g"(i-\ и теорема 13.12 вытекает из неравенства (13.11). щ

Иногда бывает полезной другая форма неравенства (13.11)

(13.13) i?<l-i.

При фиксированном Р = t/n для больших п это дает

(13.14) RC(P),

(13.15)

C(P)=l-lim

= 2 и t<{q-i)n!q,

in ±4<(") < Fmin z-" (z).

Эскиз доказательства. Для произвольного z, 0<;z<l, имеем F$"> = S A? < 2 A<th- = z S l"z* <z-<">z.

t=0 i=0 i=0

Мы утверждаем, что существуют такие значения z, что (13.161) "z>4"V для всех 1ф1.

Если соотношение (13.161) выполняется, то

At\>Ar:iZ- и "V > i!f.\z+i,

так что (13.162)

?1

Так как - монотонно неубывающая функция от i для

0i<i{q - {)n/q, то найдутся значения z, удовлетворяющие (13.162), а из (13.162) вытекает (13.161). Следовательно, существует некоторое значение z, скажем z, для которого

(Z) = 2 2 < S z = (п + 1) z,

г=0 1=0

И тогда

Значение z, минимизирующее выражения z-" [1-f (g-1) z]" и z- [1 + (g -1) z], обращает в нуль производную

Отсюда

-Pz-P- [ 1 + (g 1) г] + z-P (g - 1) = 0.

J5.i. Граница сферической упаковки Хэм.чинеа - Рао Подставив эти выражения в формулы леммы 13.16, получим

-"--Р)"""]" <F<[(g-l)P-(l-P)-<->]"-

При этом уравнение (13.15) принимает вид (13.17) С{Р) = 1-Р logg {q- I) +Р \ogg Р +

-\-il-P) log, (1 - Р).

Р и с. 13.1. Двоичный симметричный канал.

Скорость-

Р и с. 13.2. Асимптотические границы корректирующей способности для двоичного симметричного канала без обратной связи.

Если положить g = 2, то читатель, знакомый с теорией информации, узнает в этом выражении для С (Р) пропускную способность двоичного симметричного канала, показанного на рис. 13.1.

Для вычисления этого предела необходимо получить асимптотически точную оценку величины FpJ. Одну из таких оценок дает лемма 13.16, которая является модификацией более общих границ Чернова [1952] и Феллера [1943].

13.16. Лемма. Если /1" (z) = [1 4 (д-1) 2]"= ] 4"z\ Fj"=

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

В некоторых приложениях желательно выразить границу (13.14) не через R, а через tin. Такое выражение можно получить, если ввести величину б {R) - наименьшее решение уравнения

(13.18) R = С{6 {R)). Тогда соотношение (13.14) запишется в виде

(13.19) <W или <2б(/?),

где d = 2 + 1 - наименьшее из расстояний между кодовыми словами. Неравенства (13.19) дают асимптотические формулы для границы сферической упаковки. В случае двоичного симметричного канала, представленного на рис. 13.1, функции б (R) соответствует верхняя кривая, изображенная на рис. 13.2.

*13.2. Совершенные коды

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

Двоичный код с повторениями при нечетной блоковой длине п исправляет вплоть до (ге - 1)/2 ошибок. Для t = (п - 1)/2 и Л = 1/п

(п-1)/2

имеем F" = ( " ) =-2"- =2"(-«. Таким образом, двоич-

НЫЙ код с повторениями и нечетной блоковой длиной является совершенным. Как будет показано в разд. 13.6, все другие совершенные коды должны иметь либо большую скорость передачи, либо малую блоковую длину. Теорема 13.21 описывает бесконечный класс совершенных кодов с большой скоростью и малой корректируюш;ей способностью {t = 1); теорема 13.25 описывает бесконечный класс совершенных кодов в метрике Ли с малой блоковой длиной (п = 2) и произвольной корректирующей способностью.

Многие из кодов, указанных в теореме 13.21, представляют собой множество многочленов, кратных порождающему многочлену g (х) mod (а;« - ), где I € GF (q). Если (С„ С, . . ., C„ i) - кодовое слово такого кода, то его констациклический сдвиг (C„ i, Со, С, . . ., С„ 2) также принадлежит коду. Поэтому мы будем такие коды называть констациклическими. Класс констацикличе-ских кодов содержит в качестве собственных подклассов класс циклических кодов и класс негацикличееких кодов.

13.21. Т е О р е м а. J5 метрике Хэмминга совершенный систематический ) код с исправлением одной ошибки и блоковой длиной п над алфавитом из q букв существует тогда и только тогда, когда

(13.22)

для некоторого числа г.

Если q - степень простого числа и п удовлетворяет равенству (13.22), то в метрике Хэ.чминга существует совершенный линейный констациклический код ), исправляющий одну ошибку. Циклический совершенный код, исправляющий одну ошибку в метрике Хэмминга, существует тогда и только тогда, когда имеет место равенство (13.22) и (ге, g - 1) = 1.

Если q > 2, то совершенный код, исправляющий одну ошибку в метрике Ли, существует только тогда, когда для некоторого числа г

(13.23) « = --

Если q - любое нечетное число и блоковая длина п удовлетворяет равенству (13.23), то в метрике Ли существует совершенный код, исправляющий одну ошибку, линейный над кольцом классов вычетов по mod q. Если q простое, то этот код является негациклическим.

Доказательство. Так как в метрике Хэмминга Fi" = = 1 + (g - 1) re, то число кодовых слов совершенного кода, исправляющего одну ошибку, равно

1 + (д 1)„ •

Так как Rn - целое число, то число 1 (д - \) п - степень q ш п удовлетворяет равенству (13.22).

В метрике Ли Fj" = 1 + 2ге и, значит, число кодовых слов совершенного кода, исправляющего одну ошибку, равно

1 + 2л •

Так как Rn - целое число, то число 1 -j- 2ге - степень числа q и. п удовлетворяет уравнению (13.23). Существование совершенных нега-циклических кодов с блоковой длиной п, исправляющих одну ошибку, для нечетного простого q гарантируется теоремой 9.34.

) Код называется систематическим, если его символы разделяются на информационные и проверочные. Над конечными полями все линейные и некоторые нелинейные коды [см. (13.83)] являются систематическими. Если q простое, то длина несистематического совершенного кода также удовлетворяет условиям (13.22) или (13.23).

2) Эти коды были построены Голеем [1949, 1954, 1958], Зарембой [1952] и Коком [1959].