50_000337

Rfrjg; j = 1 : : : K.

При этом обычно, но не обязательно, K < M или даже K << M.

Примером преобразующего кодирования является запись исходного сообщения, представляемого3 в виде числа, в выбранной позиционной системе счисления разрядности m:

Достаточно очевидно, что чем больше основание системы счисления, тем меньшее число разрядов требуется для представления данного сообщения, следовательно, требуется меньшее время для передачи4 К сожалению, с ростом разрядности существенно повышаются требования к разрешающим устройствам и снижается помехоустойчивость итогового алфавита. Наиболее простой для реализации и традиционной для современных вычислительных машин является двоичная система: в данном случае задача различения сигналов в общем сводится к так называемой задаче обнаружения5. (есть или нет импульс), являющейся минимальной по вычислительной сложности и обеспечивающей наибольшую уверенность приема.

Крайне интересным типом преобразующего кодирования, не связанного с преобразованием систем счисления, являются коды с циклическим преобразованием алфавитов. Ярким примером таких кодов является так называемый код Грея, используемый ранее в АЦП с аналоговым выбором вариантов итоговой строки6, в которых данный код позволяет свести к единице младшего разряда ошибку неоднозначности при считывании7. На следующем рис. описаны комбинации кода Грея для десятичных чисел от 0 до 15.

3Без ограничения общности.

4При одинаковой длительности канального символа - т.е. сообщения итогового алфавита - для любого значения размерности m.

5Термин статистической радиотехники; в рамках данного курса детально не раскрывает-

ся.

6АЦП – аналого-цифровой преобразователь. Англ. эквивалент - ADC.

7В данном коде два соседних значения различаются только в одном разряде. Де-факто код Грея также представляет собой специфичную систему счисления. Описываемый двоичный код Грея является наиболее часто используемым на практике, хотя в общем случае существует бесконечное множество кодов Грея для систем счисления с любым основанием. Под кодом Грея здесь и далее будем понимать именно указанный двоичный код.

101

Рис. 9.1: Комбинации кода Грея для десятичных чисел от 0 до 15

Пример использования кода Грея объясним на примере патента самого Фрэнка Грея, посвященного созданию нового типа АЦП на базе электронно-лучевой трубки. Итак, схема работы указанного АЦП была следующей:

Измеряемое АЦП напряжение отклоняет луч ЭЛТ по вертикали - задает строчку отображаемых значений. Основная проблема указанного АЦП была в следующей - если луч оказывался около границы двух строк, на выходе получались результаты, сильно отличающиеся друг от друга в каждый момент времени. Идея Грея заключалась в том, что если строки отличаются только одним битом, то и погрешность АЦП будет составлять только один младший разряд.

9.2Методы эффективного кодирования

9.2.1Статистическое кодирование

Хотя оптимальное кодирование, используемое для доказательства теоремы Шеннона в дискретном канале без помех является недостижимым8, близкие к данному пределу результаты возможно получить и для сообщений (последовательностей символов) ограниченной длины, исполь-

зуя т.н. статистическое кодирование.

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

8Условие данного оптимального кодирования - укрупнение кодирующего алфавита до бесконечности и, соответственно, бесконечная длина исходящего сообщения.

102

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

где Ck - пропускная способность канала связи.

Для случая оптимального статистического кодирования среднее время передачи одного символа, при котором обеспечивается пропускная способность канала Ck равно:

т.е. соответствует времени на передачу одного символа, отвечающему той же пропускной способности при идеальном кодировании по Шеннону.

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

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

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

103

9.2.2Кодирование Шеннона-Фано

Кодирование методом Шеннона-Фано является одним из простейших методов статистического кодирования. Кодирование по Шеннону-Фано производится в соответствии с следующим алгоритмом:

1Все символы из исходного алфавита U записывают в порядке убывания вероятностей.

2Всю совокупность символов разбивают на две примерно равные по сумме вероятностей группы: одной из них (в группе могут быть один или более символов) присваивают значение 1 , другой - 0 .

3 Каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают значения 1 или 0 . Данный пункт повторяется итеративно и рекурсивно до разбиения всех групп.

Указанную процедуру кодирования легче всего осуществлять при помощи построения т.н. кодового дерева, построение кода с помощью которого показано на следующем рисунке.

Рис. 9.2: Пример построения кода Шеннона-Фано с помощью кодового дерева

Для полученного кода среднее число двоичных символов, приходящихся на одну букву, равно:

104

9.2.3Кодирование по Хаффману

Простейшим подмножеством кодов, на основе которых может выполняться сжатие данных, являются коды без памяти. Для определения понятия код без памяти введем определение т.н. префиксного множества10:

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

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

Алгоритм Хаффмена реализует идею оптимального статистического кодирования с использованием аппарата префиксных множеств и функционирует согласно следующему алгоритму:

1Все символы алфавита выписываются в ряд в порядке возрастания (либо убывания) вероятности их появления в исходном сообщении.

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

3От вершины дерева прослеживается путь к каждому листу, помечая направление на каждом разветвлении (например – вниз - 0; вверх - 1). Полученные последовательности для каждого листа и есть кодовые слова, соответствующие исходным символам.

Построение кодового дерева для алгоритма Хаффмана для шестизначного множества показано на рис. ниже.

10Более подробно префиксные множества будут рассмотрены в следующей лекции.

105

Рис. 9.3: Пример построения кода Хаффмана с помощью кодового дерева

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

Алгоритм кодирования Хаффмана не способен передавать на каждый символ сообщения менее одного бита информации, что является его достаточно серьезным недостатком (пример – в сообщении, состоящем из нулей и единиц, единицы встречаются в 10 раз чаще нулей). Одной из наиболее популярных схем кодирования, позволяющих кодировать некотоорые символы менее, чем одним битом, является методология арифметического кодирования, детально проработанная в 70-е года XX века11.

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

1Введем понятие рабочего интервала – полуинтервала [a; b) с расположенными на нем точками; при этом точки расположены таким образом, что длины образованных ими отрезков равны вероятностям появления исходных символов. На первом шаге алгоритма a = 0; b = 1.

2 Основной шаг алгоритма: для кодируемого символа ищется соответствующий участок на рабочем интервале. Указанный участок рекурсивно становится новым рабочим интервалом (т.е. мы переразби-

11Наиболее известная версия разработана И.Уиттеном с соавторами.

106

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

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

Рассмотрим алгоритм арифметического кодирования на примере, которым и закончим данную лекцию.

Пример 23. Пусть необходимо закодировать входное сообщение SWISS MISS с заданными вероятностями появления символов, показанными на рис. ниже:

Рис. 9.4: Вероятности появления символов для арифметического кодирования

Решение. Процесс кодирования начинается со считывания первого символа входного потока и выбора нового рабочего интервала, соответствующего данному символу. В данном случае для первого символа S получаем диапазон [0.5, 1). После этого считывается новый символ W, которому соответствует поддиапазон [0.4, 0.5) уже во втором рабочем интервале и т.д. Схема преставления новых границ символа W представлена на рис. ниже.

Рис. 9.5: Новый рабочий интервал

Указанная схема может быть записана в виде следующих формул:

12Чаще всего берется левая граница интервала.

107

NewHigh = OldLow + (OldHigh-OldLow)*HighRange(X), NewLow =

OldLow + (OldHigh-OldLow)*LowRange(X),

где OldLow – нижняя граница интервала, в котором представляется текущий символ; OldHigh – верхняя граница интервала; HighRange(X) – исходная верхняя граница кодируемого символа; LowRange(X) – исходная нижняя граница кодируемого символа.

Повторяя итеративно данный процесс, получаем значение последнего рабочего интервала [0.71753375, 0.717535). В качестве результирующего кода берется значение левой границы отрезка - 0.71753375, из которых достаточно записать в битовой форме число 71753375, кодируемое лишь 27 битами (27 битами кодируется число от 0 до 227 = 134217727).

Теперь рассмотрим возможность восстановления закодированной информации по восьми цифрам 71753375 и известным интервалам символов. Первая из восьми цифр – это 7, т.е. 0,7. Она принадлежит одному из заданных интервалов [0.5, 1), который соответствует символу S. Поэтому первый декодированный символ – это S. Теперь вернемся к рис. 3 и заметим, что второй символ был представлен в интервале символа S, т.е. [0.5, 1). Но для удобства декодирования его лучше представить в исходном интервале [0, 1). Для этого достаточно интервал [0.5, 1) увеличить до начального, т.е. умножить на два и границы сдвинуть на величину

0:5 2 = 1.

Применяя данную схему к числу 0.71753375, получаем нижнюю границу следующего закодированного символа как будто он был начальным при кодировании:

0:71753375 2 1 = 0:4350675:

Полученное значение принадлежит диапазону [0.4, 0.5), который соответствует символу W. Затем, также полученное число 0.4350675 следует нормировать, что в общем случае выполняется по формуле:

Code = (Code-LowRange(X))/(HighRange(X)-LowRange(X)),

где Code – текущее значение кода.

Итоговая схема декодирования для данного примера приведена на рис. ниже.

108

Рис. 9.6: Общая схема декодирования для исходного сообщения

109

Лекция 10

Неравенство Крафта. Словарные методы кодирования

10.1Эффективные методы кодирования

10.1.1Неравенство Крафта-Макмиллана

Для получения некоторых общих результатов для эффективных методов кодирования введем более строго понятие кодирование и сопутствующую терминологию:

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

Кодом C для алфавита U называется функция C, которая для каждого символа ui из U указывает слово C(ui), кодирующее этот символ.

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

Полным называется такой префиксный код, для которого добавление любого нового кодового слова (в заданном алфавите) нарушает свойство префиксности.¾ Разделимым1 называется такой код, в котором никаким двум словам кодируемого алфавита не может быть сопоставлено одно и то же кодовое слово. Любой префиксный код является разделимым.

1Или однозначно декодируемым.

110