Модифицированное дискретное косинусное преобразование

Математическое преобразование, используемое при обработке сигналов

Модифицированное дискретное косинусное преобразование ( MDCT ) представляет собой преобразование, основанное на дискретном косинусном преобразовании типа IV (DCT-IV), с дополнительным свойством наложения : оно предназначено для выполнения на последовательных блоках большего набора данных , где последующие блоки перекрываются таким образом, что последняя половина одного блока совпадает с первой половиной следующего блока. Это перекрытие, в дополнение к энергетическим качествам DCT, делает MDCT особенно привлекательным для приложений сжатия сигнала, поскольку оно помогает избежать артефактов, возникающих из-за границ блоков. В результате этих преимуществ MDCT является наиболее широко используемым методом сжатия с потерями в сжатии аудиоданных . Он используется в большинстве современных стандартов кодирования звука , включая MP3 , Dolby Digital (AC-3), Vorbis (Ogg), Windows Media Audio (WMA), ATRAC , Cook , Advanced Audio Coding (AAC), ^[1] High-Definition Coding (HDC), ^[2] LDAC , Dolby AC-4 , ^[3] и MPEG-H 3D Audio , ^[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 несколько необычно по сравнению с другими преобразованиями, связанными с Фурье, поскольку имеет вдвое меньше выходов, чем входов (вместо того же числа). В частности, это линейная функция (где R обозначает множество действительных чисел ). 2 N действительных чисел x ₀ , ..., x _{2 N -1} преобразуются в N действительных чисел X ₀ , ..., X _{N -1} по формуле: ${\displaystyle F\colon \mathbf {R} ^{2N}\to \mathbf {R} ^{N}}$

${\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 действительных чисел X ₀ , ..., X _{N -1} в 2 N действительных чисел y ₀ , ..., y _{2 N -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 log N ) путем рекурсивной факторизации вычисления, как в быстром преобразовании Фурье (FFT). Можно также вычислить MDCT с помощью других преобразований, обычно DFT (FFT) или DCT, в сочетании с O( N ) этапами предварительной и последующей обработки. Кроме того, как описано ниже, любой алгоритм для DCT-IV немедленно предоставляет метод для вычисления MDCT и IMDCT четного размера.

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

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

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

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

${\displaystyle w_{n}^{2}+w_{n+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+{\frac {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 соответствует чередующимся четным/нечетным граничным условиям: четным на левой границе (около n  = −1/2), нечетным на правой границе (около n  =  N  − 1/2) и т. д. (вместо периодических границ, как для DFT ). Это следует из тождеств и . Таким образом, если его входы представляют собой массив x длины N , мы можем представить расширение этого массива до ( x , − x _R , − x , x _R , ...) и т. д., где x _R обозначает x в обратном порядке. ${\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+{\frac {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]}$

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

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

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

Аналогично, формула IMDCT выше — это ровно 1/2 DCT-IV (которая является своей собственной инверсией), где выход расширен (через граничные условия) до длины 2 N и сдвинут влево на N /2. Обратный DCT-IV просто вернул бы входы (− c _R − d , a − b _R ) сверху. Когда это расширено через граничные условия и сдвинуто, получается:

IMDCT (MDCT ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

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

_{IMDCT (} MDCT ( A , B )) = ( A − AR , B + BR ) / ₂

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

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

Происхождение термина «отмена наложения во временной области» теперь ясно. Использование входных данных, которые выходят за границы логического DCT-IV, приводит к наложению данных таким же образом, как частоты за пределами частоты Найквиста накладываются на более низкие частоты, за исключением того, что это наложение происходит во временной области, а не в частотной: мы не можем различить вклады a и b _R в MDCT ( a , b , c , d ), или, что эквивалентно, в результат

IMDCT (MDCT ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

Комбинации c − d _R и так далее имеют именно те знаки, которые нужны для того, чтобы комбинации сокращались при сложении.

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

Гладкость и разрывы

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

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

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

Рассмотрим перекрывающиеся последовательные наборы из 2 N входов ( A , B ) и ( B , C ) для блоков A , B , C размером N . Напомним, что когда и подвергаются MDCT, IMDCT и складываются в их перекрывающейся половине, мы получаем , исходные данные. ${\displaystyle (A,B)}$ ${\displaystyle (B,C)}$ ${\displaystyle (B+B_{R})/2+(B-B_{R})/2=B}$

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

Поэтому вместо MDCTing мы теперь MDCT (все умножения выполняются поэлементно). Когда это IMDCTed и умножается снова (поэлементно) на оконную функцию, последняя N половина становится: ${\displaystyle (A,B)}$ ${\displaystyle (WA,W_{R}B)}$

${\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)}$

${\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,}$

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

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

• Дискретное косинусное преобразование
• Другие перекрывающиеся оконные преобразования Фурье включают в себя:
  • Модулированное комплексное перекрывающееся преобразование
  • Кратковременное преобразование Фурье
  • Метод Уэлча
• Формат аудиокодирования
• Сжатие аудио (данных)

Ссылки

1. Луо, Фа-Лонг (2008). Стандарты мобильного мультимедийного вещания: технология и практика. Springer Science & Business Media . стр. 590. ISBN 9780387782638.
2. Джонс, Грэм А.; Лайер, Дэвид Х.; Озенковски, Томас Г. (2013). Справочник инженеров Национальной ассоциации вещателей: Справочник инженеров NAB. Тейлор и Фрэнсис . С. 558–9. ISBN 978-1-136-03410-7.
3. "Dolby AC-4: Доставка звука для развлекательных сервисов следующего поколения" (PDF) . Dolby Laboratories . Июнь 2015 . Получено 11 ноября 2019 .
4. Bleidt, RL; Sen, D.; Niedermeier, A.; Czelhan, B.; Füg, S.; et al. (2017). «Разработка аудиосистемы MPEG-H TV для ATSC 3.0» (PDF) . IEEE Transactions on Broadcasting . 63 (1): 202–236. doi :10.1109/TBC.2017.2661258. S2CID  30821673.
5. Шнелл, Маркус; Шмидт, Маркус; Яндер, Мануэль; Альберт, Тобиас; Гейгер, Ральф; Руоппила, Веса; Экстранд, Пер; Бернхард, Гриль (октябрь 2008 г.). MPEG-4 Enhanced Low Delay AAC — новый стандарт высококачественной связи (PDF) . 125-я конвенция AES. Fraunhofer IIS . Audio Engineering Society . Получено 20 октября 2019 г.
6. Луцки, Манфред; Шуллер, Джеральд; Гайер, Марк; Кремер, Ульрих; Вабник, Стефан (май 2004 г.). Руководство по задержке аудиокодека (PDF) . 116-я конференция AES. Fraunhofer IIS . Audio Engineering Society . Получено 24 октября 2019 г.
7. Нагиредди, Сиваннараяна (2008). Обработка голосовых и факсимильных сигналов VoIP. John Wiley & Sons . стр. 69. ISBN 9780470377864.
8. Презентация кодека CELT, архив 2011-08-07 на Wayback Machine , Тимоти Б. Терриберри (65 минут видео, см. также слайды презентации, архив 2023-11-16 на Wayback Machine в формате PDF)
9. "Opus Codec". Opus (Домашняя страница). Фонд Xiph.org . Получено 31 июля 2012 г.
10. Брайт, Питер (2012-09-12). "Новый стандартизированный аудиокодек Opus выполняет все функции от онлайн-чата до музыки". Ars Technica . Получено 28-05-2014 .
11. Ахмед, Насир (январь 1991 г.). «Как я придумал дискретное косинусное преобразование» (PDF) . Цифровая обработка сигналов . 1 (1): 4–5. doi :10.1016/1051-2004(91)90086-Z.
12. Ахмед, Насир ; Натараджан, Т.; Рао, КР (январь 1974 г.), «Дискретное косинусное преобразование», IEEE Transactions on Computers , C-23 (1): 90–93, doi :10.1109/TC.1974.223784, S2CID  149806273
13. Princen, John P.; Johnson, AW; Bradley, Alan B. (1987). «Кодирование подполос/преобразований с использованием конструкций банка фильтров на основе отмены наложения спектров во временной области». ICASSP '87. Международная конференция IEEE по акустике, речи и обработке сигналов . Том 12. С. 2161–2164. doi :10.1109/ICASSP.1987.1169405. S2CID  58446992.
14. Джон П. Принсен, Алан Б. Брэдли: Проектирование банка фильтров анализа/синтеза на основе устранения наложения спектров во временной области , IEEE Trans. Acoust. Speech Signal Processing, ASSP-34 (5), 1153–1161, 1986. Описал предшественника MDCT, использующего комбинацию дискретных косинусных и синусных преобразований.
15. HS Malvar, «Перекрывающиеся преобразования для эффективного преобразования/подполосного кодирования», IEEE Trans. on Acoustics, Speech, and Signal Processing , т. 38, № 6, стр. 969–978 (Уравнение 22), июнь 1990 г.
16. HS Malvar, «Модулированные банки фильтров QMF с идеальной реконструкцией», Electronics Letters , т. 26, № 13, стр. 906–907 (Уравнение 13), июнь 1990 г.

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

• Энрике С. Малвар, Обработка сигналов с помощью перекрывающихся преобразований (Artech House: Norwood MA, 1992).
• AW Johnson и AB Bradley, «Адаптивное преобразование кодирования, включающее отмену наложения спектров во временной области», Speech Comm. 6 , 299-308 (1987).
• Для алгоритмов см. примеры:
  • Чи-Мин Лю и Вэнь-Чи Ли, «Унифицированный быстрый алгоритм для косинусно-модулированных банков фильтров в современных аудиостандартах ^{[ постоянная неработающая ссылка ]} », J. Audio Engineering 47 (12), 1061-1075 (1999).
  • В. Британак и К.Р. Рао, «Новый быстрый алгоритм для унифицированного прямого и обратного вычисления MDCT/MDST», Обработка сигналов 82 , 433-459 (2002)
  • Владимир Николаевич и Герхард Феттвайс, «Вычисление прямого и обратного MDCT с использованием рекуррентной формулы Кленшоу», IEEE Trans. Sig. Proc. 51 (5), 1439-1444 (2003)
  • Che-Hong Chen, Bin-Da Liu и Jar-Ferr Yang, "Рекурсивные архитектуры для реализации модифицированного дискретного косинусного преобразования и его обратного преобразования", IEEE Trans. Circuits Syst. II: Analog Dig. Sig. Proc. 50 (1), 38-45 (2003)
  • JS Wu, HZ Shu, L. Senhadji и LM Luo, "Алгоритм смешанной системы исчисления для вычисления прямых и обратных MDCT", IEEE Trans. Circuits Syst. I: Reg. Papers 56 (4), 784-794 (2009)
  • В. Британак, «Обзор эффективных реализаций MDCT в стандарте кодирования звука MP3: ретроспектива и современное состояние», Сигнал. Процесс. 91 (4), 624-672 (2011)