рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Арифметическое кодирование.

Арифметическое кодирование. - раздел Философия, Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников Алгоритм Хаффмана , Рассмотренный Ранее, Не Может Передавать На Каждый Символ...

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

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

Одним из таких алгоритмов является арифметическое кодирование, представленное в 70-х годах XX века.

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

Особенностью арифметического кодирования является то, что для отображения последовательности символов на интервале [0,1] используются относительные частоты.

Если, например, символ А а сообщении BANANANBAB (10 символов) встречается 4 раза, то его относительная частота =0,4 и, таким образом, определяют всех символов в сообщении:, ,

Результатом такого отображения является сжатие символов (посимвольное сжатие) в соответствии с их вероятностями.

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

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

Эффективность арифметического кодирования растет с увеличением длины сжимаемого сообщения (для кодирования Шеннона и Хаффмана этого не происходит).

Алгоритм арифметического кодирования заключается в построении отрезков (интервалов), однозначно определяющих заданную последовательность символов в соответствии с их вероятностями (относительными частотами появления). Объединение всех отрезков, пересекающихся только в граничных точках, для вероятностей каждого символа должно образовывать формальный интервал [0,1]. Для последнего полученного интервала, соответствующего последнему символу в сообщении, находится число, принадлежащее его внутренней части. Это число и будет двоичным кодом для рассматриваемой последовательности.

Пример арифметического кодирования:

Пусть алфавит источника состоит из 2-х символов a и b с соответствующими вероятностями p(a) =, p(b) = . Необходимо закодировать сообщение {aba}.

Рассмотрим интервал [0,1] и разобьем его на отрезки, соответствующие вероятностям [0,2/3] и [2/3,1]. Поступающий символ попадет только в один из этих отрезков, который снова разобьем на части, пропорциональные вероятностям обоих символов алфавита и т.д. до последнего символа в алфавите.

 

Шаг кодирования Поступающий символ Интервал
нет [ 0,1 ]
a [ ]
b [ ]
a

 

 

1.

       
 
b
 
a
 

 


2.

 
 

 

 


1. ,

2. ,

3.

 

3.

           
 
 
   
b
 
a
 

 

 


1. ,

2. ,

3.

Внутри последнего интервала выберем число 16/32=1/2, которое в двоичном представлении и будет кодом сообщения aba -> 0.1 (0 и десятичную точку не учитывают) => получим длину кода на символ <1 бит.

Декодирование арифметического кода производится по его значению и тем же интервалам до восстановления исходного сообщения.

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

 

 

– Конец работы –

Эта тема принадлежит разделу:

Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников

Тамбовский государственный технический университет... Кафедра Информационные системы... Дисциплина Теория информации...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Арифметическое кодирование.

Что будем делать с полученным материалом:

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

Все темы данного раздела:

Тамбов 2010
Тема №4: Оптимальное (эффективное) кодирование источников. 4.1. Понятие кодирования. Кодовое дерево. В процессе кодирования каждая буква и

Теорема кодирования источников. Неравенство Крафта. Префиксный код.
Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника: Для любого дискретного источника без памяти X с конечным алфавитом

Методы оптимального кодирования. Сжатие данных.
Процедуру оптимального кодирования часто называют сжатием данных. Таким образом задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимальн

Метод кодирования Шеннона - Фано.
Буквы исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается так, чтобы суммарные вероятности двух подмножеств были примерно равными

Метод кодирования Хаффмана.
Этот метод кодирования всегда дает оптимальный код, т.е. получаемая является минимальной. Буквы алфавит

Алгоритм универсального кодирования методом Лемпела-Зива.
Этот метод относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный, но более практический характер.

Особенности программ-архиваторов.
Если коды алгоритмов типа LZ передать для кодирования адаптивному алгоритму Хаффмана или арифметическому, то полученный двухшаговый алгоритм даст результат сжатия, подобный случайным программам: GZ

Сжатие с потерями.
Сжатие с потерями используется в основном для трех видов данных: 1.Полноцветная графика. 2. Звук. 3. Видеоинформация. Сжатие с потерями обычно происходит в два э

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги