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

4. Метод Хаффмена

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

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

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

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

где ε — сколь угодно малая, положительная величина, существует способ кодирования, позволяющий передавать по каналу все сообщения, вырабатываемые источником.

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

Поскольку строгое математическое доказательство относительно сложно [34], убедимся в справедливости теоремы, основываясь на эвристических соображениях.

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

Если количество знаков в кодируемой последовательности равно Ν, а энтропия источника — Η(Ζ), то в соответствии с (4.8) число типичных последовательностей

Так как Ν = Τ/τ, где Т — длительность кодируемой последовательности; τ — длительность одного знака, то

Каждой типичной последовательности нужно поставить в соответствие кодовую комбинацию той же продолжительности Т из символов с объемом алфавита m. При скорости манипуляции V_T число символов в кодовой комбинации составит TV_Т, что позволяет образовать n_k различных кодовых комбинаций, причем

Сравнение (5.7) и (5.8) показывает, что Следовательно, если то кодовых комбинаций, пропускаемых каналом, достаточно для того, чтобы закодировать все типичные последовательности знаков, причем останется еще некоторый излишек.

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

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

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

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

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

сообщения источника с энтропией Η(Ζ) всегда можно закодировать последовательностями символов с объемом алфавита m так, что среднее число символов на знак сообщения l_cр будет сколь угодно близко к величине но не менее ее.

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

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