- •1 Теоретические аспекты информационных технологий. 6
- •2 Сжатие информации 43
- •3 Многоканальная передача и уплотнение линий связи 68
- •Теоретические аспекты информационных технологий.
- •Теория сигналов и спектральный анализ
- •Управление колебаниями
- •Теория информации
- •Дискретизация и квантование.
- •Сжатие информации
- •Адаптивная дискретизация, разностная и дельта-модуляция.
- •Статистическое сжатие.
- •Сжатие динамического диапазона.
- •Эффективное кодирование
- •Модификации кодов Хафмана
- •Алгоритмы Лемпеля – Зива
- •Сжатие графических изображений
- •Видеостандарт mpeg
- •Многоканальная передача и уплотнение линий связи
- •Сравнение и анализ основных методов разделения каналов
- •Адресное разделение каналов.
- •Разделение каналов на основе псевдослучайных последовательностей
- •3.4. Комбинированное разделение каналов
-
Сжатие динамического диапазона.
Эта группа методов основана на том, что передаваемые сигналы подвергаются нелинейным преобразованиям амплитуды, причем в передающей и приёмной частях нелинейности взаимообратны. Например, если в передатчике используется нелинейная функция u , в приемнике – u2. Последовательное применение взаимообратных функций приведет к тому, что в целом преобразование остается линейным.
Идея нелинейных методов сжатия данных сводится к тому, что передатчик может при той же амплитуде выходных сигналов передать больший диапазон изменения передаваемого параметра (то есть, больший динамический диапазон). Динамический диапазон - это выраженное в относительных единицах или децибеллах отношение наибольшей допустимой амплитуды сигнала к наименьшей:
; |
(2.17) |
. |
(2.18) |
Естественное желание увеличить динамический диапазон с помощью уменьшения Umin ограничивается чувствительностью аппаратуры и возрастанием влияния помех и собственных шумов.
Наиболее часто сжатие динамического диапазона осуществляется с помощью пары взаимообратных функций логарифмирования и потенцирования. Первая операция изменения амплитуды называется компрессией (сжатием), вторая - экспандированием (растяжением). Выбор именно этих функций связан с их наибольшей возможностью компрессии.
В то же время эти методы имеют и недостатки. Первый из них заключается в том, что логарифм малого числа отрицателен и в пределе:
. |
(2.19) |
Это приводит к очень высокой чувствительности к помехам и нелинейностям в области малых сигналов. Второй недостаток заключается в снижении чувствительности передатчика в области больших сигналов. Известно, что чувствительность любого преобразователя (или передатчика) пропорциональна производной от его характеристики вход/выход. Для логарифмического преобразователя с характеристикой y = log(x)
, |
(2.20) |
то есть, чувствительность очень нелинейна.
Для уменьшения этих недостатков обе функции модифицируют смещением и аппроксимацией. Например, для телефонных каналов аппроксимированная функция имеет вид ( тип А,[17]):
причем А=87,6. Выигрыш от сжатия при этом составляет 24дБ.
Сжатие данных путём нелинейных процедур реализуется аналоговыми средствами с большими погрешностями. Применение цифровых средств может существенно повысить точность или быстродействие преобразования. При этом прямое применение средств вычислительной техники (то есть, непосредственное вычисление логарифмов и экспонент) даст не лучший результат ввиду низкого быстродействия и накапливающейся погрешности вычисления.
Сжатие данных путем компрессии из-за ограничений по точности используется в неответственных случаях, например, для передачи речи по телефонным и радиоканалам.
-
Эффективное кодирование
Эффективные коды были предложены К.Шенноном, Фано и Хафманом [23]. Сущность кодов заключается в том, что они неравномерные, то есть с неодинаковым числом разрядов, причем длина кода обратно пропорциональна вероятности его появления. Еще одна замечательная особенность эффективных кодов - они не требуют разделителей, то есть специальных символов, разделяющих соседние кодовые комбинации. Это достигается при соблюдении простого правила: более короткие коды не являются началом более длинных. В этом случае сплошной поток двоичных разрядов однозначно декодируется, поскольку декодер обнаруживает вначале более короткие кодовые комбинации. Эффективные коды долгое время были чисто академическими, но в последнее время успешно используются при формировании баз данных, а также при сжатии информации в современных модемах и в программных архиваторах [37].
Ввиду неравномерности вводят среднюю длину кода. Средняя длина - математическое ожидание длины кода:
. |
(2.22) |
Здесь l - длина i-й кодовой комбинации; pi - ее вероятность; 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, первый символ с вероятностью p4 = 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 - количество разрядов равномерного кода, который заменяется эффективным.