Тамбов 2010

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

4.1. Понятие кодирования. Кодовое дерево.

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

,

где n- количество элементов кодовой последовательности.

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как n-разрядное число в D-ичной системе счисления.

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

Пример: код длины n=S в двоичной системе счисления D=2 позволяет представить 32 буквы русского алфавита пятиразрядными двоичными числами.

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

.

Т.е. информационные возможности кода используются не полностью.

Пример: Для двоичного пятиразрядного кода букв русского алфавита информационная емкость составляет 5 бит, =4,35 бит.

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

Если i-ая буква, вероятность которой p_i, получает кодовую комбинацию длины n_i, то средняя длинна кода (кодового слова) равна:

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

Известно, что любую букву (событие), содержащиеся в алфавите (сообщении) источника, можно разложить на последовательности двоичных решений с исходами «да»=1 и «нет»=0 без потери информации.

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

C₁,C₂, C₃,C₄ – дерево кодов имеет разную длину кода (кодового слова).