8.3. КОДИРОВАНИЕ СООБЩЕНИЙ С ЗАДАННОЙ МЕРОЙ ВЕРНОСТИ

В предыдущем параграфе утверждалось (теорема 1), что кодирование без ошибок возможно тогда, и только тогда, когда среднее число бит, используемое на одну букву сообщения, больше или равно энтропии источника Если при кодировании использовать бит на букву и то восстановление (декодирование) исходного сообщения без ошибок невозможно ни при каком способе кодирования. В этом случае можно найти минимальное число символов на букву или на единицу времени, требуемое для кодирования букв источника таким образом, чтобы по кодовой последовательности двоичных символов можно было восстановить сообщение с заданной мерой верности. Ясно, что этот предел будет зависеть от статистики источника, меры искажения и критерия верности.

Пусть источник выдает сообщение которое кодируется с использованием бит на букву. На выходе декодера восстанавливается сообщение которое теперь не будет точно совпадать с исходным сообщением Оно будет восстановлено с некоторой ошибкой среднее значение которой

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

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

А теперь определим энтропию источника как функцию искажений Сделаем это для источника без памяти, входом которого являются сообщения а выходом декодера — сообщения Количество информации, содержащееся в восстановленном на выходе декодера сообщении А относительно исходного сообщения определяется известным соотношением [45]

где безусловная энтропия определяется выражением (8.1), а условная энтропия к

- Минимальное количество бинарных символов которое необходимо для представления сообщения А с ошибкой не превышающей некоторого заданного значения определяется эпсилон-энтропией [183]:

Согласно (8.14) для заданного источника

где максимум берется по всем условным распределениям удовлетворяющим условию Для любого источника можно вычислить предельное значение ошибки как функцию и определить среднюю ошибку при заданном способе кодирования-декодирования. Тогда можно сформулировать следующую теорему.

Теорема 2. При любом способе кодирования сообщении источника и существует способ кодирования-декодирования, при котором средняя ошибка будет сколь угодно близкой к

Пусть Тогда при может быть достигнута ошибка что соответствует утверждению теоремы 1. Для двоичного источника, вырабатывающего статистически независимые двоичные символы 0 и 1, согласно (8.17) и (8.13)

где функция, характеризующая энтропию двоичной случайной величины (8.3). При ошибка Для источника с объемом алфавита К на основании (8.17) имеем [27]

Уравнения и (8,19) позволяют вычислить предельную ошибку при заданной эпсилон-энтропии источника

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

Теорема 3. 1) Если скорость передачи меньше или равна пропускной способности канала то можно найти такой способ кодирования-декодирования (построить такой кодек канала), при котором частота ошибок (ошибка декодирования) при передаче по каналу будет сколь угодно малой. 2) При значение ошибки отлично от нуля.

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