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

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

Звук является простой волной, а оцифрованный звук — цифровое представление этой волны. Это достигается запоминанием уровня аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за секунду. Так как CD работает со стерео, мы запоминаем сигнал для левой и правой колонки параллельно. Для каждого замера используются 16-битовые числа. Поэтому нетрудно посчитать, что одна секунда звучания занимает 2 \cdot 2\cdot 44\,100 = 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−1) − X−2
PY = (2 * Y−1) − Y−2

Если X = (2, 8, 24, ?), то в ряду PX на четвертом месте будет P4 = (2 * X4-1) − X4-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−1) − X−2 = (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−1
P2 = (2 * X−1) − X−2
P3 = (3 * X−1) − (3 * X−2) + X−3

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

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

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

Базис по основанию 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, которым кодировалось число, можно с легкостью его расшифровать:

(количество нулей) * 24 + (k бит следующих за маркировочным битом) = 2*24+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.

См. также



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Сжатие звука без потерь" в других словарях:

  • Сжатие без потерь — У этого термина существуют и другие значения, см. Сжатие. Сжатие данных без потерь (англ. Lossless data compression)  метод сжатия данных: видео, аудио, графики, документов представленных в цифровом виде, при использовании которого… …   Википедия

  • AMR (сжатие звука) — У этого термина существуют и другие значения, см. AMR. AMR (Adaptive multi rate)  адаптивное кодирование с переменной скоростью. Стандарт кодирования звуковых файлов, специально предназначенный для сжатия сигнала в речевом диапазоне частот.… …   Википедия

  • Сжатие аудиоданных — В Википедии …   Википедия

  • Сжатие информации — Сжатие информации, компрессия, Шаблон:Англ. data compression  алгоритмическое преобразование данных (кодирование), при котором за счет уменьшения их избыточности уменьшается их обьём. Содержание 1 Принципы сжатия информации …   Википедия

  • Сжатие данных с потерями — У этого термина существуют и другие значения, см. Сжатие. Сжатие данных с потерями  метод сжатия (компрессии) данных, при использовании которого распакованные данные отличаются от исходных, но степень отличия не является существенной с точки …   Википедия

  • Сжатие видео — (англ. Video compression)  уменьшение количества данных, используемых для представления видеопотока. Сжатие видео позволяет эффективно уменьшать поток, необходимый для передачи видео по каналам радиовещания, уменьшать пространство,… …   Википедия

  • Сжатие данных — Возможно, эта статья содержит оригинальное исследование. Добавьте ссылки на источники, в противном случае она может быть выставлена на удаление. Дополнительные сведения могут быть на странице обсуждения. (26 мая 2012) …   Википедия

  • Цифровые аудиоформаты — Цифровой аудиоформат  формат представления звуковых данных, используемый при цифровой звукозаписи, а также для дальнейшего хранения записанного материала на компьютере и других электронных носителях информации, так называемых звуковых… …   Википедия

  • DTS — У этого термина существуют и другие значения, см. DTS (значения). Digital Theater System Тип Public (NASDAQ: DTSI) Год основания Июнь 1993 года …   Википедия

  • Dolby Digital — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»