Ошибка декодирования. Неравенство Фано

Пусть имеются два дискретных ансамбля и объема M с заданными совместными вероятностями , где . Хотя доказываемое соотношение имеет место для любых ансамблей, для наших целей удобно сразу считать ансамбль множеством передаваемых кодированных сообщений, а – множеством решений на выходе канала о том, какое из сообщений передавалось. В подобной формулировке частное решение может не совпадать с переданным сообщением . Подобное событие, если оно имеет место, получило название ошибки решения (или декодирования). Тогда полную (среднюю) вероятность ошибки декодирования можно записать как

, (3.17)

а вероятность правильного решения

. (3.18)

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

Теорема 3.4.1. (Неравенство Фано) При фиксированной вероятности ошибки условная (остаточная) энтропия

, (3.19)

где – энтропия двоичного ансамбля.

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

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