ВЕРОЯТНОСТЬ ОШИБКИ ДЛЯ ОПТИМАЛЬНЫХ кодов В ГАУССОВСКОМ КАНАЛЕ

Краткое содержание

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

1. Введение

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

Кодовое слово длины для такого канала — это последовательность из действительных чисел Оно может быть геометрически представлено точкой -мерного эвклидова пространства. Эффект воздействия шума при этом будет состоять в перемещении этой точки в близлежащую в соответствии со сферическим гауссовским распределением.

Блоковый код длины с М словами есть преобразование целых чисел во множество М кодовых слов (все они не обязательно разные). Геометрически блоковый код представляется набором М (или менее) точек с соотнесенными им целыми числами. Его можно рассматривать как способ передачи целых чисел от 1 до М на приемный конец (путем посылки соответствующего кодового слова). Декодирующая система для такого кода есть разбиение

-мерного пространства на, М подмножеств, соответствующих целым числам от 1 до М. Это есть способ решения на приемном конце, какое целое число было передано. Если принятый сигнал попал в подмножество то принимается, что передаваемое сообщение соответствует целому числу

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

а которой есть вероятность того, что при передаче кодового слова со; оно декодируется некоторым целым числом, отличным от Очевидно, есть полная вероятность, определяемая гауссовским распределением с центром в в области, дополнительной к

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

Нас интересует задача отыскания хорошего кода, т. е. такого расположения М точек, при котором минимизируется вероятность ошибки Ре. Если не накладывать ограничений на кодовые слова, то очевидно, что вероятность ошибки может быть сколь угодно малой при любых и если разместить кодовыеслова в -мерном пространстве на достаточно большом расстоянии друг от друга. Однако в практических задачах на выбор кодовых слов накладываются обычно ограничения, не позволяющие использовать этот метод. Интересным случаем, рассматривавшимся прежде, является тот, когда некоторым образом ограничена средняя мощность кодовых слов, т. е. расстояния точек от начала координат не должны быть слишком большими.

Можно определить три различных возможных ограничения этого типа:

1. Все кодовые слова имеют точно одну и ту же мощность Р, или одно и то же расстояние от начала координат. Таким образом, мы требуем, чтобы в качестве кодовых слов были выбраны точки, расположенные на поверхности сферы радиуса

2. Все кодовые слова имеют мощность Р или меньшую. В этом случае все кодовые слова должны находиться внутри или на поверхности сферы радиуса .

3. Средняя мощность всех кодовых слов равна Р или меньше. В этом случае отдельные кодовые слова могут иметь квадрат расстояния от начала, больший чем , но совокупность квадратов расстояния не может превосходить пР.

Эти три случая, как будет показано, приводят к очень сходным результатам. Первое условие наиболее просто и приводит к несколько более отчетливым выводам. Сначала будет проанализирован именно этот случай, затем полученные результаты будут использованы для двух других. Поэтому до тех пор, пока не оговаривается обратное, принимается, что все кодовые слова расположены на поверхности сферы радиуса .

Первая задача состоит в том, чтобы по возможности точно оценить вероятность ошибки для наилучшего кода длины содержащего М слов, каждое мощностью Р, которые искажаются шумом с дисперсией Эту минимальную или оптимальную вероятность ошибки обозначим через Ясно, что для фиксированных М и будет являться функцией лишь величины при изменении масштаба геометрического представления. Получим нижнюю и верхнюю границы нескольких разных типов. В важной области значений эти границы достаточно близки друг к другу и дают хорошие оценки Дадим некоторые вычисленные значения и кривые; найденные границы служат для определения аналогичных границ для второго и третьего типов условий, налагаемых на кодовые слова.

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

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

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

где — некоторая функция (а также рассматриваемого как фиксированный параметр). В выражении является членом меньшего порядка, чем так что при он становится малым по сравнению с

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

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

Относительно надежности Е нужно заметить, что в вышеописанном случае знание в выражении (1) не дает возможности точно определить вероятность ошибки даже при больших член может обусловить появление большого и растущего множителя. С другой стороны, если задана вероятность ошибки и значение то необходимую длину кода можно точно

определить при большом так как асимптотически равно величине . Эта обратная задача, возможно, практически наиболее обычна: задан допустимый уровень вероятности ошибки, спрашивается, какова должна быть длина кода?

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

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

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