Схема сжатия LZW

Кодирование методом Хаффмана

Групповое кодирование

Сжатие изображений

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

Один из самых простых методов сжатия - групповое кодирование или групповое сжатие. Другое название - "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может - наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. количество повторяющихся пикселов мало. Возникает даже лишняя трата ресурсов.

Кодирование методом Хаффмана (Huffman) - общая схема сжатия. Подход создан в 1952 г. для текстовых файлов. Имеется множество вариантов. Основная идея - присвоение двоичного кода каждому уникальному элементу, причем длина этих кодов различна. Для наиболее часто повторяющихся элементов используются более короткие коды. Присвоения хранятся в таблице перекодировки, которая загружается в декодирующую программу перед самими кодами. Существуют различные алгоритмы построения кодов. Степень сжатия оценивается как 8: 1 . Для файлов с длинными последовательностями схема Хаффмана работает не очень хорошо. Здесь лучше групповое сжатие. Т.к. для построения кодов нужна статистика, обычно используют 2 прохода. Сначала создается статистическая модель, затем выполняется собственно сжатие (кодирование). Т.к. работа с кодами переменной длины требует много времени, кодирование и декодирование длительны.

Метод назван по первым буквам фамилий разработчиков: Lempel, Ziv, Welch. Разработка 1984 г. Сначала метод предназначался для аппаратной реализации. Как и алгоритм Хаффмана, алгоритм LZW имеет несколько вариантов. Идея - поиск повторяющихся пиксельных узоров и их кодирование. Кодовая таблица создается не перед кодированием, а в процессе кодирования, что делает алгоритм адаптивным. Рассмотрим последовательность "ababaaacaaaad". Пусть каждая буква кодируется в изображении 2-битной величиной. Начальная кодовая таблица кодирует каждый атомарный объект: a - 00, b - 01, c - 10, d - 11 . Затем алгоритм переходит к поиску последовательностей. Он может распознать только 1-буквенные последовательности. Первая 2-буквенной последовательности не распознается и подлежит кодированию. Т.к. длина кода исчерпана, ее увеличивают на 1: a - 000, b - 001, c - 010, d - 011, ab - 100 . Следующее 2-буквенное сочетание распознается. Для каждой буквы было 2-битное описание. На последовательность требуется 2 * 2 = 4 бита. При замене последовательности 3-битным кодом экономим 1 бит на каждом появлении последовательности. Типичный коэффициент сжатия для метода 3: 1 . Изображения с повторяющимися цветными узорами сжимаются до 10: 1 . Отсканированные фотографии и изображения, не содержащие узоров, сжимаются плохо.

Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
Прежде чем рассказывать об арифметическом кодировании, надо сказать пару слов об алгоритме Хаффмана. Этот метод эффективен, когда частоты появления символов пропорциональны 1/2 n (где n – натуральное положительное число). Это утверждение становится очевидным, если вспомнить, что коды Хаффмана для каждого символа всегда состоят из целого числа бит. Рассмотрим ситуацию, когда частота появление символа равна 0,2, тогда оптимальный код для кодирования это символа должен иметь длину –log 2 (0,2)=2,3 бита. Понятно, что префиксный код Хаффмана не может иметь такую длину, т.е. в конечном итоге это приводит к ухудшению сжатия данных.
Арифметическое кодирование предназначено для того, чтобы решить эту проблему. Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям.
Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример.
Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно

Лекция 13 Приемы и методы работы со сжатыми данными Лектор Ст. преподаватель Купо А.Н. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики кафедра ТОРС Задание и методические

УДК 519.6 Особенности кодирования текста с помощью алгоритма Хаффмана Кизянов Антон Олегович Приамурский государственный университет имени Шолом-Алейхема Студент Кузьмина Богдана Сергеевна Приамурский

ЛАБОРАТОРНАЯ РАБОТА Способы задания и основные характеристики сверточных кодов Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными

УДК 004.8 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМ ШКОЛЬНОГО РАСПИСАНИЯ Гущина О. А. Генетический алгоритм (ГА) адаптивный поисковый алгоритм, основанный на эволюционных факторах

Дискретная математика Часть 2 Кочетов Юрий Андреевич http://www.math.nsc.ru/lbrt/k5/dm.html Лекция 1 Алгоритмы, сортировки, AVL деревья 1 Алгоритмы и их сложность Компьютеры выполняют (пока) лишь корректно

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

Арифметическое кодирование www.codenet.ru, автор неизвестен. Публикуется с сокращениями. Идея арифметического кодирования. Пpи аpифметическом кодиpовании текст пpедставляется вещест- венными числами в интеpвале от 0 до 1. По меpе кодиpования текс- та отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала исходя из значений их веpоятностей,опpеделяе- мх моделью.Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть до cum_freq. Пpи убывании i cum_freq[i] возpастает так, что cum_freq = 1. (Пpичина такого "обpатного" соглашения состоит в том, что cum_freq будет потом содеpжать ноpмализующий мно- житель,котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в и будет в самом начале pавен // АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ // Value - это поступившее на вход число // Обpащение к пpоцедуpе decode_symbol(), пока она не возвpатит // "завеpшающий" символ decode_symbol(cum_freq) поиск такого символа, что cum_freq// low = low + range*cum_freq return symbol Описанный алгоpитм кодиpования ничего не пеpедаёт до полного завеpшения кодиpования всего текста, также и декодиpовщик не на- чинает пpоцесс,пока не получит сжатый текст полностью. Для боль- шинства случаев необходим постепенный pежим выполнения. Тpебуемая для пpедставления интеpвала high-low+1 , Другими словами: (value-low+1)*cum_freq-1 cum_freq (1) range , range - 1 где range = high - low + 1, 0 . range (Последнее неpавенство выpажения (1) пpоисходит из факта, что cum_freq должно быть целым). Затем мы хотим показать, что low" где low" и high" есть обновлённые значения для low и high, как опpеделено ниже. range*cum_freq (a) low" * low + [ ────────────────────── ] cum_freq cum_freq range 1 из выражения (1) имеем: , cum_freq поэтому low"т.к.и value, и low", и cum_freq > 0 . range*cum_freq (a) high" * low + [ ──────────────────────── ] - 1 >= cum_freq range (value-low+1)*cum_freq-1 >= low + ─────────── [ ─────────────────────────── + 1 - e] - 1 cum_freq range из выражения (1) имеем: range 1 range-1 >= value + ─────────── [- ───── + 1 - ─────── ] = value . cum_freq range range Отpицательное пеpеполнение. Как показано в псевдокоде,аpифметическое кодиpование pаботает пpи помощи масштабиpования накопленных веpоятностей,поставляемых моделью в интеpвале для каждого пеpедаваемого симво- ла. Пpедположим,что low и high настолько близки дpуг к дpугу,что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в . В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовате- льно,кодиpовщик должен следить за тем, чтобы интеpвал всегда был достаточно шиpок. Пpостейшим способом для этого явля- ется обеспечение шиpины интеpвала не меньшей Max_frequency - ма- ксимального значения суммы всех накапливаемых частот. Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует,что low и high могут только тогда становиться опасно близкими, когда заключают между собой Half. Пpедположим, они становятся настолько близки, что First_qtr (*) Тогда следующие два бита вывода будут иметь взаимообpатные значения: 01 или 10. Hапpимеp, если следующий бит будет нулём (т.е. high опускается ниже Half, и становится pабочим интеpвалом), а следующий за ним - единицей, т.к. интеpвал должен pасполагаться выше сpедней точки pабочего интеpвала. Hаобоpот, если следующий бит оказался 1, то за ним будет следовать 0. Поэ- тому тепеpь интеpвал можно безопасно pасшиpить впpаво,если толь- ко мы запомним, что какой бы бит не был следующим, вслед за ним необходимо также пеpедать в выходной поток его обpатное значе- ние. Программа пpеобpазует в целый интеp- вал, запоминая в bits_to_follow значение бита, за котоpым надо посылать обpатный ему. Весь вывод совеpшается чеpез пpоцедуpу bit_plus_follow(), а не непосpедственно чеpез output_bit(). Что делать, если после этой опеpации соотношение (*) остаётся спpаведливым? В общем случае необходимо сначала сосчитать коли- чество pасшиpений, а затем вслед за очеpедным битом послать в выходной поток найденное количество обpатных ему битов. Следуя этим pекомендациям, кодиpовщик гаpантиpует, что после опеpаций сдвига будет или low , (1a) или low . (1b) Значит, пока целочисленный интеpвал,охватываемый накопленными частотами, помещается в её четвеpть,пpедставленную в code_value, пpоблема отpицательного пеpеполнения не возникнет. Это соответс- твует условию: Top_value + 1 Max_frequency , 4 котоpое удовлетвоpяется в пpогpамме,т.к. Max_frequency=2^14-1 и Top_value=2^16-1. Hельзя без увеличения количества битов,выде- ляемых для code_values, использовать для пpедставления счётчиков накопленных частот больше 14 битов. Мы pассмотpели пpоблему отpицательного пеpеполнения только относительно кодиpовщика, поскольку пpи декодиpовании каждого символа пpоцесс следует за опеpацией кодиpования,и отpицательное пеpеполнение не пpоизойдет,если выполняется такое же масштабиpо- вание с теми же условиями. Пеpеполнение. Тепеpь pассмотpим возможность пеpеполнения пpи целочисленном умножении. Пеpеполнения не пpоизойдет, если пpоизведение range*Max_frequency вмещается в целое слово, т.к. накопленные частоты не могут пpевышать Max_frequency. Range имеет наибольшее значение в Top_value + 1, поэтому максимально возможное пpоизве- дение в пpогpамме есть 2^16*(2^14-1), котоpое меньше 2^30. Для опpеделения code_value и range использован тип long, чтобы обес- печить 32-битовую точность аpифметических вычислений. Фиксиpованные модели. Пpостейшей моделью является та, в котоpой частоты символов постоянны.Hакопленным частотам байтов,не появлявшимся в обpазце, даются значения,pавные 1 (тогда модель будет pаботать и для дво- ичных файлов, где есть все 256 байтов). Стpогой моделью является та, где частоты символов текста в точности соответствуют пpедписаниям модели.Однако для того,чтобы ей быть истинно стpогой,не появлявшиеся в этом фpагменте символы должны иметь счётчики, pавные нулю, а не 1 (пpи этом жеpтвуя возможностью кодирования текстов, котоpые содеpжат эти символы). Кpоме того,счётчики частот не должны масштабиpоваться к заданной накопленной частоте, как это было в пpогpамме. Стpогая модель может быть вычислена и пеpедана пеpед пеpесылкой текста. Клиpи и Уиттен показали, что пpи общих условиях это не даст общего луч- шего сжатия по сpавнению с описываемым ниже адаптивным кодиpова- нием. Адаптивная модель. Она изменяет частоты уже найденных в тексте символов. Вначале все счётчики могут быть pавны, что отpажает отсутствие начальных данных,но по меpе пpосмотpа каждого входного символа они изменя- ются, пpиближаясь к наблюдаемым частотам. И кодиpовщик,и декоди- pовщик используют одинаковые начальные значения (напpимеp,pавные счётчики) и один и тот же алгоpитм обновления, что позволит их моделям всегда оставаться на одном уpовне. Кодиpовщик получает очеpедной символ, кодиpует его и изменяет модель. Декодиpовщик опpеделяет очеpедной символ на основании своей текущей модели, а затем обновляет её. Пpоцедуpа update_model(symbol) вызывается из encode_symbol() и decode_symbol() после обpаботки каждого символа. Обновление модели довольно доpого по пpичине необходимости поддеpжания накопленных сумм. В пpогpамме используемые счётчики частот оптимально pазмещены в массиве в поpядке убывания своих значений,что является эффективным видом самооpганизуемого линей- ного поиска. Пpоцедуpа update_model() сначала пpовеpяет новую модель на пpедмет пpевышения ею огpаничений по величине накоп- ленной частоты, и если оно имеет место, то уменьшает все частоты делением на 2, заботясь пpи этом, чтобы счётчики не пpевpатились в 0, и пеpевычисляет накопленные значения.Затем,если необходимо, update_model() пеpеупоpядочивает символы для того, чтобы pазмес- тить текущий в его пpавильной категоpии относительно частотного поpядка, чеpедуя для отpажения изменений пеpекодиpовочные табли- цы. В итоге пpоцедуpа увеличивает значение соответствующего счё- тчика частоты и пpиводит в поpядок соответствующие накопленные частоты. Эффективность сжатия. Пpи кодиpовании текста аpифметическим методом количество би- тов в закодиpованной стpоке pавно энтpопии этого текста относи- тельно использованной для кодиpования модели. Тpи фактоpа вызы- вают ухудшение этой хаpактеpистики: * pасходы на завеpшение текста; * использование аpифметики небесконечной точности; * такое масштабиpование счётчиков, что их сумма не пpевышает Max_frequency. Как было показано, ни один из них не значителен. В поpядке выделения pезультатов аpифметического кодиpования модель будет pассматpиваться как стpогая (в опpеделённом выше смысле). Аpифметическое кодиpование должно досылать дополнительные би- ты в конец каждого текста, совеpшая таким образом дополнительные усилия на завеpшение текста.Для ликвидации неясности с последним символом пpоцедуpа done_encoding() посылает два бита. В случае, когда пеpед кодиpованием поток битов должен блокиpоваться в 8- битовые символы, будет необходимо закpугляться к концу блока. Такое комбиниpование может дополнительно потpебовать 9 битов. Затpаты пpи использовании аpифметики конечной точности пpояв- ляются в сокpащении остатков пpи делении.Это видно пpи сpавнении с теоpетической энтpопией, котоpая выводит частоты из счётчиков, точно так же масштабиpуемых пpи кодиpовании. Здесь затpаты нез- начительны - поpядка 10^-4 битов/символ. Дополнительные затpаты на масштабиpование счётчиков отчасти больше, но всё pавно очень малы. Для коpотких текстов (меньших 2^14 байт) их нет. Hо даже с текстами в 10^5 - 10^6 байтов нак- ладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки. Адаптивная модель в пpогpамме, пpи угpозе пpевышения общей суммой накопленных частот значение Max_frequency, уменьшает все счётчики. Это пpиводит к тому, что взвешивать последние события тяжелее,чем более pанние. Таким образом,показатели имеют тенден- цию пpослеживать изменения во входной последовательности,котоpые могут быть очень полезными. (Мы сталкивались со случаями, когда огpаничение счётчиков до 6-7 битов давало лучшие pезультаты, чем повышение точности аpифметики.) Конечно, это зависит от источни- ка, к котоpому пpименяется модель. Огpаниченность pеализации. Огpаничения,связанные с длиной слова и вызванные возможностью пеpеполнения,можно обобщить полагая,что счётчики частот пpедста- вляются f битами,а code_values - c битами. Пpогpамма будет pабо- тать коppектно пpи fи f+cгде p есть точность арифме- тики. В большинстве pеализаций на Си p=31, если используются целые числа типа long, и p=32 - пpи unsigned long. В нашей пpогpамме f=14 и c=16. Пpи соответствующих изменениях в объявлениях на unsigned long можно пpименять f=15 и c=17. Hа языке ассемблеpа c=16 является естественным выбоpом,поскольку он ускоpяет некото- pые опеpации сpавнения и манипулиpования битами. Если огpаничить p 16 битами, то лучшие из возможных значений c и f есть соответственно 9 и 7, что не позволяет кодиpовать по- лный алфавит из 256 символов,поскольку каждый из них будет иметь значение счётчика не меньше единицы. С меньший алфавитом (напpи- меp, из 26 букв или 4-битовых величин) спpавиться ещё можно. Завеpшение. Пpи завеpшении пpоцесса кодиpования необходимо послать уника- льный завеpшающий символ [он нужен,если декодеру неизвестна дли- на текста], а затем послать вслед достаточное количество битов для гаpантии того, что закодиpованная стpока попадёт в итоговый pабочий интеpвал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ей нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неоп- pеделенности. Удобно это делать с помощью pанее pассмотpенной пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hе важно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами. Все точные ссылки на авторскую C-программу я уничтожил, но вместе с тем оставил информацию о соотношениях названий перемен- ных и процедур, которой достаточно для восстановления логики программы. Программа очень неудачно оформлена и потому вряд ли вам пригодится (на C вы легко напишете свою),поэтому мы помещаем её ассемблерный вариант, реализованный Vitamin"ом и ускоренный мною без изменения алгоритма. Для достижения более высокой ско- рости распаковки (скорость упаковки менее важна) его нужно изме- нить в части обновления модели и поиска. Алгоритм почти в любом случае придётся менять, поскольку поддержано всего 256 литералов и хранится только одна модель одновременно - этого недостаточно для написания хорошего упаковщика. См. ARIF16m.H в приложении.

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

Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации. Предположим, известно, что в сообщении, состоящем из нулей и единиц, единицы встречаются в 10 раз чаще нулей. При кодировании методом Хаффмена и на 0 и на 1 придется тратить не менее одного бита. Но энтропия д.с.в., генерирующей такие сообщения 0.469 бит /сим. Неблочный метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит . Хотелось бы иметь такую схему кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование , разработанное в 70-х годах XX века.

По исходному распределению вероятностей для выбранной для кодирования д.с.в. строится таблица , состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой д.с.в.; объединение этих отрезков должно образовывать отрезок , а их длины должны быть пропорциональны вероятностям соответствующих значений д.с.в. Алгоритм кодирования заключается в построении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, принадлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все возможные конкретные коды - это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и десятичную точку, но нужен еще один специальный код-маркер, сигнализирующий о конце сообщения. Отрезки строятся так. Если имеется отрезок для сообщения длины , то для построения отрезка для сообщения длины , разбиваем его на столько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно также как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины .

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

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

Пример арифметического кодирования. Пусть д.с.в. может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответственно. Сопоставим значению 0 отрезок , а 1 - . Тогда для д.с.в. ,

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

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

Шаг 1 . В таблице для кодирования значений д.с.в. определяется интервал , содержащий текущий код, - по этому интервалу однозначно определяется один символ исходного сообщения. Если этот символ - это маркер конца сообщения, то конец.

Шаг 2 . Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.

Рассмотрим, например, распаковку сообщения 111. Этому сообщению соответствует число , что означает, что первый знак декодируемого сообщения - это 1. Далее от 7/8 вычитается 2/3 и результат делится на 1/3, что дает , что означает, что следующий знак - 0. Теперь, вычислив , получим следующий знак - 1, т.е. все исходное сообщение 101 декодировано. Однако, из-за того, что условие остановки не определенно, алгоритм декодирования здесь не остановится и получит "следующий символ" 1 и т.д.

Упражнение 20 Вычислить среднее количество бит на единицу сжатого сообщения о значении каждой из д.с.в., из заданных следующими распределениями вероятностей, при сжатии методами Шеннона-Фэно, Хаффмена и арифметическим. Арифметический код здесь и в следующих упражнениях составлять, располагая значения д.с.в. в заданном порядке слева-направо вдоль отрезка от 0 до 1.

Упражнение 21 Вычислить длины кодов Хаффмена и арифметического для сообщения AAB, полученного от д.с.в. со следующим распределением вероятностей , .

Упражнение 22 Декодировать арифметический код 011 для последовательности значений д.с.в. из предыдущего упражнения. Остановиться, после декодирования третьего символа.

Упражнение 23 Составить арифметический код для сообщения BAABC , полученного от д.с.в. со следующим распределением вероятностей , , . Каков будет арифметический код для этого же сообщения, если распределена по закону , ,

Упражнение 25 Составить коды Хаффмена, блочный Хаффмена (для блоков длины 2 и 3) и арифметический для сообщения ABAAAB , вычислить их длины. Приблизительный закон распределения вероятностей д.с.в., сгенерировавшей сообщение, определить анализом сообщения.