§ 3.3. Неравенство Фано

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

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

где

Величину будем называть условной вероятностью ошибки при фиксированном а величину к — средней вероятностью ошибки.

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

где и

Безусловное распределение вероятностей на есть При этом

В следующей теореме устанавливается связь между условной энтропией и вероятностью ошибки .

Теорема 3.3.1 (неравенство Фано). Для любого дискретного ансамбля справедливо неравенство

Доказательство. Рассмотрим условную энтропию При имеем

где последнее равенство следует из (3.3.1) и (3.3.3). Из соотношения (3.3.1) следует также, что

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

При (такое найдется, если имеем

Так как при всегда происходит ошибка, то при таких значениях Следовательно, из (3.3.10) вытекает, что неравенство (3.3.9) имеет место при всех

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

Поскольку условная энтропия не превосходит безусловную то из (3.3.11) следует неравенство (3.3.6). Теорема доказана.

Рассмотрим, как неравенство Фано может применяться для оценки вероятности ошибки декодирования в дискретном канале связи. Пусть задан дискретный канал, т. е. заданы множества входных X и выходных сигналов, а также при всех заданы условные вероятности Предположим, что для передачи по каналу используется код им, длины и объема

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

где

При этом величина (см. (3.3.1)) представляет собой условную вероятность ошибки декодирования для кода при условии, что в результате декодирования вынесено решение а величина X (см. (3.3.2)) представляет собой среднюю вероятность ошибки декодирования. Эта средняя вероятность ошибки может быть вычислена также по формуле (3.2.5):

Энтропия в рассматриваемом случае представляет собой среднюю условную информацию ансамбля кодовых слов при фиксированном множестве решений. Величину

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

Неравенство Фано можно интерпретировать следующим образом. Для того чтобы наблюдатель, находящийся в декодере, мог точно установить переданное сообщение, он, во-первых, должен знать, допускает или не допускает ошибку декодер. Среднее количество информации, необходимое для этого, равно Если наблюдатель знает, что при декодировании произошла ошибка, то ему необходимо дополнительно установить, какое из оставшихся кодовых слов было действительно передано. Среднее количество информации, необходимое для этого, не превосходит Так как такая необходимость возникает с вероятностью X, то среднее количество дополнительной информации не превосходит Неравенство (3.3.6) обосновывает тот интуитивно ясный факт, что потеря информации в канале из-за действия шумов, т. е. величина не превосходит величины которая является верхней оценкой количества информации, необходимого для точного установления переданного сообщения.

Рис. 3.3.1. График функции

Правая часть неравенства Фано является функцией только от обозначим ее через

Заметим, что причем равенство имеет место только при Функция является непрерывной на интервале 10, 11. Беря производную по , можно убедиться в том, что она монотонно возрастает, если убывает, если и имеет максимум в точке График функции изображен на рис. 3.3.1.

Пусть а — некоторое положительное число, меньшее или равное наименьшее решение уравнения Нетрудно видеть, что следующие два неравенства

равносильны, т. е. первое влечет второе и наоборот.