Реферат: Арифметическое кодирование. Кодирование длин повторений - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 26 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕНН ЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ К афедра РЭС Р еферат на тему: «Арифметическое кодирование. Кодирование длин повторений» МИНСК, 2009 Арифметическое кодирование Пpи аpифметическом кодиpовании, в от личие от рассмотренных нами методов, когда кодируемый символ (или группа символов) заменяется соответству ю щим им кодом, результат кодирования всего сообщения пpедставляется одним или парой вещественн ых чисел в интеpвале от 0 до 1 . По меpе к о диpования исходного текста отобpажающий его интеpвал уменьшается, а коли чество дес я тичных (или дво ичных) разрядов, служащих для его пpедставления, возpастает. Очеpедные симв олы входного текста сокpащают вели чину интеpвала исходя из значений их веpоятностей, опред е ляемых моделью. Более веpоятные символы делают это в меньшей степени, чем мене е веpоятные, и, следовательно, доба в ляют меньше разрядов к pезультату. Поясним идею арифметического кодирования на просте йшем примере. Пусть нам нужно закодировать следующую текстовую строку: РАДИ О ВИЗИР. Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет [0; 1). Алфавит кодируемого сообщения содержит следующие симв олы (б у квы): Р, А, Д, И, О, В, З . Определим количество (встречаемость, вероятность) каждого из символов алфавита в сообщении и назначим каждому из них интервал, про порционал ь ный его вероятнос ти. С учетом того, что в кодируемом слове всего 10 букв, п о лучим табл. 1 Таблица 1 Символ Веpоятность Интеpвал А 0.1 0 – 0.1 Д 0.1 0.1 – 0.2 В 0.1 0.2 – 0.3 И 0.3 0.3 – 0.6 З 0.1 0.6 – 0.7 О 0.1 0.7 – 0.8 Р 0.2 0.8 – 1 Располагать символы в таблице можно в любом порядке : по мере их появления в тексте, в алфавитном или по возрастанию вероятнос тей – это с о вершенно не при нципиально. Результат кодирования при этом будет разным, но эффект – од инаковым. Процедура кодирования Итак, перед началом кодирования исходный интервал с оставляет [0 – 1). После пpосмотpа пеpвого символа сообщения Р кодер сужает исхо д ный интеpвал до новог о - [0.8; 1), котоpый модель выделяет этому символу. Таким образом, после кодирования первой буквы результат кодиро вания будет нах о диться в и нтервале чисел [ 0.8 - 1). Следующим символом сообщения, поступающим в кодер, бу дет буква А . Есл и бы эта буква была первой в кодируемом сообщении, ей был бы отв е ден интервал [ 0 - 0.1 ), но она следует за Р и поэтому кодируется новым подынтервалом внутри уже выделенного для первой буквы , сужая его до вел и чины [ 0.80 - 0.82 ). Другими словами, ин тервал [ 0 - 0.1 ), выделенный для буквы А , располагается теперь внутри интервала, занимаемого пред ы дущим символом ( начало и конец нового и нтервала определяются путем прибавления к началу предыдущего интервал а произведения ширины пред ы дущего интервала на значения инт ервала, отведенные текущему символу ). В pезультате получим н о вый pабочий интеpв ал [0.80 - 0.82), т.к. пpедыдущий интеpвал имел шиpину в 0.2 единицы и одна десятая от н его есть 0.02. Следующему символу Д соответствует выделенный интервал [0.1 - 0.2), что пpименительно к уже имеющемуся рабочему интервалу [0.80 - 0.82) сужает его до величины [0.802 - 0.804). Следующим символом, поступающим на вход кодера, будет буква И с выделенным для нее фиксированным ин тервалом [ 0,3 – 0,6). Применител ь но к уже имеющемуся рабочему инт ервалу получим [ 0,8026 - 0,8032 ). Пpодолжая в том же духе, имеем: вначале [0.0 - 1.0) после пpосмотpа Р [0.8 - 1.0) А [0.80 - 0.82) Д [0.802 - 0.804) И [0.8026 - 0.8032) О [0.80302 - 0.80308) В [0.803032 - 0.803038) И [0.8030338 - 0.8030356) З [0.80303488 - 0.80303506) И [0.803034934 - 0.803034988) Р [0.8030349772 - 0.8030349880) Результат кодирования: интервал [0,8030349772 – 0,8030349880]. На самом д е ле, для однозначного декодирования теперь достаточно знать только одну границу интервала – нижнюю или вер хнюю, то есть результатом кодиров а ния может служить начало конечного интервала - 0,8030349772. Ес ли быть еще более точным, то любое число, заключенное внутри этого инте р вала, однозначно декодируется в исх одное сообщение. К примеру, это можно пр о верить с числом 0,80303498, у довлетворяющим этим условиям. При этом последнее число имеет меньшее чи сло десятичных разрядов, чем числа, с о ответствующие нижней и верхней границам интервала, и, след овательно может быть представлено меньшим числом двоичных разрядов. Нетрудно убедиться в том, что, чем шире конечный инт ервал, тем мен ь шим числом десятичных (и, следовательно, двоичных) разрядов он может быть представл ен. Ширина же интервала зависит от распределения вероятностей кодиру е мых символов – более ве роятные символы сужают интервал в меньшей степени и , следовательно, доб авляют к результату кодирования меньше бит. Покажем это на простом примере. Допустим, нам нужно закодировать следующую строку с имволов: A A A A A A A A A # , где вероятность буквы А составляет 0,9. Процедура кодир о вания этой строки и получаемый результат будут выгл ядеть в этом случае следующим образом: Входной символ Нижняя граница Верхняя граница 0.0 1.0 A 0.0 0.9 A 0.0 0.81 A 0.0 0.729 A 0.0 0.6561 A 0.0 0.59049 A 0.0 0.531441 A 0.0 0.4782969 А 0.0 0.43046721 А 0.0 0.387420489 # 0.3486784401 0.387420489 Результатом кодирования теперь может быть, к примеру, число 0.35 , цел и ком попадающее внутрь конечного интервала 0.3486784401 – 0.387420489. Для двоичного представления этого числа нам понадобится 7 бит (два де сятичных разряда соответствуют примерно семи двоичным ), тогда как для д воичного представления результатов кодирования из предыдущего прим е ра – 0,80303498 – нужно 27 бит !!! Декодирование Пpедположим, что все что декодер знает о тексте, – это конечный и н теpвал [0,8030349772 - 0,8030349880]. Декодеру, как и коде ру, известна также та б лица распределения выделенных алфавиту интервалов. Он сpазу же поним а ет, что пеpвый закодиpованный сим вол есть Р , так как результат кодирования цел и ком лежит в интеpвале [0.8 - 1), выделенном моделью си мволу Р согласно та б лице . Тепеpь повтоpим действия кодера: вначале [0.0 - 1.0); после пpосмотpа [0.8 - 1.0). Исключим из результата кодирования влияние теперь уже известного перв ого символа Р , для этого вычтем из результата кодирования нижнюю границу ди а пазона, отведенного для Р, – 0,8030349772 – 0.8 = =0,0030349772 – и разделим полученный результат на ширину ин тервала, отв е денного для Р, – 0.2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещает ся в интервал, отведенный для буквы А, – [0 – 0,1) , следовательно, вторым символом декодированной последов а тельности будет А . Поскольку теперь мы знаем уже две декодированные буквы - РА , иск лючим из итогового интервала влияние буквы А . Для этого выч тем из о с татка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А , то есть на 0,1. В результат е получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д , следовательно, очередная б у ква будет Д . Исключим из результата кодирования влияние буквы Д . Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Резул ьтат попадает в интервал, отведе н ный для буквы И , следо вательно, очередной декодированный символ – И , и так д а лее, пока не декодируем все символы: Декодируемое Символ Границы Шир и на число на выходе нижняя верхняя интерв а л а 0,8030349772 Р 0.8 1.0 0.2 0,015174886 А 0.0 0.1 0.1 0,15174886 Д 0.1 0.2 0.1 0,5174886 И 0.3 0.6 0.3 0,724962 О 0,7 0,8 0,1 0,24962 В 0,2 0,2 0,1 0,4962 И 0,3 0,6 0,3 0,654 З 0,6 0,7 0,1 0,54 И 0,3 0,6 0,3 0,8 Р 0,6 0,8 0,2 0.0 Конец декодирования Это основная идея арифметического кодирования, его практическая реализация несколько сложнее. Некоторые проблемы можно з аметить непосредс т венно из приведенного примера. Первая состоит в том, что декодеру нужно обязательно каким-либо обр а зом дать знать об окончании п роцедуры декодирования, поскольку остаток 0,0 может означать букву а или последовательность аа, аа а, аааа и т.д. Решить эту проблему мож но двумя способами. Во-первых, кроме кода данных можно сохранять число, представляющее с о бой размер кодируемого массива. Процесс декодирования в этом случае будет прекращен, как только массив на выходе декодера станет тако го ра з мера. Другой способ – включить в модель источника специальный символ конца б лока, например #, и прекращать декодирование, когда этот сим вол по я вится на выходе дек одера. Вторая проблема вытекает из самой идеи арифметичес кого кодирования и состоит в том, что окончательный результат кодирован ия – конечный интервал – станет и звестен только по окончании процесса кодирования. Сл е довательно, нельзя начать передачу закодированного сообщения, пока не получена последняя буква исходного сообщения и не определен окончательный интервал? На самом деле в этой задержке нет необходим о сти. По мере того, как интервал, предс тавляющий результат кодир о вания, сужается, старшие десятичные знаки его (или старшие бит ы, если число записывается в двоичной форме) перестают изменяться (посмо трите на приведенный пр и м ер кодирования). Следовательно, эти разряды (или биты) уже могут пер е даваться. Таким образом, передач а закодированной последовательности осуществл я ется, хотя и с некоторой задержкой, н о последняя незначительна и не зав и сит от размера кодируемого сообщения. И третья проблема – это вопрос точности представления. Из приведенн о го примера видно, что точн ость представления интервала (число десятичных разр я дов, требуемое для его представлени я) неограниченно возрастает при увелич е нии длины кодируемого сообщения. Эта проблема обычно реша ется использованием арифметики с конечной разрядностью и отслеживание м переполнения ра з ряднос ти регистров. Кодирование длин повторений Кодирование длин участков (или повторений) может быть достаточно эффект ивным при сжатии двоичных данных, например, черно-белых факсимильных изо бражений, черно-белых изображений, содержащих множес т во прямых линий и однородных участк ов, схем и т.п. Кодирование длин п о вторений является одним из э лементов известного алгоритма сжатия из о бражений JPEG. Идея сжатия данных на основе кодирования длин повторений состоит в том, что вместо кодирования собственно данных подвергаются к о дированию числа, соответствующие д линам участков, на которых данные сохраняют неизменное значение. Предположим, что нужно закодировать двоичное (двухцветное) изображ е ние размером 8 х 8 элеме нтов, приведенное на рис. 1. Рис. 1 Просканируем это изображение по строкам (двум цвет ам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных X= (0111000011110000000100000001000000010000000111100011110111101111) длиной 64 бита (скорость исходного кода составляет 1 бит на элемент изобр а жения). Выделим в в екторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирую щая последовательность длин участ ков - положительных целых чисел, соответствующих исходному ве к тору данных X, - будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4). Теперь эту последовательность, в которой заметна опр еделенная повт о ряемость (еди ниц и четверок гораздо больше, чем других символов), можно закодировать каким-либо статистическим кодом, например, кодом Хаффмена без п а мяти, имеющим таблицу кодирования ( табл. 2) Таблица 2 К одер Длина участка Кодов ое слово 4 0 1 10 7 110 3 111 Для того, чтобы указать, что кодируемая последова тельность начинается с нуля, добавим в начале кодового слова префиксный символ 0. В результате получим кодовое слово B (r) = (0100011010110101101011001110100100) длиной в 34 бита, то есть результирующая скорость кода R состави т 34/64, или немногим более 0,5 бита на элемент изображения. При сжатии изобр а жений большего размера и содержащих множество повторяющихся элеме н тов эффективность сжатия может оказаться существенно более высокой. Ниже приведен другой пример использования кодиров ания длин повт о рений, когд а в цифровых данных встречаются участки с большим количес т вом нулевых значений. Всякий раз, ко гда в потоке данных встречается “ ноль ”, он кодируется двумя числами. Первое - 0, являющееся флагом нач ала кодирования длины пот о ка нулей, и второе – количество нулей в очередной группе. Если среднее число нулей в группе больше двух, б удет иметь место сжатие. С другой стороны, большое число отдельных нулей может привести даже к увеличению размера к о дируемого файла: Еще одним простым и широко используемым для сжатия изображений и звуковых сигналов методом неразрушающего кодирования яв ляется метод дифференциального кодирования.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Что вас согревает? Теплый плед? Любовь?
А меня вот ноутбук, который лежит у меня на коленях...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Арифметическое кодирование. Кодирование длин повторений", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru