Transformada de coseno discreta modificada

Transformación matemática utilizada en el procesamiento de señales

La transformada de coseno discreta modificada ( MDCT ) es una transformada basada en la transformada de coseno discreta de tipo IV (DCT-IV), con la propiedad adicional de estar superpuesta : está diseñada para ser realizada en bloques consecutivos de un conjunto de datos más grande , donde los bloques subsiguientes se superponen de modo que la última mitad de un bloque coincida con la primera mitad del bloque siguiente. Esta superposición, además de las cualidades de compactación de energía de la DCT, hace que la MDCT sea especialmente atractiva para aplicaciones de compresión de señales, ya que ayuda a evitar artefactos derivados de los límites de los bloques. Como resultado de estas ventajas, la MDCT es la técnica de compresión con pérdida más utilizada en la compresión de datos de audio . Se emplea en la mayoría de los estándares de codificación de audio modernos , incluidos 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] y MPEG-H 3D Audio , ^[4] así como estándares de codificación de voz como AAC-LD (LD-MDCT), ^[5] G.722.1 , ^[6] G.729.1 , ^[7] CELT , ^[8] y Opus . ^{[9] [10]}

La transformada discreta del coseno (DCT) fue propuesta por primera vez por Nasir Ahmed en 1972, ^[11] y demostrada por Ahmed con T. Natarajan y KR Rao en 1974. ^[12] La MDCT fue propuesta posteriormente por John P. Princen, AW Johnson y Alan B. Bradley en la Universidad de Surrey en 1987, ^[13] siguiendo el trabajo anterior de Princen y Bradley (1986) ^[14] para desarrollar el principio subyacente de la MDCT de cancelación de aliasing en el dominio del tiempo (TDAC), descrito a continuación. (También existe una transformada análoga, la MDST, basada en la transformada discreta del seno , así como otras formas, raramente utilizadas, de la MDCT basadas en diferentes tipos de DCT o combinaciones DCT/DST).

En MP3, la MDCT no se aplica directamente a la señal de audio, sino a la salida de un banco de filtros de cuadratura polifásica (PQF) de 32 bandas. La salida de esta MDCT se posprocesa mediante una fórmula de reducción de alias para reducir el aliasing típico del banco de filtros PQF. Esta combinación de un banco de filtros con una MDCT se denomina banco de filtros híbrido o MDCT de subbanda . AAC, por otro lado, normalmente utiliza una MDCT pura; solo la variante MPEG-4 AAC-SSR (de Sony ) (raramente utilizada ) utiliza un banco PQF de cuatro bandas seguido de una MDCT. De manera similar a MP3, ATRAC utiliza filtros de espejo en cuadratura apilados (QMF) seguidos de una MDCT.

Definición

Como transformada superpuesta, la MDCT es algo inusual en comparación con otras transformadas relacionadas con Fourier, ya que tiene la mitad de salidas que de entradas (en lugar del mismo número). En particular, es una función lineal (donde R denota el conjunto de números reales ). Los 2 N números reales x ₀ , ..., x _{2 N -1} se transforman en los N números reales X ₀ , ..., X _{N -1} según la fórmula: ${\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]}$

(El coeficiente de normalización delante de esta transformación, aquí la unidad, es una convención arbitraria y difiere entre tratamientos. Sólo el producto de las normalizaciones de la MDCT y la IMDCT, a continuación, está restringido).

Transformada inversa

La MDCT inversa se conoce como IMDCT . Debido a que hay diferentes cantidades de entradas y salidas, a primera vista podría parecer que la MDCT no debería ser invertible. Sin embargo, la invertibilidad perfecta se logra sumando las IMDCT superpuestas de los bloques superpuestos posteriores, lo que hace que los errores se cancelen y se recuperen los datos originales; esta técnica se conoce como cancelación de alias en el dominio del tiempo ( TDAC ).

La IMDCT transforma N números reales X ₀ , ..., X _{N -1} en 2 N números reales y ₀ , ..., y _{2 N -1} según la fórmula:

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

(Al igual que en el caso de la DCT-IV , una transformada ortogonal, la inversa tiene la misma forma que la transformada directa).

En el caso de una MDCT con ventana con la normalización de ventana habitual (ver más abajo), el coeficiente de normalización delante de la IMDCT debe multiplicarse por 2 (es decir, convertirse en 2/ N ).

Cálculo

Aunque la aplicación directa de la fórmula MDCT requeriría O( N ² ) operaciones, es posible calcular lo mismo con solo O( N log N ) complejidad mediante la factorización recursiva del cálculo, como en la transformada rápida de Fourier (FFT). También se pueden calcular MDCT mediante otras transformadas, normalmente una DFT (FFT) o una DCT, combinadas con pasos de preprocesamiento y posprocesamiento O( N ). Además, como se describe a continuación, cualquier algoritmo para la DCT-IV proporciona inmediatamente un método para calcular la MDCT y la IMDCT de tamaño par.

Funciones de ventana

Funciones de la ventana MDCT:
azul: coseno, rojo: seno-coseno, verde: Kaiser-Bessel modificado

En aplicaciones típicas de compresión de señales, las propiedades de transformación se mejoran aún más utilizando una función de ventana w _n ( n = 0, ..., 2 N −1) que se multiplica por x _n en la MDCT y por y _n en las fórmulas IMDCT, anteriores, para evitar discontinuidades en los límites n = 0 y 2 N haciendo que la función llegue suavemente a cero en esos puntos. (Es decir, la función de ventana se aplica a los datos antes de la MDCT o después de la IMDCT). En principio, x e y podrían tener diferentes funciones de ventana, y la función de ventana también podría cambiar de un bloque al siguiente (especialmente para el caso en el que se combinan bloques de datos de diferentes tamaños), pero para simplificar, consideramos el caso común de funciones de ventana idénticas para bloques de igual tamaño.

La transformada sigue siendo invertible (es decir, TDAC funciona), para una ventana simétrica w _n = w _{2 N −1− n} , siempre que w satisfaga la condición de Princen-Bradley:

${\displaystyle w_{n}^{2}+w_{n+N}^{2}=1}$.

Se utilizan varias funciones de ventana. Una ventana que produce una forma conocida como transformada superpuesta modulada (MLT) ^{[15] [16]} viene dada por

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

y se utiliza para MP3 y MPEG-2 AAC, y

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

para Vorbis. AC-3 utiliza una ventana derivada de Kaiser-Bessel (KBD) y MPEG-4 AAC también puede utilizar una ventana KBD.

Tenga en cuenta que las ventanas que se aplican a la MDCT son diferentes de las que se utilizan para otros tipos de análisis de señales, ya que deben cumplir la condición de Princen-Bradley. Una de las razones de esta diferencia es que las ventanas de MDCT se aplican dos veces, tanto para la MDCT (análisis) como para la IMDCT (síntesis).

Relación con DCT-IV y origen de TDAC

Como se puede ver al examinar las definiciones, para N pares , la MDCT es esencialmente equivalente a una DCT-IV, donde la entrada se desplaza en N /2 y se transforman dos N bloques de datos a la vez. Al examinar esta equivalencia con más cuidado, se pueden derivar fácilmente propiedades importantes como la TDAC.

Para definir la relación precisa con la DCT-IV, uno debe darse cuenta de que la DCT-IV corresponde a condiciones de contorno alternas pares/impares: par en su contorno izquierdo (alrededor de n  = −1/2), impar en su contorno derecho (alrededor de n  =  N  − 1/2), y así sucesivamente (en lugar de contornos periódicos como para una DFT ). Esto se deduce de las identidades y . Por lo tanto, si sus entradas son una matriz x de longitud N , podemos imaginar extender esta matriz a ( x , − x _R , − x , x _R , ...) y así sucesivamente, donde x _R denota x en orden inverso. ${\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]}$

Consideremos una MDCT con 2 N entradas y N salidas, donde dividimos las entradas en cuatro bloques ( a , b , c , d ) cada uno de tamaño N /2. Si los desplazamos hacia la derecha en N /2 (a partir del término + N /2 en la definición de MDCT), entonces ( b , c , d ) se extienden más allá del final de las N entradas DCT-IV, por lo que debemos "plegarlas" hacia atrás de acuerdo con las condiciones de contorno descritas anteriormente.

Por lo tanto, la MDCT de 2 N entradas ( a , b , c , d ) es exactamente equivalente a una DCT-IV de las N entradas: (− c _R − d , a − b _R ), donde R denota inversión como arriba.

(De esta manera, cualquier algoritmo para calcular la DCT-IV se puede aplicar de manera trivial a la MDCT).

De manera similar, la fórmula IMDCT anterior es exactamente la mitad de la DCT-IV (que es su propia inversa), donde la salida se extiende (a través de las condiciones de contorno) a una longitud 2 N y se desplaza hacia la izquierda por N /2. La DCT-IV inversa simplemente devolvería las entradas (− c _R − d , a − b _R ) de arriba. Cuando esto se extiende a través de las condiciones de contorno y se desplaza, se obtiene:

TCMI (TCMD ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

La mitad de las salidas de IMDCT son, por tanto, redundantes, ya que b − a _R = −( a − b _R ) _R , y lo mismo ocurre con los dos últimos términos. Si agrupamos la entrada en bloques más grandes A , B de tamaño N , donde A  = ( a , b ) y B  = ( c , d ), podemos escribir este resultado de una forma más sencilla:

TCMI (TCMD ( _A , B ) ) = ( A − AR , B + BR ₎ / 2

Ahora se puede entender cómo funciona la TDAC. Supongamos que se calcula la MDCT del bloque 2 N posterior ( B , C ), superpuesto al 50 %. La IMDCT arrojará entonces, de forma análoga a lo anterior: ( B − B _R , C + C _R ) / 2. Cuando esto se suma con el resultado de la IMDCT anterior en la mitad superpuesta, los términos invertidos se cancelan y se obtiene simplemente B , recuperando los datos originales.

Origen del TDAC

El origen del término "cancelación de aliasing en el dominio del tiempo" ahora está claro. El uso de datos de entrada que se extienden más allá de los límites de la DCT-IV lógica hace que los datos se aliasen de la misma manera que las frecuencias más allá de la frecuencia de Nyquist se aliasen a frecuencias más bajas, excepto que este aliasing ocurre en el dominio del tiempo en lugar del dominio de la frecuencia: no podemos distinguir las contribuciones de a y de b _R a la MDCT de ( a , b , c , d ), o equivalentemente, al resultado de

TCMI (TCMD ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

Las combinaciones c − d _R y así sucesivamente, tienen precisamente los signos correctos para que las combinaciones se cancelen cuando se suman.

Para los valores N impares (que rara vez se utilizan en la práctica), N /2 no es un número entero, por lo que la MDCT no es simplemente una permutación de desplazamiento de una DCT-IV. En este caso, el desplazamiento adicional de media muestra significa que la MDCT/IMDCT se vuelve equivalente a la DCT-III/II, y el análisis es análogo al anterior.

Suavidad y discontinuidades

Hemos visto arriba que la MDCT de 2 N entradas ( a , b , c , d ) es equivalente a una DCT-IV de las N entradas ( − c _R − d , a − b _R ). La DCT-IV está diseñada para el caso donde la función en el límite derecho es impar, y por lo tanto los valores cerca del límite derecho son cercanos a 0. Si la señal de entrada es suave, este es el caso: los componentes más a la derecha de a y b _R son consecutivos en la secuencia de entrada ( a , b , c , d ), y por lo tanto su diferencia es pequeña. Veamos el medio del intervalo: si reescribimos la expresión anterior como ( − c _R − d , a − b _R ) = ( − d , a ) − ( b , c ) _R , el segundo término, ( b , c ) _R , da una transición suave en el medio. Sin embargo, en el primer término, (− d , a ), existe una discontinuidad potencial donde el extremo derecho de − d se encuentra con el extremo izquierdo de a . Esta es la razón por la que se utiliza una función de ventana que reduce los componentes cerca de los límites de la secuencia de entrada ( a , b , c , d ) hacia 0.

TDAC para la MDCT con ventana

En la imagen anterior se demostró la propiedad TDAC para la MDCT ordinaria, mostrando que al agregar IMDCT de bloques subsiguientes en su mitad superpuesta se recuperan los datos originales. La derivación de esta propiedad inversa para la MDCT en ventana es apenas un poco más complicada.

Considere conjuntos consecutivos superpuestos de 2 N entradas ( A , B ) y ( B , C ), para bloques A , B , C de tamaño N. Recuerde de lo anterior que cuando y se MDCTizan, se IMDCTizan y se suman en su mitad superpuesta, obtenemos , los datos originales. ${\displaystyle (A,B)}$ ${\displaystyle (B,C)}$ ${\displaystyle (B+B_{R})/2+(B-B_{R})/2=B}$

Ahora supongamos que multiplicamos tanto las entradas MDCT como las salidas IMDCT por una función de ventana de longitud 2 N . Como antes, suponemos una función de ventana simétrica, que por lo tanto tiene la forma donde W es un vector de longitud N y R denota inversión como antes. Entonces la condición de Princen-Bradley puede escribirse como , con los cuadrados y las sumas realizadas elemento por elemento. ${\displaystyle (W,W_{R})}$ ${\displaystyle W^{2}+W_{R}^{2}=(1,1,\ldots )}$

Por lo tanto, en lugar de MDCT , ahora realizamos MDCT (con todas las multiplicaciones realizadas elemento por elemento). Cuando se realiza IMDCT y se multiplica nuevamente (elemento por elemento) por la función de ventana, la última mitad N se convierte en: ${\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}}$.

(Tenga en cuenta que ya no tenemos la multiplicación por 1/2, porque la normalización IMDCT difiere en un factor de 2 en el caso con ventana).

De manera similar, la MDCT y la IMDCT en ventana de rendimientos, en su primera mitad : ${\displaystyle (B,C)}$

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

Cuando sumamos estas dos mitades obtenemos:

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

recuperando los datos originales.

Véase también

• Transformada de coseno discreta
• Otras transformadas de Fourier con ventanas superpuestas incluyen:
  • Transformación superpuesta compleja modulada
  • Transformada de Fourier de corta duración
  • El método de Welch
• Formato de codificación de audio
• Compresión de audio (datos)

Referencias

1. Luo, Fa-Long (2008). Estándares de transmisión multimedia móvil: tecnología y práctica. Springer Science & Business Media . pág. 590. ISBN 9780387782638.
2. Jones, Graham A.; Layer, David H.; Osenkowsky, Thomas G. (2013). Manual de ingeniería de la Asociación Nacional de Radiodifusores: Manual de ingeniería de la NAB. Taylor & Francis . págs. 558-9. ISBN 978-1-136-03410-7.
3. "Dolby AC-4: Audio Delivery for Next-Generation Entertainment Services" (PDF) . Dolby Laboratories . Junio ​​de 2015 . Consultado el 11 de noviembre de 2019 .
4. Bleidt, RL; Sen, D.; Niedermeier, A.; Czelhan, B.; Füg, S.; et al. (2017). "Desarrollo del sistema de audio de TV MPEG-H para ATSC 3.0" (PDF) . IEEE Transactions on Broadcasting . 63 (1): 202–236. doi :10.1109/TBC.2017.2661258. S2CID  30821673.
5. Schnell, Markus; Schmidt, Markus; Jander, Manuel; Albert, Tobias; Geiger, Ralf; Ruoppila, Vesa; Ekstrand, Per; Bernhard, Grill (octubre de 2008). MPEG-4 Enhanced Low Delay AAC: un nuevo estándar para comunicaciones de alta calidad (PDF) . 125.ª Convención AES. Fraunhofer IIS . Sociedad de Ingeniería de Audio . Consultado el 20 de octubre de 2019 .
6. Lutzky, Manfred; Schuller, Gerald; Gayer, Marc; Krämer, Ulrich; Wabnik, Stefan (mayo de 2004). Una guía para el retardo de los códecs de audio (PDF) . 116.ª Convención de la AES. Fraunhofer IIS . Sociedad de Ingeniería de Audio . Consultado el 24 de octubre de 2019 .
7. Nagireddi, Sivannarayana (2008). Procesamiento de señales de voz y fax VoIP. John Wiley & Sons . pág. 69. ISBN 9780470377864.
8. Presentación del códec CELT Archivado el 7 de agosto de 2011 en Wayback Machine por Timothy B. Terriberry (65 minutos de video, consulte también las diapositivas de la presentación Archivado el 16 de noviembre de 2023 en Wayback Machine en formato PDF)
9. "Opus Codec". Opus (página de inicio). Fundación Xiph.org . Consultado el 31 de julio de 2012 .
10. Bright, Peter (12 de septiembre de 2012). "El nuevo códec de audio Opus estandarizado cumple todas las funciones, desde el chat en línea hasta la música". Ars Technica . Consultado el 28 de mayo de 2014 .
11. Ahmed, Nasir (enero de 1991). "Cómo se me ocurrió la transformada discreta del coseno" (PDF) . Procesamiento de señales digitales . 1 (1): 4–5. doi :10.1016/1051-2004(91)90086-Z.
12. Ahmed, Nasir ; Natarajan, T.; Rao, KR (enero de 1974), "Transformada discreta del coseno", 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). "Codificación de subbanda/transformación utilizando diseños de bancos de filtros basados ​​en cancelación de aliasing en el dominio del tiempo". ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing . Vol. 12. págs. 2161–2164. doi :10.1109/ICASSP.1987.1169405. S2CID  58446992.
14. John P. Princen, Alan B. Bradley: Diseño de un banco de filtros de análisis/síntesis basado en la cancelación de aliasing en el dominio del tiempo , IEEE Trans. Acoust. Speech Signal Processing, ASSP-34 (5), 1153–1161, 1986. Describieron un precursor de la MDCT que utiliza una combinación de transformadas discretas de coseno y seno.
15. HS Malvar, "Transformadas superpuestas para una codificación de subbanda/transformación eficiente", IEEE Trans. on Acoustics, Speech, and Signal Processing , vol. 38, núm. 6, págs. 969–978 (Ecuación 22), junio de 1990.
16. HS Malvar, "Bancos de filtros QMF modulados con reconstrucción perfecta", Electronics Letters , vol. 26, núm. 13, págs. 906–907 (Ecuación 13), junio de 1990.

Bibliografía

• Henrique S. Malvar, Procesamiento de señales con transformadas superpuestas (Artech House: Norwood MA, 1992).
• AW Johnson y AB Bradley, "Codificación de transformación adaptativa que incorpora cancelación de aliasing en el dominio del tiempo", Speech Comm. 6 , 299-308 (1987).
• Para conocer los algoritmos, consulte los ejemplos:
  • Chi-Min Liu y Wen-Chieh Lee, "Un algoritmo rápido unificado para bancos de filtros modulados por coseno en los estándares de audio actuales ^{[ enlace muerto permanente ]} ", J. Audio Engineering 47 (12), 1061-1075 (1999).
  • V. Britanak y KR Rao, "Un nuevo algoritmo rápido para el cálculo MDCT/MDST unificado directo e inverso", Signal Processing 82 , 433-459 (2002)
  • Vladimir Nikolajevic y Gerhard Fettweis, "Cálculo de MDCT directa e inversa utilizando la fórmula de recurrencia de Clenshaw", IEEE Trans. Sig. Proc. 51 (5), 1439-1444 (2003)
  • Che-Hong Chen, Bin-Da Liu y Jar-Ferr Yang, "Arquitecturas recursivas para la realización de la transformada de coseno discreta modificada y su inversa", IEEE Trans. Circuits Syst. II: Analog Dig. Sig. Proc. 50 (1), 38-45 (2003)
  • JS Wu, HZ Shu, L. Senhadji y LM Luo, "Algoritmo de base mixta para el cálculo de MDCT directas e inversas", IEEE Trans. Circuits Syst. I: Reg. Papers 56 (4), 784-794 (2009)
  • V. Britanak, "Un estudio de las implementaciones eficientes de MDCT en el estándar de codificación de audio MP3: retrospectiva y estado del arte", Signal. Process. 91 (4), 624-672(2011)