|
|
|
|
|
01011000 |
Таким образом, операция подстановки непредсказуемым образом искажает исходные данные. Для восстановления исходных данных достаточно выполнить подстановку вторично:
01011000
11001011
10010011
Операция перемешивания заключается в обмене местами двух блоков в соответствии с заранее составленными таблицами. Длина обмениваемых блоков одинакова, но варьирует от одного прохода к другому. Операция подстановки выполняется не над целым ключом, а над случайно выбираемой его частью. Эта случайно выбираемая часть сама определяется значением ключа. Одним из способов получения псевдослучайных чисел является следующий:
.
(1.15)
Здесь – псевдослучайное число, порожденное на шаге i. первоначально полагают, например, . В качестве константы C примем
,
(1.16)
где K – секретный ключ. Величина M как правило равна ; величина n равна числу разрядов генерируемого псевдослучайного числа. Например, пусть , , , , :
,
,
,
,
и т.д.
Порожденные псевдослучайные числа могут определять номера разрядов, выбираемых из ключа в формируемую часть для выполнения операции подстановки.
Для дешифрации принятой комбинации нужно знать ключ K и выполнять операции подстановки и перемешивания в обратном порядке
Сжатие по методу Д. Хаффмана
Метод сжатия Хаффмана является одним из лучших способов сжатия информации. Данный метод мы изложим на следующем примере. Пусть дана подлежащая сжатию последовательность из «0» и «1»:
010000101000101111001011.
(1.17)
Разобьем эту последовательность на тройки разрядов и для каждой тройки подсчитаем, сколько раз она встречается в последовательности (рис. 1.13)
010’000’101’000’101’111’001’011
010 – 1
000 – 2
101 – 2
111 – 1
001 – 1
011 – 1
a)
000 – 2
101 – 2
010 – 1
111 – 1
001 – 1
011 – 1
b)
Рис. 1.13.
Упорядочим комбинации по частоте встречаемости (рис. 1.13b). Теперь «объединим» две последние комбинации на рис. 1.13b в одну и все комбинации снова переупорядочим по убыванию частоты встречаемости (рис. 1.14)
‘001-011’ – 2
000 – 2
101 – 2
010 – 1
111 – 1
Рис. 3.14.
Теперь снова объединим две последние комбинации в одну и проведем очередное упорядочение (рис. 1.15)
‘010-111’ – 2
‘001-011’ – 2
000 – 2
101 – 2
Рис. 1.15.
Дальнейший процесс объединения комбинаций выполним по аналогии (рис. 1.16, 1.17)
‘000-101’ – 2
‘010-111’ – 2
‘001-011’ – 2
Рис. 3.16.
‘010-111-001-011’ – 4
‘000-101’ – 4
Рис. 3.17.
Теперь нарисуем дерево, схематически передающее реализованный нами способ объединения комбинаций (рис. 1.18)
Рис. 1.18.
Для полученного дерева выполним движение с корневой вершины к исходным тройкам. При выходе из любого узла помечаем одно из двух ребер «1», а другое – «0» (рис. 1.18). Итак, запомним, что разметка выполняется при движении справа на лево по построенному дереву. Теперь новый код для любой из исходных троек получаем как комбинацию, сопоставляемую пути из корня в данную вершину. Получаем следующее соответствие исходных троек и новых комбинаций:
000 – 11
101 – 10
010 – 001
111 – 010
001 – 001
011 – 000
С учетом нового способа кодировки исходная последовательность (1.17) может быть переписана таким образом:
01111101110010001000.
(1.18)
Длина последовательности (3.18) сократилась в сравнении с длиной (1.17) с 24 бит до 20 бит. Основной принцип кодирования Хаффмана состоит в том, что часто встречаемые комбинации кодируются более короткими последовательностями. Таким образом, общая длина последовательности оценивается как
,
(1.19)
где – число битов в i-ой комбинации,
– относительная частота встречаемости i-ой комбинации.
Было замечено, хотя это и не обязательно верно во всех случаях, что длина кода Хаффмана комбинации , как правило, не превосходит величину (– ). Так, в нашем примере относительная частота комбинации 000 составляет . Ее код Хаффмана есть 11 (длина этого кода равна 2). Имеем
(что справедливо).
Таким образом, при кодировании Хаффмана результирующую длину кода можно ориентированно записать в виде
.
(1.20)
Кодирование Хаффмана модно применять повторно.
Арифметическое кодирование
Пусть имеется последовательность
.
(1.21)
Относительная частота символов:
, , .
При арифметическом кодировании последовательность (1.21) заменяется одним единственным числом. Для получения этого числа разобьем интервал [0,1] на подинтервалы:
[0; 0,25], (0,25; 0,75], (0,75; 1].
(1.22)
Заметим, что длина каждого подинтервала соответствует относительной частоте соответствующего символа. Нетрудно сообразить, что первый подинтервал [0; 0,25] соответствует ; подинтервал (0,25; 0,75] – символу и (0,75; 1] – символу . В последовательности (3.22) первый символ . Ему соответствует интервал [0; 0,25]. Поэтому выбираем этот подинтервал и делим его опять согласно относительным частотам символов:
[0; 0,0625), [0,0625; 0,1875), [0,1875; 0,25].
(1.23)
Следующий символ – . Ему соответствует интервал (0,0625; 0,1875]. Делим его на подинтервалы:
[0,0625; 0,09375), [0,09375; 0,15625), [0,15625; 0,1875].
(1.24)
Следующий символ – . Выбираем второй подинтервал (0,09375; 0,15625]. Делим его на три подинтервала соответственно частотам символов:
[0,09375; 0,109375), [0,109375; 0,140625), [0,140625; 0,15625].
(1.25)
Наконец, последний символ – . Ему соответствует третий интервал. Поэтому в качестве окончательного кода для последовательности (1.21) можно указать любое число из интервала [0,140625; 0,15625]. Например, возьмем 0,15. Итак, последовательность (1.21) кодируется числом 0.15.
Чтобы восстановить исходную последовательность, нужно действовать таким образом. Согласно частотам символов составляем исходное разбиение (1.22). Видим, что наш код 0,15 попадает в первый подинтервал [0; 0,25]. Значит первый символ – . Далее разбиваем интервал [0; 0,25] на три подинтервала (1.23) и смотрим, к какому из них принадлежит наш код 0,15. Теперь этот второй подинтервал, поэтому следующий символ . Далее из представления (1.24) снова выбираем второй подинтервал и символ . Наконец, из (1.25) выбираем символ .
Арифметическое сжатие может давать большие последовательности цифр и поэтому его применение ограничивается небольшими последовательностями символов.
Сжатие графических файлов
Сжатие графической информации основано на частичной потере информации. В самом деле, в изображении соседние пиксели (точки) мало различаются по яркости (светимости) и цвету. Особенностью является то обстоятельство, что глаз человека меньше различает именно светимость двух соседних точек. Поэтому модель данных YCbCr в большей степени ориентирована на сжатие, чем модель RGB. Для получения сжатого изображения применяют ортогональные преобразования данных. Ортогональные преобразования выполняют таким образом, чтобы большая часть данных при преобразовании получила маленькие (близкие к нулю значения) и лишь небольшая часть данных оказалась значимой. Затем выполняется квантование (округление данных) так, что малозначимые данные становятся равными 0. Дадим иллюстрацию сказанному. Пусть исходные данные представлены следующей матрицей:
.
Возьмем матрицу преобразования:
.
(1.26)
Сначала найдем по правилам матричной алгебры произведение
,
затем
.
(1.27)
Получим
.
В этой матрице доминирует лишь небольшое число элементов. Можно выполнить квантование, например, следующим образом:
.
Именно эта операция (квантования) и приводит к потере данных, хотя эта потеря мало отражается на исходных данных. В самом деле, легко восстановить из (3.27) матрицу С:
.
(1.28)
и, аналогично,
.
(1.29)
С помощью (3.28), (3.29) получим восстановленную приближенную матрицу исходных данных:
.
После квантования получим
.
Эта последняя матрица очень близка к исходной матрице D (!).
Прежде всего, заметим, что матрица преобразования W должна строится специальным образом. Во-первых, она должна быть ортогональной, что означает, что векторное произведение любых ее двух строк или столбцов равно 0 (а это означает, что строки и столбцы матрицы не зависимы и, следовательно, определитель матрицы отличен от 0). Во-вторых, матрица W подбирается так, что сумма элементов только в первой строке и в первом столбце максимальны; в остальных строках и столбцах суммы элементов равны или близки к 0.
При использовании материалов активная ссылка на источник обязательна.