17. Энтропия источника дискретных сообщений

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

Свойства:

18. Эффективное кодирование дискретных сообщений

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

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

Эффективное кодирование осуществляется с применением неравномерных кодов, в которых более короткие кодовые комбинации соответствуют более вероятным символам сообщения, а более длинные — менее вероятным символам. Основными требованиями, предъявляемыми к эффективному коду, являются:

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

• в среднем на один символ сообщения должно приходиться минимальное число элементов кодовой комбинации эффективного кода;

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

Рассмотрим построение эффективного кода на примере кода Шеннона-Фано и кода Хаффмена.

1. Записываются сообщения a_i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу).

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

3. Записываются кодовые комбинации, соответствующие каждому элементу сообщения, при этом 1-я группа соответствует старшему разряду, 2-я следующему и т. д. по всем столбцам. Если в столбце элемента a_i отсутствует символ «0» или «1», то в соответствующем разряде кодовой комбинации он не пишется.

1. Записываются сообщения a_i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу).

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

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