Файл: Методы кодирования данных (Основные понятия.pdf

Для иного класса источников (марковских) имеется статистическая связь среди порождаемых символов. В последующем мы будем анализировать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти [17, с. 117].

Пусть наличествует дискретный вероятностный источник без памяти, порождающий знаки алфавита А={a₁,…,a_n} с вероятностями , . Ведущей чертой источника считается энтропия, которая представляет из себя среднее значение числа информации в сообщении источника и находится выражением (для двоичного случая):

. (2.2)

Энтропия охарактеризовывает меру неопределенности выбора для предоставленного источника.

Приведем пример. В случае если А={a₁,a₂}, p₁=0, p₂ =1, т.е. источник имеет возможность породить лишь только знак a₂, то неопределенности нету, энтропия H(p₁,p₂)=0 [16, с. 82].

Источник с равновероятными символами А={a₁,a₂}, p₁ =1/2, p₂ =1/2, станет иметь наибольшую энтропию H(p₁,p₂)=1.

Величина называется энтропией на символ последовательности длины L, где A^L  множество всех последовательностей длины L в алфавите A, x=(x₁,x₂,...,x_L)  последовательность L букв дискретного cтационарного источника. Обозначим через предел энтропии H_L при L  . Данное значение именуют предельной энтропией источника. Показано, собственно, что для стационарного бернуллиевского источника:

. (2.3)

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

Ведущей чертой неравномерного кода считается численность знаков, затрачиваемых на кодирование одного сообщения. Пускай есть разделимый побуквенный код для источника, порождающего знаки алфавита А={a₁,…,a_n} с вероятностями p_i =P(a_i), состоящий из n кодовых слов с длинами L₁,…,L_n в алфавите {0,1}.

---

Средней длиной кодового слова именуется величина , которая демонстрирует среднее количество кодовых букв на 1-ну букву источника.

Приведем пример. Пускай есть 2-ва источника с одинаковым алфавитом А={a₁,a₂,a₃} и различными вероятностными распределениями P₁={1/3, 1/3, 1/3}, P₂={1/4, 1/4, 1/2}, которые кодируются одинаковым кодом:

. (2.4)

Средняя длина кодового слова для различных источников станет разной:

L_ср(P₁)=1/3^.2 + 1/3^.3 + 1/3^.2= 7/3 ≈2.33;

L_ср(P₂)=1/4^.2 + 1/4^.3 + 1/2^.2= 9/4 =2.25.

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

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

. (2.5)

Избыточность кода – есть показатель качества кода, подходящий код имеет минимальную избыточность. Задача действенного неискажающего сжатия заключается в построении кодов с минимальной избыточностью, у коих средняя длина кодового слова близка к энтропии источника. К этим кодам относятся традиционные коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код [10, с. 17].

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

Теорема 1 (Шеннон). Для источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i), и любого разделимого побуквенного кода средняя длина кодового слова всякий раз не меньше энтропии:

L_cp ≥ H(p₁,…,p_n) (2.6)

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

L_cp < H(p₁,…,p_n)+1 (2.7)

Возможно получить больше крепкие итоги, в случае если кодовые слова приписывать не отдельными буквами, а блоками из L букв источника. Так, для неравномерных блоковых кодов справедлива приведенная ниже теорема.

Теорема 2. Пусть H_L  энтропия на букву в блоке длины L дискретного источник. Тогда есть префиксный код для кодировки блоков длины L, такой, что средняя длина кодового слова L_cp станет удовлетворять неравенствам:

---

. (2.8)

Отметим, что в случае бернуллиевского стационарного источника для всякого >0 возможно избрать довольно большущее L, дабы размер L_cp удовлетворял неравенствам:

, (2.9)

и левое неравенство для L_cp ни разу не нарушается для разделимого кода.

Приведем кое-какие качества, которыми владеет всякий подходящий побуквенный код [8, с. 186].

Лемма 1. Для рационального кода с длинами кодовых слов L₁,…,L_n: правильно соответствие L₁≤L₂≤…≤L_{n ,} если p₁≥p₂≥…≥p_n.

Подтверждение (от противного): Пусть имеется i и j, что L_i>L_j при p_i>p_j. Отсюда будем иметь:

L_ip_i+L_jp_j=

=L_ip_i+L_jp_j+L_ip_j+L_jp_i-L_ip_j-L_jp_i=

=p_i(L_i-L_j)-p_j(L_i-L_j)+L_jp_i+L_ip_j=

=(p_i-p_j)(L_i-L_j) +L_ip_j+L_jp_i>L_ip_j+L_jp_i,

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

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

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

Этим образом, новая схема кодирования также считается префиксной, при этом с наименьшей средней длиной кодового слова , что собственно противоречит оптимальности начальной схемы кодировки [5, с. 141].

---

Пусть теперь 2 кодовых слова и наибольшей длины различаются не в конечном разряде, т.е. , , , . Причем , не считаются префиксами для иных кодовых слов и напротив. Тогда новая схема также считается префиксной, при этом , что противоречит оптимальности начальной схемы кодировки. Лемма 2 подтверждена [10, с. 19].

В заключение можно сделать вывод, что при кодировании сообщений является то, что символы сообщения порождаются определенным источником информации. Источник является установленным целиком, в случае если предоставлено вероятностное представление процесса появления сообщений на выходе источника. Данное значит, то что в любой момент времени установлена возможность порождения источником любой очередности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник именуется дискретным вероятностным источником.

2.2. Метод оптимального побуквенного кодирования Д. Хаффмана

Метод оптимального побуквенного кодирования был создан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана имеет минимальную среднюю длину кодового слова между всех побуквенных кодов для предоставленного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i).

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

1. Упорядочим знаки начального алфавита А={a₁,…,a_n} по убыванию их вероятностей p₁≥p₂≥…≥p_n.
2. Если А={a₁,a₂}, то a₁0, a₂1.
3. Если А={a₁,…,a_j,…,a_n} и известны коды <a_j  b_j >, j = 1,…,n, то для алфавита {a₁,…a_j^/, a_j^//…,a_n} с новыми символами a_j^/ и a_j^// вместо a_j, и вероятностями p(a_j)=p(a_j^/)+ p(a_j^//), код символа a_j заменяется на коды a_j^/  b_j0, a_j^// b_j1 [10, с. 19].

---

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями

p₁=0,36, p₂=0,18, p₃=0,18, p₄=0,12, p₅=0,09, p₆=0,07.

Тут знаки источника уже упорядочены в согласовании с их вероятностями. Станем складывать 2 меньшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется 2 символа. Тогда закодируем эти 2 символа 0 и 1. Дальше кодовые слова достраиваются, как указано на рисунке 2.1.

Рис. 2.1 Процесс построения кода Хаффмана [10, с. 20]

Таблица 2.1 Код Хаффмана [10, с. 20]

ai	pi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	0,36 0,18 0,18 0,12 0,09 0,07	2 3 3 4 4 4	1 000 001 011 0100 0101

Рассчитаем среднюю длину, построенного кода Хаффмана:

L_ср(P)=1^.0,36 + 3^.0,18 + 3^.0,18 + 3^.0,12 + 4^.0,09 + 4^.0.07 =2,44,

при этом энтропия этого источника:

H(p₁,…,p₆) = − 0,36^.log0,36 − 2^.0,18^.log0,18 −

− 0,12^.log0,12 − 0,09^.log0,09 − 0,07log0,07=2,37

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

Рис. 2.2 Кодовое дерево для кода Хаффмана [10, с. 20]

Алгоритм на псевдокоде

Построение оптимального кода Хаффмана (n, P).

Обозначим:

• n – количество символов исходного алфавита;
• P – массив вероятностей, упорядоченных по убыванию;
• С – матрица элементарных кодов;
• L – массив длин кодовых слов.

Huffmаn (n,P)

IF (n=2) С [1,1]:= 0, L [1]:= 1

С [2,1]:=1, L [2]:=1

ELSE q:= Р [n-1]+P [n]

j:= Up (n,q) (поиск и вставка суммы)

Huffmаn (n-1,Р)

Dоwn (n,j) (достраивание кодов)

FI

Функция Uр (n,q) находит в массиве Р место, куда поставить число q, и вставляет его, сдвигая вниз другие элементы.

DО (i=n-1, n-2,…,2)

---