2.4. Оптимальное статистическое (эффективное) кодирование

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

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

Пусть кодирующее устройство использует алфавит, состоящий из m символов. В этом алфавите требуется представить любой элемент сообщения из множества возможных элементов Z_j, j = 1,2, ..., М; вероятности (частоты) P_j появления в сообщении каждого из элементов Z_j известны. Обычно m < M, поэтому каждому из возможных элементов сообщения ставится в соответствие некоторая последовательность символов алфавита, называемая кодовым словом. Кодовое слово должно находиться во взаимно-однозначном соответствии с кодируемым элементом. Так как сообщение, как правило, представляет собой последовательность элементов, то, кроме очевидного требования о недопустимости одинаковых кодовых слов для разных элементов, накладывается требование, чтобы ни одно кодовое слово нельзя было получить из другого, более короткого, за счет добавления дополнительных символов. Например, кодовые комбинации 01110 и 011100 не могут использоваться в одном кодовом множестве. Это необходимо для однозначного декодирования кодовых слов при их последовательной передаче. Для различения кодовых комбинаций можно использовать пространственные или временные разделители (как пробелы при письме или разделительные интервалы в телеграфии), но это равносильно введению в алфавит системы дополнительного символа специального назначения, что увеличивает объем сообщения и снижает эффективность системы. При использовании рассмотренных выше равномерных кодов, имеющих одинаковую длину кодовых слов, разделение кодовых комбинаций можно осуществлять простым подсчетом числа символов; однако такое кодирование не оптимально, т.к. и часто встречающимся в сообщении элементам и очень редко встречающимся элементам ставятся в соответствие кодовые комбинации одной и той же длины.

Эффективное кодирование сообщений для передачи их по дискретному каналу без помех базируется на теореме Шеннона, которую можно сформулировать так:

1) при производительности источника сообщений меньше пропускной способности канала связи существует способ кодирования, позволяющий передавать по каналу все сообщения, вырабатываемые источником;

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

Указанная теорема Шеннона часто приводится и в другой формулировке:

· сообщения источника с неопределенностью (энтропией) H всегда можно закодировать последовательностями символов с объемом алфавита т так, что среднее число символов на знак сообщения l_ср будет сколь угодно близко к величине H / log m, но не менее ее, т.е. l_ср ³ H / log m.

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

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