Методы арифметического кодирования информации и сравнение их коэффициентов сжатия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
bsp;
Таблица 1.2 - Коды Райса для различных параметров k
n\ k 1 2 3 456000000000000000000000000000110001000100001000001000000121100100010000100000100000010311100110011000011000011000001141111010000100000100000100000010051111101001010100010100010100001016111111010100110000110000110000011071111111010110111000111000111000011181111111101100010000001000001000000100091111111110110011000100100100100100010011011111111110110101001000101000101000010101111111111111011011100110010110010110001011121111111111110111000101000011000011000001100131111111111111011100110101001101001101000110114111111111111110111010101100011100011100001110151111111111111110111011101110011110011110001111
Код Райса - это частный случай кода Голомба, это легко увидеть из таблицы 1.3, представленной ниже:
Таблица 1.3 - Сравнительная таблица кода Райса и кода Голомба
Код Голомбаm=1m=2m=3m=4m=5m=6m=7m=8Код Райсаk=0k=1k=2k=3n=1000000000000000000000 2100101000100100100100001 3110100011010010010000110010 411101011000110110010101000011 5111101100101010000111011001010100 61111101101101110011000011101100101 7111111011100110010101001100001110110 8…111011101010111010100110000111 9…111100110111100010110101001001010000
.4 Коды Фибоначчи
Самые интересные, нетривиальные коды. В данном кодировании исходное число n раскладывается в сумму чисел Фибоначчи fi (f1 = 1; f2 = 2; fi = fi?1 + fi?2). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.
Заметим также, что если в разложении числа n присутствует fi, то в этом разложении не может быть числа fi+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.
Рассмотрим несколько примеров кодов Фибоначчи в таблице 1.4:
Таблица 1.4 - Примеры кода Фибоначчи
n\f1235813213411(1)201(1)3001(1)4101(1)50001(1)61001(1)70101(1)800001(1)…………………1210101(1)13000001(1)……………………20010101(1)210000001(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, nN
Иногда числа Фибоначчи рассматривают и для неположительных номеров 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 7F 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 - Гамма-коды Элиаса малых натуральных чисел
ЧислаКодДлина1112-301х34-7001хх58-150001ххх716-3100001хххх932-63000001ххххх1164-1270000001хххххх13
1.6 Дельта-коды Элиаса
Дельта-код Элиаса является производным от гамма-кода. В начале кодируется количество значащих двоичных разрядов в числе посредством гамма-кода, после чего записываются все значащие разряды, за исключением старшей единицы (общим количеством на 1 меньше закодированного количества). В таблице 1.7 приведены дельта-коды Элиаса для некоторых чисел. Закодированное количество разрядов и остальная часть числа разделены пробелом. Знаки х соответствуют разрядам двоичного представления кодируемого числа.
Таблица 1.7 - Дельта-коды Элиаса для некоторых чисел
ЧислаКодДлина1112-3010 х44-7011 хх58-1500100 ххх816-3100101 хххх932-6300110 ххххх1064-12700111 хххххх11128-2550001000 ххххххх14256-5110001001 хххххххх15
Дельта-код даёт более оптимальное распределение длин для больших чисел, чем для малых (отношение длины кода к числу его разрядов стремится к единице).
Несколько примеров ? и ? кодов Элиаса приведены в таблице 1.8:
Таблица 1.8 - ? и ? коды Элиаса
n-код-код0-1110 12…301х0 01х4…7001хх0 001хх8…150001ххх0 0001ххх16…3100001хххх0 00001хххх32…63000001ххххх0 000001ххххх
.7 Омега-код Элиаса
Омега-код Элиаса (рекурсивный код Элиаса) состоит из нескольких битовых групп, начинающихся с единичного бита, и замыкаемых нулевым битом [1]. Первая группа всегда имеет длину 2 бита. Длина каждой последующей группы определяется как на единицу большая, чем значение предыдущей. Последняя группа выражает кодируемое число. Исключение составляет число 1, оно кодируется единственным битом 0. Примеры кодов приведены в таблице 1.9:
Таблица 1.9 - Омега коды Элиаса
ЧислоКодДлина1012-31х 034-710 1хх 068-1511 1ххх 0716-3110 100 1хххх 01132-6310 101 1ххххх 01264-12710 110 1хххххх 013128-25510 111 1ххххххх 014256-51111 1000 1хххххххх 016512-102311 1001 1ххххххххх 017
Количество групп в коде возрастает быстро вначале, но далее - очень медленно:
для 1 будет 0 групп;
2 ... 3 (21 ... 22 ? 1) - 1 группа;
4 ... 15 (22 ... 222 ? 1) - 2 группы;
16 ... 65536 (222 ... 2222 ? 1) - 3 группы;
65536 ... 2 1019728 (2222 ... 22222 ? 1) - всего 4 группы.
.8 Коды Ивэн- Родэ
Данные коды, также как и омега-коды Элиаса, состоят из последовательности групп длинной L1, L2, L3, …, Lm би?/p>