Экономное кодирование. 
Общая теория связи

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

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

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

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

Рассмотрим экономное кодирование источников с известной статистикой сообщений. Очевидно, что средняя длина неравномерного кода будет минимизироваться тогда, когда с более вероятными сообщениями источника будут сопоставляться более короткие комбинации канальных символов. Проблема, однако, состоит в том, что у неравномерного кода на приемной стороне оказываются неизвестными границы этих комбинаций. Если же мы попытаемся их выделить, используя известный способ кодирования, то декодирование может оказаться неоднозначным (действительно, если, например, с буквой, А сопоставлена комбинация 0, с буквой Б — 1, а с буквой В — 10, то невозможно определить по принятой комбинации 10, передавались ли буква В или пара букв, А и Б). Для того чтобы используемый код обладал свойством однозначной декодируемое™, он должен удовлетворять некоторым условиям. Однозначное декодирование будет обеспечено, если ни одно кодовое слово не является началом другого кодового слова. Такие коды называются префиксными. Неравномерное префиксное кодирование устраняет избыточность источника, вызванную неодинаковой вероятностью сообщений.

Экономное кодирование методом Шеннона — Фано. Упрощенно принцип алгоритма Шеннона — Фано заключается в следующем. Символы алфавита источника сообщения записывают в порядке убывающих вероятностей. Затем их разделяют на две части так, чтобы суммы вероятностей символов, входящих в каждую из частей, были примерно одинаковыми. Всем символам первой части в качестве первого символа комбинации кода приписывают нуль, а символам второй части в качестве первого символа комбинации — единицу. Потом каждую из этих частей делят в свою очередь на две по возможности равновероятные части и к ним применяют то же правило кодирования. Процедуру повторяют до тех пор, пока в каждой из частей не останется по одному сообщению.

Экономное кодирование методом Хаффмана. Этот метод кодирования имеет большое сходство с алгоритмом Шеннона — Фано и получил широкое распространение из-за простоты реализации и высокой скорости передачи. Для работы алгоритма необходимо иметь таблицу значений вероятностей различных символов, которые могут встретиться в данный момент кодирования.

На основе таблицы строят бинарное дерево Хаффмана следующим образом:

• 1) отсортировать символы по возрастанию вероятности их появления;
• 2) первые два символа в получившемся ряде объединить в один, сопоставив первому символу 0, второму — 1; вероятности этих двух символов сложить. Если в ряде остался один символ, то закончить, иначе перейти к первому пункту.

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

Помехоустойчивое кодирование. Проблема повышения верности приема обусловлена несоответствием между требованиями, предъявляемыми при передаче данных, и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность приема не хуже 10 ⁽⁾—10 ⁹, а при использовании реальных каналов связи и простого (первичного) кода верность не превышает 10 ²—10 Одним из методов повышения помехоустойчивости систем связи является оптимизация устройств приема и обработки сигналов с помехоустойчивыми видами модуляции. Другим методом повышения помехоустойчивости приема дискретной информации является введение избыточности в передаваемые сообщения, что позволяет обнаруживать и исправлять ошибки в принятом сообщении. Методы внесения избыточности в передаваемый сигнал связаны с увеличением его объема, т. е. с увеличением либо энергии сигнала, либо ширины спектра, либо времени передачи. Наиболее часто применяют введение избыточности увеличением времени передачи сигнала за счет использования помехоустойчивых кодов.

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

Пусть двоичная информация подлежит передаче по каналу, подверженному случайным ошибкам. Задача помехоустойчивого кодирования состоит в таком добавлении к информационным символам дополнительных символов, чтобы в приемнике искажения с помощью дополнительных символов могли быть найдены и исправлены. Пусть для передачи информации по каналу связи используются четырехэлементные кодовые комбинации, отличающиеся друг от друга не менее чем в двух разрядах: ООП, ОНО, 1001, 1010, 1100, 1111, 0101, 0000. Если при передаче любой из этих комбинаций произошла одиночная ошибка, то принятая комбинация будет запрещенной, что и свидетельствует о наличии в ней ошибки. Комбинация 1011, которая является запрещенной, получается за счет одиночной ошибки в первой, третьей, четвертой и шестой кодовых комбинациях соответственно в первом, втором, третьем и четвертом разрядах.

Возьмем четырехэлементные комбинации, различающиеся всеми четырьмя разрядами: 0011 и 1100. Легко убедиться в том, что при использовании этих комбинаций обнаруживаются одно-, двухи трехкратные ошибки. Этот код, состоящий из двух кодовых комбинаций, можно использовать для исправления одиночных ошибок. Если, как и ранее, будет принята комбинация 1011, она будет отличаться от разрешенной комбинации ООП одним разрядом, а от другой разрешенной 1100 — тремя, т. е. принятая комбинация «ближе» к комбинации ООН, чем к комбинации 1100, что и дает основание считать, что была комбинация 0011.

Повышенная помехоустойчивость двух рассмотренных кодов связана с имеющейся в них избыточностью. Так, первый код использует восемь кодовых комбинаций из возможных 16 (2⁴ = 16), и можно было бы для их образования применить трехэлементный код (2³ = 8). Второй код, обладающий большей помехоустойчивостью, потребовал, соответственно, еще большей избыточности — трех дополнительных разрядов.

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

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

Рассмотрим его подробнее.