Сжатие звука без потерь

Звук является простой волной, а оцифрованный звук — цифровое представление этой волны. Это достигается запоминанием уровня аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за секунду. Так как CD работает со стерео, мы запоминаем сигнал для левой и правой колонки параллельно. Для каждого замера используются 16-битовые числа. Поэтому нетрудно посчитать, что одна секунда звучания занимает 2 × 2 × 44100 = 176 400 байт.

Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это:

Знание границ семплов: мы знаем, сколько битов или байтов отводится на один отсчёт (семпл), и сколько в семпле аудиоканалов.
Невысокая производная: другими словами, значения соседних семплов мало отличаются.
Невысокая вторая производная: значения соседних трёх семплов близки к линейной функции.
Близость левого и правого каналов: уровни сигнала в левой и в правой колонке, как правило, близки.

Преобразование координат (L, R) → (X, Y)

Первым шагом в сжатии будет представление каналов аудио L и R более эффективным образом, представив их некими числами X, Y согласно следующему алгоритму:

$X=(L+R)/2$
$Y=L-R$

Для дробных чисел это преобразование не теряет информации и является эквивалентным оригинальному. Для целых же $(L+R)/2$ теряет 0,5 при конверсии в integer, когда L и R имеют разную чётность, но, проверив чётность $L-R$ , легко восполняем эти 0,5.

Предиктор

Следующий шаг — пропустить X и Y через алгоритм, который максимально эффективно уберёт весь избыток информации в представлении X, Y.

В данном случае весь процесс направлен на представление массивов X, Y минимально возможными числами, все еще сохраняя обратимость процесса. Есть множество способов сделать это. Один из них — преобразование с использованием линейной алгебры:

PX = (2 * X₋₁) − X₋₂
PY = (2 * Y₋₁) − Y₋₂

Если X = (2, 8, 24, ?), то в ряду PX на четвертом месте будет P4 = (2 * X_4-1) − X_4-2 = (2 * 24) − 8 = 40
То есть, если X = (2,8,24,27,25,28,21,17), то PX = (2,8,14,40,30,…)

Заметим, что X и Y таковы, что на всем протяжении спектра в данную секунду в среднем не должно происходить огромных изменений в значениях между соседними частотами, что облегчает кодирование.

При этом стоит помнить, что хорошие алгоритмы организуют обработку входящих данных таким образом, чтобы уменьшить числа в массиве PX, PY.

Пусть число m лежит в диапазоне 0 … 1024. Для массива PX выполняется серия преобразований с разными значениями m следующим образом:

X = (2, 8, 24, ?), тогда соответственно
PX = (2 * X₋₁) − X₋₂ = (2 * 24) − 8 = 40

Если ? = 45 и m = 512, тогда конечное значение = $?-(PX*m/1024)=45-(40*m/1024)=45-(40*512/1024)=45-20=25$

Далее происходит перебор других значений m, поскольку большие значения могут быть более эффективны.

Тогда, получив для определенного m массив данных, происходит увеличение или уменьшение m в зависимости от того, была ли последняя попытка в алгоритме удачной.

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

Приведем пример нескольких уравнений, как это следует из технической литературы

P0 = 0
P1 = X₋₁
P2 = (2 * X₋₁) − X₋₂
P3 = (3 * X₋₁) − (3 * X₋₂) + X₋₃

Кодирование. Алгоритм Райса

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

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

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

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

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

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

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

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

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

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

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

n = 46 (десятичное) = 101110 (двоичное)
k = 4 (выбирается)

Тогда $r=mod(46,16)=14$ (1110 в двоичной системе). $q=2$ .
$46=2*2^{4}+14$

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

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

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

(количество нулей) * 2⁴ + (k бит следующих за маркировочным битом) = 2*2⁴+14 = 46

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

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

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

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

См. также