Глава 9. ИОДИРОВАНИЕ ДЛЯ ДИСНРЕТНЫХ ПОСТОЯННЫХ НАНАЛОВ

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

К. Шеннону мы обязаны открытием того, что вероятность ошибки может быть сделана как угодно малой для любой скорости передачи, меньшей пропускной способности. Его основные теоремы, содержащие этот результат, опубликованные в 1948 г. [1, 2], относятся к ограниченному классу дискретных каналов с памятью, включающему дискретные постоянные каналы, и к непрерывным каналам с аддитивным белым гауссовским шумом и ограниченной средней мощностью входного сигнала. Первое доказательство того, что вероятность ошибки может экспоненциально убывать с ростом числа двоичных символов, представляющих каждое сообщение, было опубликовано Файнстейном в 1954 г. [3]. С тех пор характер неограниченного убывания вероятности ошибки для различных классов каналов исследовался в ряде статей Блекуэлла с соавторами, Элайеса, Файнстейна, Хинчина, Шеннона, Вольфовица и др. Особенно важными для техники являются границы, полученные Шенноном для дискретных каналов [4], для двухсторонних дискретных постоянных каналов [5] и постоянных гауссовских каналов с дискретным временем [6]. Важным является также недавно полученное Ю. Келли [7] доказательство того, что для гауссовских каналов с дискретным временем не происходит никакого заметного ухудшения результатов от использования класса аддитивных кодов, в некотором смысле аналогичных кодам, рассмотренным в разд. 7.4, в которых сигналы, представляющие сообщения, могут быть образованы как суммы

сигналов генераторов, где число двоичных символов, образующих каждое сообщение.

Большинство результатов этой главы было совсем недавно разработано автором и публикуется здесь впервые. Однако границы вероятности ошибок, приведенные в разд. 9.2 и 9.3, впервые были получены К. Шенноном другим способом в 1957 г. Эта часть работы Шеннона, включающей также другие интересные результаты, еще не опубликована.

9.1. Дискретные постоянные каналы

Дискретный постоянный канал задается его входным пространством X, состоящим из К различных букв его выходным пространством У, состоящим из различных букв и фиксированным условным распределением вероятностей связывающим буквы на входе и выходе. Вычисление пропускной способности С таких каналов рассмотрено в разд. 5.5. Там мы видели, что средняя взаимная информация между буквами на входе и выходе достигает своего максимального значения С, когда распределение вероятностей на входе таково, что

Эта система К уравнений совместно с системой уравнений

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

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

Кроме того, Шеннон [8] показал, что, кодируя сообщения в последовательности как смежных, так и несмежных букв, возможно во многих случаях вести передачу с нулевой вероятностью ошибки и со скоростью, большей чем Наименьшая верхняя граница скорости передачи, для которой можно получить вероятность ошибки, равную нулю, известна как «пропускная способность канала при нулевой ошибке». К сожалению, не найдено общего метода вычисления пропускной способности канала с нулевой ошибкой. Однако во многих случаях она может быть хорошо оценена с помощью верхней и нижней границ, выведенных Шенноном [8]. Простой пример канала, указанный Шенноном, для которого наибольшее число несмежных букв равно двум, а пропускная способность с нулевой ошибкой больше одной двоичной единицы, приведен на рис. 9.1. Легко проверить, что, в то время как в этом примере имеется несколько пар несмежных букв, не существует троек несмежных букв. С другой стороны, пять последовательностей из двух букв

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

Рис. 9.1. Канал с положительной пропускной способностью при нулевой ошибке.