6.2. Вероятность ошибки и ненадежность

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

где

есть вероятность ошибки, когда принадлежит подмножеству Мы хотим установить связь вероятности ошибки с ненадежностью для канала с входным пространством и выходным пространством (см. рис. 6.1). Для этой цели удобно определить энтропию

выбора из двух исходов: ошибка и отсутствие ошибки, и соответствующую условную энтропию V

при заданной точке пространства

Теорема. Ненадежность удовлетворяет неравенству

Доказательство. Ненадежность, по определению, равна

где

— ненадежность в предположении, что точка выходного пространства принадлежит подмножеству Правую часть

последнего равенства с помощью выражения (6.13) можно переписать в следующем виде:

Сумма в правой части равенства (6.19) (со знаком минус) есть энтропия ансамбля, содержащего точку. И как таковая она не может превзойти значение Отсюда следует, что

Усредняя это выражение по ансамблю и используя выражение (6.15), получаем

Доказываемое соотношение (6.16) немедленно следует из неравенства (6.21) в силу того, что

Ч. Т. Д.

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

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

Теорема. Рассмотрим какой-либо метод декодирования сообщений для степени дискретного постоянного канала и обозначим через соответствующее разбиение выходного пространства V на непересекающиеся подмножества сопоставленные точкам пространства сообщений. Если энтропия ансамбля сообщений превосходит пропускную способность степени канала), то вероятность неправильного декодирования сообщений имеет положительную нижнюю границу. Точнее,

где нижняя граница удовлетворяет соотношению

Доказательство. Из выражения (6.8) и определения пропускной способности канала имеем

где С — пропускная способность канала на событие. Тогда из соотношения (6.16) следует, что

Положим

Эта функция от z совпадает с левой частью неравенства (6.26) для она положительна для и равна нулю для Кроме того,

Отсюда следует, что

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

Эта теорема наиболее просто интерпретируется, когда ансамбль сообщений состоит из последовательностей статистически независимых равновероятных двоичных символов; в этом случае

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

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

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

Теоремы этого раздела можно легко обобщить на каналы с дискретным временем и с непрерывными входными и выходными пространствами, а также на каналы с непрерывным временем и аддитивным стационарным шумом.