Лекция 5. Комплексные методы сжатия без потерь
Курс “Теория информации и кодирования”

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

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

5.1 Подходы к созданию и оценке комплексных методов сжатия

Статистическое и контекстное сжатие
Современные методы сжатия сообщений без потерь информации стремятся использовать все важные закономерности, которые обычно существуют в сообщениях (рис.5.1):
  • статистические закономерности выражаются в различиях вероятностей знаков. Они характерны для большинства сообщений, то-есть, универсальны. Вторая универсальная категория закономерностей — связи между знаками в сообщениях (например, между буквами в словах): появление определенного знака зависит от его предыстории или, иначе говоря, от контекста. Комплексные методы сжатия учитывают как статистические, так и контекстные закономерности;
  • в существующих комплексных методах сжатия использование упомянутых закономерностей реализуется в два этапа: сначала выполняется контекстное сжатие (то-есть, кодирование цепочек соседних знаков), а затем — статистическое сжатие полученных на первом этапе данных;
  • контекстное сжатие обычно связано с некоторым обобщением характеристик исходных сообщений. Например, повторяющиеся слова можно компактно представить ссылками на них в предыдущем тексте. Каждая из таких ссылок может включать номер первой буквы слова в тексте и количество букв в слове. Теперь вместо громадного множества слов описание источника должно включать лишь числовые характеристики ссылок. Очевидно, что при этом оно значительно обобщается и упрощается. Такое обобщенное описание уместно назвать “информационной моделью источника”. Соответственно, этап контекстного сжатия часто называют также “моделированием источника”;
  • обобщающий характер контекстного сжатия очень важен для сжатия статистического. Если его непосредственное применение ограничивалось из-за разнообразия исходных алфавитов и статистик, то теперь широкий класс источников сообщений может успешно сжиматься одним статистическим кодером (например, статистические характеристики ссылок для текстов на разных европейских языках достаточно близки). Все это объясняет широкое распространение двухэтапной схемы комплексного сжатия сообщений.

Направления разработки комплексных методов
В современной практике используется несколько принципиально различных подходов к контекстному сжатию и, соответственно, к формированию комплексных методов (рис.5.2):
  • простейшим и очень распространенным (хотя и не универсальным в строгом смысле) является метод сжатия однородных цепочек знаков. Такой метод известен под названием «кодирование длин серий» run-length encoding (RLE). Он предполагает замену серии одинаковых знаков парой <знак, число повторений>. В дальнейшем для значений счетчиков повторов может выполняться статистическое сжатие, хотя на практике такое решение используется нечасто. Разумеется, применение данного подхода ограничено сообщениями, где однородные цепочки встречаются часто (как в факсах или файлах некоторых графических форматов). Однако, он широко используется также в качесте вспомогательного (например, для обработки результатов моделирования источников). ;
  • среди универсальных подходов, пригодных для любых типов сообщений, наибольшее распространение получил так называемый «словарный» метод. Он основан на замене ранее встречавшихся цепочек знаков, - например, слов, - короткими ссылками на их предшественников в уже обработанной части текста (мы упоминали данный подход выше). Cуществует большое разнообразие способов поиска повторяющихся цепочек, которые применяются в многочисленных версиях метода. Сатистическое сжатие здесь может выполняться для числовых параметров ссылок. Метод предложен Лемпелем и Зивом и потому в обозначениях различных его версий в качестве префикса используются буквы LZ;
  • еще одно направление часто называют «прогнозным». Здесь модель источника включает набор повторяющихся цепочек знаков с данными о количестве повторений (в общем случае отдельный знак тоже рассматривается как элементарная цепочка). Для эффективного статистического сжатия метод предусматривает прогнозирование вероятностей появления разных знаков в каждой следующей позиции и постоянную корректировку кодовой таблицы исходя из меняющегося прогноза. Метод обычно обозначают аббревиатурой PPM - Prediction by Partial Matching — предсказание по частичному совпадению;
  • последнее направление, которое принято называть “сортировочным” или “блочно-сортирующим”, предусматривает обработку блоков данных сообщения. Благодаря специальному преобразованию, предложенному Барроузом и Уиллером (Burrows-Wheeler transform - BWT ), все одинаковые знаки, встретившиеся в разных позициях блока, собираются в однородные цепочки. В дальнейшем может быть использован метод RLE или статистическое сжатие. Последнее оказывается наиболее эффективным, если предварительно применить преобразование MTF (move-to-front, движение к началу), в результате которого чаще встречающиеся знаки получают меньшие номера, а все знаки в цепочке кроме первого заменяются нулями.

В дальнейшем мы детально рассмотрим все упомянутые здесь методы.

Эффективность сжатия
Эффективность сжатия сообщений характеризуется рядом факторов (рис.5.3):
  • качество оценивается прежде всего по степени сжатия (показателем здесь обычно служит отношение полученного объема кода к исходному объему в процентах). Однако, на практике важны также скорость и необходимый объем памяти. При этом требования по скорости и памяти могут существенно различаться для сжатия (упаковки) и восстановления (распаковки) сообщений. В таком случае говорят об асимметрии алгоритма по этим параметрам;
  • требования к показателям эффективности, как правило, противоречивы. Наилучшие показатели плотности сжатия достигаются обычно за счет более трудоемкой обработки и при использовании больших объемов памяти. Уместный компромисс зависит от области применения. Например, в системах реального времени предпочтение отдается скорости, а при массовом архивировании данных — плотности;
  • описанные выше универсальные методы сжатия имеют типичные особенности по показателям эффективности. “Cловарный” метод характеризуется максимальным быстродействием при приемлемой плотности сжатия, он также наиболее требователен к памяти. “Прогнозный” метод, напротив, медлен, но экономичен по памяти, при этом он обеспечивает максимальную степень сжатия для текстовых данных (для других данных это не всегда так). «Сортировочный» метод занимает промежуточное положение по всем показателям. При этом с точки зрения пользователя программ архиваторов различия в эффективности методов не слишком заметны;
  • эффективность сжатия зависит не только от используемого метода, но и от его программной реализации: один и тот же метод в разных программах-архиваторах может давать существенно разные показатели.

Кодирование длин серий RLE
В этом разделе мы также детально рассмотрим наиболее простой способ контекстного сжатия — кодирование однородных цепочек знаков. Рис.5.4 иллюстрирует примеры его применения:
  • в случае А способ кодирования RLE используется в самом простом варианте. В примере 6 однородных цепочек суммарной длиной 32 знака заменяются шестью парами «повторитель+знак», что позволяет сократить длину кода до 12 байт;
  • однако, на практике цепочки повторяющихся знаков могут чередоваться с одиночными знаками. В таком случае эффективность описанного простого решения резко снижается. Так, в случае Б на рисунке 5.4 исходной цепочке из 12 знаков соответствует код длиной 14 байтов;
  • усовершенствованное решение показано для случая В. Здесь для кодирования однородной цепочки знаков используется условно положительное значение повторителя (старший разряд байта равен 0). Если же в сообщение включается цепочка разнородных знаков, ее длина (до начала следующей однородной цепочки) кодируется условно отрицательным повторителем (старший разряд байта равен 1). В примере длина кода составит уже не 14, а 10 байт. Платой за такую возможность является сокращение предельной длины цепочки с 256 знаков до 128. Однако, на практике столь длинные однородные цепочки знаков встречаются редко.

Напомним, что метод RLE кодирования используется при передаче факсов и встроен в отдельные графические форматы (в частности, в формат pcx). Однако даже более важным является частое применение данного кода как вспомогательного элемента различных методов сжатия, с которыми мы познакомимся в дальнейшем.

Контрольные вопросы
1) Какие основные виды закономерностей в появлении знаков сообщений учитывают современные методы сжатия. В какой последовательности они учитываются.
2) Поясните термин “моделирование источника”. В чем состоит преимущество предварительной контекстной обработки для применения статистического сжатия.
3) Перечислите основные направления разработки комплексных методов сжатия и кратко охарактеризуйте их подходы, опираясь на рис.5.2.
4) Назовите основные показатели эффективности сжатия сообщений. В чем проявляется их противоречивость.
5) Сравните основные виды комплексных методов сжатия с точки зрения показателей эффективности.
6) Охарактеризуйте метод кодирования длин серий однотипных знаков RLE. Опираясь на рис.5.4 поясните простейший и усовершенствованный способы такого кодирования.


5.2 Словарные методы сжатия. Семейство алгоритмов LZ*

Способ «скользящего окна»
Напомним, что словарные методы обеспечивают сжатие в основном за счет замены повторяющихся цепочек знаков более короткими ссылками на ранее встретившиеся цепочки, которые хранятся в специальном “словаре”. Наибольшее распространение получил способ, где словарь представляет собой «окно», перемещающееся по тексту сообщения (рис.5.5). При этом:
  • словарь заполняется по мере обработки сообщения. Это похоже на перемещения рамки, которая движется от начала текста к его концу и внутрь которой попадают несколько сотен или тысяч знаков. Поиск повторяющихся цепочек ведется только внутри рамки (словаря) и знаки, оказавшиеся за ее левой границей “забываются”. В начале рамки (у правой границы) имеется узкая “прорезь” “буфер” для знаков, чей код подлежит сжатию (обычно их число не велико — например, от 16 до 64);
  • кодер выбирает цепочку знаков из буфера и пытается найти совпадающую с ней в словаре. Если это удается, то содержание буфера можно заменить короткой ссылкой на фрагмент словаря. Иначе Кодер постепенно укорачивает искомую цепочку и повторяет поиск. Если даже короткие цепочки в словаре не находятся, кодер передает эту часть сообщения по отдельным знакам. В любом случае все обработанные знаки пополняют словарь, одновременно из него удаляются знаки «устаревшие». С ростом объема словаря растет и вероятность нахождения совпадающих цепочек знаков, однако при этом время поиска быстро увеличивается;
  • сжатый код сообщения помещается в архивный файл. Он включает коды ссылок на найденные цепочки в словаре. Такая ссылка формата [d,l] включает номер первого знака d (distance) и длину цепочки l (length). В словарь также попадают стандартные коды знаков для случаев, когда цепочки в словаре не обнаруживались. Чтобы различать эти два типа кодов, они предваряются битовым префиксом (0 для кода знака и 1 для кода цепочки). Например, если объем буфера составляет 32 знака, то l=log232=5 бит, а при объеме словаря 1024 знака d=log21024=10 бит. Вместе с битовым префиксом длина кода цепочки составит 10+5+1=16 бит. При этом длина кода знака с учетом префикса составит 8+1 = 9 бит (для Unicode – 17 бит).

Пример сжатия способом “скользящего окна”
Рассмотрим пример сжатия по рассмотренному способу фразы «коси косой, косой Косой», в которой очевидно присутствуют повторяющиеся цепочки знаков (рис.5.6):











  • для первых пяти знаков в словаре (шаги 1-5) не находится подходящих цепочек и они передаются по отдельности (за счет использования битовых признаков на этом этапе мы проигрываем в объеме кода);
  • далее в словаре находится цепочка “кос”, которой отвечает ссылка [1,3] (начиная с первого знака в словаре — длина 3 знака) – шаг 6. Исходя из длины буфера и словаря длина кода цепочки составит 3+4+1=8 бит. Последующие 3 знака передаются по отдельности (шаги 7-9);
  • шаги 10-12 - передача кода длинной цепочки из 6 знаков, а затем 2 отдельных знаков. Наконец, шаг 13 — передача кода цепочки из 4 знаков. На этом этапе мы получаем наиболее существенный эффект по сжатию;
  • в целом длина сжатого кода в примере составляет 66% от исходной. Обратим внимание, что заметные потери в эффективности связаны с начальным заполнением словаря. В примере значимость этого этапа преувеличена, поскольку сжимаемый текст короток. В среднем степень сжатия текста словарным методом составляет обычно 40-60%.

Способ «прямой адресации цепочек»
Значительное замедление сжатия при больших объемах словаря в случае способа “скользящего окна” побудило использовать альтернативный способ организации словаря, который характеризуется меньшим временем поиска (рис.5.7):
  • словарь представляет собой не длинную однородную последовательность, а таблицу, каждая строка которой содержит цепочку знаков. При этом двоичный номер строки — это и есть код такой цепочки. Первоначально таблица содержит стандартный набор знаков с однобайтными кодами. В дальнейшем она дополняется появляющимися цепочками знаков. Содержание таблицы охватывает всю обработанную часть сообщения. Чтобы ограничить ее объем, редко используемые строки удаляются;
  • кодер ищет в таблице словаря строки с цепочками знаков, появляющимися в буфере. Такой поиск значительно быстрее, чем по длинной последовательности, и мало зависит от длины словаря. К найденной цепочке кодер добавляет следующий знак из сообщения и заводит для дополненного варианта новую строку, дополняя словарь. Слабостью данного метода является медленное заполнение словаря, поскольку новые цепочки каждый раз увеличиваются лишь на один знак;
  • сжатый код содержит двоичные номера строк словаря. При этом для одиночных символов такие коды однобайтны, а для цепочек — увеличиваются по мере роста их длины, однако их рост медлен (например, строка с номером 2000 будет иметь длину всего 11 бит).

Пример способа «прямой адресации цепочек»
Пример сжатия уже упомянутой выше фразы иллюстрирует рис.5.8.










  • первые пять знаков (шаги 1-5) сохраняются в виде стандартных кодов, в то же время в словаре сохраняются первые короткие двухзнаковые цепочки, которым присваиваются номера, следующие за емкостью байта;
  • на шаге 6 впервые появляется возможность использовать цепочку знаков из словаря. При этом в словарь помещается ее дополненный вариант. В дальнейшем сохранение отдельных знаков (шаги 7-11, 14, 15, 17) чередуется с сохранением ссылок на цепочки (шаги 12, 13, 16);
  • степень сжатия в примере получается существенно более низкой, чем по способы со скользящим окном. Это связано с краткостью сжимаемого текста, из-за которой сильно сказывается медленное заполнение словаря. При больших объемах сообщений эффективность сжатия будет существенно выше. В целом показатели эффективности двух рассмотренных подходов отличаются не слишком значительно.

Контрольные вопросы
1) Поясните принцип сжатия со «скользящим словарем», опираясь на рис.5.5.
2) Прокомментируйте пример сжатия со «скользящим словарем», опираясь на рис.5.6.
3) Поясните принцип сжатия с «прямой адресацией цепочек», опираясь на рис.5.7.
4) Прокомментируйте пример сжатия с «прямой адресацией цепочек», опираясь на рис.5.8.


5.3 Реализация и применение словарных методов

Обзор реализаций словарного сжатия
Показательна и интересна история развития словарного метода (рис.5.9):
  • первоначальная реализация метода была разработана около 40 лет назад Лемпелем и Зивом: сначала в варианте со скользящим словарем (алгоритм LZ77), а затем — с прямой адресацией цепочек (алгоритм LZ78). В обоих случаях это были теоретические работы, в которых не рассматривались проблемы эффективности (по скорости и памяти). Интересно, что для LZ78 была показана сходимость средней длины кода к энтропии, но лишь для очень длинных сообщений. В дальнейшем обе ветви развивались в направлении практической оптимизации;
  • практичные алгоритмы, приспособленные для программной реализации, были предложены Сторером и Шимански (LZSS), а также Вэлчем (LZW). В приведенном выше описании мы опирались именно на эти алгоритмы. В дальнейшем они стали основой последующих разработок, которые уже сосредотачивались на оптимизации по отдельным показателям эффективности;
  • для направления “скользящего словаря” можно привести примеры усовершенствований на базе LZSS. В частности, алгоритм LZM оптимизирован по скорости (за счет использования, где это возможно, быстрого сжатия RLE) и несколько проигрывает оригиналу в сжатии. LZH, напротив, увеличивает плотность путем сжатия по Хаффмену указателей и кодов одиночных знаков, но при этом он заметно медленнее;
  • для направления «прямой адресации цепочек» на основе LZW был создан улучшенный по скорости алгоритм LZC (в основном за счет оптимизации программной реализации). Позже на его базе реализован алгоритм LZMV, в котором за счет роста предельных длин цепочек в словаре улучшена плотность сжатия;
  • в целом существует большое разнообразие алгоритмов семейства LZ. Каждый из них имеет свои особенности и преимущества. Ниже в качестве примера удачного современного решения рассматривается алгорит LZMA (Lempel-Ziv-Markov Algorithm).

Особенности алгоритма LZMA (архиватор 7-Zip)
Алгоритм LZMA (Lempel-Ziv-Markov Algorithm) реализован, в частности, в архиваторе 7-Zip, с которым мы познакомимся в лабораторной работе (рис.5.10). К его особенностям относятся, в частности:
  • использование предварительного «разностного» кодирования (синоним «дельта- кодирование») для входного потока знаков. Поток исходных кодов знаков преобразуется в их разности. Поскольку чаще всего соседние знаки имеют близкие номера в таблице кодирования, такие разности невелики. Например, для текста длина их двоичных кодов в случае букв не превышает 5 бит, а в случае цифр — 4 бит. Напомним, что при исходном кодировании в Unicode для каждого знака требовалось 16 бит;
  • усовершенствованная бит-ориентированная модель сжатых данных, которая позволяет более экономично кодировать ссылки. Здесь вместо фиксированного формата пары "начальный адрес-длина цепочки" применяется набор форматов, выбор которых зависит от контекста. Такой подход позволяет, в частности, при необходимости значительно увеличивать размер словаря;
  • применение более эффективного арифметического кодирования для дополнительного статистического сжатия взамен классического кодирования по Хаффмену;
  • оптимизация на программном уровне (например, поддержка многопоточности сжатия, а также использование исключительно быстрых команд целочисленной арифметики).

Алгоритм LZMA наглядно демонстрирует, насколько важной является «тонкая» оптимизировання программная реализация метода. В настоящее время он является одной из самых эффективных и популярных реализаций словарного подхода к сжатию.

Формы применения словарного сжатия
Словарные методы сжатия широко используются прежде всего в программах-архиваторах, а также в ряде графических форматов (рис.5.11). При этом:
  • современные архиваторы наряду со словарными, как правило, используют также разновидновидности прогнозных и сортировочных алгоритмов. При этом «по умолчанию» предусматривается применение именно наиболее популярного словарного метода, а альтернативные варианты могут быть выбраны опционально;
  • хотя словарное сжатие применимо к файлам любых типов, его эффективность может сильно различаться. Так, текст (возможно, со встроенными иллюстрациями) или числовые данные обычно сжимается в два-три раза. Табличная информация (в частности, базы данных или таблицы Excel) может сжиматься на порядок. А вот сообщения, в которых исходные контекстные закономерности искусственно разрушены предшествующей компрессией (например, файлы jpg, mp3 или архивные), сжимаются очень плохо;
  • словарное сжатие растровых изображений встроено в некоторые графические форматы - в частности, gif и png (при этом для форматов tiff и bmp применяется быстрый алгоритм RLE). Такое сжатие обеспечивает высокую эффективность например для деловой графики, где большие площади заполняются одинаковыми цветами. Для фотографических изображений большую эффективность дают методы сжатия изображений с потерями, которые будут рассмотрены ниже;
  • словарное сжатие звука практически не используется, поскольку важным дополнительным требованием здесь является возможность прокрутки трека. В результате для сжатия звука без потерь применяются специализированные методы, которые также будут описаны в следующей лекции.

Контрольные вопросы
1) Охарактеризуйте направления и этапы развития словарных методов, используя рис.5.9.
2) Расскажите об основных особенностях алгоритма LZMA, опираясь на рис.5.10.
3) Каковы основные формы применения словарных методов сжатия.
4) Охарактеризуйте эффективность словарных методов для сжатия файлов разных типов.


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

Подходы к сжатию звука без потерь
Как мы уже знаем, оцифрованный звук представляет собой последовательность двоично-кодированных чисел — значений амплитуд. При этом важными ресурсами сжатия являются относительная плавность и предсказуемость изменения таких амплитуд, а также взаимозависимости их значений для различных стереоканалов (рис.5.12):
  • в силу плавности изменения амплитуд звука разности между их соседними значениями обычно значительно меньше, чем сами исходные амплитуды. Это означает, что кодирование таких разностей (его также называют дифференциальным или дельта-кодированием) может быть более компактным. В современной практике разностный принцип широко используется для кодирования звука на двух стереоканалах. В частности, в стандартном режиме MS-Stereo вместо двух значений амплитуд левого и правого каналов (Li, Ri) сохраняют Mi=(Li+Ri)/2, Si=(Li-Ri)/2, где величина Si в силу относительной малости может кодироваться экономично. Перед воспроизведением значения Li и Ri восстанавливаются;
  • развитием разностного подхода является экономичное кодирование отклонения звуковых амплитуд от их прогнозных значений. В силу плавности изменения звуковых амплитуд последующее значение, например Mi может прогнозироваться по нескольким предыдущим значениям Mi-k (где k=1, 2, … n). Для прогнозирования обычно используется аппроксимация полиномом. Разумеется, фактическое значение звуковой амплитуды Mi будет часто будет отличаться от прогнозного Mi*. Именно такое отличие ΔMi и сохраняется в виде компактного кода. Отметим, что такой способ называют еще адаптивным дифференциальным кодированием;
  • для экономичного кодирования полученных разностей применяются два подхода: сокращенная фиксированная разрядность кода (такой вариант на практике применяют при кодировании речи) или использование переменной длина кода, когда меньшие числа могут и должны кодироваться короче. В последнем случае необходимы специальные признаки, позволяющие различать границы кодовых цепочек, то-есть, код должен быть префиксным. Это снижает эффективность данного решения, однако оно все равно остается предпочтительным в случае двухбайтного исходного кодирования амплитуд. На практике для решения этой задачи применяется код Райса, который детально рассмотрен ниже.

Практическая реализация сжатия звука без потерь
Описанные выше подходы широко используются в практике сжатия звука. При этом конкретные решения существенно различаются для произвольного звука и для речи (рис.5.13):
  • для сжатия речи применяется относительно простой метод сжатия АДИКМ — адаптивная дифференциальная импульсно-кодовая модуляция (аббревиатура ИКМ традиционно использовалась для обозначения представления непрерывного звука в качестве последовательности импульсов соответствующих амплитуд). В рамках этого метода использование разностного сжатия позволяет сократить битрейт в 2 раза, а прогнозного — в 4 раза (с 64 до 32 и до 16 кбит/c). В обоих случаях эффект достигается за счет сокращения фиксированной длины кодов разностей (4 разряда вместо 8 для ДИКМ и 2 разряда для АДИКМ);
  • сжатие произвольного звука оказывается гораздо более сложной задачей в силу того, что диапазоны частот и уровней здесь значительно больше. Здесь применяется полный набор описанных приемов: разностное кодирование амплитуд для пары стереоканалов; адаптивное прогнозное кодирование соседних звуковых отсчетов; экономичное кодирование разностей по Райсу. При этом в итоге обеспечивается сжатие в 1,5 — 2 раза. Подобный уровень сжатия могут обеспечить и универсальные методы (в частности, словарные), однако они исключают возможность прокрутки треков, поэтому на практике не применяются;
  • описанные приемы сжатия звука без потерь используются практически во всех программах этого направления. В частности, это относится к популярным кодерам Monkey и FLAC, с работой которых мы познакомимся в рамках лабораторной №3. При этом эффективность сжатия без потерь значительно уступает сжатию с потерями качества, которое реализовано, в частности, в популярном стандарте mp3 (последний обеспечивает сжатие d 5-7 раз без существенных искажений звука). Однако, в последнее время в связи с удешевлением памяти методы сжатия звука без потерь набирают популярность.

Использование кода Райса при сжатии звука
Код Райса, который применяется для компактного представления малых чисел при кодировании звука, характеризуется такими особенностями (рис.5.14):
  • любое число x может быть представлено в виде x=q*2k+r, где r – остаток от деления x на 2k, где значение k заранее задано. Например, при k=4 число 45 = 2*24+13, 58=3*24+10, а 7=0*24+7. В таком представлении явно выделяются две части: первый параметр q “грубо” задает порядок числа (в нашем случае с точностью до 2k=16), а второй параметр r определяет его точное значение;
  • код числа х строится по следующей схеме. Первыми идут нули, количеством в q штук (например, при x=45 это [00]). Затем справа к нулям добавляется маркировочный бит [1], который указывает на границу первой части кода. Вторая часть включает остаток r c с фиксированной длиной в k бит (в случае x=45 [1101]). Таким образом код Райса для числа 45 будет иметь вид [0011101], а для 58 - [00011010], а для 7 - [11010];
  • как видно, длина кода получается переменной и убывает для меньших значений x. При этом условие префиксности (выделения границ кодовых цепочек в общем потоке битов) приводит к дополнительным накладным расходам. Так, минимальная длина двоичного кода для чисел 45, 58 и 7 составляет соответственно 6, 6 и 3 разряда, а для кода Райса — 7, 8 и 5. Тем не менее именно для малых значений x, которые чаще встречаются для дифференциального и особенно для адаптивного прогнозного кодирования, такой код является эффективным;
  • обратим внимание, что при кодировании по Райсу значение параметра k является заданным. При этом его увеличение приводит к сокращению длины первой половины кода и одновременно к росту второй половины. Это может быть целесообразым, если относительно часто появляются большие значения x. Например, для x=100 при k=4 число представляется как x=6*24+4 (код [00000010100] – 11 разрядов), а при k=5 - как x=3*25+4 (код [000100100] – 9 разрядов). С другой стороны для x=7 при k=5 длина кода по сравнению с k=4 увеличится на один разряд — [101010] вместо [11010]. На практике выбор параметра k выполняется программой-кодером автоматически по результатам оценки характеристик кодируемого звука.


Контрольные вопросы
1) Какие закономерности звуковых данных используются для их сжатия без потерь.
2) Поясните принцип разностного кодирования для случая последовательности амплитуд и для кодирования стереоканалов.
3) Поясните принцип адаптивного прогнозного метода сжатия звуковых данных.
4) Расскажите о методе АДИКМ сжатия речевых данных. Какова здесь эффективность сжатия и за счет чего оно достигается.
5) Каковы основные составляющие современных методов сжатия произвольного звука без потерь и какой уровень эффективности они обеспечивают.
6) Поясните алгоритм Райса экономичного кодирования разностей при сжатии звука.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP