Интернет магазин китайских планшетных компьютеров

Компьютеры - Сжатие звука без потерь - Кодирование. Алгоритм Райса

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

Меньшие числа предпочтительней тем, что их представление в бинарном представлении короче. Например, необходимо закодировать следующий ряд:

Базис по основанию 10: 10, 14, 15, 46

Или тот же ряд в бинарном виде

Базис по основанию 2: 1010, 1110, 1111, 101110

Теперь если требуется представить этот в виде строки, где для каждого числа зарезервировано 32 бита, то это будет неэффективно, поскольку понадобится 128 бит. Однако существует более эффективный метод. Наилучшим решением было бы просто записать бинарные числа 1010, 1110, 1111, 101110 без запятых, получив ряд вида 101011101111101110. Проблема в том, что после нет возможности узнать границы каждого числа. В качестве решения подобной задачи, как правило, используется алгоритм Райса.

Кодирование Райса — это способ представить маленькие числа одной строкой, сохраняя способность их различать.

Примечание: алгоритм тем эффективнее, чем меньше числа, поэтому необходимо изначально позаботиться об этом

На каком-то этапе кодирования данные представлены в виде числа n. Закодированное, оно добавляется справа к строке уже закодированных чисел таким образом, чтобы был возможен обратный процесс.

Основная идея представить число n как n = q * 2 + r, так чтобы 0 <= r < 2^k.

Так как в машинном языке существует сверхбыстрая команда ротации числа, соответствующая делению числа на степени двойки, достаточно использовать k=log n/log 2, округленное до наименьшего целого числа. Таким образом, в алгоритме гарантированно выполняются условия для k. Исходя из формулы, необходимо определить число q и остаток r: r = mod. Например,

n = 46 = 101110
k = 4

Тогда r = mod = 14. q = 2. 46 = 2 * 2 + 14

Далее строится кодированное число по следующей схеме. Первыми идут нули, количеством в q штук. Затем справа к нулям добавляется маркировочный бит, чтобы знать когда кончаются нули. А за ними дописывается остаток r, длиной в k бит.

То есть число 46 в закодированном виде выглядит = 0011110

Теперь, с учетом определенности k, которым кодировалось число, можно с легкостью его расшифровать:

* 2 + = 2*2+14 = 46

Следующее число начинается сразу же со следующего бита.

Если данные кодируются с помощью слишком большого числа k, например k=32, тогда способ превращается в описанный в начале раздела метод, когда каждому числу соответствует 32 бита, только оно предваряется бесполезным маркировочным битом. В случае малого k количество нулей экспоненциально возрастает — для k=0. Для представления числа 46 понадобится 46 нулей и 1 маркировочный бит. Оптимальный вариант, учитывая, что в ряду калибровочные изменения минимальны, — это кодировать среднестатистическим значением для k, например для кодирования сотого числа k высчитывается как среднестатистический размер чисел в массиве под индексами 0…99.

Например, для 16-ти разрядного представления отсчетов число 46 будет представлено следующим двоичным кодом: 0000000000011110. После перекодировки это же число будет содержать всего лишь 7 разрядов: 0011110.

Оптимальное k может быть вычислено и экспериментальным способом: например, любое k между 16…128 нормально работает. В любом случае, если известен примерный диапазон закодированных значений, то оптимальное значение для k = log n / log 2.