Требование префиксности эффективных кодов

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

Более целесообразно обеспечить однозначное декодирование без введения дополнительных символов. Для этого эффективный код необходимо строить так, чтобы ни одна комбинация кода не совпадала с началом более длинной комбинации. Коды, удовлетворяющие этому условию, называют префиксными кодами. Последовательность 100000110110110100 комбинаций префиксного кода, например кода Z₁ – 00; Z₂ – 01; Z₃ – 101; Z₄ – 100, декодируется однозначно:

Последовательность 000101010101 комбинаций непрефиксного кода, например кода Z₁ – 00; Z₂ – 01; Z₃ – 101; Z₄ – 010 (комбинация 01 является началом комбинации 010), может быть декодирована по-разному:

Нетрудно убедиться, что коды, получаемые в результате применения алгоритма Шеннона – Фано или Хаффмена, являются префиксными.

Недостатки системы эффективного кодирования

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

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

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

2.5. Помехоустойчивое кодирование. Классификация помехоустойчивых кодов

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

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

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

Все помехоустойчивые коды можно разделить (см. рис. 2.3.) на два основных класса: блочные и непрерывные (рекурентные или цепные).

Рис. 2.3

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

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

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

Как блочные, так и непрерывные коды в зависимости от методов внесения избыточности подразделяются на разделимые и неразделимые. В разделимых кодах четко разграничена роль отдельных символов. Одни символы являются информационными, другие являются проверочными и служат для обнаружения и исправления ошибок. Разделимые блочные коды называются обычно п,k-кодами, где п – длина кодовых комбинаций, k – число информационных символов в комбинациях.

Неразделимые коды не имеют четкого разделения кодовой комбинации на информационные и проверочные символы.

Разделимые блочные коды делятся, в свою очередь, на несистематические и систематические. Несистематические разделимые коды строятся таким образом, что проверочные символы определяются как сумма подблоков длины l, на которые разделяется блок информационных символов.

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