Методическое пособие 640

стоит в том, что они сокращают среднюю длину кодовых символов путем присвоения кодовых символов минимальной длины символам сообщения, которые встречаются более часто [5].

Кодовые слова могут быть представлены в виде кодовых таблиц и кодовых деревьев (см. рисунок 6.1).

Вершина

Рис. 6.1. Пример построения кодового дерева

Для того, чтобы построить кодовое дерево для данного кода, начиная с некоторой точки - корня кодового дерева - проводятся ветви - 0 или 1. На вершинах кодового дерева находятся буквы алфавита источника, причем каждой букве соответствуют своя вершина и свой путь от корня к вершине. К примеру, букве А соответствует код 000, букве В – 010, букве Е – 101 и т.д.

Код, полученный с использованием кодового дерева, изображенного на рис. 6.2, является равномерным трехраз-

рядным кодом.

Равномерные коды очень широко используются в силу своей простоты и удобства процедур кодированиядекодирования: каждой букве – одинаковое число бит; принял заданное число бит – ищи в кодовой таблице соответствующую букву.

Наряду с равномерными кодами могут применяться и неравномерные коды, когда каждая буква из алфавита источника кодируется различным числом символов, к примеру, А - 10, Б – 110, В – 1110 и т.д.

131

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

Однако можно построить неравномерные неприводимые коды, допускающие однозначное декодирование. Для этого необходимо, чтобы всем буквам алфавита соответствовали лишь вершины кодового дерева, например, такого, как показано на рис. 6.2. Здесь ни одна кодовая комбинация не является началом другой, более длинной, поэтому неоднозначности декодирования не будет. Такие неравномерные коды называются префиксными.

Рис. 6.2. Неравномерный неприводимый код

Рассмотрим пример кодирования сообщений λi из алфавита объемом K = 8 с помощью произвольного n - разрядного двоичного кода.

Пусть источник сообщения выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв p(λi ) = 1/8.

Кодирующее устройство кодирует эти буквы равномерным трехразрядным кодом (см. табл. 6.1).

132

Определим основные информационные характеристики источника с таким алфавитом:

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

Пусть теперь вероятности появления в тексте различных букв будут разными (табл. 6.2).

133

Таблица 6.2

Среднее число символов на одно сообщение при использовании того же равномерного трехразрядного кода

K K

n niPi n Pi n 3.

i 1 i 1

Избыточность кода в этом случае будет

Кk 1 H 1 1.781 0.41, n 3

или довольно значительной величиной (в среднем 4 символа из

10не несут никакой информации).

Всвязи с тем, что при кодировании неравновероятных сообщений равномерные коды обладают большой избыточно-

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

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

Такое кодирование называется статистическим. Неравномерный код при статистическом кодировании вы-

бирают так, чтобы более вероятные буквы передавались с помощью более коротких комбинаций кода, менее вероятные - с

помощью более длинных. В результате уменьшается средняя длина кодовой группы в сравнении со случаем равномерного кодирования.

Обратим внимание на тот факт, что как для кода Хаффмена, так и для кода Шеннона-Фано среднее количество дво-

134

ичных символов, приходящееся на символ источника, приближается к энтропии источника, но не равно ей. Данный результат представляет собой следствие теоремы кодирования для источника без шума (первой теоремы Шеннона), которая утверждает:

Если источник сообщений имеет энтропию Н бит/символ, а канал обладает пропускной способностью С бит/сек, то всегда можно найти способ кодирования, который обеспечит передачу символов сообщения по каналу со средней скоростью

где ɛ — сколь угодно малая величина.

Обратное утверждение говорит, что передача символов

сообщения по каналу со средней скоростью

ср > С

Эта теорема часто приводится в иной формулировке:

Любой источник можно закодировать двоичной последовательностью при среднем количестве двоичных символов на символ источника i , сколь угодно близком к энтропии, и невозможно добиться средней длины кода, меньшей, чем энтропия H(λ).

Таким образом, для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D - ичный префиксный код, в котором средняя длинна кодового слова n, удовлетворяет неравенству:

Значение этой теоремы для современной радиотехники трудно переоценить – она устанавливает те границы в ком-

135

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

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

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

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

Для существования однозначно декодируемого D- ичного кода, содержащего k кодовых слов с длинами n1,n2,…,nk, необходимо и достаточно, чтобы выполнялось неравенство Крафта:

≤ 1 .

136

6.2. Цель сжатия данных и типы систем сжатия

Передача и хранение информации требуют достаточно больших затрат. И чем с большим количеством информации нам приходится иметь дело, тем дороже это стоит. К сожалению, большая часть данных, которые нужно передавать по каналам связи и сохранять, имеет не самое компактное представление. Скорее, эти данные хранятся в форме, обеспечивающей их наиболее простое использование, например: обычные книжные тексты, ASCII коды текстовых редакторов, двоичные коды данных ЭВМ, отдельные отсчеты сигналов в системах сбора данных и т.д. Однако такое наиболее простое в использовании представление данных требует вдвое - втрое, а иногда и в сотни раз больше места для их сохранения и полосу частот для их передачи, чем на самом деле нужно. Поэтому сжатие данных – это одно из наиболее актуальных направлений современной радиотехники.

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

Существуют два типа систем сжатия данных:

•системы сжатия без потерь информации (неразрушающее сжатие) - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя;

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

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

137

ния более быстро или хранить более экономно. Такие программные средства, реализующие сжатие, называют архиваторами [12]. Существует достаточно большое их разнообразие.

Методы или алгоритмы сжатия данных без потерь можно разделить на:

1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др.

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

2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.

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

3.Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела - Зива.

Сжатие с потерями используется в основном для трех видов данных:

1.Полноцветная графика.

2.Видеоинформация.

3.Звуковая информация.

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

138

6.3. Методы эффективного кодирования некоррелированной последовательности знаков. Код Шеннона-Фано

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

Код строится следующим образом. Кодируемые знаки выписывают в таблицу в порядке убывания или возрастания их вероятностей в сообщениях. Затем их разделяют на две группы так, чтобы значения сумм вероятностей в каждой группе были близкими. Все буквы верхнего подмножества в качестве первого символа кода получают 1, а буквы нижнего подмножества – 0. Затем последнее подмножество снова разбивается на два подмножества с соблюдением того же условия и проводят то же самое присвоение кодовым элементам второго символа. Процесс продолжается до тех пор, пока во всех подмножествах не останется по одной букве кодового алфавита (таб-

лица 6.3).

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

139

Таблица 6.3

= = 0,25∙2+0,25∙2+0,15∙3+0,05∙4+0,05∙4

+0,15∙4 = 2,7 бит

быточности кода. Эту избыточность можно устранить, если перейти к кодированию блоками [2]. Рассмотрим простой пример кодирования двумя знаками z1, z2 с вероятностями их появления в сообщениях 0,1 и 0,9 соответственно.

Если один из этих знаков кодировать, например, нулем, а другой единицей, т.е. по одному символу на знак, имеем соот-

ветственно = 0,1·1 + 0,9·1 = 1,0, 140