одному /, а вклады остальных ребер не содержат /. Поэтому, как и ранее, получим

T(D L Л-

= DL4 + DL (1 + L) /2 + DL5 (l A-Lf P + ... ... 4- Z)s+L3+ (1 -f L)*

Мы видим, что путь веса 5 имеет длину 3 и соответствует информационной последовательности с одним единичным символом. Вес 6 имеют два пути, каждому из которых соответствует информационная последовательность с двумя единицами; длина одного из этих путей равна 5, а другого 6.

Таким образом мы полностью определим свойства сверточного кода. Эти свойства полезно знать при сравнении структур двух сверточных кодов; кроме того, знание дистанционной структуры кода необходимо при оценке вероятности ошибки кода, используемого в конкретном канале.

14.4. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ БЛОКОВЫХ КОДОВ

О контролирующем ошибки коде с длиной п и скоростью R судят по его минимальному расстоянию d*. Если имеются два кода с одинаковыми п и R, то в общем случае следует предпочесть код с большим d*. Для данрюго кода хотелось бы знать, является ли его d* максимально большим среди минимальных расстояний кодов с данными п и R. Вообще говоря, не считая случаев, когда п довольно мало, ответ на этот вопрос неизвестен, и можно указать лишь некоторые грубые границы для d*. В частности, мы уже встречались с границей Синглтона, которая при п, много больших q, становится весьма грубой.

Мы проведем лишь асимптотический анализ. При фиксированном объеме алфавита q введем обозначение

d{n, R) = maxd*{e),

где максимум берется по всем кодам с длиной п и скоростью R, а d* {) равно

d* {) = min d (х, у)

и представляет собой минимальное расстояние кода ё. Функция d (п, R) определяет наибольшее минимальрюе расстояние среди всех кодов над GF (q) со скоростью R и длиной п. Если не считать

Пг(«г!)

; еПН (р)

и сделать это как можно короче. Этому условию удовлетворяет доказательство, использующее формулу Стирлинга

) Эта граница известна также под названием границы Варшамова-Гилберта. - Прим. ред.

области малых значений п, функция d (п, R) неизвестна. Определим, далее,

diR) = Umld{n, R)/n]

n-юо

при условии, что этот предел существует. Если функция d (R) известна, то мы можем сказать, что при достаточно больших п наилучший блоковый код со скоростью R имеет минимальное расстояние d*, приблизительно равное nd{R). Поэтому функция d{R), если она известна, дает нам критерий, по которому можно судить о существующих классах контролирующих ошибки кодов. Кроме того, знание d{R) может дать нам некоторый ключ к изучению структуры хороших кодов и указать путь их построения.

Хотя знать функции d{n, R) и d{R) было бы весьма желательно, в настоящее время они не известны. Все что мы знаем - это их нижние и верхние границы; некоторые из них выводятся в данном параграфе. Остановимся лишь на тех границах, которые можно получить, не прилагая больших усилий; в частности, мы получим границы, известные как нижняя граница Гилберта ) и верхняя граница Элайса.

Чтобы получить эти границы, воспользуемся методом исчерпывания и оценим композиции типичных кодовых слов. Композицией 9-ичного кодового слова назовем д-мерный вектор (по, figj), 2;П; = п, 1-я компонента которого определяет, сколько раз в кодовом слове встречается 1-я буква. Относительной частотой <7-ичного кодового слова называется <?-мерный вектор (ро, ••-•••.Pq-i). где pi = n;/n. Выразим границы минимального расстояния через полиномиальные коэффициенты п!/П;П(!, где П(П;! означает произведение П/Гё (fi;!). Функция энтропии Н (р) определяется как

Н(р) = - TiPi log Pi.

Мы хотим доказать асимптотически справедливое при больших п равенство

, n! , 1Л 2пя(п/е)"[1 + 1/(12п-1)]

= log Пгп"г , , 1Л2[1 + 1/(12п-1)]

Замена = npi доказывает правую часть неравенства. Левая часть доказывается тем же способом. □

Теперь можно приступить к доказательству границы Гилберта. Мы проведем его, подсчитав число кодовых слов внутри сферы с центром в произвольной точке пространства (не обязательно представляющей кодовое слово) и затем усреднив это число. Число точек внутри сферы радиуса d назовем объемом сферы; оно равно

Теорема 14.4.2. Пусть V - число точек внутри сферы радиуса d с центром в некоторой точке векторного пространства GF (д). Для заданного кода Ф мощности д среднее число кодовых слов внутри сферы радиуса d с центром в произвольной точке пространства равно

f = giV/g".

Доказательство. Опишем сферы радиуса d вокруг каждой точки пространства. Подсчитаем число кодовых слов внутри каждой сферы и затем просуммируем по всем сферам. Так как на расстоянии, не превышающем d, вокруг кодового слова находится V точек, это слово лежит внутри V таких сфер. Поэтому сумма числа кодовых слов внутри всех сфер равна gV, и, следовательно, в среднем на сферу приходится gVlq кодовых слов. □

Теорема 14.4.1.

gn [Н(р)-о (1)] 1-gn [Н (р) -о, (1)]

Пг {nil)

01 (1) = i (9 - 1) log (2пп) + -LJlogp,-±-log[l+ ,

02il) = {q-l)log(2nn) + 2 logpz +

+ ~iog{l+j).

Доказательство.