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

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

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

Ситуация напоминает график, изображенный на рис. 13.5. С первого же взгляда можно легко заметить, что минимум функции равен примерно 0,10; однако при определении точки, в которой достигается этот минимум, возникают существенные трудности. Легко определить, что но невозможно с большой точностью указать или

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

Рис. 13.5. Графический аналог вероятности ошибки по ансамблю кодов.

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

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

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

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

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

Пусть — вероятность ошибки наилучшего кода с блоковой длиной кодовыми словами. Функция — частный случай функции представляющей собой вероятность ошибки наилучшего кода с блоковой длиной кодовыми словами при декодировании «списком» длины При таком декодировании декодер на базе полученного слова составляет список всех возможных переданных кодовых слов в порядке убывания их апостериорных вероятностей. Если переданное слово появится в любом месте этого списка, то декодер правильно примет его. Ошибка декодирования произойдет только тогда, когда фактически переданное слово не содержится в списке. Декодирование списком для двоичного симметричного канала впервые рассматривалось Элайесом [1957].

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

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

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

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

Файнстейн [1954, 1958] показал, что если то

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

К сожалению, равенство (13.81) не может служить строгим определением так как до сих пор не доказано существование этого предела! Тем не менее мы будем использовать соотношение (13.81) в качестве эвристического определения, мысленно подразумевая, что все верхние границы для по существу являются верхними границами типа а все нижние границы для нижними границами типа

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

Функция вычислена для всех скоростей только для малого числа патологических каналов. Для большинства каналов известные точные границы для различны для всех из диапазона хотя и совпадают. определяется как При очень малых скоростях вероятность ошибки связана с числами . В противоположность пределу из формулы (13.81) об этом пределе известно, что он существует. Числа Ем точно не известны, за исключением нескольких случаев простых каналов, включающих двоичный симметричный канал. Тем не менее известно простое общее выражение для предела Ем, а именно Однако единственное известное доказательство этого факта очень трудоемко.

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

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

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

Функция неявно зависит от канала. Пусть есть для двоичного симметричного канала с вероятностью перехода символов друг в друга. Тогда

Отсюда видно, что асимптотические границы, изображенные на рис. 13.2, в действительности дают функции надежности. Действительно, если стремится к нулю, то превращается в границу Хэмминга для в точке с нулевой скоростью превращается в границу Плоткина для граница Элайеса для становится границей Элайеса для нижняя граница для — полученная методом «выбрасывания», становится границей Гилберта для Часто выдвигается гипотеза, что функция в действительности лежит на границе Гилберта. Это эквивалентно предположению о том, что совпадает с границей для двоичного симметричного канала, полученной методом выбрасывания. Доказательства обоих этих предположений, высказанных несколько лет назад, представляются очень трудными.

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

экспоненциально малую вероятность ошибки для всех скоростей, лежащих ниже пропускной способности, несмотря на то, что Шеннон [1956] показал, что бесшумная мгновенная обратная связь не увеличивает пропускной способности любого прямого дискретного канала без памяти.

Лучшие известные асимптотические границы для границы Гилберта и Элайеса — применимы к линейным и к нелинейным кодам.

Рис. 13.6. Асимптотика корректирующей способности для двоичного симметричного канала с обратной связью (сплошная линия).

Предполагается, что нелинейные коды асимптотически не лучше линейных кодов, однако до сих пор это не доказано. Для некоторых конечных случаев Грин [1966], Джулин [1965], Нейдлер [1962 а, b], Нордстром и Робинсон [1967] построили нелинейные коды, которые лучше любых линейных. Особый интерес представляет нелинейный «квадратичный» код Нордстрома над с блоковой длиной 15, восемью информационными символами и семью проверочными символами Первый проверочный символ определяется соотношением

Остальные координаты вычисляются путем подстановки в (13.83) вместо .

Препарата [1968] и Редди [1968] показали, что кодовое расстояние этого кода равно 5. Особый интерес этот код представляет потому, что Джонсон [1962] показал, что ни один двоичный код с не может иметь более чем 28 кодовых слов, а Вагнер [1965] показал, что лучший линейный код с содержит только 27 кодовых слов. Некоторые соображения подсказывают, что соотношения типа (13.83) позволяют строить другие хорошие нелинейные коды, однако никакие конструкции общего типа до сих пор пока не найдены.

Большое число работ посвящено определению функции максимального минимального веса для множества произвольных линейных двоичных кодов с блоковой длиной и скоростью Для некоторых малых значений пик предложено много способов вычисления Нижняя граница для может быть получена либо путем подбора специальных хороших кодов, либо с помощью модификации Варшамова [1957] или Сакса [1958] для границы Гилберта. Верхняя граница для исследовалась с помощью большого числа разнообразных методов. Для малых к граница сферической упаковки и ее «квазисовершенный вариант» дают точные результаты. Для малых к Мак-Дональд [1960] и Грисмер [1960] получили точные границы с помощью модификации рассуждений Плоткина [1960]. Соломон и Стиффлер [1965] предложили класс кодов с малыми скоростями, достигающих границы Грайсмера. Краткое описание кодов Соломона — Стиффлера дается в § 14.2.

Для многих и к точная верхняя граница для получена с помощью методики Джонсона [1962, 1963]. В ряде случаев оказалась полезной граница Вакса [1959]. Некоторые результаты о возможных локальных изменениях при малых изменениях и к были получены Калаби и Мирваанесом [1964]. Они также построили таблицу известных значений Некоторые элементы в этой таблице были найдены Вагнером [1965].

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