Методы арифметического кодирования информации и сравнение их коэффициентов сжатия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
информации. Основная идея арифметического кодирования была сформулирована Элайесом ещё в начале 60-х годов. Преимущество арифметического кода по отношению к другим методам заключается в том, что он позволяет достичь произвольно низкой избыточности на символ источника (избыточность - центральное понятие в теории сжатия информации. Любые данные с избыточной информацией можно сжать; в которых нет избыточности - сжать нельзя). Показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов.
Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента Xi (экспоненту Ei) и отдельно - значащие цифры значения (мантиссу Mi).
Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, сжимающее преобразование) равна скорости декомпрессора (реализующего обратное, разжимающее преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.
Существует четыре варианта этого метода:
Fixed+Fixed (фиксированная длина экспоненты - фиксированная длина мантиссы)
Fixed+Variable (фиксированная длина экспоненты - переменная длина мантиссы)
Variable+Variable (переменная длина экспоненты - переменная длина мантиссы)
Variable+Fixed (переменная длина экспоненты - фиксированная длина мантиссы)
В данной работе будут рассмотрены коды переменной длины (Variable+Variable).
.1 Унарный код
Унарный код сопоставляет числу i двоичную комбинацию вида 10.Запись вида 0 или 1 означает соответственно серию из m нулей или единиц. Например, унарными кодами чисел 1, 2, и 3 являются последовательности unar(1)=10, unar(2)=110 и unar(3)=1110 соответственно. Длина кодового слова для числа n равна ln=n+1. На рисунке 1.1 приведен унарный код чисел от 0 до 6.
Рисунок 1.1 - Унарный код чисел от 0 до 6
Унарный код оптимален, если числа i распределены по геометрическому закону (1.1) с параметром =:
p=(1-), (1.1)
где i=1,2,
Для значений < более эффективен код Голомба.
.2 Код Голомба
Коды Голомба - это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Кодирование энтропии- кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равна -logP, где b- это количество символов, используемых для изготовления выходного кода, и Р- вероятность входного символа. Унарный код - это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем ( либо n нулей и единица). Например, 5 представляется в виде 111110. Унарное кодирование оптимально для распределения вероятности: P(x)=2. Также под кодом Голомба может подразумеваться один из представителей этого семейства.
Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону (1.2):
P(i) = (1-p)p, (1.2)
где i - номер символа, а р - параметр геометрического распределения. Также должно соблюдаться условие (1.3):
p= , (1.3)
где m - основной параметр кода Голомба.
Для кодирования символа с номером n необходимо представить n в виде (1.4):
n = qm + r, (1.4)
где q и r - целые положительные числа, 0 r < m.Затем r кодируется унарным кодом, а q - бинарным. Полученные двоичные последовательности объединяются в результирующее слово.
Пример: Основной параметр кода m=4, кодируемое число n=13 .
Частное q===3;
унарный код q - 1110;
остаток r=n mod m=13 mod 4=1;
бинарный код r - 01;
результирующее кодовое слово - 111001.
Рассмотрим несколько примеров кодов Голомба для различного параметра m в таблице 1.1:
Таблица 1.1 - Коды Голомба для различных параметров m
n\ m 1 2 3 4 50000000000001100101000100121101000110100103111010110001101104111101100101010000111511111011011011100110006111111011100110010101001711111110111011101010111010811111111011110011011110001011091111111110111101111001100110111101111111111011111001110101101011000111111111111101111101111011110111100112111111111111011111100111100111000110101311111111111110111111011111010111001110110141111111111111101111111001111011111010110111151111111111111110111111101111110011101111100016111111111111111101111111100111110101111000111001171111111111111111101111111101111110111111001111010
Ниже приводится рисунок 1.2, поясняющий устройство данных кодов: как именно двоичное представление остатка следует за унарным кодом :
Рисунок 1.2 - Формирование кодов Голомба
.3 Код Райса
Код Райса идентичен коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2k.
Введем параметр Т=2 . Код Райса для числа n состоит из двух частей. Первая часть - унарный код числа [], вторая часть - двоичная запись в виде последовательности длины k остатка от деления n на T. Очевидно, длина кода Райса для числа n равна ln=[]+1+k. Например, при k=3 и n=21 имеем []=2, остаток равен 5. Поэтому кодом Райса числа 21 будет последовательность 110101.
Рассмотрим несколько примеров кодов Райса для различных параметров k, которые представлены в таблице 1.2:
&n