Описание программы кодирования Хаффмана

 

Числа Фибоначчи – элементы числовой последовательности:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …,

в которой каждое последующее  число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи).

Более формально, последовательность чисел Фибоначчи {F } задается рекуррентным соотношением:

F =1, F =1, F =F +F , n N

Иногда числа  Фибоначчи рассматривают и для  неположительных номеров n как двусторонне  бесконечную последовательность, удовлетворяющую  основному соотношению. Члены с  такими номерами легко получить с  помощью эквивалентной формулы «назад» (1.5):

 

F =F - F   (1.5)

 

Пример двусторонне  бесконечной последовательности чисел  Фибоначчи представлен в таблице 1.5:

 

 

Таблица 1.5–Двусторонняя  последовательность чисел Фибоначчи в интервале [-7..7]

n	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7
F	13	-8	5	-3	2	-1	1	0	1	1	2	3	5	8	13

 

Легко видеть, что F =(-1) F .

 

5)Д Гамма- коды Элиаса

 

Гамма-код Элиаса — двоичный префиксный код представления  натуральных чисел. Число кодируется в два этапа. Определяется количество двоичных разрядов кодируемого числа. Вначале кодируется n посредством  инвертированного унарного кода, после чего в неизменном виде дописываются n младших разрядов (старший единичный разряд, таким образом, опускается). Иными словами, код представляет собой число в двоичном представлении, заполненное нулями на 1 меньшей длины. В сумме длина кода должна равняться 2 n + 1. В таблице 1.6 приведены гамма-коды Элиаса малых натуральных чисел:

 

Таблица 1.6 –  Гамма-коды Элиаса малых натуральных  чисел

Числа	Код	Длина
1	1	1
2-3	01х	3
4-7	001хх	5
8-15	0001ххх	7
16-31	00001хххх	9
32-63	000001ххххх	11
64-127	0000001хххххх	13

 

 

6) Дельта-коды Элиаса

 

Дельта-код Элиаса является производным от гамма-кода. В начале кодируется количество значащих двоичных разрядов в числе посредством  гамма-кода, после чего записываются все значащие разряды, за исключением  старшей единицы (общим количеством на 1 меньше закодированного количества). В таблице 1.7 приведены дельта-коды Элиаса для некоторых чисел. Закодированное количество разрядов и остальная часть числа разделены пробелом. Знаки х соответствуют разрядам двоичного представления кодируемого числа.

 

Таблица 1.7 –  Дельта-коды Элиаса для некоторых  чисел

Числа	Код	Длина
1	1	1
2-3	010 х	4
4-7	011 хх	5
8-15	00100 ххх	8
16-31	00101 хххх	9
32-63	00110 ххххх	10
64-127	00111 хххххх	11
128-255	0001000 ххххххх	14
256-511	0001001 хххххххх	15

 

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

Несколько примеров γ и δ кодов Элиаса приведены  в таблице 1.8:

 

Таблица 1.8 –  γ и δ коды Элиаса

n	-код	-код
0	-	1
1	1	0 1
2…3	01х	0 01х
4…7	001хх	0 001хх
8…15	0001ххх	0 0001ххх
16…31	00001хххх	0 00001хххх
32…63	000001ххххх	0 000001ххххх

 

7) Омега-код Элиаса

 

Омега-код Элиаса (рекурсивный код Элиаса) состоит из нескольких битовых групп, начинающихся с единичного бита, и замыкаемых нулевым битом [1]. Первая группа всегда имеет длину 2 бита. Длина каждой последующей группы определяется как на единицу большая, чем значение предыдущей. Последняя группа выражает кодируемое число. Исключение составляет число 1, оно кодируется единственным битом 0. Примеры кодов приведены в таблице 1.9:

 

Таблица 1.9 –  Омега коды Элиаса

Число	Код	Длина
1	0	1
2-3	1х 0	3
4-7	10 1хх 0	6
8-15	11 1ххх 0	7
16-31	10 100 1хххх 0	11
32-63	10 101 1ххххх 0	12
64-127	10 110 1хххххх 0	13
128-255	10 111 1ххххххх  0	14
256-511	11 1000 1хххххххх 0	16
512-1023	11 1001 1ххххххххх  0	17

 

Количество  групп в коде возрастает быстро вначале, но далее — очень медленно:

• для 1 будет 0 групп;
• 2 ... 3 (2¹ ... 2² − 1) — 1 группа;
• 4 ... 15 (2² ... 2²² − 1) — 2 группы;
• 16 ... 65536 (2²² ... 2²²² − 1) — 3 группы;
• 65536 ... 2 · 10¹⁹⁷²⁸ (2²²² ... 2²²²² − 1) — всего 4 группы.

 

8) Коды Ивэн- Родэ

 

Данные коды, также как и омега-коды Элиаса, состоят из последовательности групп длинной L₁, L₂, L₃, …, L_m бит [1], которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m−1 групп служат лишь для указания длины последней группы.

В Ивэн-Родэ-кодах  длина первой группы — 3 бита, а длина  каждой последующей группы равна  значению предыдущей. Первые три значения заданы особым образом.

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

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

Рассмотрим несколько примеров кодов Ивэн-Родэ - таблица 1.10:

 

Таблица 1.10 – Коды Ивэн-Родэ

n	Код Ивэн-Родэ
0	000
1	001
2	010
3	011
4	100 0
16	101 10000 0
32	110 100000 0
100	111 1100100 0

 

9) Код Левенштейна

 

Этот код  проще всего объяснить на конкретном примере. Предположим, что нужно передать число n=21. Двоичное представление этого числа имеет вид 10101. Непосредственно использовать при кодировании двоичные представления натуральных чисел нельзя. Самый простой выход состоит в том, чтобы приписать в начале слова префикс, указывающий длину двоичной записи числа (в данном случае это число 5). Если это число закодировать унарным кодом и приписать слева к двоичной записи числа, то код получится однозначно декодируемым. В данном примере для числа 21 получим кодовое слово 11111010101. В общем случае длина двоичного представления будет равна 2[logn].

Шаг за шагом  будем улучшать этот способ кодирования. Важно заметить, что первая значащая цифра двоичной записи числа –  всегда 1. Её можно не передавать, декодер  сам допишет недостающую единицу, если будет знать длину двоичной записи числа. Обозначим через bin’(n) двоичную запись натурального числа n без первой единицы.

Длины кодовых  слов равны (1.6):

 

l_n=2[log n]+1    (1.6)

 

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

Например, для  числа 21 вычисляется bin'(21)=0101, затем bin'(4)=00, bin'(2)=0. Число итераций равно 3, поэтому кодовое слово кода Левенштейна имеет вид lev(21)=(1110)(0)(00)(0101)=11100000101. Декодер кода Левенштейна, декодируя унарный код, узнает, что итераций было три. Прочитав один значащий разряд (0) и дописав к нему в начало 1, получает последовательность 10. Это означает, что на предпоследней итерации длина числа была 2. Прочитав 2 разряда и дописав слева 1, получает 100. Теперь декодер считает 4 разряда и дописывает слева 1. Получается последовательность 10101, ей соответствует число 21. Поскольку это уже последняя 3-я итерация, число 21 является результатом декодирования.

Ниже приведена  таблица 1.11 – таблица кодов Левенштейна  для некоторых чисел натурального ряда.

 

Таблица 1.11 –  примеры кодов Левенштейна

n	Код Левенштейна
	Lev(n)	ln
1	0	1
2	100	3
3	101	3
4	110000	6
…	…	6
7	110011	6
8	1101000	7
…	…	7
15	1101111	7
16	11100000000	11
…	…	11
31	11100001111	11
32	111000100000	12
…	…	12
63	111000111111	12
2	1 01111110	26
2	1 010011 0	1041

 

Коды Левенштейна  и Элиаса практически эквивалентны, выигрыш кода Левенштейна проявляется  только при астрономически больших значениях n.

 

10) Гамма-коды Левенштейна

 

Данный код  для числа n получается путем обращения  последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n.

Рассмотрим  несколько примеров кодов Левенштейна  в таблице 1.12:

 

Таблица 1.12 – Коды Левенштейна

n	Гамма-код Левенштейна
1	1
5	01001
13	0100011
63	01010101011
129	010000000000001

 

Подчеркиванием  показаны флаговые биты. Заметим, что  последним таким битом всегда будет единица, которая являлась старшим битом в двоичном представлении  кодируемого числа.

 

11) Старт-шаг-стоп коды (Start-step-stop codes)

 

Эти коды определяются тремя параметрами {i, j, k}. Код определяет серии блоков кодовых слов возрастающей длины: первый блок с числовой частью длиной i битов, второй — i + j битов, затем — i + 2j битов, и так далее до длины k битов. Группы кодовых слов имеют унарный префикс, дающий номер группы. Таким образом, код {3, 2, 9} имеет кодовые слова с числовой частью 3, 5, 7 и 9 бит и префиксы 0, 10, 110 и 111 (опуская последний 0 в последнем префиксе). Данные коды представлены в таблице 1.13 и выглядят так:

 

Таблица 1.13 –  Старт-шаг-стоп коды

Кодовое слово	Диапазон
0xxx	0-7
10xxxxx	8-39
110xxxxxxx	40-167
111xxxxxxxxx	168-679

 

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

Восстановление  числа n по заданному {i, j, k}-start-step-stop коду

Пусть дан {i, j, k}-код  и пусть количество единиц в унарной  части (экспоненты) равно Q. Тогда число n (закодированное число) равно (1.7):

 

, (1.7)

 

где β — мантисса записанного кода, Dec(x) — функция, переводящая x в десятичную систему счисления.

Получение {i, j, k}-start-step-stop кода по заданному числу n

Теперь наоборот, пусть задано число n. Для получения  его кода необходимо найти такое  минимальное положительное число Q₀, чтобы выполнялось неравенство (1.8):