Una transformada discreta de Hartley (DHT) es una transformada relacionada con Fourier de datos discretos y periódicos similar a la transformada discreta de Fourier (DFT), con aplicaciones análogas en el procesamiento de señales y campos relacionados. Su principal distinción con la DFT es que transforma las 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]
Debido a 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 donde 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 el DHT.
Definición
Formalmente, el discreto Hartley transformada es una lineal, invertible función H : R n → R n (donde R denota el conjunto de números reales ). Los N números reales x 0 , ..., x N −1 se transforman en los N números reales H 0 , ..., H N −1 según la fórmula
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 frente a la transformada y el signo del término seno son una cuestión de convención. Aunque estas convenciones varían ocasionalmente entre los autores, no afectan las propiedades esenciales de la transformación.
Propiedades
La transformada se puede interpretar 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 le permite a uno para recuperar el x n de la H k , es simplemente el DHT de H k multiplicada por 1 / N . Es decir, la DHT es su propia inversa ( involutiva ), hasta un factor de escala general.
El DHT se puede utilizar para calcular el DFT y viceversa. Para las entradas reales x n , la salida 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 , luego tomando 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 el DHT. En particular, suponga que los vectores X , Y y Z denotan la DHT de x , y y z respectivamente. Entonces los elementos de Z vienen dados por:
donde tomamos todos los vectores como periódicos en N ( X N = X 0 , etcétera). Así, así como 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 entonces produce el vector z deseado . De esta manera, un algoritmo rápido para el DHT (ver más abajo) produce un algoritmo rápido para la convolución. (Esto es un poco más caro que el procedimiento correspondiente para la DFT, sin incluir los costos de las transformadas a continuación, porque la operación por pares anterior requiere 8 operaciones aritméticas reales en comparación con el 6 de una multiplicación compleja. Este recuento no incluye el división por 2, que se puede absorber, 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 operaciones aritméticas O ( N 2 ) (vea la notación Big O ). Sin embargo, existen algoritmos rápidos similares a la FFT que calculan el mismo resultado solo en operaciones O ( N log N ). Casi todos los algoritmos FFT, desde Cooley-Tukey hasta el factor primo, 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 el QFT, aún no se han investigado en el contexto del 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 la potencia de dos tamaños N , es objeto de la patente estadounidense número 4.646.256, expedida 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 suelen ser ligeramente menos eficientes (en términos del número 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 y Vetterli (1987). [8] Los últimos autores obtuvieron lo que parece ser el recuento de operaciones más bajo publicado para la DHT de potencia de dos tamaños, empleando un algoritmo de base dividida (similar a la FFT de base dividida ) que divide una 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 una DHT de potencia de dos de longitud se puede calcular con, en el mejor de los casos, 2 adiciones más que el número correspondiente de operaciones aritméticas para la DFT de entrada real.
En las computadoras actuales, el rendimiento se determina más por consideraciones de canalización de CPU y caché que por recuentos estrictos de operaciones, y es poco probable que una pequeña 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ć 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 otro lado, los cálculos redundantes en FFT debido a entradas reales son más difíciles de eliminar para N primos grandes , 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 intrincadas permutaciones. y / o rotaciones de fase en esos algoritmos. En contraste, un algoritmo estándar de FFT de tamaño principal, el algoritmo de Rader , se puede aplicar directamente a la DHT de datos reales por aproximadamente un factor de dos cálculos menos que el de la FFT compleja equivalente (Frigo y Johnson, 2005). [10] Por otro lado, 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]
Transformada de Hartley discreta multidimensional (MD-DHT)
El rD-DHT (MD-DHT con dimensiones "r") viene dado por
con y donde
Similar al caso 1-D, como una transformación real y simétrica, el MD-DHT es más simple que el MD-DFT. Por un lado, la DHT inversa es idéntica a la transformada 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 usa ampliamente en áreas como el procesamiento de imágenes y señales ópticas. Las aplicaciones específicas incluyen visión por computadora, televisión de alta definición y teleconferencias, áreas que procesan o analizan imágenes en movimiento (Zeng, 2000). [12]
Algoritmos rápidos para MD-DHT
A medida que la velocidad de la computación sigue aumentando, los problemas multidimensionales más grandes se vuelven factibles computacionalmente, lo que requiere la necesidad de algoritmos multidimensionales rápidos. Siguen tres de esos algoritmos.
En la búsqueda de la separabilidad para la eficiencia, consideramos la siguiente transformada (Bracewell, 1983), [2]
En Bortfeld (1995), [13] se demostró que los dos pueden relacionarse mediante algunas adiciones. Por ejemplo, en 3-D,
Para , entonces se pueden implementar algoritmos de fila-columna. Esta técnica se usa comúnmente debido a la simplicidad de tales algoritmos RC, pero no están optimizados para espacios MD generales.
Se han desarrollado otros algoritmos rápidos, como radix-2, radix-4 y split radix. Por ejemplo, Boussakta (2000) [14] desarrolló la base del vector 3-D,
También se presentó en Boussakta (2000) [14] que este algoritmo de base de vectores 3D toma multiplicaciones y adiciones en comparación con multiplicaciones y adiciones del enfoque fila-columna. El inconveniente es que la implementación de estos algoritmos de tipo base es difícil de generalizar para señales de dimensiones arbitrarias.
Las transformaciones teóricas de números también se han utilizado para resolver el MD-DHT, ya que realizan convoluciones extremadamente rápidas. En Boussakta (1988), [15] se mostró cómo descomponer la transformación MD-DHT en una forma que consta de convoluciones:
Para el caso 2-D (el caso 3-D también se cubre 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 viene dado por, con . Los conocidos números de Fermat son para ( es primordial 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 será denotado como , luego
Si y son raíces primitivas de y (que se garantiza que existen si y son primos ) entonces y mapa a Entonces, mapeo y a y , uno obtiene lo siguiente,
.
Que ahora es una circunvolución circular . Con, , y , uno tiene
dónde denota 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-20 sobre otros algoritmos DHT a costa de un ligero aumento en el número de operaciones de cambio y suma, que son se supone que es más simple que las multiplicaciones. El inconveniente 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 de la IRE . 30 (3): 144-150. doi : 10.1109 / JRPROC.1942.234333 .
- ^ a b c Bracewell, Ronald N. (1983). "Transformada discreta de Hartley". Revista de la Optical Society of America . 73 (12): 1832–1835. doi : 10.1364 / josa.73.001832 .
- ^ Sorensen, Henrik V .; Jones, Douglas L .; Burrus, Charles Sidney ; Heideman, Michael T. (1985). "Sobre el cálculo de la transformada discreta de Hartley". Transacciones IEEE sobre acústica, habla y procesamiento de señales . ASSP-33 (4): 1231–1238.
- ^ Bini, Dario Andrea; Bozzo, Enrico (1993). "Transformada rápida discreta mediante autopolinomios". Computadoras y Matemáticas (con Aplicaciones) . 26 (9): 35–52. doi : 10.1016 / 0898-1221 (93) 90004-f .
- ^ Bracewell, Ronald N. (1984). "La Transformada Rápida de Hartley". Actas del IEEE . 72 (8): 1010–1018. doi : 10.1109 / proc.1984.12968 .
- ^ Bracewell, Ronald N. (1995). "Computación con la Transformada de Hartley" . Computadoras en Física . 9 (4): 373–379. Código Bibliográfico : 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 de valor real". Transacciones IEEE sobre acústica, habla y procesamiento de señales . ASSP-35 (6): 849–863.
- ^ Duhamel, Pierre; Vetterli, Martin (1987). "Mejora de los algoritmos de transformación de Fourier y Hartley: aplicación a la convolución cíclica de datos reales". Transacciones IEEE sobre acústica, habla y procesamiento de señales . ASSP-35: 818–824.
- ^ Поповић [Popović], Миодраг [Miodrag] ; Š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 e Implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi : 10.1109 / jproc.2004.840301 .}
- ^ Chu, Shuni; Burrus, Charles Sidney (1982). "Un algoritmo de factor primo FTT [ sic ] utilizando aritmética distribuida". Transacciones IEEE sobre acústica, habla y procesamiento de señales . 30 (2): 217–227. doi : 10.1109 / tassp.1982.1163875 .
- ^ Zeng, Yonghang; Bi, Guoan; Leyman, Abdul Rahim (2000). "Algoritmos de transformación polinomial para la transformada de Hartley discreta multidimensional". Simposio internacional de 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". Transacciones IEEE sobre procesamiento de señales . 43 (5): 1306-1310. Código bibliográfico : 1995ITSP ... 43.1306B . doi : 10.1109 / 78.382424 .
- ^ a b Boussakta, dijo; Alshibami, Osama (2000). "Algoritmo rápido para la transformada Hartley discreta 3-D". Conferencia internacional sobre acústica, habla y procesamiento de señales '00 (4): 2302–2305.
- ^ a b c Boussakta, dijo; Holt, Alan GJ (1988). "Transformada de Hartley discreta multidimensional rápida usando la transformación de número de Fermat". Actas de la IEE G - Circuitos y sistemas electrónicos . 135 (6): 235–237. doi : 10.1049 / ip-g-1.1988.0036 .
Otras lecturas
- Bracewell, Ronald N. (1986). La Transformada de Hartley (1 ed.). Prensa de la Universidad de Oxford . ISBN 978-0-19503969-6.
- Boussakta, dijo; Holt, Alan GJ (1988). "Transformada de Hartley discreta multidimensional rápida usando la transformación de número de Fermat". Actas de la IEE 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). "Basefield se transforma 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 el rápido Fourier". BYTE . 13 (4): 293–300.
- Olnejniczak, Kraig J .; Heydt, Gerald T. (marzo de 1994). "Escaneo de la sección especial sobre la transformación de Hartley". Actas del IEEE . 82 : 372–380. (NB. Contiene una extensa bibliografía).