P(x₁x₂...x_L ) = P(x₁)·P(x₂)·...·P(x_L),

где P(x) – вероятность появления символа х, Р(x₁x₂x₃...x_L) – вероятность появления последовательности x₁x₂x₃...x_L.

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

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

.

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

• 1. Оптимальный код Хаффмана

Метод оптимального побуквенного кодирования был разработан в 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.

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

---

Рисунок 2 Кодовое дерево для кода Хаффмана

1. почти оптимальное кодирование

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

• 1. Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона из п. 5.1

.

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита А={a₁,a₂,…,a_n} по убыванию их вероятностей: p₁≥p₂≥p₃≥…≥p_n.
2. Вычислим величины Q_i:, которые называются кумулятивные вероятности

Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1.

1. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые знаков после запятой.

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения

, .

• 1. Код Фано

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

• 1. Алфавитный код Гилберта – Мура

Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого .

Пусть символы алфавита некоторым образом упорядочены, например, a₁≤a₂≤…≤a_n. Код называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. .

Процесс построения кода происходит следующим образом.

1. Вычислим величины Q_i, i=1,n:

---

Q₁=p₁/2,

Q₂=p₁+p₂/2,

Q₃=p₁+p₂+p₃/2,

…

Q_n=p₁+p₂+…+p_n-1+p_n/2.

1. Представим суммы Q_iв двоичном виде.
2. В качестве кодовых слов возьмем младших бит в двоичном представлении Q_i, .

Пусть дан алфавит 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. Построенный код приведен в таблице 8.

Таблица 8 Код Гилберта-Мура

ai	Pi	Qi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	1/23≤0.18 1/23≤0.18<1/22 1/22≤0.36<1/21 1/24≤0.07 1/24≤0.09 1/24≤0.12	0.09 0.27 0.54 0.755 0.835 0.94	4 4 3 5 5 5	0001 0100 100 11000 11010 11110

Средняя длина кодового слова не превышает значения энтропии плюс 2. Действительно,

L_ср=4^.0.18+4^.0.18+3^.0.36+5^.0.07+5^.0.09+5^.0.12=3.92<2.37+2

1. арифметический код

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

Рассмотрим общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита А={a₁,a₂,…,a_n} с вероятностями p_i=P(a_i), . Необходимо закодировать последовательность символов данного источника Х=х₁х₂х₃х_4.

1. Вычислим кумулятивные вероятности Q₀ ,Q₁,…,Q_n:

Q₀=0

Q₁=p₁

---

Q₂=p₁+p₂

Q₃=p₁+p₂+p₃

...

Q_n=p₁+p₂+…+p_n=1

1. Разобьем интервал [Q₀,Q_n) (т.е. интервал [0,1)) так, чтобы каждой букве исходного алфавита соответствовал свой интервал, равный ее вероятности (см. рис. 3):

a₁ [Q₀,Q₁)

a₂ [Q₁,Q₂)

a₃ [Q₂,Q₃)

a₄[Q₃,Q₄)

...

a_n [Q_n-1,Q_n)

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

На рисунке 3 показан этот процесс для кодирования последовательности а₃а₂а₃…

Рисунок 3 Схема арифметического кодирования

Для удобства вычислений введем следующие обозначения:

l_i нижняя граница отрезка, соответствующего i-той букве исходного сообщения;

h_i верхняя граница этого отрезка;

r_i длина отрезка [l_i, h_i), т.е. r_i = h_i  l_i.

Возьмем начальные значения этих величин

l₀ = Q₀=0, h₀= Q_k=1, r₀ = h₀  l₀=1

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

, ,

где m  порядковый номер кодируемой буквы в алфавите источника, m=1,...,n.

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

Для однозначного декодирования исходной последовательности достаточно взять разрядов двоичной записи любой точки из интервала [l_i,h_i), где r_k длина интервала после кодирования k символов источника.

1. адаптивные методы кодирования

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

---

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

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

Рисунок 4 Схема перемещения окна при кодировании

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

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

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

Теорема. Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству

,

где Н – энтропия источника информации, C – константа, зависящая от размера алфавита источника и длины окна.

• 1. Адаптивный код Хаффмана

В 1978 году Р. Галлагер предложил метод кодирования источников с неизвестной или меняющейся статистикой, основанный на коде Хаффмана, и поэтому названный адаптивным кодом Хаффмана.

Адаптивный код Хаффмана используется как составная часть во многих методах сжатия данных. В нем кодирование осуществляется на основе информации, содержащейся в окне длины W. Алгоритм такого кодирования заключается в выполнении следующих действий:

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

P(a₁)= q(a₁)/W, P(a₂) =q(a₂)/W, ..., P(a_n)= q(a_n)/W.

---

Смотрите также файлы

• Методы кодирования данных (Кодирование целых И действительных чисел).pdf

• Особенности семейного воспитания(Семья – основа семейного воспитания).pdf

• Тенденции развития международной валютной системы ( Понятие и сущность международной валютной системы).pdf

• Социальное страхование и его функции (Проблемы и перспективы развития).pdf

• Государственная служба в Российской Федерации: опыт, современное состояние и направления совершенствования (История и опыт государственной службы в Российской Федерации ).pdf