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 transformación basada en la transformada de coseno discreta de tipo IV (DCT-IV), con la propiedad adicional de ser superpuesta : está diseñada para realizarse en bloques consecutivos de un conjunto de datos más grande , donde las siguientes Los bloques se superponen de modo que la última mitad de un bloque coincida con la primera mitad del siguiente bloque. 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] Alta definición. Codificación (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 más tarde por John P. Princen, AW Johnson y Alan B. Bradley en la Universidad de Surrey en 1987, ^[13] siguiendo un trabajo anterior de Princen y Bradley (1986) ^[14] para desarrollar el principio subyacente de la MDCT de cancelación de alias en el dominio del tiempo (TDAC), que se describe a continuación. (También existe una transformada análoga, la MDST, basada en la transformada sinusoidal discreta , así como otras formas de MDCT, rara vez utilizadas, basadas en diferentes tipos de combinaciones DCT o DCT/DST).

En MP3, la MDCT no se aplica directamente a la señal de audio, sino a la salida de un banco de filtro de cuadratura polifásico (PQF) de 32 bandas. La salida de esta MDCT se postprocesa mediante una fórmula de reducción de alias para reducir el alias 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 . La CAA, por otra parte, normalmente utiliza una TCMD pura; sólo la variante MPEG-4 AAC-SSR (rara vez utilizada) (de Sony ) utiliza un banco PQF de cuatro bandas seguido de una MDCT. Al igual que MP3, ATRAC utiliza filtros de espejo de cuadratura apilados (QMF) seguidos de una MDCT.

Definición

Como transformada traslapada, la MDCT es un poco inusual en comparación con otras transformadas relacionadas con Fourier en el sentido de 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 los 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í unidad, es una convención arbitraria y difiere entre tratamientos. Solo el producto de las normalizaciones de MDCT y IMDCT, a continuación, está restringido).

transformada inversa

La TCMD inversa se conoce como IMDCT . Debido a que hay diferentes números 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 agregando las IMDCT superpuestas de 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 para DCT-IV , una transformación ortogonal, la inversa tiene la misma forma que la transformación directa).

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

Cálculo

Aunque la aplicación directa de la fórmula MDCT requeriría operaciones O( N ² ), es posible calcular lo mismo con solo O( N log N ) complejidad factorizando recursivamente el cálculo, como en la transformada rápida de Fourier (FFT). También se pueden calcular MDCT mediante otras transformaciones, generalmente una DFT (FFT) o una DCT, combinadas con O ( N ) pasos de procesamiento previo y posterior. Además, como se describe a continuación, cualquier algoritmo para DCT-IV proporciona inmediatamente un método para calcular MDCT e IMDCT de tamaño uniforme.

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 mediante el uso de 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 la IMDCT. fórmulas 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, xey 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 donde se combinan bloques de datos de diferentes tamaños), pero por simplicidad consideramos el caso común de funciones de ventana idénticas para bloques del mismo tamaño.

La transformada permanece 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 traslapada 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 aplicadas a la MDCT son diferentes de las ventanas utilizadas 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 TCMD se aplican dos veces, tanto para la TCMD (análisis) como para la TCMD (síntesis).

Relación con DCT-IV y origen de TDAC

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

Para definir la relación precisa con el DCT-IV, uno debe darse cuenta de que el DCT-IV corresponde a condiciones de contorno alternas pares/impares: par en su límite izquierdo (alrededor de n  = −1/2), impar en su límite derecho (alrededor de n  =  N  − 1/2), y así sucesivamente (en lugar de límites periódicos como para una DFT ). Esto se desprende 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]}$

Considere 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 (del término + N /2 en la definición MDCT), entonces ( b , c , d ) se extienden más allá del final de las entradas N DCT-IV, por lo que debemos "doblar " devuélvalos de acuerdo con las condiciones límite 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 se indicó anteriormente.

(De esta manera, cualquier algoritmo para calcular la DCT-IV puede aplicarse trivialmente a la MDCT).

De manera similar, la fórmula IMDCT anterior es precisamente 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 de 2 N y se desplaza hacia la izquierda en N /2 . . El DCT-IV inverso simplemente devolvería las entradas (− c _R − d , a − b _R ) desde arriba. Cuando esto se extiende a través de las condiciones de contorno y se desplaza, se obtiene:

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

Por lo tanto, la mitad de los resultados de IMDCT son 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 manera más sencilla:

IMDCT (MDCT ( A , B )) = ( A − A _R , B + B _R ) / 2

Ahora podemos entender cómo funciona TDAC. Supongamos que se calcula la MDCT del bloque 2 N posterior, superpuesto al 50% ( B , C ). La IMDCT entonces producirá, de forma análoga a lo anterior: ( B − B _R , C + C _R ) / 2. Cuando esto se suma con el resultado anterior de la IMDCT 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 alias en el dominio del tiempo" ahora está claro. El uso de datos de entrada que se extienden más allá de los límites del DCT-IV lógico hace que los datos tengan alias de la misma manera que las frecuencias más allá de la frecuencia de Nyquist tienen alias para frecuencias más bajas, excepto que este alias ocurre en el dominio del tiempo en lugar del dominio del tiempo. Dominio de la frecuencia: no podemos distinguir las contribuciones de a y de b _R a la MDCT de ( a , b , c , d ), o de manera equivalente, al resultado de

IMDCT (MDCT ( 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 N impar (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 pasa a ser equivalente a la DCT-III/II, y el análisis es análogo al anterior.

Suavidad y discontinuidades.

Hemos visto anteriormente 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 ). El DCT-IV está diseñado para el caso en el que 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 tanto, su diferencia es pequeña. Miremos la mitad 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 ), hay una discontinuidad potencial donde el extremo derecho de − d se encuentra con el extremo izquierdo de a . Esta es la razón para utilizar 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 en ventana

Arriba, se demostró la propiedad TDAC para la MDCT ordinaria, lo que demuestra que al agregar IMDCT de bloques posteriores en su mitad superpuesta se recuperan los datos originales. La derivación de esta propiedad inversa para la MDCT en ventana es sólo un poco más complicada.

Considere la superposición de conjuntos consecutivos de 2 N entradas ( A , B ) y ( B , C ), para bloques A , B , C de tamaño N. Recuerde lo anterior que cuando y se realizan MDCT, IMDCT y se agregan 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 suponemos que multiplicamos tanto las entradas MDCT como las salidas IMDCT por una función de ventana de longitud 2 N. Como arriba, asumimos 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 se puede escribir como , con los cuadrados y las sumas realizadas por elementos. ${\displaystyle (W,W_{R})}$ ${\displaystyle W^{2}+W_{R}^{2}=(1,1,\ldots )}$

Por lo tanto, en lugar de MDCTing , ahora utilizamos MDCT (con todas las multiplicaciones realizadas por elementos). Cuando esto se IMDCTed y se multiplica nuevamente (por elementos) por la función de ventana, la última N mitad 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 de ventana).

De manera similar, el MDCT en ventanilla y el IMDCT de rendimientos, en su primera mitad N : ${\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.

Ver también

• Transformada de coseno discreta
• Otras transformadas de Fourier con ventanas superpuestas incluyen:
  • Transformada superpuesta compleja modulada
  • Transformada de Fourier de corto tiempo
  • 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 radiodifusión multimedia móvil: tecnología y práctica. Medios de ciencia y negocios de Springer . pag. 590.ISBN​ 9780387782638.
2. Jones, Graham A.; Capa, 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 y Francisco . págs. 558–9. ISBN 978-1-136-03410-7.
3. "Dolby AC-4: entrega de audio para servicios de entretenimiento de próxima generación" (PDF) . Laboratorios Dolby . Junio ​​de 2015 . Consultado el 11 de noviembre de 2019 .
4. Bleidt, RL; Enviar.; Niedermeier, A.; Czelhan, B.; Fug, S.; et al. (2017). «Desarrollo del Sistema de Audio de TV MPEG-H para ATSC 3.0» (PDF) . Transacciones IEEE sobre radiodifusión . 63 (1): 202–236. doi :10.1109/TBC.2017.2661258. S2CID  30821673.
5. Schnell, Markus; Schmidt, Markus; Jander, Manuel; Alberto, Tobías; Geiger, Ralf; Ruoppila, Vesa; Ekstrand, Per; Bernhard, Grill (octubre de 2008). MPEG-4 AAC mejorado de bajo retardo: 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, Manfredo; Schuller, Gerald; Gayer, Marc; Krämer, Ulrich; Wabnik, Stefan (mayo de 2004). Una guía para el retraso del códec de audio (PDF) . 116ª Convención 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 e hijos . pag. 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, ver también diapositivas de presentación Archivado el 16 de noviembre de 2023 en Wayback Machine en PDF)
9. "Códec Opus". Opus (Página de inicio). Fundación Xiph.org . Consultado el 31 de julio de 2012 .
10. Brillante, Peter (12 de septiembre de 2012). "El códec de audio Opus recientemente estandarizado cubre todas las funciones, desde el chat en línea hasta la música". Ars Técnica . Consultado el 28 de mayo de 2014 .
11. Ahmed, Nasir (enero de 1991). "Cómo se me ocurrió la transformada del coseno discreto". 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 de coseno discreta", IEEE Transactions on Computers , C-23 (1): 90–93, doi :10.1109/TC.1974.223784, S2CID  149806273
13. Príncipe, John P.; Johnson, AW; Bradley, Alan B. (1987). "Codificación de subbanda/transformación utilizando diseños de bancos de filtros basados ​​en la cancelación de alias en el dominio del tiempo". ICASP '87. Conferencia internacional IEEE sobre acústica, voz y procesamiento de señales . vol. 12. págs. 2161-2164. doi :10.1109/ICASSP.1987.1169405. S2CID  58446992.
14. John P. Princen, Alan B. Bradley: Diseño de banco de filtros de análisis/síntesis basado en la cancelación de alias en el dominio del tiempo , IEEE Trans. Acústico. Speech Signal Processing, ASSP-34 (5), 1153–1161, 1986. Describió un precursor de la MDCT utilizando una combinación de transformadas discretas de coseno y seno.
15. HS Malvar, "Transformaciones superpuestas para codificación de subbanda/transformación eficiente", IEEE Trans. sobre acústica, habla y procesamiento de señales , 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 alias en el dominio del tiempo", Speech Comm. 6 , 299-308 (1987).
• Para algoritmos, consulte 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 unificado MDCT/MDST 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 realizar la transformada de coseno discreta modificada y su inversa", IEEE Trans. Sistema de circuitos. II: Excavación analógica. 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. Sistema de circuitos. Yo: Reg. Artículos 56 (4), 784-794 (2009)
  • V. Britanak, "Un estudio de implementaciones MDCT eficientes en el estándar de codificación de audio MP3: retrospectiva y vanguardia", Signal. Proceso. 91 (4), 624-672 (2011)