Методы арифметического кодирования информации и сравнение их коэффициентов сжатия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? [1], которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m?1 групп служат лишь для указания длины последней группы.
В Ивэн-Родэ-кодах длина первой группы - 3 бита, а длина каждой последующей группы равна значению предыдущей. Первые три значения заданы особым образом.
При кодировании формируется сначала последняя группа, следующая непосредственно перед нулем, а потом по очереди восстанавливаются все предыдущие группы одна за другой, пока процесс не будет завершен.
При декодировании, наоборот, группы получаются, начиная с первой, одна за другой, то есть по значению битов уже найденной группы определяется длина последующей и так далее, пока не будет найдена итоговая группа, после которой идет ноль.
Рассмотрим несколько примеров кодов Ивэн-Родэ - таблица 1.10:
Таблица 1.10 - Коды Ивэн-Родэ
nКод Ивэн-Родэ00001001201030114100 016101 10000 032110 100000 0100111 1100100 0
.9 Код Левенштейна
Этот код проще всего объяснить на конкретном примере. Предположим, что нужно передать число n=21. Двоичное представление этого числа имеет вид 10101. Непосредственно использовать при кодировании двоичные представления натуральных чисел нельзя. Самый простой выход состоит в том, чтобы приписать в начале слова префикс, указывающий длину двоичной записи числа (в данном случае это число 5). Если это число закодировать унарным кодом и приписать слева к двоичной записи числа, то код получится однозначно декодируемым. В данном примере для числа 21 получим кодовое слово 11111010101. В общем случае длина двоичного представления будет равна 2[logn].
Шаг за шагом будем улучшать этот способ кодирования. Важно заметить, что первая значащая цифра двоичной записи числа - всегда 1. Её можно не передавать, декодер сам допишет недостающую единицу, если будет знать длину двоичной записи числа. Обозначим через bin(n) двоичную запись натурального числа n без первой единицы.
Длины кодовых слов равны (1.6):
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)ln101210033101341100006……671100116811010007……71511011117161110000000011……113111100001111113211100010000012……1263111000111111122101111110262101001101041
Коды Левенштейна и Элиаса практически эквивалентны, выигрыш кода Левенштейна проявляется только при астрономически больших значениях n.
.10 Гамма-коды Левенштейна
Данный код для числа n получается путем обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n.
Рассмотрим несколько примеров кодов Левенштейна в таблице 1.12:
Таблица 1.12 - Коды Левенштейна
nГамма-код Левенштейна115010011301000116301010101011129010000000000001
Подчеркиванием показаны флаговые биты. Заметим, что последним таким битом всегда будет единица, которая являлась старшим битом в двоичном представлении кодируемого числа.
1.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 - Старт-шаг-стоп коды
Кодовое словоДиапазон0xxx0-710xxxxx8-39110xxxxxxx40-167111xxxxxxxxx168-679
Далее приводится общая формула для восстановления числа по коду, а также алгоритм, позволяющий получить код по заданному числу n.
Восстановление числа n по заданному {i, j, k}-start-step-stop коду