Модифицированное дискретное косинусное преобразование - Modified discrete cosine transform

В модифицированное дискретное косинусное преобразование (MDCT) это преобразование с перекрытием на базе IV типа дискретное косинусное преобразование (DCT-IV), с дополнительным свойством быть притертый: он предназначен для выполнения на последовательных блоках большего набор данных, где последующие блоки перекрываются, так что последняя половина одного блока совпадает с первой половиной следующего блока. Это перекрытие, в дополнение к качеству сжатия энергии DCT, делает MDCT особенно привлекательным для приложений сжатия сигналов, поскольку помогает избежать артефакты вытекающие из границ блока. В результате этих преимуществ MDCT является наиболее широко используемым сжатие с потерями техника в сжатие аудиоданных. Он используется в большинстве современных стандарты кодирования звука, включая MP3, Dolby Digital (АС-3), Vorbis (Огг), Windows Media Audio (WMA), ATRAC, повар, Расширенное кодирование звука (AAC),^[1] Кодирование высокой четкости (HDC),^[2] LDAC, Dolby AC-4,^[3] и MPEG-H 3D аудио,^[4] а также кодирование речи стандарты, такие как AAC-LD (LD-MDCT),^[5] G.722.1,^[6] G.729.1,^[7] CELT,^[8] и Opus.^[9]^[10]

В дискретное косинусное преобразование (DCT) был впервые предложен Насир Ахмед в 1972 г.,^[11] и продемонстрировано Ахмедом с Т. Натараджаном и К. Р. Рао в 1974 г.^[12] Позднее MDCT был предложен Джоном П. Принсеном, А.В. Джонсон и Алан Б. Брэдли в Университет Суррея в 1987 г.^[13] после более ранней работы Принсена и Брэдли (1986)^[14] разработать основной принцип MDCT отмена алиасинга во временной области (TDAC), описанный ниже. (Существует также аналогичное преобразование MDST, основанное на дискретное синусоидальное преобразование, а также другие, редко используемые формы MDCT, основанные на различных типах DCT или комбинаций DCT / DST.)

В MP3 MDCT применяется не к аудиосигналу напрямую, а к выходу 32-полосного многофазный квадратурный фильтр (PQF) банк. Выходные данные этого MDCT подвергаются постобработке по формуле уменьшения псевдонимов для уменьшения типичного наложения спектров банка фильтров PQF. Такая комбинация банка фильтров с MDCT называется гибридный банк фильтров или поддиапазон MDCT. С другой стороны, AAC обычно использует чистый MDCT; только (редко используется) MPEG-4 AAC-SSR вариант (по Sony ) использует четырехполосный банк PQF, за которым следует MDCT. Подобно MP3, ATRAC использует сложенные квадратурные зеркальные фильтры (QMF) с последующим MDCT.

Определение

Как преобразование с перекрытием, MDCT немного необычен по сравнению с другими преобразованиями, связанными с Фурье, поскольку он имеет вдвое меньше выходов, чем входов (вместо того же числа). В частности, это линейная функция ${ Displaystyle F двоеточие mathbf {R} ^ {2N} to mathbf {R} ^ {N}}$ (куда р обозначает набор действительные числа ). 2N действительные числа Икс₀, ..., Икс_2N-1 превращаются в N действительные числа Икс₀, ..., Икс_N-1 в соответствии с формулой:

{ displaystyle X_ {k} = sum _ {n = 0} ^ {2N-1} x_ {n} cos left [{ frac { pi} {N}} left (n + { frac { 1} {2}} + { frac {N} {2}} right) left (k + { frac {1} {2}} right) right]}

(Коэффициент нормализации перед этим преобразованием, здесь единица, является произвольным соглашением и различается в зависимости от лечения. Ограничивается только произведение нормализации MDCT и IMDCT, приведенное ниже.)

Обратное преобразование

Обратный MDCT известен как IMDCT. Поскольку количество входов и выходов разное, на первый взгляд может показаться, что MDCT не должен быть обратимым. Однако идеальная обратимость достигается за счет добавление перекрывающиеся IMDCT последующих перекрывающихся блоков, в результате чего ошибки Отмена и исходные данные, которые необходимо восстановить; этот метод известен как отмена алиасинга во временной области (TDAC).

IMDCT трансформирует N действительные числа Икс₀, ..., Икс_N-1 в 2N действительные числа у₀, ..., у_2N-1 в соответствии с формулой:

{ displaystyle y_ {n} = { frac {1} {N}} sum _ {k = 0} ^ {N-1} X_ {k} cos left [{ frac { pi} {N }} left (n + { frac {1} {2}} + { frac {N} {2}} right) left (k + { frac {1} {2}} right) right] }

(Как для DCT-IV, ортогональное преобразование, обратное преобразование имеет ту же форму, что и прямое преобразование.)

В случае оконного MDCT с обычной оконной нормализацией (см. Ниже), коэффициент нормализации перед IMDCT следует умножить на 2 (т. Е. Стать 2 /N).

Вычисление

Хотя прямое применение формулы MDCT потребует O (N²) операций, то же самое можно вычислить, используя только O (N бревно N) сложность путем рекурсивной факторизации вычисления, как в быстрое преобразование Фурье (БПФ). Также можно вычислить MDCT с помощью других преобразований, обычно DFT (FFT) или DCT, в сочетании с O (N) этапы предварительной и последующей обработки. Кроме того, как описано ниже, любой алгоритм для DCT-IV немедленно предоставляет способ вычисления MDCT и IMDCT четного размера.

Оконные функции

Функции окна MDCT:
синий: косинус, красный: синус-косинус, зеленый: модифицированный Кайзера-Бесселя

В типичных приложениях сжатия сигнала свойства преобразования дополнительно улучшаются за счет использования оконная функция ш_п (п = 0, ..., 2N−1), который умножается на Икс_п и у_п в формулах MDCT и IMDCT выше, чтобы избежать разрывов в п = 0 и 2N границ, заставляя функцию плавно переходить к нулю в этих точках. (То есть мы окна данных перед MDCT и после IMDCT.) В принципе, Икс и у могут иметь разные оконные функции, и оконная функция также может изменяться от одного блока к другому (особенно для случая, когда блоки данных разных размеров объединяются), но для простоты мы рассматриваем общий случай идентичных оконных функций для равных размеров блоки.

Преобразование остается обратимым (то есть TDAC работает) для симметричного окна ш_п = ш_2N−1−п, так долго как ш удовлетворяет условию Принсена-Брэдли:

{ Displaystyle ш_ {п} ^ {2} + ш_ {п + N} ^ {2} = 1}

.

Используются различные оконные функции. Окно, которое создает форму, известную как модулированное преобразование с перекрытием (MLT).^[15]^[16] дан кем-то

{ displaystyle w_ {n} = sin left [{ frac { pi} {2N}} left (n + { frac {1} {2}} right) right]}

и используется для MP3 и MPEG-2 AAC, и

{ displaystyle w_ {n} = sin left ({ frac { pi} {2}} sin ^ {2} left [{ frac { pi} {2N}} left (n + { гидроразрыв {1} {2}} right) right] right)}

для Vorbis. AC-3 использует Производное окно Кайзера-Бесселя (KBD), и MPEG-4 AAC также может использовать окно KBD.

Обратите внимание, что окна, применяемые к MDCT, отличаются от окон, используемых для некоторых других типов анализа сигналов, поскольку они должны удовлетворять условию Принсена-Брэдли. Одна из причин этого различия заключается в том, что окна MDCT применяются дважды, как для MDCT (анализ), так и для IMDCT (синтез).

Связь с DCT-IV и происхождением TDAC

Как видно из определений, для четное N MDCT по существу эквивалентен DCT-IV, где вход сдвигается на N/ 2 и два N-блоки данных преобразуются сразу. Более тщательно изучив эту эквивалентность, можно легко получить важные свойства, такие как TDAC.

Чтобы определить точное отношение к DCT-IV, нужно понимать, что DCT-IV соответствует чередующимся четным / нечетным граничным условиям: четность на своей левой границе (около п= −1 / 2), нечетное на его правой границе (около п=N−1/2) и т.д. (вместо периодических границ, как для DFT ). Это следует из тождеств ${ displaystyle cos left [{ frac { pi} {N}} left (-n-1 + { frac {1} {2}} right) left (k + { frac {1}) {2}} right) right] = cos left [{ frac { pi} {N}} left (n + { frac {1} {2}} right) left (k + { гидроразрыв {1} {2}} right) right]}$ и ${ displaystyle cos left [{ frac { pi} {N}} left (2N-n-1 + { frac {1} {2}} right) left (k + { frac {1 } {2}} right) right] = - cos left [{ frac { pi} {N}} left (n + { frac {1} {2}} right) left (k + { frac {1} {2}} right) right]}$ . Таким образом, если его входы представляют собой массив Икс длины N, мы можем представить расширение этого массива до (Икс, −Икс_р, −Икс, Икс_р, ...) и так далее, где Икс_р обозначает Икс в обратном порядке.

Рассмотрим MDCT с 2N входы и N выходы, где мы делим входы на четыре блока (а, б, c, d) каждый размер N/ 2. Если мы сдвинем их вправо на N/ 2 (из +N/ 2 в определении MDCT), то (б, c, d) выходят за конец N Входы DCT-IV, поэтому мы должны «свернуть» их обратно в соответствии с граничными условиями, описанными выше.

Таким образом, MDCT 2N входы (а, б, c, d) является точно эквивалент DCT-IV N входы: (-c_р−d, а−б_р), куда р обозначает разворот, как указано выше.

(Таким образом, любой алгоритм вычисления DCT-IV может быть тривиально применен к MDCT.)

Точно так же формула IMDCT, приведенная выше, составляет ровно 1/2 от DCT-IV (которая является собственной инверсией), где выходной сигнал расширяется (с помощью граничных условий) до длины 2N и сдвинулся назад влево на N/ 2. Обратный DCT-IV просто вернет входные данные (-c_р−d, а−б_р) сверху. Когда это расширяется с помощью граничных условий и сдвигается, получается:

IMDCT (MDCT (а, б, c, d)) = (а−б_р, б−а_р, c+d_р, d+c_р) / 2.

Таким образом, половина выходов IMDCT является избыточной, поскольку б−а_р = −(а−б_р)_р, и то же самое для последних двух сроков. Если мы сгруппируем ввод в более крупные блоки А,B размера N, куда А=(а, б) и B=(c, d), мы можем записать этот результат более простым способом:

IMDCT (MDCT (А, B)) = (А−А_р, B+B_р) / 2

Теперь можно понять, как работает TDAC. Предположим, что вычисляется MDCT следующих, перекрывающихся на 50%, 2N блокировать (B, C). IMDCT тогда выдаст, аналогично приведенному выше: (B−B_р, C+C_р) / 2. Когда это добавляется к предыдущему результату IMDCT в перекрывающейся половине, обратные члены отменяются, и получается просто B, восстанавливая исходные данные.

Происхождение TDAC

Происхождение термина «отмена псевдонимов во временной области» теперь ясно. Использование входных данных, выходящих за пределы логического DCT-IV, приводит к тому, что данные псевдоним точно так же, как частоты за пределами Частота Найквиста находятся псевдоним на более низкие частоты, за исключением того, что это наложение спектров происходит во временной области, а не в частотной: мы не можем различить вкладыа и из б_р к MDCT (а, б, c, d) или, что то же самое, результат IMDCT (MDCT (а, б, c, d)) = (а−б_р, б−а_р, c+d_р, d+c_р) / 2. Комбинации c−d_р и так далее, имеют правильные знаки для отмены комбинаций при их добавлении.

За странный N (которые на практике используются редко), N/ 2 не является целым числом, поэтому MDCT - это не просто перестановка сдвига DCT-IV. В этом случае дополнительный сдвиг на половину выборки означает, что MDCT / IMDCT становится эквивалентным DCT-III / II, и анализ аналогичен приведенному выше.

Плавность и неоднородность

Выше мы видели, что MDCT 2N входы (а, б,c, d) эквивалентно DCT-IV N входы (-c_р−d,а−б_рDCT-IV разработан для случая, когда функция на правой границе является нечетной, и, следовательно, значения около правой границы близки к 0. Если входной сигнал гладкий, это так: крайние правые компоненты а и б_р являются последовательными во входной последовательности (а, б, c, d), поэтому разница между ними невелика. Давайте посмотрим на середину интервала: если мы перепишем приведенное выше выражение как (-c_р−d,а−б_р) = (−d, а)−(б,c)_р, второй член, (б,c)_р, дает плавный переход в середине, но в первом члене (-d, а), существует разрыв потенциала, где правый конец -d встречает левый конец аЭто причина использования оконной функции, которая уменьшает компоненты вблизи границ входной последовательности (а, б,c, d) к 0.

TDAC для оконного MDCT

Выше свойство TDAC было доказано для обычного MDCT, показывая, что добавление IMDCT последующих блоков в их перекрывающуюся половину восстанавливает исходные данные. Вывод этого обратного свойства для оконного MDCT лишь немного сложнее.

Рассмотрите возможность перекрытия последовательных наборов из 2N входы (А,B) и (B,C), для блоков А,B,C размера NНапомним, что когда ${ Displaystyle (А, В)}$ и ${ displaystyle (B, C)}$ MDCTed, IMDCTed и добавлены в их перекрывающуюся половину, мы получаем ${ Displaystyle (В + В_ {R}) / 2+ (В-В_ {R}) / 2 = В}$ , исходные данные.

Теперь предположим, что мы умножаем обе входы MDCT и IMDCT выводит оконную функцию длиной 2N. Как и выше, мы предполагаем симметричную оконную функцию, которая, следовательно, имеет вид ${ displaystyle (W, W_ {R})}$ куда W это длина-N вектор и р обозначает разворот, как и раньше. Тогда условие Принсена-Брэдли можно записать как ${ Displaystyle W ^ {2} + W_ {R} ^ {2} = (1,1, ldots)}$ , при этом квадраты и сложения выполняются поэлементно.

Поэтому вместо МДКТ ${ Displaystyle (А, В)}$ , мы сейчас MDCT ${ displaystyle (WA, W_ {R} B)}$ (при этом все умножения выполняются поэлементно). Когда это IMDCTed и снова умножается (поэлементно) на оконную функцию, последний-N половина становится:

{ Displaystyle W_ {R} cdot (W_ {R} B + (W_ {R} B) _ {R}) = W_ {R} cdot (W_ {R} B + WB_ {R}) = W_ {R } ^ {2} B + WW_ {R} B_ {R}}

.

(Обратите внимание, что у нас больше нет умножения на 1/2, потому что нормализация IMDCT отличается в 2 раза в оконном случае.)

Аналогичным образом оконные MDCT и IMDCT ${ displaystyle (B, C)}$ дает, в первую очередьN половина:

{ Displaystyle W cdot (WB-W_ {R} B_ {R}) = W ^ {2} B-WW_ {R} B_ {R}}

.

Когда мы складываем эти две половинки вместе, получаем:

{ displaystyle (W_ {R} ^ {2} B + WW_ {R} B_ {R}) + (W ^ {2} B-WW_ {R} B_ {R}) = left (W_ {R} ^ {2} + W ^ {2} right) B = B,}

восстановление исходных данных.

Смотрите также

Дискретное косинусное преобразование
Другие перекрывающиеся оконные преобразования Фурье включают:
Формат кодирования аудио
Аудио сжатие (данные)

Библиография

Энрике С. Малвар, Обработка сигналов с перекрывающимися преобразованиями (Дом Artech: Норвуд, Массачусетс, 1992).
А. В. Джонсон и А. Б. Брэдли, «Адаптивное преобразование кодирования, включающее отмену наложения спектров во временной области», Speech Comm. 6, 299-308 (1987).
Для алгоритмов см. Примеры:
- Чи-Мин Лю и Вэнь-Чи Ли "Унифицированный быстрый алгоритм для наборов фильтров с косинусной модуляцией в современных стандартах звука.^{[постоянная мертвая ссылка ]}", J. Аудиотехника 47 (12), 1061-1075 (1999).
- В. Британак и К. Р. Рао, «Новый быстрый алгоритм для унифицированного прямого и обратного вычисления MDCT / MDST», Обработка сигналов 82, 433-459 (2002)
- Владимир Николаевич и Герхард Феттвайс, «Вычисление прямого и обратного MDCT с использованием формулы рекурсии Кленшоу», IEEE Trans. Sig. Proc. 51 (5), 1439-1444 (2003)
- Че-Хонг Чен, Бин-Да Лю и Джар-Ферр Ян, «Рекурсивные архитектуры для реализации модифицированного дискретного косинусного преобразования и его обратного», IEEE Trans. Circuits Syst. II: Аналоговый Dig. Sig. Proc. 50 (1), 38-45 (2003)
- J.S. Ву, Х.З. Шу, Л. Сенхаджи и Л.М. Луо, «Алгоритм со смешанным основанием для вычисления прямого и обратного MDCT», IEEE Trans. Circuits Syst. I: Рег. Статьи 56 (4), 784-794 (2009)
- В. Британак, «Обзор эффективных реализаций MDCT в стандарте кодирования аудио MP3: ретроспективный и современный», Сигнал. Процесс. 91 (4), 624-672(2011)

[Luo-1] Ло, Фа-Лонг (2008). Стандарты мобильного мультимедийного вещания: технологии и практика. Springer Science & Business Media. п. 590. ISBN 9780387782638.

[2] Джонс, Грэм А .; Layer, Дэвид Х .; Осенковский, Томас Г. (2013). Техническое руководство Национальной ассоциации вещателей: Техническое руководство NAB. Тейлор и Фрэнсис. С. 558–9. ISBN 978-1-136-03410-7.

[3] «Dolby AC-4: передача звука для развлекательных услуг нового поколения» (PDF). Dolby Laboratories. Июнь 2015 г.. Получено 11 ноября 2019.

[4] Bleidt, R. L .; Отправить.; Niedermeier, A .; Czelhan, B .; Füg, S .; и другие. (2017). «Разработка аудиосистемы телевидения MPEG-H для ATSC 3.0» (PDF). IEEE Transactions on Broadcasting. 63 (1): 202–236. Дои:10.1109 / TBC.2017.2661258.

[5] Шнелл, Маркус; Шмидт, Маркус; Джандер, Мануэль; Альберт, Тобиас; Гейгер, Ральф; Руоппила, Веса; Экстранд, Пер; Бернхард, Гриль (октябрь 2008 г.). MPEG-4 Enhanced Low Delay AAC - новый стандарт высококачественной связи (PDF). 125-я конвенция AES. Фраунгофера IIS. Аудио инженерное общество. Получено 20 октября 2019.

[6] Луцки, Манфред; Шуллер, Джеральд; Гейер, Марк; Кремер, Ульрих; Вабник, Стефан (май 2004 г.). Руководство по задержке аудиокодека (PDF). 116-я Конвенция AES. Фраунгофера IIS. Аудио инженерное общество. Получено 24 октября 2019.

[Nagireddi-7] Нагиредди, Шиваннараяна (2008). Обработка голосовых и факсимильных сигналов VoIP. Джон Уайли и сыновья. п. 69. ISBN 9780470377864.

[presentation-8] Презентация кодека CELT Тимоти Б. Террибери (65 минут видео, см. также слайды презентации в PDF)

[homepage-9] «Кодек Opus». Opus (Домашняя страница). Фонд Xiph.org. Получено 31 июля, 2012.

[ars-role-10] Брайт, Питер (2012-09-12). «Новый стандартизированный аудиокодек Opus выполняет все функции, от онлайн-чата до музыки». Ars Technica. Получено 2014-05-28.

[Ahmed-11] Ахмед, Насир (Январь 1991 г.). "Как я пришел к дискретному косинусному преобразованию". Цифровая обработка сигналов. 1 (1): 4–5. Дои:10.1016 / 1051-2004 (91) 90086-Z.

[pubDCT-12] Ахмед, Насир; Натараджан, Т .; Рао, К. Р. (январь 1974 г.), "Дискретное косинусное преобразование", Транзакции IEEE на компьютерах, С-23 (1): 90–93, Дои:10.1109 / T-C.1974.223784

[13] Princen, Джон П .; Johnson, A.W .; Брэдли, Алан Б. (1987). «Кодирование поддиапазона / преобразования с использованием схем набора фильтров, основанных на отмене наложения спектров во временной области». ICASSP '87. Международная конференция IEEE по акустике, речи и обработке сигналов. 12: 2161–2164. Дои:10.1109 / ICASSP.1987.1169405.

[14] Джон П. Принсен, Алан Б. Брэдли: Дизайн банка фильтров анализа / синтеза на основе отмены наложения спектров во временной области, IEEE Trans. Акуст. Обработка речевого сигнала, АССП-34 (5), 1153–1161, 1986. Описан предшественник MDCT с использованием комбинации дискретных косинусных и синусоидальных преобразований.

[15] Х. С. Малвар, "Преобразования с перекрытием для эффективного преобразования / кодирования поддиапазонов", IEEE Trans. по акустике, речи и обработке сигналов, т. 38, нет. 6, pp. 969–978 (уравнение 22), июнь 1990 г.

[16] Х. С. Малвар, "Модулированные банки фильтров QMF с идеальной реконструкцией", Письма об электронике, т. 26, вып. 13, pp. 906–907 (уравнение 13), июнь 1990 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]