Transformada discreta del seno

En matemáticas , la transformada discreta de seno (DST) es una transformada relacionada con Fourier similar a la transformada discreta de Fourier (DFT), pero que utiliza 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 los datos de entrada y/o salida se desplazan media muestra.

La DST está relacionada con la transformada discreta del coseno (DCT), que es equivalente a una DFT de funciones reales y pares . Consulte el artículo sobre DCT para una discusión general de cómo las condiciones de contorno relacionan los distintos 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 . ^{[ 1 ]} Tanto la DCT como la DST fueron descritas por Nasir Ahmed , T. Natarajan y KR Rao en 1974. ^{[ 2 ]}^{[ 3 ]} La DST de tipo I (DST-I) fue descrita posteriormente por Anil K. Jain en 1976, y la DST de tipo II (DST-II) fue descrita por HB Kekra y JK Solanka en 1978. ^{[ 4 ]}

Desde la perspectiva del procesamiento algebraico de señales , tanto la DST como la DCT surgen como transformadas espectrales asociadas al grupo diedral , diferenciándose únicamente en la elección de las condiciones de contorno: la DCT corresponde a contornos simétricos (pares, Neumann), mientras que la DST corresponde a contornos antisimétricos (impares, Dirichlet). Juntas, forman una familia completa de transformadas espectrales para el grupo diedral, al igual que la DFT es la transformada espectral para el grupo cíclico con condiciones de contorno periódicas. ^{[ 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 contorno pares/impares ligeramente diferentes en los dos extremos de la matriz.

Descripción general informal

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

Al igual que cualquier transformada relacionada con Fourier, las transformadas discretas de seno (DST) expresan una función o una señal en términos de una suma de sinusoides con diferentes frecuencias y amplitudes . Al igual que la transformada discreta de Fourier (DFT), una DST opera sobre 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 utiliza solo funciones seno , mientras que la segunda utiliza 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 condiciones de contorno diferentes a las de la DFT u otras transformadas relacionadas.

Las transformadas relacionadas con Fourier que operan sobre una función en un dominio finito , como la DFT o la DST o una serie de Fourier , pueden considerarse como la definición implícita de una extensión de esa función fuera del dominio. Es decir, una vez que escribes una función $f(x)$ como una suma de sinusoides, puedes evaluar esa suma en cualquier $x$ , incluso para $x$ donde el original $f(x)$ No se especificó. La DFT, al igual que la serie de Fourier, implica una extensión periódica de la función original. Una DST, al igual que una transformada sinusoidal , implica una extensión impar de la función original.

Sin embargo, debido a que las transformadas de seno discretas (DST) operan sobre secuencias finitas y discretas , surgen dos problemas que no se aplican a la transformada de seno continua. Primero, hay que especificar si la función es par o impar en los límites izquierdo y derecho del dominio (es decir, los límites min- n y max -n en las definiciones siguientes, respectivamente). Segundo, hay que especificar alrededor de qué punto la función es par o impar. En particular, consideremos 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 bien los datos son impares alrededor del punto anterior a a , en cuyo caso la extensión impar es ( −c , −b , −a , 0 , a , b , c ) , o bien los datos son impares alrededor del punto medio entre a y el punto anterior, en cuyo caso la extensión impar es ( −c , −b , −a , a , b , c ) .

Estas opciones dan lugar a todas las variaciones estándar de las transformadas discretas de coseno (DST) y también a las transformadas discretas de coseno (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 al punto medio entre dos puntos de datos (2 opciones por límite), para un total de $2\times 2\times 2\times 2=16$ posibilidades. La mitad de estas posibilidades, aquellas donde 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 notablemente las aplicaciones de la transformada y dan lugar a propiedades singularmente útiles para los distintos tipos de DCT. De forma más directa, al utilizar 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, la transformada discreta del seno es una función lineal e invertible F : R ^N → R ^N (donde R denota el conjunto de los números reales ), o equivalentemente una matriz cuadrada N × N. Existen varias variantes de la DST con definiciones ligeramente modificadas. Los N números reales x ₀ , …, x _N₋₁ se transforman en los N números reales X ₀ , …, X _N₋₁ según una de las fórmulas:

DST-I

{\begin{aligned}X_{k}&=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N+1}}(n+1)(k+1)\right]&k&=0,\dots ,N-1\\X_{k-1}&=\sum _{n=1}^{N}x_{n-1}\sin \left[{\frac {\pi nk}{N+1}}\right]&k&=1,\dots ,N\end{aligned}}

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

Un DST-I es exactamente equivalente a un DFT de una secuencia real que es impar alrededor del punto cero y el punto medio, escalado por 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 ) , escalado por 1/2 . ( En contraste , los tipos II-IV de DST implican un desplazamiento de media muestra en el DFT equivalente). Esta es la razón del N + 1 en el denominador de la función seno: el DFT equivalente tiene 2( N + 1) puntos y tiene 2π/2( N + 1) en su frecuencia sinusoidal, por lo que el DST-I tiene π/( N + 1) en su frecuencia.

Por lo 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

$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 además el término X _{N − 1} por 1/ √ 2 (véase más abajo el cambio correspondiente en DST-III). Esto hace que la matriz DST-II sea ortogonal (salvo un factor de escala), pero rompe la correspondencia directa con una DFT real impar de entrada desplazada a la mitad.

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 y par alrededor de k = N − 1.

DST-III

$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 además el término x _{N − 1} por √ 2 (véase más arriba el cambio correspondiente en DST-II). Esto hace que la matriz DST-III sea ortogonal (salvo un factor de escala), pero rompe la correspondencia directa con una DFT real impar de salida desplazada a la mitad.

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

DST-IV

$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 (salvo un factor de escala).

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

DST V–VIII

Los tipos I-IV de DST son equivalentes a las DFT de orden par con números reales impares. En principio, existen cuatro tipos adicionales de transformada discreta del seno (Martucci, 1994), que corresponden a DFT de orden lógicamente impar con números reales impares, cuyos denominadores de los argumentos del seno tienen factores de N + 1/2. Sin embargo, estas variantes rara vez se utilizan en la práctica.

Transformadas inversas

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

En cuanto a la DFT , el factor de normalización que precede a estas definiciones de transformada es simplemente una convención y difiere entre los distintos tratamientos. Por ejemplo, algunos autores multiplican las transformadas por ${\textstyle {\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 O( N² ) operaciones, es posible calcular lo mismo con una complejidad de solo O( ^Nlog N ) factorizando el cálculo de forma similar a la transformada rápida de Fourier (FFT). (También se pueden calcular DST mediante FFT combinadas con pasos de preprocesamiento y postprocesamiento de O( N )).

Una DST-III o DST-IV se puede calcular a partir de una DCT-III o DCT-IV (véase transformada discreta del coseno ), respectivamente, invirtiendo el orden de las entradas y cambiando el signo de cada salida alterna, y viceversa para la DST-II a partir de la DCT-II. De este modo, 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 DCT correspondientes.

Generalizaciones

Existe una familia de transformadas compuestas por funciones seno y seno hiperbólico ; estas transformadas se realizan a partir de la vibración natural de placas cuadradas delgadas con diferentes condiciones de contorno . ^[⁶^]

Referencias

↑ Britanak, Vladimir; Yip, Patrick C.; Rao, KR (2010). Transformadas discretas de coseno y seno: propiedades generales, algoritmos rápidos y aproximaciones enteras . Elsevier . págs. 35–36 . ISBN 9780080464640.
↑ Ahmed, Nasir ; Natarajan, T.; Rao, KR (enero de 1974), "Transformada discreta del coseno" (PDF) , IEEE Transactions on Computers , C-23 (1): 90–93 , doi : 10.1109/TC.1974.223784 , S2CID 149806273
↑ Ahmed, Nasir (enero de 1991). "Cómo desarrollé la transformada discreta del coseno" . Procesamiento de señales digitales . 1 (1): 4– 5. Bibcode : 1991DSP.....1....4A . doi : 10.1016/1051-2004(91)90086-Z .
↑ Dhamija, Swati; Jain, Priyanka (septiembre de 2011). "Análisis comparativo de la transformada discreta de seno como método adecuado para la estimación de ruido" . Revista Internacional de Ciencias de la Computación . 8 (5): 162– 164. Recuperado el 4 de noviembre de 2019 a través de ResearchGate.
↑ Püschel, Markus; Moura, José MF (2008). "Teoría del procesamiento de señales algebraicas: espacio 1-D". IEEE Transactions on Signal Processing . 56 (8): 3586– 3599. doi : 10.1109/TSP.2008.925259 .
↑ Abedi, M.; Sun, B.; Zheng, Z. (julio de 2019). "Una familia de transformadas hiperbólicas sinusoidales con aplicaciones potenciales en detección compresiva". IEEE Transactions on Image Processing . 28 (7): 3571– 3583. Bibcode : 2019ITIP...28.3571A . doi : 10.1109/TIP.2019.2912355 . PMID 31071031. S2CID 174820107 .

Bibliografía

SA Martucci, "Convolución simétrica y transformadas discretas de seno y coseno", IEEE Trans. Signal Process. SP-42 , 1038–1051 (1994).
Matteo Frigo y Steven G. Johnson : FFTW , página principal de FFTW . Una biblioteca C gratuita ( GPL ) que puede calcular DST rápidos (tipos I-IV) en una o más dimensiones, de tamaño arbitrario. Véase también M. Frigo y SG Johnson, " El diseño e implementación de FFTW3 ", Actas del IEEE 93 (2), 216-231 (2005).
Takuya Ooura: Paquete FFT de propósito general, paquete FFT de 1 dimensión / 2 dimensiones . Bibliotecas gratuitas en C y FORTRAN para calcular transformadas de Fourier discretas (DST) rápidas en una, dos o tres dimensiones, con tamaños que son potencias de 2.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 12.4.1. Transformada del seno" , Numerical Recipes: The Art of Scientific Computing (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011 , consultado el 13 de agosto de 2011..
R. Chivukula y Y. Reznik, " Cálculo rápido de transformadas discretas de coseno y seno de tipos VI y VII ", Proc. SPIE Vol. 8135, 2011.

[1] Britanak, Vladimir; Yip, Patrick C.; Rao, KR (2010). Transformadas discretas de coseno y seno: propiedades generales, algoritmos rápidos y aproximaciones enteras . Elsevier . págs. 35–36 . ISBN 9780080464640.

[pubDCT-2] Ahmed, Nasir ; Natarajan, T.; Rao, KR (enero de 1974), "Transformada discreta del coseno" (PDF) , IEEE Transactions on Computers , C-23 (1): 90–93 , doi : 10.1109/TC.1974.223784 , S2CID 149806273

[Ahmed-3] Ahmed, Nasir (enero de 1991). "Cómo desarrollé la transformada discreta del coseno" . Procesamiento de señales digitales . 1 (1): 4– 5. Bibcode : 1991DSP.....1....4A . doi : 10.1016/1051-2004(91)90086-Z .

[4] Dhamija, Swati; Jain, Priyanka (septiembre de 2011). "Análisis comparativo de la transformada discreta de seno como método adecuado para la estimación de ruido" . Revista Internacional de Ciencias de la Computación . 8 (5): 162– 164. Recuperado el 4 de noviembre de 2019 a través de ResearchGate.

[5] Püschel, Markus; Moura, José MF (2008). "Teoría del procesamiento de señales algebraicas: espacio 1-D". IEEE Transactions on Signal Processing . 56 (8): 3586– 3599. doi : 10.1109/TSP.2008.925259 .

[6] Abedi, M.; Sun, B.; Zheng, Z. (julio de 2019). "Una familia de transformadas hiperbólicas sinusoidales con aplicaciones potenciales en detección compresiva". IEEE Transactions on Image Processing . 28 (7): 3571– 3583. Bibcode : 2019ITIP...28.3571A . doi : 10.1109/TIP.2019.2912355 . PMID 31071031. S2CID 174820107 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[