Алфавитное кодирование

Автор работы: Пользователь скрыл имя, 12 Декабря 2011 в 16:35, курсовая работа

Описание работы

Начало математическому исследованию вопросов экономного кодирования, учитывающего вероятностные и структурные свойства информации, было положено работой К. Шеннона «Математическая теория связи», опубликованной в 1948 году. При построении алгоритмов кодирования Шенноном учитывались главным образом вероятностные свойства сообщений, порождаемых источником с конечным числом состояний. Однако эти вероятностные свойства определялись как вероятностными свойствами состояний источника, так и синтаксическими (структурными) свойствами последовательностей символов, генерируемых источником.

Содержание работы

Введение 3
1. Теоретические основы задачи кодирования……………………………………………...6
1.1. Постановка задачи кодирования………….……………………………..….……………6
1.2. Первая теорема Шеннона…………………………………………………………….....10
1.3. Вторая теорема Шеннона……………………………………………………………….13
1.4. Помехоустойчивые коды…..........………………………………………….......…….…14
2. Алфавитное кодирование......................................................................................................17
2.1. Основные определения.....................................................................................................17
2.2. Проблема распознавания взаимной однозначности алфавитного кодирования.......18
2.3. Алгоритм построения префиксного кода по набору длин элементарных кодов........22
2.4. Алгоритмы экономного алфавитного кодирования......................................................23
2.4.1. Алгоритм Хаффмана...............................................................................................24
2.4.2. Алгоритм Фано........................................................................................................26
2.4.3. Алгоритм Шеннона.................................................................................................27
2.4.4. Энтропия и ее связь со стоимостью оптимального алфавитного
код

Файлы: 1 файл

Алфавитное кодирование.doc

— 473.00 Кб (Скачать файл)

    Пример 2.7. Пусть B = {b1, b2, b3, b4, b5, b6, b7}, P=(0,20;0,20;0,19;0,12;0,11;0,09;0,09).

    Процесс построения оптимального кода можно  представить следующим образом: 

 

    Фигурными скобками отмечены объединяемые вероятности. Для каждой скобки верхнему члену  приписываем символ 0, нижнему –  символ 1. Затем осуществляем движение в обратном направлении к p1, p2,…, p7 и, проходя скобки, выписываем соответствующие элементарные коды.

    Например, путь 0,60 – 0,23 – 0,11 дает элементарный код 011 для буквы b5. Таким образом, мы получаем следующую схему f для оптимального кода:

    Стоимость кодирования C * ( P) = 2,78. 

2.4.2. Алгоритм Фано (1961 г.) 

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

    В алгоритме Фано кодовое дерево строится от корня, а в алгоритме Хаффмана –  начиная с листьев. Это отличие позволяет в алгоритме Хаффмана полнее использовать специфику данного распределения вероятностей и строить оптимальный код. Алгоритм Фано строит код, близкий к оптимальному.

    Пример  2.8. Применим алгоритм Фано к тому же распределению вероятностей.

    Пусть B = {b1, b2, b3, b4, b5, b6, b7}, P = (0,20;0,20;0,19;0,12;0,11;0,09;0,09). 

 

Получаем следующую  схему алфавитного кодирования:

    Стоимость кодирования CФ (P) = 2,80.  

    2.4.3. Алгоритм Шеннона (1948 г.)

Алгоритм Шеннона  применим в случае, когда все вероятности  pi > 0. Букве bi ставится в соответствие последовательность из двоичных символов (здесь - ближайшее целое сверху числа x и log здесь и везде далее берется по основанию 2). Алгоритм Шеннона основан на том, что выбранные длины li (i=1,2, …, m) удовлетворяют неравенству Мак-Миллана. После выбора длин применяется алгоритм Шеннона построения схемы кодирования по заданному набору длин элементарных кодов, описанный ранее.

    Пример 2.9.

    Пусть B = {b1, b2, b3, b4, b5, b6, b7}, P = (0,20;0,20;0,19;0,12;0,11;0,09;0,09).

    Вычислим  набор длин для P.

      

    Построим  префиксный код по алгоритму Шеннона  с вычисленными длинами

элементарных  кодов.

    Стоимость кодирования CШ (P) = 3,41. 

    2.4.4. Энтропия и ее связь со стоимостью оптимального алфавитного

кодирования. 

    Важную  роль для оценки эффективности кодирования  играет энтропия вероятностного распределения:

      

    Пусть C *(P) - стоимость оптимального алфавитного кодирования.

    Теорема 2.6. C *(P) ≥ H(P).

    Доказательство. Будем использовать неравенство log x ≤ (x -1) loge. Так как для длин элементарных кодов выполняется неравенство Мак-Миллана, .

    Рассмотрим  разность H(P)-C*(P):

        

    Отсюда  C *(P) ≥ H(P).

    Теорема доказана.

    При некоторых распределениях стоимость C *(P) может достигать нижней границы.

    Пример  2.10. Рассмотрим распределение вероятностей .

Вычислим C(m) = C(Pm).

Положим . Получим

l1 = 1, l2 = 2,…, li = i,…,lm-2 = m -2, lm-1 = lm = m -1.

    Величины  li удовлетворяют неравенству Мак-Миллана, следовательно, существует

префиксный код  с таким набором длин элементарных кодов. Так как pi являются степенью двойки, li = - log pi , поэтому

      

    В общем же случае C *(P) = H(P) + ε , где 0 ≤ ε <1, как показывает следующая теорема. 

    Теорема 2.7. C *(P) < H(P) +1.

    Доказательство. Возьмем li = - log pi , (i =1,…,m) . Тогда откуда

.Т.е. набор длин (l1,…,lm) реализуем.

    Но li  < - log pi +1, откуда pili < - pi log pi + pi и суммируя по i, получаем:

      

    Теорема доказана.

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

    Дополнительные  возможности для сжатия могут возникнуть при конечно-автоматном кодировании. Вместо того, чтобы кодировать каждую букву, разобьем сообщение на блоки длины N, которые и будем кодировать как буквы нового алфавита BN .

    Пусть PN - распределение вероятностей на BN , которое индуцируется распределением P на B:

    

    Теорема 2.8. H(PN ) = N H(P).

    Доказательство  проведем индукцией по N. При N = 1 утверждение теоремы тривиально.

    Пусть теорема верна при N = 2,…,k -1. Тогда 

        

    Теорема доказана.

    Покажем, что, выбирая длину блока N достаточно большой, можно сделать стоимость кодирования на одну букву сообщения CN (P) сколь угодно близкой к H(P).

    Теорема 2.9. .

Доказательство. Имеем:

N H(P) = H(PN ) ≤ C(PN ) = N CN (P) < H(PN )+1 = N H(P) +1.

    Отсюда получаем:

    

При N → ∞ CN (P) →H(P). Теорема доказана.

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

    Пример 2.11. Пусть B = {b1 , b2 , b3 }, P = {0,5;0,4;0,1}.

    Применяя  алгоритм Хаффмана к распределению  P, получаем следующую схему кодирования:

     

    Вычислим  стоимость оптимального кодирования: C1 = 1,5.

    Положим N = 2 и рассмотрим всевозможные блоки длины 2. Определим произведение вероятностей каждого блока как произведение вероятностей входящих в него букв:

              

    Применяя  алгоритм Хаффмана к построенному вероятностному распределению, получим следующую схему кодирования для блоков длины N=2:

      

    Построенная схема имеет стоимость кодирования  одного блока C2 = 2,78, и стоимость кодирования одной буквы . Найдем энтропию H(P):

    H(P) = -(0,5 log0,5 + 0,4 log0,4 + 0,1 log0,1) ≈1,36.

Получаем H(P) ≈ 1,36 <

    2.4.5. Возможности сжатия при алфавитном кодировании, учитывающем

синтаксис языка сообщений. 

    Дополнительные  возможности для сжатия появляются при L B* , когда в качестве

сообщений могут  быть не любые последовательности символов, а только некоторые из

них.

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

    В качестве языка L рассмотрим множество слов в алфавите B = {b1 , b2 , b3 }, не содержащих диаграмму b1 b2 . Синтаксис этого языка описывается источником с двумя состояниями, изображенным на рис.2.4. 

 

Рис. 2.4. Источник, генерирующий сообщения, не содержащие диграмму b1b2. 

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

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

    Насколько эффективно можно использовать те или  иные свойства языка для сжатия информации при алфавитном кодировании?

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

    Определение 2.4. Пусть B = {b1 ,... , bm} и L B*. Буква bi называется фиктивной в L, если отображение α a', состоящее в замене bi пустым словом λ во всех вхождениях bi в α, таково, что из α,β L и a b следует a' b '. В противном случае буква bi называется существенной в L.

    Буквы bi и bj (i j) называются контекстно-различимыми в L, если отображение

  α a', состоящее в замене bi буквой bj во всех вхождениях bi в α, таково, что из α,β L и a b следует a' b' .

    Определение 2.5. Язык L называется неприводимым, если все его буквы

существенные  и попарно контекстно-неразличимы. В противном случае говорят, что L

допускает алфавитную редукцию.

    За  счет алфавитной избыточности можно  сжимать сообщения языка в  любое число 

Информация о работе Алфавитное кодирование