свободная длина. Конечно, если несколькими способами определять и кодовое расстояние, и длину кода, то, комбинируя эти определения, можно получить различные границы.

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

Пусть объем алфавита q фиксирован; определим

й (п, R) = max d* (),

где максимум берется по всем сверточным кодам с длиной блока п и скоростью R, а d* (W) означает минимальное расстояние для кода . Функция Л {п, R) определяет наибольшее минимальное расстояние по всем сверточным кодам над GF (<?) со скоростью R и длиной блока п. Обозначим, далее,

d (R) = lim [d (n, R)/n]

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

Аналогичные определения можно дать и для свободного расстояния. В зависимости от того, что рассматривается: отношение свободного расстояния к длине блока или к свободной длине, можно получить различные функции. Определим

doc (п, R) = max doc С),

где максимум берется по всем сверточным кодам с длиной блока п и скоростью R, а dco {) означает свободное расстояние кода . Функция doo (п, R) определяет наибольшее свободное расстояние по всем сверточным кодам над GF (q) со скоростью R и длиной блока п.

Обозначим, далее,

doo (R) = lim [doo (n, R)/n]

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

) Это утверждение неточно. - Прим. ред.

Так как обычно doo С) больше d* (), можно ожидать, что и doo (R) больше d{R). В некоторых случаях полезно использовать также следующее альтернативное определение. Пусть Поо (п, R) означает свободную длину кода, на котором достигается doo (п, R). Свободная длина более тесно связана со свободным расстоянием и сложностью декодера, чем длина кода. Обозначим

doo (R) = lim [doo (n, R)lnoo (n, R) ]

n-foo

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

Теорема f4.5.1 (граница Элайса). Для двоичного сверточного кода со скоростью R функция d (R) удовлетворяет условию

d (R) < 2р (1 - р)

при любом р, таком, что 1 - Яь (р) > R.

Доказательство. Усечением сверточного кода с длиной блока п = тПд, где т произвольно, получим блоковый код длины п. Скорость этого блокового кода также равна R, так как каждые информационныхсимволов кодируются По симв)лами кодового слова. Минимальноерасстояние этого усеченного~кода не больше минимального расстояния наилучшего блокового кода. Следовательно, любая верхняя граница минимального расстояния блокового кода является также верхней границей минимального расстояния сверточного кода ). Такой границей является граница Элайса. П

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

Прежде чем доказывать границу Гилберта, необходимо дока-зать лемму. Лемма касается"начального сегмента кодового слова

Поэтому ioPo = Ро; это равенство задает - о ограничений на 0 ih - Ю элементов Ро; отсюда следует, что {ко - 1) («о - К) элементов могут быть выбраны независимо. Следовательно, при фиксированном первом кадре кодового слова матрица Ро может быть выбрана :- q {ко - 1) («о - о) способами. Аналогично oPi = Pi - оРо и матрица Pi может быть выбрана q (ko - - 1) {По - о) способами. Продолжая процесс, убеждаемся, что каждая матрица Pj может быть выбрана столькими же способами, и поэтому существует [q<.o-) («о-о) ]in+i сверточных кодов, у которых начальное кодовое слово фиксировано. □

Теорема 14.5.3. Пусть при заданной скорости R = кд/по и длине блока п = (/л -f 1) «о величина р удовлетворяет условию

l)i<q

Тогда существует хотя бы один систематический сверточный код над GF {q), минимальное расстояние d* которого больше р.

Доказательство. Минимальное расстояние сверточного кода больше р, если код не содержит начального сегмента кодового слова длины п и веса не больше р, у которого некоторый информационный символ первого кадра отличен от нуля. В множестве

сверточного кода, т. е. сегмента кодового слова, состоящего из первых п символов.

Лемма 14.5.2. Начальный сегмент кодового слова, начинающийся с ненулевого кадра, входит точно в gC+i) («о-л») различных систематических сверточных (пд, k-кодсв с длиной слова (т + 1) ко-

Доказательство. Так как код систематический, задание первых п символов кодового слова определяет первые (т -f 1) kg информационных символов. Первые (т + 1) символов кодового слова связаны с первыми (т + 1) информационными символами через порождающую матрицу. Эта матрица описывается т 4- 1 матрицами Pq, Р, каждая из которых имеет размер ко x [По ~ ко). Проверочные кадры (Ро, Pi, р), число которых равно m -f- 1, определяются следующим матричным равенством;