Una transformada Hartley discreta (DHT) es una transformada relacionada con Fourier de datos discretos y periódicos similar a la transformada de Fourier discreta (DFT), con aplicaciones análogas en el procesamiento de señales y campos relacionados. Su principal distinción con la DFT es que transforma entradas reales en salidas reales, sin la participación intrínseca de números complejos . Así como la DFT es el análogo discreto de la transformada de Fourier continua (FT), la DHT es el análogo discreto de la transformada de Hartley continua (HT), introducida por Ralph VL Hartley en 1942. [1]
Dado que existen algoritmos rápidos para la DHT análogos a la transformada rápida de Fourier (FFT), la DHT fue propuesta originalmente por Ronald N. Bracewell en 1983 [2] como una herramienta computacional más eficiente en el caso común en el que los datos son puramente reales. Sin embargo, posteriormente se argumentó que los algoritmos FFT especializados para entradas o salidas reales se pueden encontrar normalmente con un poco menos de operaciones que cualquier algoritmo correspondiente para la DHT.
La combinación a veces se denota cas( z ) , y no debe confundirse con cis( z ) = e iz = cos( z ) + i sin( z ) , o e − iz = cis(− z ) que aparece en la definición de DFT (donde i es la unidad imaginaria ).
Al igual que con la DFT, el factor de escala general delante de la transformada y el signo del término seno son una cuestión de convención. Aunque estas convenciones varían ocasionalmente entre autores, no afectan las propiedades esenciales de la transformada.
Propiedades
La transformada puede interpretarse como la multiplicación del vector ( x 0 , ...., x N −1 ) por una matriz N -por- N ; por lo tanto, la transformada discreta de Hartley es un operador lineal . La matriz es invertible; la transformación inversa, que permite recuperar la x n a partir de la H k , es simplemente la DHT de H k multiplicada por 1/ N . Es decir, la DHT es su propia inversa ( involutiva ), hasta un factor de escala global.
La DHT se puede utilizar para calcular la DFT, y viceversa. Para entradas reales x n , la salida de la DFT X k tiene una parte real ( H k + H N−k )/2 y una parte imaginaria ( H N−k − H k )/2. Por el contrario, la DHT es equivalente a calcular la DFT de x n multiplicada por 1 + i , y luego tomar la parte real del resultado.
Al igual que con la DFT, una convolución cíclica z = x ∗ y de dos vectores x = ( x n ) e y = ( y n ) para producir un vector z = ( z n ), todos de longitud N , se convierte en una operación simple después de la DHT. En particular, supongamos que los vectores X , Y y Z denotan la DHT de x , y y z respectivamente. Entonces los elementos de Z están dados por:
donde tomamos todos los vectores como periódicos en N ( X N = X 0 , etcétera). Por lo tanto, al igual que la DFT transforma una convolución en una multiplicación puntual de números complejos ( pares de partes reales e imaginarias), la DHT transforma una convolución en una combinación simple de pares de componentes de frecuencia real. La DHT inversa produce entonces el vector deseado z . De esta manera, un algoritmo rápido para la DHT (ver más abajo) produce un algoritmo rápido para convolución. (Esto es ligeramente más caro que el procedimiento correspondiente para la DFT, sin incluir los costos de las transformaciones a continuación, porque la operación por pares anterior requiere 8 operaciones aritméticas reales en comparación con las 6 de una multiplicación compleja. Este recuento no incluye la división por 2, que puede ser absorbida, por ejemplo, en la normalización 1/ N de la DHT inversa).
Algoritmos rápidos
Al igual que para la DFT, evaluar la definición de DHT directamente requeriría O( N 2 ) operaciones aritméticas (ver notación Big O ). Sin embargo, existen algoritmos rápidos similares a la FFT que calculan el mismo resultado en solo O( N log N ) operaciones. Casi todos los algoritmos FFT, desde Cooley-Tukey hasta el factor primo , pasando por Winograd (1985) [3] y Bruun (1993), [4] tienen un análogo directo para la transformada discreta de Hartley. (Sin embargo, algunos de los algoritmos FFT más exóticos, como la QFT, aún no se han investigado en el contexto de la DHT).
En particular, el análogo DHT del algoritmo Cooley–Tukey se conoce comúnmente como el algoritmo de transformada rápida de Hartley (FHT), y fue descrito por primera vez por Bracewell en 1984. [5] Este algoritmo FHT, al menos cuando se aplica a tamaños de potencia de dos N , es el tema de la patente de los Estados Unidos número 4.646.256, otorgada en 1987 a la Universidad de Stanford . Stanford colocó esta patente en el dominio público en 1994 (Bracewell, 1995). [6]
Como se mencionó anteriormente, los algoritmos DHT son típicamente ligeramente menos eficientes (en términos de la cantidad de operaciones de punto flotante ) que el algoritmo DFT correspondiente (FFT) especializado para entradas (o salidas) reales. Esto fue argumentado por primera vez por Sorensen et al. (1987) [7] y Duhamel & Vetterli (1987). [8] Los últimos autores obtuvieron lo que parece ser el recuento de operaciones publicado más bajo para el DHT de tamaños de potencia de dos, empleando un algoritmo de base dividida (similar a la FFT de base dividida ) que divide un DHT de longitud N en un DHT de longitud N /2 y dos DFT de entrada real ( no DHT) de longitud N /4. De esta manera, argumentaron que un DHT de longitud de potencia de dos se puede calcular con, en el mejor de los casos, 2 adiciones más que el número correspondiente de operaciones aritméticas para el DFT de entrada real.
En las computadoras actuales, el rendimiento está determinado más por consideraciones de caché y pipeline de CPU que por recuentos estrictos de operaciones, y es poco probable que una ligera diferencia en el costo aritmético sea significativa. Dado que los algoritmos FHT y FFT de entrada real tienen estructuras computacionales similares, ninguno parece tener una ventaja de velocidad sustancial a priori (Popović [sr] y Šević, 1994). [9] Como cuestión práctica, las bibliotecas FFT de entrada real altamente optimizadas están disponibles de muchas fuentes (por ejemplo, de proveedores de CPU como Intel ), mientras que las bibliotecas DHT altamente optimizadas son menos comunes.
Por otra parte, los cálculos redundantes en las FFT debido a las entradas reales son más difíciles de eliminar para números primos grandes N , a pesar de la existencia de algoritmos de datos complejos O( N log N ) para tales casos, porque las redundancias están ocultas detrás de permutaciones intrincadas y/o rotaciones de fase en esos algoritmos. Por el contrario, un algoritmo FFT de tamaño primo estándar, el algoritmo de Rader , se puede aplicar directamente a la DHT de datos reales para aproximadamente un factor de dos menos de cálculo que el de la FFT compleja equivalente (Frigo y Johnson, 2005). [10] Por otra parte, también es posible una adaptación no basada en DHT del algoritmo de Rader para DFT de entrada real (Chu y Burrus , 1982). [11]
La rD-DHT (MD-DHT con dimensiones "r") viene dada por
con y donde
De manera similar al caso 1-D, como transformación real y simétrica, la MD-DHT es más simple que la MD-DFT. Por un lado, la DHT inversa es idéntica a la transformación directa, con la adición de un factor de escala;
y segundo, dado que el núcleo es real, evita la complejidad computacional de los números complejos . Además, la DFT se puede obtener directamente de la DHT mediante una simple operación aditiva (Bracewell, 1983). [2]
El MD-DHT se utiliza ampliamente en áreas como el procesamiento de imágenes y señales ópticas. Las aplicaciones específicas incluyen visión artificial, televisión de alta definición y teleconferencias, áreas que procesan o analizan imágenes en movimiento (Zeng, 2000). [12]
Algoritmos rápidos para el MD-DHT
A medida que aumenta la velocidad de procesamiento, los problemas multidimensionales más grandes se vuelven factibles computacionalmente, lo que requiere algoritmos multidimensionales rápidos. A continuación, se presentan tres de esos algoritmos.
En busca de la separabilidad para la eficiencia, consideramos la siguiente transformación (Bracewell, 1983), [2]
Bortfeld (1995) [13] demostró que ambos pueden relacionarse mediante algunas adiciones. Por ejemplo, en 3-D,
Para , se pueden implementar algoritmos de fila-columna. Esta técnica se utiliza comúnmente debido a la simplicidad de dichos algoritmos RC, pero no están optimizados para espacios MD generales.
Se han desarrollado otros algoritmos rápidos, como el de base 2, base 4 y base dividida. Por ejemplo, Boussakta (2000) [14] desarrolló el vector de base 3D,
En Boussakta (2000) [14] también se presentó que este algoritmo de base vectorial 3D toma multiplicaciones y sumas en comparación con las multiplicaciones y sumas del enfoque fila-columna. El inconveniente es que la implementación de estos algoritmos de base es difícil de generalizar para señales de dimensiones arbitrarias.
Las transformadas de teoría de números también se han utilizado para resolver la MD-DHT, ya que realizan convoluciones extremadamente rápidas. En Boussakta (1988), [15] se mostró cómo descomponer la transformada MD-DHT en una forma que consta de convoluciones:
Para el caso 2-D (el caso 3-D también está cubierto en la referencia indicada),
,
se puede descomponer en convoluciones circulares 1-D y 2-D de la siguiente manera,
dónde
Desarrollando más,
En este punto presentamos la transformada del número de Fermat (FNT). El t -ésimo número de Fermat está dado por , con . Los números de Fermat bien conocidos son para ( es primo para ), (Boussakta, 1988). [15] La transformada del número de Fermat está dada por
con . y son raíces de unidad de orden y respectivamente .
Volviendo a la descomposición, el último término para se denotará como , entonces
Si y son raíces primitivas de y (cuya existencia está garantizada si y son primos ), entonces y se asignan a . Por lo tanto, al asignar y a y , se obtiene lo siguiente:
donde denota la multiplicación término por término. También se afirmó en (Boussakta, 1988) [15] que este algoritmo reduce el número de multiplicaciones en un factor de 8 a 20 con respecto a otros algoritmos DHT a costa de un ligero aumento en el número de operaciones de desplazamiento y adición, que se supone que son más simples que las multiplicaciones. La desventaja de este algoritmo es la restricción de que cada dimensión de la transformación tiene una raíz primitiva .
Referencias
^ Hartley, Ralph VL (marzo de 1942). "Un análisis de Fourier más simétrico aplicado a problemas de transmisión". Actas del IRE . 30 (3): 144–150. doi :10.1109/JRPROC.1942.234333. S2CID 51644127.
^ Sorensen, Henrik V.; Jones, Douglas L .; Burrus, Charles Sidney ; Heideman, Michael T. (1985). "Sobre el cálculo de la transformada discreta de Hartley". IEEE Transactions on Acoustics, Speech, and Signal Processing . ASSP-33 (4): 1231–1238.
^ Bini, Dario Andrea; Bozzo, Enrico (1993). "Transformada discreta rápida mediante polinomios propios". Computers & Mathematics with Applications . 26 (9): 35–52. doi : 10.1016/0898-1221(93)90004-f .
^ Bracewell, Ronald N. (1995). "Computación con la transformada de Hartley". Computers in Physics . 9 (4): 373–379. Bibcode :1995ComPh...9..373B. doi : 10.1063/1.168534 .
^ Sorensen, Henrik V.; Jones, Douglas L .; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Algoritmos de transformada rápida de Fourier con valores reales". IEEE Transactions on Acoustics, Speech, and Signal Processing . ASSP-35 (6): 849–863.
^ Duhamel, Pierre; Vetterli, Martin (1987). "Algoritmos mejorados de transformada de Fourier y Hartley: aplicación a la convolución cíclica de datos reales". IEEE Transactions on Acoustics, Speech, and Signal Processing . ASSP-35: 818–824.
^ Поповић [Popović], Миодраг [Miodrag] [en serbio] ; Šević, Dragutin (1994). "Una nueva mirada a la comparación de las transformadas rápidas de Hartley y Fourier". Transacciones IEEE sobre procesamiento de señales . 42 (8): 2178–2182. Código bibliográfico : 1994ITSP...42.2178P. doi : 10.1109/78.301854.
^ Frigo, Matteo; Johnson, Steven G. (2005). "El diseño y la implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi :10.1109/jproc.2004.840301. S2CID 6644892. }
^ Chu, Shuni; Burrus, Charles Sidney (1982). "Un algoritmo de factor primo FTT [ sic ] que utiliza aritmética distribuida". IEEE Transactions on Acoustics, Speech, and Signal Processing . 30 (2): 217–227. doi :10.1109/tassp.1982.1163875.
^ Zeng, Yonghang; Bi, Guoan; Leyman, Abdul Rahim (2000). "Algoritmos de transformada polinómica para transformada Hartley discreta multidimensional". Simposio internacional IEEE sobre circuitos y sistemas (V): 517–520.
^ Bortfeld, Thomas; Dinter, Wolfgang (1995). "Cálculo de transformadas de Hartley multidimensionales utilizando transformadas de Fourier unidimensionales". IEEE Transactions on Signal Processing . 43 (5): 1306–1310. Bibcode :1995ITSP...43.1306B. doi :10.1109/78.382424.
^ abc Boussakta, Said; Holt, Alan GJ (1988). "Transformada de Hartley discreta multidimensional rápida utilizando la transformada de números de Fermat". IEE Proceedings G - Circuitos y sistemas electrónicos . 135 (6): 235–237. doi :10.1049/ip-g-1.1988.0036.
Boussakta, Said; Holt, Alan GJ (1988). "Transformada de Hartley discreta multidimensional rápida utilizando la transformada de números de Fermat". IEE Proceedings G - Circuitos y sistemas electrónicos . 135 (6): 235–237. doi :10.1049/ip-g-1.1988.0036.
Hong, Jonathan; Vetterli, Martin ; Duhamel, Pierre (1994). "Transformadas de campo base con la propiedad de convolución" (PDF) . Actas del IEEE . 82 (3): 400–412. doi :10.1109/5.272145.
O'Neill, Mark A. (1988). "Más rápido que Fast Fourier". BYTE . 13 (4): 293–300.
Olnejniczak, Kraig J.; Heydt, Gerald T. (marzo de 1994). "Escaneo de la sección especial sobre la transformada de Hartley". Actas del IEEE . 82 : 372–380.(NB. Contiene bibliografía extensa.)