Тогда каждый линейный код с расстоянием d, скоростью R и блоковой длиной п над GF (q) является собственным подкодом расширенного линейного кода с тем же минимальным расстоянием.

Доказательство. Любой код со скоростью R имеет; "(i-R) лидеров смежных классов, а все пространство содержит д" точек и среди них только F"\ слов веса < d. Следовательно, если в метрике Хэмминга Fi <g"(-к) о имеется лидер смежного класса с весом > d. Вес всех скалярных (ненулевых) кратных слов этого смежного класса также > d. Согласно лем- ме 13.72, исходный линейный код можно расширить, превратив этот смежный класс и его скалярные кратные в кодовые слова. <

В метрике Ли смежный класс с лидером веса > d может содер-! жать слова, вес скалярных кратных которых будет меньше, чем d,4 так что расширение кода надо производить определенным образом.f Множество g"(i-R) - 1 собственных смежных классов (исключается! сам код) можно разбить на подмножества, каждое из которых содер-! жит g - 1 ненулевых скалярных кратных каждого из элементов.] Элемент наименьшего веса в данном подмножестве можно выбрать! в качестве лидера. Если g нечетно, aw - лидер, то (-w) также может" быть выбран в качестве лидера; в этом случае подмножество содержит два лидера. Если число лидеров превосходит число ненулевыГ слов с весом Ли < d - 1, то существует лидер веса > d. Элемент! подмножества, содержащего этот лидер, могут быть выбраны в каче стве кодовых слов расширенного кода, щ

Для конечных значений п, d ж R Варшамов [1957] и Сакс [1958 доказали несколько более строгие варианты теорем 13.71 и 13.73.

Если d - минимальное расстояние исходного кода, то шары радиуса d -1, описанные вокруг кодовых точек, будут мало пересекаться, и учет этих пересечений позволяет улучшить границу. Однако ни одно из предложенных до сих пор улучшений не изменяет асимптотического поведения границы. Из теорем 13.71, 13.73, 13.75 и 13.18 вытекает

13.74. Теорема. Над GF (д) ) существуют линейные коды с произвольно большой блоковой длиной п, скоростью R и минимальным расстоянием d, которые удовлетворяют соотношению

4>б(й).

Асимптотическая форма границы Гилберта для двоичных кодов изображена на рис. 13.2.

Не известно, существуют ли циклические коды с произвольно большой длиной, удовлетворяющие соотношению теоремы 13.74.

С практической точки зрения теорема 13.73 не дает легкого способа построения хороших кодов. Хотя для данного линейного кода может быть известно, что существуют смежные классы с большим, чем кодовое расстояние, весом, однако какие-либо легкие способы отыскания этих смежных классов не известны. Числа же кодовых слов и смежных классов при больших блоковых длинах и умеренных скоростях столь велики, что полный перебор невозможен.

13.8. Асимптотические границы для вероятности ошибки и конечные частные случаи

Хотя минимальное расстояние характеризует корректирующие возможности кода, оно не раскрывает их полностью. Большинство кодов с расстоянием d позволяют исправлять не только все ошибки кратности d/2, но также и многие ошибки более высокой кратности. Часто оказывается возможным исправлять столь много ошибок кратности, большей чем d/2, что вероятности отказа от декодирования и ошибки декодирования существенно меньше, чем вероятность того, что в канале произойдет более d/2 ошибок.

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

) См. замечания, следующие за доказательством следствия 13.26.

имеет вид s (v + g) или sg, где s - скаляр. Так как sg £ G, то слово принадлежит расширенному коду тогда и только тогда, когда оно имеет вид sv + g, g 6 G. Отсюда ясно, что расширенный код - также линейный. Он содержит gi+"« слов, соответствующих q возможным выборам S и д" возможным выборам g в выражении sv + g. щ

13.73. Теорема. Пусть либо q - степень простого числа и в метрике Хэмминга

либо д -степень нечетного простого числа и в метрике Ли т/(«) л 1 W

Кй 1<И---1

либо q -степень числа 2 и в жтрике Ли

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

Ситуация напоминает график, изображенный на рис. 13.5. С первого же взгляда можно легко заметить, что минимум функции / (х) равен примерно 0,10; однако при определении точки, в которой достигается этот минимум, возникают существенные трудности. Легко определить, что / (О, 4) = 0,2, но невозможно с большой точностью указать / (0,5) или / (0,6).

Хотя аналогия между вероятностью ошибки для ансамбля всех кодов и функцией/(ж), изображенной на рис. 13.5, не очень глубока, представляется полезным подчеркнуть следующее:

/(X)

0,1 -

I I I I u

l I 1

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

P И с. 13,5. Графический аналог вероятности ошибки по ансамблю кодов.

1. Ансамбль всех кодов с заданными скоростью и блоковой длиной содержит много кодов, вероятность ошибки для которых близка к минимуму.

2. Очень трудно вычислить вероятность ошибки для любого кода, за исключением нескольких случаев несомненно плохих кодов.

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

Таким образом, о вероятности ошибки для «наилучшего» кода известно достаточно много, несмотря на то, что о самом наилучшем

13.8. Асимптотические границы для еероятности ошибки

коде не известно ничего. Большинство сведений о вероятности ошибки для наилучшего кода получено с помощью неконструктивных вероятностных методов, не являющихся ни алгебраическими, ни комбинаторными. Зачастую они запутанны и длинны, так что мы дадим только краткую аннотацию наиболее важных результатов. Интересующийся читатель может найти доказательства большинства этих результатов в статьях Шеннона, Галлагера и Берлекэмпа [1967] и приведенной в них литературе или в выходящей книге Галлагера [1968] и в книге Джелинека [1968].

Пусть Pg (N, М, 1) - вероятность ошибки наилучшего кода с блоковой длиной Ли М кодовыми словами. Функция Pg (N, М, 1) - частный случай функции Ре {N, М, L), представляющей собой вероятность ошибки наилучшего кода с блоковой длиной N ж М кодовыми словами при декодировании «списком» длины L. При таком декодировании декодер на базе полученного слова составляет список всех возможных переданных кодовых слов в порядке убывания их апостериорных вероятностей. Если переданное слово появится в любом месте этого списка, то декодер правильно примет его. Ошибка декодирования произойдет только тогда, когда фактически переданное слово не содержится в списке. Декодирование списком для двоичного симметричного канала впервые рассматривалось Элайе-сом [1957].

Скорость передачи (в натуральных единицах) для кода с М кодовыми словами, блоковой длиной Л и списком длины L определяется равенством

Наибольший интерес вызывает поведение функции Р {N, М, L), когда R фиксировано, а Л принимает произвольно большие значения. В 1949 г. Шеннон доказал свою классическую теорему кодирования, согласно которой для любого дискретного канала без памяти (так же как и для большинства других каналов) существует пропускная способность С, зависящая только от статистики шума в канале и не зависящая от кода. Эта пропускная способность обладает тем важным свойством, что если Л << С, то

Иш Pg{N, [expRN], 1)=0,

iV-юо

где [ехр RN] -- наименьшее целое число, не превосходящее ехр RN. Шеннон [1948, 1949] показал также, что если i? > С, то

lim Pe{N, [expRN], 1)>0.

JV-VOO

Вольфовиц [1961] доказал, что при R> С

lim Pe{N, [expRN], 1) = 1.

(13.81)

E{R, L) = lim

N-l-CO

к сожалению, равенство (13.81) не может служить строгим определением Е {R, L), так как до сих пор не доказано существование этого предела! Тем не менее мы будем использовать соотношение (13.81) в качестве эвристического определения, мысленно подразумевая, что все верхние границы для Е {R, L) по существу являются верхними границами типа lim sup, а все нижние границы для Е {R, L) - нижними границами типа lim inf.

Функция Е {R, оо) = lim Е {R, L) известна точно для всех скоро-

стей из диапазона i?oo <iR <iC, где i?oo - скорость, ниже которой Е {R, оо) = оо. Функция Е {R, оо) называется границей сферической упаковки и получается как верхняя граница для Е {R, L) при конечных L. Эта граница достигается при достаточно больших R. В частности, существует последовательность критических скоростей О < i?oo <. . . <i?i <i?o = С, такая, что Е {R, L) = Е {R, оо) для всех R из интервала Rx <;i? < С. При скоростях, лежащих в интервале i?i <И < С, функция Е (R, L) не зависит от L. Однако при достаточно малых скоростях функция Е {R, L) уже зависит otL.

Функция Е {R, 1) вычислена для всех скоростей только для малого числа патологических каналов. Для большинства каналов известные точные границы для Е {R, 1) различны для всех R из диапазона О <i?<i?i, хотя Е (Ri, I) ж Е (О, 1) совпадают. (Е (О, 1) определяется как lim Е {R, 1).) При очень малых скоростях вероятность ошибки

Д-1.0

{N, М, 1) . В противопо-

связапа с числами E]j = lim

ложность пределу из формулы (13.81) об этом пределе известно, что он существует. Числа Ем точно не известны, за исключением нескольких случаев простых каналов, включающих двоичный симметричный канал. Тем не менее известно простое общее выражение для предела £00 = lim Ем, а именно Еоо = Е (О, 1). Однако единственное извест-

М->оо

ное доказательство этого факта очень трудоемко.

Все данные говорят за то, что функция Е {R, L) должна быть выпуклой функцией от R, хотя это пока и нё доказано. Лучшие из известных верхних и нижних границ для Е {R, L) являются выпуклыми, и функция Е {R, оо) выпукла. Известно также, что если / (i?, L) - верхняя граница для Е {R, L), то ее выпуклая оболочка и Е {R, оо) - также верхние границы для Е {R, L).

Для выяснения связи между асимптотическими границами для вероятности ошибки и асимптотическими границами для минимального расстояния (рис. 13.2) введем функцию е {R), эвристически определив ее равенством

(13.82) e(R)=\im-!:i.

Здесь d (п, М) - минимальное расстояние двоичного кода, обладающего максимальным минимальным расстоянием среди всех двоичных кодов с блоковой длиной п ж М кодовыми словами. Как и раньше, в зависимости от ситуации предел в (13.82) интерпретируем как lim sup или lim inf.

Функция Е {R, L) неявно зависит от канала. Пусть Е {R, L; Р) есть Е (R, L) для двоичного симметричного канала с вероятностью Р перехода символов друг в друга. Тогда

,. E{R, 1; Р)

ЛпР -(Д)-

Р-1.0

Отсюда видно, что асимптотические границы, изображенные на рис. 13.2, в действительности дают функции надежности. Действительно, если Р стремится к нулю, то -Е {R, оо; Р)/1п Р превращается в границу Хэмминга для е (R); в точке с нулевой скоростью -Е (0; 1, Р)1\п Р превращается в границу, Плоткина для е (R); граница Элайеса для -Е (R; 1; Р)/\пР становится границей Элайеса для е (R); нижняя граница для -Е {R; 1; Р)/1п Р, полученная методом «выбрасывания», становится границей Гилберта для е (R). Часто выдвигается гипотеза, что функция е (R) в действительности лежит на границе Гилберта. Это эквивалентно предположению о том, что Е {R, 1) совпадает с границей для двоичного симметричного канала, полученной методом выбрасывания. Доказательства обоих этих предположений, высказанных несколько лет назад, представляются очень трудными.

Хотя функция е (R) известна только в пределах границ, указанных на рис. 13.2, соответствующая функция для случая канала с бесшумной мгновенной обратной связью определена точно. Эта функция изображена на рис. 13.6, а детали ее поведения описаны Берлекэмном [1964 а; 1968 Ь]. Так как функция, изображенная на рис. 13.6, превосходит границу Элайеса на рис. 13.2, то использование бесшумной обратной связи в двоичных симметричных каналах с относительно невысоким шумом позволяет получить экспоненциаль-

Файнстейн [1954, 1958] показал, что если R <;С, то Ре (N, [ехр RN], 1) <ехр { - NEr{R)},

где Er{R) - положительная функция от R, стремящаяся к О, когда R стремится к С. Граница Файнстейна была затем уточнена и улучшена Фано [1961], Галлагером [1965], Шенноном, Галлагером и Берлекэмном [1967] и другими. Существенный интерес представляет функция надежности Е {R, L), которую нам удобно определить равенством

In Pe{N, [LexpRN], L)}.