Избыточность информационных потоков и ее практическое использование.
Приведение ДЭФ по модулю и свойства приведения для четного и нечетного N.
Приведем примеры матриц ДЭФ для двух вариантов 
, четного и нечетного. Рассмотрим четное 
, например 
. Матрица значений 
напоминает таблицу умножения (см.рис.5.5).
Рис. 5.5. Матрица ДЭФ при 
|
Матрица а) представляет перечисление фаз в их абсолютном выражении. В частности, фаза последней функции (правый нижний угол) соответствует шести полным оборотам (и еще немного).
Матрица б) соответствует формуле приведения, согласно которой из фазовой координаты вычитается число, удаляющее кратное число оборотов вектора. В приведенном нами примере, удаляются цифры, кратные 8. Остаток должен лежать в пределах от 0 до 
. В частности, в элементе, стоящем на пересечении пятого столбца и седьмой строки (это число 20), при получается 
.
Приведение по модулю 
является базовым преобразованием в ЦОС.
Обратим внимание на вторую матрицу б). Она приведена по модулю . При этом остатки от приведения лежат в пределах заданного множества . Приведение сводится к тому, что остаток находится в пределах от 0 до .
Стоит отметить, что нами принято четное число . При этом получается семейство комплексно сопряженных функций, симметричных относительно центра сопряжения. В варианте центром сопряжения является функция с номером 
. Если выделить эту функцию и изменять значения аргумента в пределах от 0 до , получаем после приведения, т. е. в остатках, матрицу типа б).
Приведение по модулю является фундаментальной операцией, приводящей к оригинальным последствиям. Рассмотрим матрицу ДЭФ в полном и приведенном варианте при 
, т. е. нечетном.
Рис. 5.6. Матрица ДЭФ при
|
В итоге после приведения по модулю 
получается два семейства комплексно сопряженных функций; количество таких пар равно 
, а чисто действительная функция одна – нулевая. Это свойство обобщается на любое 
, причем везде есть разница между четными и нечетными значениями.
Эффективное кодирование. Коды Шеннона-Фано.
Сущность кодов заключается в том, что они неравномерные, то есть с неодинаковым числом разрядов, причем длина кода обратно пропорциональна вероятности его появления. Еще одна замечательная особенность эффективных кодов – они не требуют разделителей, то есть специальных символов, разделяющих соседние кодовые комбинации. Это достигается при соблюдении простого правила: более короткие коды не являются началом более длинных. В этом случае сплошной поток двоичных разрядов однозначно декодируется, поскольку декодер обнаруживает вначале более короткие кодовые комбинации. Эффективные коды долгое время были чисто академическими, но в последнее время успешно используются при формировании баз данных, а также при сжатии информации в современных модемах и в программных архиваторах [39].
Ввиду неравномерности вводят среднюю длину кода. Средняя длина – математическое ожидание длины кода:
 .
| (2.22) |
Здесь 
– длина 
-той кодовой комбинации; 
– ее вероятность; 
– число различных комбинаций. Особенностью эффективных кодов является то, что средняя длина кода приближается к энтропии источника:
 ,
| (2.23) |
причем, 
стремится к 
сверху (то есть 
).
Выполнение условия (2.23) усиливается при увеличении 
.
Существует две разновидности эффективных кодов: Шеннона-Фано и Хафмана. Рассмотрим их получение на примере. Предположим, вероятности символов в последовательности имеют значения, приведенные в таблице 2.1.
Таблица 2.1
Вероятности символов
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0,1 | 0,2 | 0,1 | 0,3 | 0,05 | 0,15 | 0,03 | 0,02 | 0,05 |
Символы ранжируются, то есть представляются в ряд по убыванию вероятностей. После этого по методу Шеннона-Фано периодически повторяется следующая процедура: вся группа событий делится на две подгруппы с одинаковыми (или примерно одинаковыми) суммарными вероятностями. Процедура продолжается до тех пор, пока в очередной подгруппе не останется один элемент, после чего этот элемент устраняется, а с оставшимися указанные действия продолжаются. Это происходит до тех пор, пока в последних двух подгруппах не останется по одному элементу. Продолжим рассмотрение нашего примера, которое сведено в таблице 2.2.
Таблица 2.2.
Кодирование по методу Шеннона-Фано
|
|
| 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, первый символ с вероятностью 
участвовал в двух процедурах разбиения на группы и оба раза попадал в группу с номером I . В соответствии с этим он кодируется двухразрядным кодом II. Второй элемент на первом этапе разбиения принадлежал группе I, на втором – группе II. Поэтому его код 10. Коды остальных символов в дополнительных комментариях не нуждаются.
Обычно неравномерные коды изображают в виде кодовых деревьев. Кодовое дерево – это граф, указывающий разрешенные кодовые комбинации [24]. Предварительно задают направления ребер этого графа, как показано на рис.2.10 (выбор направлений произволен).
Рис. 2.10. Кодовое дерево для табл. 2.2
По графу ориентируются следующим образом: составляют маршрут для выделенного символа; количество разрядов для него равно количеству ребер в маршруте, а значение каждого разряда равно направлению соответствующего ребра. Маршрут составляется из исходной точки (на чертеже она помечена буквой А). Например, маршрут в вершину 5 состоит из пяти ребер, из которых все, кроме последнего, имеют направление 0; получаем код 00001.
Вычислим для этого примера энтропию и среднюю длину слова:
Как видно, средняя длина слова близка к энтропии.
Коды Хафмана.
Коды Хафмана строятся по иному алгоритму. Процедура кодирования состоит из двух этапов. На первом этапе последовательно проводят однократные сжатия алфавита. Однократное сжатие – замена двух последних символов (с низшими вероятностями) одним, с суммарной вероятностью. Сжатия проводят до тех пор, пока не останется два символа. При этом заполняют таблицу кодирования, в которой проставляют результирующие вероятности, а также изображают маршруты, по которым новые символы переходят на следующем этапе.
На втором этапе происходит собственно кодирование, которое начинается с последнего этапа: первому из двух символов присваивают код 1, второму – 0. После этого переходят на предыдущий этап. К символам, которые не участвовали в сжатии на этом этапе, приписывают коды с последующего этапа, а к двум последним символам дважды приписывают код символа, полученного после склеивания, и дописывают к коду верхнего символа 1, нижнего – 0. Если символ дальше в склеивании не участвует, его код остается неизменным. Процедура продолжается до конца (то есть до первого этапа).
Таблица 2.3.
Кодирование по алгоритму Хафмана
| N | 
| код | 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.3 показано кодирование по алгоритму Хафмана. Как видно из таблицы, кодирование осуществлялось за семь этапов. Слева указаны вероятности символов, справа – промежуточные коды. Стрелками показаны перемещения вновь образованных символов. На каждом этапе два последних символа отличаются только младшим разрядом, что соответствует методике кодирования. Вычислим среднюю длину слова:
Недостатком кода Хафмана можно считать то, что нулевая кодовая комбинация не всегда соответствует наименее вероятному символу. Это может привести к потере этого символа при передаче нулей низкими уровнями.
Оба кода удовлетворяют требованию однозначности декодирования: как видно из таблиц, более короткие комбинации не являются началом более длинных кодов.
При увеличении количества символов эффективности кодов возрастают, поэтому в некоторых случаях кодируют более крупные блоки (например, если речь идет о текстах, можно кодировать некоторые наиболее часто встречающиеся слоги, слова и даже фразы).
Эффект от внедрения таких кодов определяется в сравнении их с равномерным кодом:
| (2.24) |
где 
– количество разрядов равномерного кода, который заменяется эффективным.
Классический алгоритм Хафмана относится к двухпроходным, т. е. требует вначале набора статистики по символам и сообщениям, а потом описанных выше процедур. Это неудобно на практике, поскольку увеличивает время обработки сообщений и накопления словаря. Чаще используются однопроходные методы, в которых процедуры накопления и кодирования совмещаются. Такие методы называются ещё адаптивным сжатием по Хафману [48].
Сущность адаптивного сжатия по Хафману сводится к построению первоначального кодового дерева и последовательной его модификации после поступления каждого очередного символа. Как и прежде, деревья здесь бинарные, т. е. из каждой вершины графа – дерева исходит максимум две дуги. Принято называть исходную вершину родителем, а две связанных с ней следующих вершины – детьми. Введём понятие веса вершины – это количество символов (слов), соответствующих данной вершине, полученных при подаче исходной последовательности. Очевидно, что сумма весов детей равна весу родителя.
После введения очередного символа входной последовательности пересматривается кодовое дерево: пересчитываются веса вершин и при необходимости вершины переставляются. Правило перестановки вершин следующее: веса нижних вершин наименьшие, причём вершины, находящиеся слева на графе, имеют наименьшие веса.
Одновременно вершины нумеруются. Нумерация начинается с нижних (висячих, т. е. не имеющих детей) вершин слева направо, потом переносится на верхний уровень и т.д. до нумерации последней, исходной вершины. При этом достигается следующий результат: чем меньше вес вершины, тем меньше её номер.
Перестановка осуществляется в основном для висячих вершин. При перестановке должно учитываться сформулированное выше правило: вершины с большим весом имеют и больший номер.
После прохождения последовательности (она называется также контрольной или тестовой) всем висячим вершинам присваиваются кодовые комбинации. Правило присвоения кодов аналогично вышеизложенному: количество разрядов кода равно количеству вершин, через которые проходит маршрут от исходной до данной висячей вершины, а значение конкретного разряда соответствует направлению от родителя к «ребёнку» (скажем, переход влево от родителя соответствует значению 1, вправо – 0).
Полученные кодовые комбинации заносятся в память устройства сжатия вместе с их аналогами и образуют словарь. Использование алгоритма заключается в следующем. Сжимаемая последовательность символов разбивается на фрагменты в соответствии с имеющимся словарём, после чего каждый из фрагментов заменяется его кодом из словаря. Не обнаруженные в словаре фрагменты образуют новые висячие вершины, приобретают вес и также заносятся в словарь. Таким образом формируется адаптивный алгоритм пополнения словаря.
Для повышения эффективности метода желательно увеличивать размер словаря; в этом случае коэффициент сжатия повышается. Практически размер словаря составляет 4 – 16 килобайт памяти.
Проиллюстрируем приведённый алгоритм примером. На рис. 2.12 приведена исходная диаграмма (её называют также деревом Хафмана). Каждая вершина дерева показана прямоугольником, в котором вписаны через дробь две цифры: первая означает номер вершины, вторая – её вес. Как можно убедиться, соответствие весов вершин и их номеров выполняется.
| 
|
| Рис. 2.12. Исходное дерево кода Хафмана | Рис. 2.13. Изменение весов |
Предположим теперь, что символ, соответствующий вершине 1, в тестовой последовательности встретился вторично. Вес вершины изменился, как показано на рис. 2.13, вследствие чего правило нумерации вершин нарушено. На следующем этапе меняем расположение висячих вершин, для чего меняем местами вершины 1 и 4 и перенумеровываем все вершины дерева. Полученный граф приведён на рис. 2.14. Далее процедура продолжается аналогично.
Рис. 2.14. Перестановки в дереве Хафмана
Следует помнить, что каждая висячая вершина в дереве Хафмана соответствует определённому символу или их группе. Родитель отличается от детей тем, что группа символов, ему соответствующая, на один символ короче, чем у его детей, а эти дети различаются последним символом. Например, родителю соответствуют символы «кар»; тогда у детей могут быть последовательности «кара» и «карп».
Дата добавления: 2018-02-18; просмотров: 637; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!