Transformada sinusoidal discreta

En matemáticas , la transformada sinusoidal discreta (DST) es una transformada relacionada con Fourier similar a la transformada discreta de Fourier (DFT), pero utilizando una matriz puramente real . Es equivalente a las partes imaginarias de una DFT de aproximadamente el doble de longitud, que opera sobre datos reales con simetría impar (ya que la transformada de Fourier de una función real e impar es imaginaria e impar), donde en algunas variantes la entrada y / o salida los datos se desplazan en media muestra.

Existe una familia de transformadas compuestas por funciones hiperbólicas seno y seno . Estas transformaciones se realizan en base a la vibración natural de placas cuadradas delgadas con diferentes condiciones de contorno . ^[1]

La DST está relacionada con la transformada de coseno discreta (DCT), que es equivalente a una DFT de funciones reales y pares . Consulte el artículo de DCT para obtener una descripción general de cómo las condiciones de contorno se relacionan con los diversos tipos de DCT y DST. Generalmente, la DST se deriva de la DCT reemplazando la condición de Neumann en x = 0 con una condición de Dirichlet . ^[2] Tanto el DCT como el DST fueron descritos por Nasir Ahmed T. Natarajan y KR Rao en 1974. ^{[3] [4]} El DST tipo I (DST-I) fue descrito más tarde por Anil K. Jain en 1976, y el DST tipo II (DST-II) fue descrito por HB Kekra y JK Solanka en 1978. ^[5]

Aplicaciones

Las DST se emplean ampliamente en la resolución de ecuaciones diferenciales parciales mediante métodos espectrales , donde las diferentes variantes de la DST corresponden a condiciones de frontera pares / impares ligeramente diferentes en los dos extremos de la matriz.

Resumen informal

Ilustración de las extensiones pares / impares implícitas de los datos de entrada de DST, para N = 9 puntos de datos (puntos rojos), para los cuatro tipos más comunes de DST (tipos I-IV).

Como cualquier transformada relacionada con Fourier, las transformadas sinusoidales discretas (DST) expresan una función o una señal en términos de una suma de sinusoides con diferentes frecuencias y amplitudes . Como la transformada discreta de Fourier (DFT), una DST opera en una función en un número finito de puntos de datos discretos. La distinción obvia entre una DST y una DFT es que la primera usa solo funciones sinusoidales , mientras que la segunda usa tanto cosenos como senos (en forma de exponenciales complejas ). Sin embargo, esta diferencia visible es simplemente una consecuencia de una distinción más profunda: una DST implica diferentes condiciones de frontera que la DFT u otras transformadas relacionadas.

Se puede pensar que las transformadas relacionadas con Fourier que operan en una función sobre un dominio finito , como la DFT o DST o una serie de Fourier , definen implícitamente una extensión de esa función fuera del dominio. Es decir, una vez que escribes una función${\displaystyle f(x)}$ como una suma de sinusoides, puede evaluar esa suma en cualquier ${\displaystyle x}$, incluso para ${\displaystyle x}$ donde el original ${\displaystyle f(x)}$no se especificó. La DFT, como la serie de Fourier, implica una extensión periódica de la función original. Un DST, como una transformada sinusoidal , implica una extensión extraña de la función original.

Sin embargo, debido a que las DST operan en secuencias finitas y discretas , surgen dos problemas que no se aplican a la transformada sinusoidal continua. En primer lugar, uno tiene que especificar si la función es par o impar en ambos de los límites izquierdo y derecho del dominio (es decir, la min- n y max- n límites en las definiciones de abajo, respectivamente). En segundo lugar, hay que especificar en qué punto la función es par o impar. En particular, considere una secuencia ( a , b , c ) de tres puntos de datos igualmente espaciados y digamos que especificamos un límite izquierdo impar . Hay dos posibilidades razonables: o los datos son extraños sobre el punto anterior a a , en cuyo caso la extensión impar es (- c , - b , - a , 0, a , b , c ), o los datos son extraños sobre el punto a mitad de camino entre una y el punto anterior, en cuyo caso la extensión impar es (- c , - b , - un , una , b , c )

Estas opciones conducen a todas las variaciones estándar de las DST y también a las transformadas de coseno discretas (DCT). Cada límite puede ser par o impar (2 opciones por límite) y puede ser simétrico con respecto a un punto de datos o el punto a medio camino entre dos puntos de datos (2 opciones por límite), para un total de${\displaystyle 2\times 2\times 2\times 2=16}$posibilidades. La mitad de estas posibilidades, aquellas en las que el límite izquierdo es impar, corresponden a los 8 tipos de DST; la otra mitad son los 8 tipos de DCT.

Estas diferentes condiciones de contorno afectan en gran medida las aplicaciones de la transformada y conducen a propiedades especialmente útiles para los diversos tipos de DCT. Más directamente, cuando se utilizan transformadas relacionadas con Fourier para resolver ecuaciones diferenciales parciales mediante métodos espectrales , las condiciones de contorno se especifican directamente como parte del problema que se está resolviendo.

Definición

Formalmente, el sine transformada discreta es una lineal , invertible función F  : R ^N -> R ^N (donde R denota el conjunto de números reales ), o equivalentemente un N × N matriz cuadrada . Hay varias variantes del DST con definiciones ligeramente modificadas. Los N números reales x ₀ , x _{N - 1} se transforman en los N números reales X ₀ , X _{N - 1} según una de las fórmulas:

DST-I

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N+1}}(n+1)(k+1)\right]\quad \quad k=0,\dots ,N-1}$

La matriz DST-I es ortogonal (hasta un factor de escala).

Un DST-I es exactamente equivalente a un DFT de una secuencia real que es impar alrededor de los puntos cero y medio, con una escala de 1/2. Por ejemplo, un DST-I de N = 3 números reales ( a , b , c ) es exactamente equivalente a un DFT de ocho números reales (0, a , b , c , 0, - c , - b , - a ) (simetría impar), escalada en 1/2. (Por el contrario, los tipos II-IV de DST implican un desplazamiento de media muestra en la DFT equivalente.) Esta es la razón del N  + 1 en el denominador de la función seno: la DFT equivalente tiene 2 ( N +1) puntos y tiene 2π / 2 ( N +1) en su frecuencia sinusoide, por lo que el DST-I tiene π / ( N +1) en su frecuencia.

Por tanto, el DST-I corresponde a las condiciones de contorno: x _n es impar alrededor de n  = −1 e impar alrededor de n = N ; de manera similar para X _k .

DST-II

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)(k+1)\right]\quad \quad k=0,\dots ,N-1}$

Algunos autores multiplican aún más el término X _{N - 1} por 1 / √ 2 (ver más abajo el cambio correspondiente en DST-III). Esto hace que la matriz DST-II sea ortogonal (hasta un factor de escala), pero rompe la correspondencia directa con una DFT real impar de entrada medio desplazada.

El DST-II implica las condiciones de contorno: x _n es impar alrededor de n  = −1/2 e impar alrededor de n  =  N  - 1/2; X _k es impar alrededor de k  = −1 e incluso alrededor de k  =  N  - 1.

DST-III

${\displaystyle X_{k}={\frac {(-1)^{k}}{2}}x_{N-1}+\sum _{n=0}^{N-2}x_{n}\sin \left[{\frac {\pi }{N}}(n+1)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}$

Algunos autores multiplican aún más el término x _{N - 1} por √ 2 (consulte más arriba el cambio correspondiente en DST-II). Esto hace que la matriz DST-III sea ortogonal (hasta un factor de escala), pero rompe la correspondencia directa con una DFT real impar de salida medio desplazada.

El DST-III implica las condiciones de contorno: x _n es impar alrededor de n  = −1 e incluso alrededor de n  =  N  - 1; X _k es impar alrededor de k  = −1/2 e impar alrededor de k  =  N  - 1/2.

DST-IV

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}$

La matriz DST-IV es ortogonal (hasta un factor de escala).

El DST-IV implica las condiciones de contorno: x _n es impar alrededor de n  = −1/2 e incluso alrededor de n  =  N  - 1/2; de manera similar para X _k .

DST V-VIII

Los tipos de DST I – IV son equivalentes a los DFT reales impares de orden par. En principio, existen en realidad cuatro tipos adicionales de transformada sinusoidal discreta (Martucci, 1994), correspondientes a DFT reales impares de orden lógicamente impar, que tienen factores de N +1/2 en los denominadores de los argumentos sinusoidales. Sin embargo, estas variantes parecen utilizarse raramente en la práctica.

Transformaciones inversas

El inverso de DST-I es DST-I multiplicado por 2 / ( N  + 1). La inversa de DST-IV es DST-IV multiplica por 2 / N . El inverso de DST-II es DST-III multiplicado por 2 / N (y viceversa).

En cuanto a la DFT , el factor de normalización frente a estas definiciones de transformación es simplemente una convención y difiere entre tratamientos. Por ejemplo, algunos autores multiplican las transformadas por${\displaystyle {\sqrt {2/N}}}$ de modo que la inversa no requiera ningún factor multiplicativo adicional.

Cálculo

Aunque la aplicación directa de estas fórmulas requeriría operaciones O ( N ² ), es posible calcular lo mismo con solo complejidad O ( N log N ) factorizando el cálculo similar a la transformada rápida de Fourier (FFT). (También se pueden calcular las DST a través de las FFT combinadas con los pasos de procesamiento previo y posterior de O ( N )).

Un DST-III o DST-IV se puede calcular a partir de un DCT-III o DCT-IV (ver transformada de coseno discreta ), respectivamente, invirtiendo el orden de las entradas y cambiando el signo de cada otra salida, y viceversa para DST -II de DCT-II. De esta forma se deduce que los tipos II-IV de la DST requieren exactamente el mismo número de operaciones aritméticas (sumas y multiplicaciones) que los tipos correspondientes de DCT.

Referencias

1. Abedi, M .; Sun, B .; Zheng, Z. (julio de 2019). "Una familia de transformaciones sinusoidal-hiperbólicas con aplicaciones potenciales en la detección por compresión". Transacciones IEEE sobre procesamiento de imágenes . 28 (7): 3571–3583. Código bibliográfico : 2019ITIP ... 28.3571A . doi : 10.1109 / TIP.2019.2912355 . PMID  31071031 .
2. Britanak, Vladimir; Yip, Patrick C .; Rao, KR (2010). Transformaciones discretas de coseno y seno: propiedades generales, algoritmos rápidos y aproximaciones enteras . Elsevier . págs. 35–6. ISBN 9780080464640.
3. Ahmed, Nasir ; Natarajan, T .; Rao, KR (enero de 1974), "Discrete Cosine Transform" (PDF) , IEEE Transactions on Computers , C-23 (1): 90–93, doi : 10.1109 / TC.1974.223784
4. Ahmed, Nasir (enero de 1991). "Cómo se me ocurrió la transformada discreta del coseno" . Procesamiento de señales digitales . 1 (1): 4–5. doi : 10.1016 / 1051-2004 (91) 90086-Z .
5. Dhamija, Swati; Jain, Priyanka (septiembre de 2011). "Análisis comparativo para la transformada senoidal discreta como método adecuado para la estimación de ruido" . Revista Internacional de Ciencias de la Computación . 8 (5): 162-164 . Consultado el 4 de noviembre de 2019 , a través de ResearchGate.

Bibliografía

• SA Martucci, "Convolución simétrica y transformaciones discretas de seno y coseno", IEEE Trans. Proceso de señal. SP-42 , 1038-1051 (1994).
• Matteo Frigo y Steven G. Johnson : FFTW , http://www.fftw.org/ . Una biblioteca C gratuita ( GPL ) que puede calcular DST rápidos (tipos I-IV) en una o más dimensiones, de tamaño arbitrario. También M. Frigo y SG Johnson, " The Design and Implementation of FFTW3 ", Proceedings of the IEEE 93 (2), 216-231 (2005).
• Takuya Ooura: Paquete FFT de uso general, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Bibliotecas C & FORTRAN gratuitas para calcular DST rápidas en una, dos o tres dimensiones, potencia de 2 tamaños.
• Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 12.4.1. Transformación sinusoidal" , Recetas numéricas: El arte de la informática científica (3ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8.
• R. Chivukula e Y. Reznik, " Cálculo rápido de transformadas discretas del coseno y del seno de los tipos VI y VII ", Proc. SPIE Vol. 8135, 2011.