§ 3.4. Общая обратная теорема кодирования для дискретных каналов

Теперь мы используем неравенство Фано для доказательства обратной теоремы кодирования для широкого класса дискретных каналов.

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

где

Обозначим через С максимальное значение средней взаимной информации в единицу времени между входом и выходом канала

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

Теорема 3.4.1 (обратная теорема кодирования для дискретных каналов). Пусть С — информационная емкость дискретного канала и где произвольное положительное число. Тогда существует положительное число , зависящее от такое, что для всякого кода

Доказательство. Зафиксируем некоторое и рассмотрим код кодовыми словами Зададим распределение вероятностей на следующим образом. Положим

Пусть средняя взаимная информация между входом и выходом канала, вычисленная для распределения вероятностей (3.4.5). Тогда где ансамбль слов рассматриваемого кода, и из определения информационной емкости следует, что

Пусть ансамбль решений. Этот ансамбль можно рассматривать как результат отображения ансамбля всех последовательностей да выходе канала в множество решений. Это отображение задается посредством набора решающих областей Каждая последовательность однозначно определяет решение по следующему правилу:

Поскольку информация не возрастает в результате преобразований (см. теорему 2.1.2), то

Так как и согласно то используя неравенство (3.4.6), получим, что

или

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

Тогда из неравенства Фано и неравенства (3.4.10) следует, что средняя вероятность ошибки X для кода удовлетворяет неравенству X Легко увидеть, что стремится к при Из свойств функции (см. предыдущий параграф) следует, что при число остается положительным при

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

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