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

Модифицированного дискретного косинусного преобразования ( МДКП ) представляет собой преобразование на основе типа IV дискретного косинусного преобразования (ДКП-IV), с дополнительным свойством внахлест : она предназначена для быть выполнены на последовательных блоках большего набора данных , где последующее блоки перекрываются так, чтобы последняя половина одного блока совпадала с первой половиной следующего блока. Это перекрытие, в дополнение к качеству сжатия энергии DCT, делает MDCT особенно привлекательным для приложений сжатия сигналов, поскольку помогает избежать артефактов, возникающих из-за границ блоков. В результате этих преимуществ MDCT является наиболее широко используемым методом сжатия с потерями.техника сжатия аудиоданных . Он используется в большинстве современных стандартов кодирования звука , включая MP3 , Dolby Digital (AC-3), Vorbis (Ogg), Windows Media Audio (WMA), ATRAC , Cook , Advanced Audio Coding (AAC), ^[1] High-Definition Кодирование (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]

Дискретного косинусного преобразования (ДКП) впервые был предложен Насира Ахмеда в 1972 году, ^[11] , и продемонстрирована Ahmed с Т. Natarajan и КР Рао в 1974 г. ^[12] МДКП позже был предложен Джоном П. Princen, Джонсон и AW Алан Б. Брэдли из Университета Суррея в 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 ₂_N_-1 преобразуются в N действительных чисел X ₀ , ..., X _N_-1 по формуле: $F\colon \mathbf {R} ^{2N}\to \mathbf {R} ^{N}$

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} по формуле:

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

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

w_{n}^{2}+w_{n+N}^{2}=1

.

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

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

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

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) и так далее (вместо периодических границ, как для ДПФ ). Это следует из тождеств и . Таким образом, если его входные данные представляют собой массив x длины N , мы можем представить расширение этого массива до ( x , - x _R , - x , x _R , ...) и так далее, где x _R обозначает x $\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]$ $\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 - A _R , B + B _R ) / 2

Теперь можно понять, как работает 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. The combinations c−d_R and so on, have precisely the right signs for the combinations to cancel when they are added.

For odd N (which are rarely used in practice), N/2 is not an integer so the MDCT is not simply a shift permutation of a DCT-IV. In this case, the additional shift by half a sample means that the MDCT/IMDCT becomes equivalent to the DCT-III/II, and the analysis is analogous to the above.

Smoothness and discontinuities[edit]

We have seen above that the MDCT of 2N inputs (a, b,c, d) is equivalent to a DCT-IV of the N inputs (−c_R−d,a−b_R). The DCT-IV is designed for the case where the function at the right boundary is odd, and therefore the values near the right boundary are close to 0. If the input signal is smooth, this is the case: the rightmost components of a and b_R are consecutive in the input sequence (a, b, c, d), and therefore their difference is small. Let us look at the middle of the interval: if we rewrite the above expression as (−c_R−d,a−b_R) = (−d, a)−(b,c)_R, the second term, (b,c)_R, gives a smooth transition in the middle. However, in the first term, (−d, a), there is a potential discontinuity where the right end of −d meets the left end of a. This is the reason for using a window function that reduces the components near the boundaries of the input sequence (a, b,c, d) towards 0.

TDAC for the windowed MDCT[edit]

Above, the TDAC property was proved for the ordinary MDCT, showing that adding IMDCTs of subsequent blocks in their overlapping half recovers the original data. The derivation of this inverse property for the windowed MDCT is only slightly more complicated.

Consider to overlapping consecutive sets of 2N inputs (A,B) and (B,C), for blocks A,B,C of size N. Recall from above that when $(A,B)$ and $(B,C)$ are MDCTed, IMDCTed, and added in their overlapping half, we obtain $(B+B_{R})/2+(B-B_{R})/2=B$ , the original data.

Now we suppose that we multiply both the MDCT inputs and the IMDCT outputs by a window function of length 2N. As above, we assume a symmetric window function, which is therefore of the form $(W,W_{R})$ where W is a length-N vector and R denotes reversal as before. Then the Princen-Bradley condition can be written as $W^{2}+W_{R}^{2}=(1,1,\ldots )$ , with the squares and additions performed elementwise.

Therefore, instead of MDCTing $(A,B)$ , we now MDCT $(WA,W_{R}B)$ (with all multiplications performed elementwise). When this is IMDCTed and multiplied again (elementwise) by the window function, the last-N half becomes:

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}

.

(Note that we no longer have the multiplication by 1/2, because the IMDCT normalization differs by a factor of 2 in the windowed case.)

Similarly, the windowed MDCT and IMDCT of $(B,C)$ yields, in its first-N half:

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

.

When we add these two halves together, we obtain:

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

recovering the original data.

References[edit]

^ Luo, Fa-Long (2008). Mobile Multimedia Broadcasting Standards: Technology and Practice. Springer Science & Business Media. p. 590. ISBN 9780387782638.
^ Jones, Graham A.; Layer, David H.; Osenkowsky, Thomas G. (2013). National Association of Broadcasters Engineering Handbook: NAB Engineering Handbook. Taylor & Francis. pp. 558–9. ISBN 978-1-136-03410-7.
^ "Dolby AC-4: Audio Delivery for Next-Generation Entertainment Services" (PDF). Dolby Laboratories. June 2015. Retrieved 11 November 2019.
^ Bleidt, R. L.; Sen, D.; Niedermeier, A.; Czelhan, B.; Füg, S.; et al. (2017). "Development of the MPEG-H TV Audio System for ATSC 3.0" (PDF). IEEE Transactions on Broadcasting. 63 (1): 202–236. doi:10.1109/TBC.2017.2661258.
^ Schnell, Markus; Schmidt, Markus; Jander, Manuel; Albert, Tobias; Geiger, Ralf; Ruoppila, Vesa; Ekstrand, Per; Bernhard, Grill (October 2008). MPEG-4 Enhanced Low Delay AAC - A New Standard for High Quality Communication (PDF). 125th AES Convention. Fraunhofer IIS. Audio Engineering Society. Retrieved 20 October 2019.
^ Lutzky, Manfred; Schuller, Gerald; Gayer, Marc; Krämer, Ulrich; Wabnik, Stefan (May 2004). A guideline to audio codec delay (PDF). 116th AES Convention. Fraunhofer IIS. Audio Engineering Society. Retrieved 24 October 2019.
^ Nagireddi, Sivannarayana (2008). VoIP Voice and Fax Signal Processing. John Wiley & Sons. p. 69. ISBN 9780470377864.
^ Presentation of the CELT codec by Timothy B. Terriberry (65 minutes of video, see also presentation slides in PDF)
^ "Opus Codec". Opus (Home page). Xiph.org Foundation. Retrieved July 31, 2012.
^ Bright, Peter (2012-09-12). "Newly standardized Opus audio codec fills every role from online chat to music". Ars Technica. Retrieved 2014-05-28.
^ Ahmed, Nasir (January 1991). "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
^ Ahmed, Nasir; Natarajan, T.; Rao, K. R. (January 1974), "Discrete Cosine Transform", IEEE Transactions on Computers, C-23 (1): 90–93, doi:10.1109/T-C.1974.223784
^ Princen, John P.; Johnson, A.W.; Bradley, Alan B. (1987). "Subband/Transform coding using filter bank designs based on time domain aliasing cancellation". ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing. 12: 2161–2164. doi:10.1109/ICASSP.1987.1169405.
^ John P. Princen, Alan B. Bradley: Analysis/synthesis filter bank design based on time domain aliasing cancellation, IEEE Trans. Acoust. Speech Signal Processing, ASSP-34 (5), 1153–1161, 1986. Described a precursor to the MDCT using a combination of discrete cosine and sine transforms.
^ H. S. Malvar, "Lapped Transforms for Efficient Transform/Subband Coding", IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. 38, no. 6, pp. 969–978 (Equation 22), June 1990.
^ H. S. Malvar, "Modulated QMF Filter Banks with Perfect Reconstruction", Electronics Letters, vol. 26, no. 13, pp. 906–907 (Equation 13), June 1990.

Bibliography[edit]

Henrique S. Malvar, Signal Processing with Lapped Transforms (Artech House: Norwood MA, 1992).
A. W. Johnson and A. B. Bradley, "Adaptive transform coding incorporating time domain aliasing cancellation," Speech Comm. 6, 299-308 (1987).
For algorithms, see examples:
- Chi-Min Liu and Wen-Chieh Lee, "A unified fast algorithm for cosine modulated filterbanks in current audio standards^{[permanent dead link]}", J. Audio Engineering 47 (12), 1061-1075 (1999).
- V. Britanak and K. R. Rao, "A new fast algorithm for the unified forward and inverse MDCT/MDST computation," Signal Processing 82, 433-459 (2002)
- Vladimir Nikolajevic and Gerhard Fettweis, "Computation of forward and inverse MDCT using Clenshaw's recurrence formula," IEEE Trans. Sig. Proc. 51 (5), 1439-1444 (2003)
- Che-Hong Chen, Bin-Da Liu, and Jar-Ferr Yang, "Recursive architectures for realizing modified discrete cosine transform and its inverse," IEEE Trans. Circuits Syst. II: Analog Dig. Sig. Proc. 50 (1), 38-45 (2003)
- J.S. Wu, H.Z. Shu, L. Senhadji, and L.M. Luo, "Mixed-radix algorithm for the computation of forward and inverse MDCTs," IEEE Trans. Circuits Syst. I: Reg. Papers 56 (4), 784-794 (2009)
- V. Britanak, "A survey of efficient MDCT implementations in MP3 audio coding standard: retrospective and state-of-the-art," Signal. Process. 91 (4), 624-672(2011)

[Luo-1] Luo, Fa-Long (2008). Mobile Multimedia Broadcasting Standards: Technology and Practice. Springer Science & Business Media. p. 590. ISBN 9780387782638.

[2] Jones, Graham A.; Layer, David H.; Osenkowsky, Thomas G. (2013). National Association of Broadcasters Engineering Handbook: NAB Engineering Handbook. Taylor & Francis. pp. 558–9. ISBN 978-1-136-03410-7.

[3] "Dolby AC-4: Audio Delivery for Next-Generation Entertainment Services" (PDF). Dolby Laboratories. June 2015. Retrieved 11 November 2019.

[4] Bleidt, R. L.; Sen, D.; Niedermeier, A.; Czelhan, B.; Füg, S.; et al. (2017). "Development of the MPEG-H TV Audio System for ATSC 3.0" (PDF). IEEE Transactions on Broadcasting. 63 (1): 202–236. doi:10.1109/TBC.2017.2661258.

[5] Schnell, Markus; Schmidt, Markus; Jander, Manuel; Albert, Tobias; Geiger, Ralf; Ruoppila, Vesa; Ekstrand, Per; Bernhard, Grill (October 2008). MPEG-4 Enhanced Low Delay AAC - A New Standard for High Quality Communication (PDF). 125th AES Convention. Fraunhofer IIS. Audio Engineering Society. Retrieved 20 October 2019.

[6] Lutzky, Manfred; Schuller, Gerald; Gayer, Marc; Krämer, Ulrich; Wabnik, Stefan (May 2004). A guideline to audio codec delay (PDF). 116th AES Convention. Fraunhofer IIS. Audio Engineering Society. Retrieved 24 October 2019.

[Nagireddi-7] Nagireddi, Sivannarayana (2008). VoIP Voice and Fax Signal Processing. John Wiley & Sons. p. 69. ISBN 9780470377864.

[presentation-8] Presentation of the CELT codec by Timothy B. Terriberry (65 minutes of video, see also presentation slides in PDF)

[homepage-9] "Opus Codec". Opus (Home page). Xiph.org Foundation. Retrieved July 31, 2012.

[ars-role-10] Bright, Peter (2012-09-12). "Newly standardized Opus audio codec fills every role from online chat to music". Ars Technica. Retrieved 2014-05-28.

[Ahmed-11] Ahmed, Nasir (January 1991). "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.

[pubDCT-12] Ahmed, Nasir; Natarajan, T.; Rao, K. R. (January 1974), "Discrete Cosine Transform", IEEE Transactions on Computers, C-23 (1): 90–93, doi:10.1109/T-C.1974.223784

[13] Princen, John P.; Johnson, A.W.; Bradley, Alan B. (1987). "Subband/Transform coding using filter bank designs based on time domain aliasing cancellation". ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing. 12: 2161–2164. doi:10.1109/ICASSP.1987.1169405.

[14] John P. Princen, Alan B. Bradley: Analysis/synthesis filter bank design based on time domain aliasing cancellation, IEEE Trans. Acoust. Speech Signal Processing, ASSP-34 (5), 1153–1161, 1986. Described a precursor to the MDCT using a combination of discrete cosine and sine transforms.

[15] H. S. Malvar, "Lapped Transforms for Efficient Transform/Subband Coding", IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. 38, no. 6, pp. 969–978 (Equation 22), June 1990.

[16] H. S. Malvar, "Modulated QMF Filter Banks with Perfect Reconstruction", Electronics Letters, vol. 26, no. 13, pp. 906–907 (Equation 13), June 1990.

[1]