3. Сжатие динамического диапазона.

Эта группа методов основана на том, что передаваемые сигналы подвергаются нелинейным преобразованиям амплитуды, причем в передающей и приёмной частях нелинейности взаимообратны. Например, если в передатчике используется нелинейная функция u , в приемнике – u². Последовательное применение взаимообратных функций приведет к тому, что в целом преобразование остается линейным.

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

;	(2.17)
.	(2.18)

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

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

В то же время эти методы имеют и недостатки. Первый из них заключается в том, что логарифм малого числа отрицателен и в пределе:

.

(2.19)

Это приводит к очень высокой чувствительности к помехам и нелинейностям в области малых сигналов. Второй недостаток заключается в снижении чувствительности передатчика в области больших сигналов. Известно, что чувствительность  любого преобразователя (или передатчика) пропорциональна производной от его характеристики вход/выход. Для логарифмического преобразователя с характеристикой y = log(x)

,

(2.20)

то есть, чувствительность очень нелинейна.

Для уменьшения этих недостатков обе функции модифицируют смещением и аппроксимацией. Например, для телефонных каналов аппроксимированная функция имеет вид ( тип А,[17]):

причем А=87,6. Выигрыш от сжатия при этом составляет 24дБ.

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

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

4. Эффективное кодирование

Эффективные коды были предложены К.Шенноном, Фано и Хафманом [23]. Сущность кодов заключается в том, что они неравномерные, то есть с неодинаковым числом разрядов, причем длина кода обратно пропорциональна вероятности его появления. Еще одна замечательная особенность эффективных кодов - они не требуют разделителей, то есть специальных символов, разделяющих соседние кодовые комбинации. Это достигается при соблюдении простого правила: более короткие коды не являются началом более длинных. В этом случае сплошной поток двоичных разрядов однозначно декодируется, поскольку декодер обнаруживает вначале более короткие кодовые комбинации. Эффективные коды долгое время были чисто академическими, но в последнее время успешно используются при формировании баз данных, а также при сжатии информации в современных модемах и в программных архиваторах [37].

Ввиду неравномерности вводят среднюю длину кода. Средняя длина - математическое ожидание длины кода:

.

(2.22)

Здесь l - длина i-й кодовой комбинации; p_i - ее вероятность; N - число различных комбинаций. Особенностью эффективных кодов является то, что средняя длина кода приближается к энтропии источника:

,

(2.23)

причем, l_ср стремится к H(x) сверху (то есть l_ср > H(x)).

Выполнение условия (2.23) усиливается при увеличении N.

Существует две разновидности эффективных кодов: Шеннона-Фано и Хафмана. Рассмотрим их получение на примере. Предположим, вероятности символов в последовательности имеют значения, приведенные в таблице 2.1.

Таблица 2.1.

Вероятности символов

N	1	2	3	4	5	6	7	8	9
pi	0.1	0.2	0.1	0.3	0.05	0.15	0.03	0.02	0.05

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

Таблица 2.2.

Кодирование по методу Шеннона-Фано

N	Pi	1	2	3	4	5
4	0.3		I				11
2	0.2	I	II				10
6	0.15		I	I			011
3	0.1			II			010
1	0.1			I	I		0011
9	0.05	II			II		0010
5	0.05		II		I		00001
7	0.03			II	II	I	000001
8	0.02					II	000000

Как видно из таблицы 2.2, первый символ с вероятностью p₄ = 0.3 участвовал в двух процедурах разбиения на группы и оба раза попадал в группу с номером I . В соответствии с этим он кодируется двухразрядным кодом II. Второй элемент на первом этапе разбиения принадлежал группе I, на втором - группе II. Поэтому его код 10. Коды остальных символов в дополнительных комментариях не нуждаются.

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

По графу ориентируются следующим образом: составляют маршрут для выделенного символа; количество разрядов для него равно количеству ребер в маршруте, а значение каждого разряда равно направлению соответствующего ребра. Маршрут составляется из исходной точки (на чертеже она помечена буквой А). Например, маршрут в вершину 5 состоит из пяти ребер, из которых все, кроме последнего, имеют направление 0; получаем код 00001.

Вычислим для этого примера энтропию и среднюю длину слова.

H(x) = -(0.3•log 0.3 + 0.2•log 0.2 + 2•0.1•log 0.1+ 2•0.05•log 0.05+

+ 0.03•log 0.03 + 0.02•log 0.02) = 2.23 бит

l_ср = 0.3•2 + 0.2•2 + 0.15•3 + 0.1•3 + 0.1•4 + 0.05•5 +0.05•4+

+0.03•6 + 0.02•6 = 2.9 .

Как видно, средняя длина слова близка к энтропии.

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

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

В таблице 2.3 показано кодирование по алгоритму Хафмана. Как видно из таблицы, кодирование осуществлялось за 7 этапов. Слева указаны вероятности символов, справа - промежуточные коды. Стрелками показаны перемещения вновь образованных символов. На каждом этапе два последних символа отличаются только младшим разрядом, что соответствует методике кодирования. Вычислим среднюю длину слова:

l_ср = 0.3•2 + 0.2•2 + 0.15•3 ++ 2•0.1•3 + +0.05•4 + 0.05•5 + 0.03•6 + 0.02•6 = 2.7

Это еще ближе к энтропии: код еще более эффективен. На рис. 2.12 приведено дерево кода Хафмана.

Таблица 2.3.

Кодирование по алгоритму Хафмана

N	pi	код	I	II	III	IV	V	VI	VII
4	0.3	11	0.3 11	0.3 11	0.3 11	0.3 11	0.3 11	0.4 0	0.6 1
2	0.2	01	0.2 01	0.2 01	0.2 01	0.2 01	0.3 10	0.3 11	0.4 0
6	0.15	101	0.15 101	0.15 101	0.15 101	0.2 00	0.2 01	0.3 10
3	0.1	001	0.1 001	0.1 001	0.15 100	0.15 101	0.2 00
1	0.1	000	0.1 000	0.1 000	0.1 001	0.15 100
9	0.05	1000	0.05 1000	0.1 1001	0.1 000
5	0.05	10011	0.05 10011	0.05 1000
7	0.03	100101	0.05 10010
8	0.02	100100

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

Оба кода удовлетворяют требованию однозначности декодирования: как видно из таблиц, более короткие комбинации не являются началом более длинных кодов.

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

Эффект от внедрения таких кодов определяется в сравнении их с равномерным кодом:

(2.24)

где n - количество разрядов равномерного кода, который заменяется эффективным.