stringtranslate.com

Transformada de Hartley discreta

Una transformada discreta de Hartley (DHT) es una transformada relacionada con Fourier de datos periódicos discretos similar a la transformada discreta de Fourier (DFT), con aplicaciones análogas en el procesamiento de señales y campos relacionados. Su principal diferencia 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 continua de Fourier (FT), la DHT es el análogo discreto de la transformada continua de Hartley (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 normalmente se pueden encontrar con un número ligeramente menor de operaciones que cualquier algoritmo correspondiente para DHT.

Definición

Formalmente, la transformada de Hartley discreta es una función lineal e invertible H : R nR 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 el DFT definición (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 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 permite recuperar x n de 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.

El DHT se puede utilizar para calcular el DFT y viceversa. Para 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−kH k )/2. Por el contrario, la DHT equivale 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 = xy 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 el 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 vienen dados por:

donde tomamos que todos los vectores son 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 produce entonces el vector z deseado . De esta manera, un algoritmo rápido para DHT (ver más abajo) produce un algoritmo rápido para convolución. (Esto es un poco más costoso que el procedimiento correspondiente para la DFT, sin incluir los costos de las transformadas siguientes, 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 conteo no incluye el división por 2, que puede absorberse, 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 ) (ver notación O grande ). 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 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 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 potencia de- dos tamaños N , es objeto de la patente estadounidense número 4.646.256, concedida 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 de número de operaciones de punto flotante ) que el algoritmo DFT (FFT) correspondiente especializado para entradas (o salidas) reales. Esto fue argumentado por primera vez por Sorensen et al. (1987) [7] y Duhamel y Vetterli (1987). [8] Estos últimos autores obtuvieron lo que parece ser el recuento de operaciones más bajo publicado para el DHT de potencia de dos tamaños, 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 una DHT de longitud de potencia de dos se puede calcular con, en el mejor de los casos, 2 sumas más que el número correspondiente de operaciones aritméticas para la DFT de entrada real.

En las computadoras actuales, el rendimiento está determinado más por consideraciones de caché y 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 sustancial en velocidad a priori (Popović  [sr] y Šević, 1994). [9] Como cuestión práctica, las bibliotecas FFT de entrada real altamente optimizadas están disponibles en 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 debidos 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 permutaciones intrincadas. y/o rotaciones de fase en esos algoritmos. Por el contrario, un algoritmo FFT estándar de tamaño primo, el algoritmo de Rader , se puede aplicar directamente a la DHT de datos reales por aproximadamente un factor de dos menos de cálculo 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 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 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 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 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 el MD-DHT

A medida que la velocidad informática sigue aumentando, los problemas multidimensionales más grandes se vuelven computacionalmente factibles, lo que requiere la necesidad de algoritmos multidimensionales rápidos. A continuación se presentan tres de estos algoritmos.

En busca de la separabilidad para la eficiencia, consideramos la siguiente transformada (Bracewell, 1983), [2]

Bortfeld (1995) [13] demostró que ambos pueden estar relacionados mediante algunas adiciones. Por ejemplo, en 3D,

Para , luego se pueden implementar algoritmos de fila-columna. Esta técnica se usa 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 radix-2, radix-4 y split radix. Por ejemplo, Boussakta (2000) [14] desarrolló la base vectorial tridimensional,

También se presentó en Boussakta (2000) [14] que este algoritmo de base vectorial 3D toma multiplicaciones y sumas en comparación con multiplicaciones y sumas 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 transformadas de teoría de números también se han utilizado para resolver 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 viene dado por , con . Los conocidos números de Fermat son para ( es primo para ), (Boussakta, 1988). [15] La transformada del número de Fermat viene dada por

con . y son raíces de unidad de orden y respectivamente .

Volviendo a la descomposición, el último término de se denotará como , entonces

Si y son raíces primitivas de y (que se garantiza que existen si y son primos ), entonces y se asigna a Entonces, al asignar y a y , se obtiene lo siguiente,

.

Que ahora es una convolución circular . Con , , y , se tiene

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

  1. ^ 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.
  2. ^ abc Bracewell, Ronald N. (1983). "Transformación discreta de Hartley". Revista de la Sociedad Óptica de América . 73 (12): 1832–1835. doi :10.1364/josa.73.001832. S2CID  120611904.
  3. ^ 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, voz y procesamiento de señales . ASSP-33 (4): 1231–1238.
  4. ^ Bini, Darío Andrea; Bozzo, Enrico (1993). "Transformación discreta rápida mediante polinomios propios". Computadoras y Matemáticas con Aplicaciones . 26 (9): 35–52. doi : 10.1016/0898-1221(93)90004-f .
  5. ^ Bracewell, Ronald N. (1984). "La rápida transformación de Hartley". Actas del IEEE . 72 (8): 1010–1018. doi :10.1109/proc.1984.12968. S2CID  21988816.
  6. ^ Bracewell, Ronald N. (1995). "Computación con la transformada de Hartley". Computadoras en Física . 9 (4): 373–379. Código Bib : 1995ComPh...9..373B. doi : 10.1063/1.168534 .
  7. ^ 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, voz y procesamiento de señales . ASSP-35 (6): 849–863.
  8. ^ Duhamel, Pedro; Vetterli, Martín (1987). "Algoritmos mejorados de transformada de Fourier y Hartley: aplicación a la convolución cíclica de datos reales". Transacciones IEEE sobre acústica, voz y procesamiento de señales . ASSP-35: 818–824.
  9. ^ Поповић [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.
  10. ^ Frigo, Mateo; 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. }
  11. ^ Chu, Shuni; Burrus, Charles Sidney (1982). "Un algoritmo FTT [ sic ] de factor primo que utiliza aritmética distribuida". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 30 (2): 217–227. doi :10.1109/tassp.1982.1163875.
  12. ^ Zeng, Yonghang; Bi, Guoan; Leyman, Abdul Rahim (2000). "Algoritmos de transformación polinómica para transformada de Hartley discreta multidimensional". Simposio internacional IEEE sobre circuitos y sistemas (V): 517–520.
  13. ^ Bortfeld, Thomas; Dinter, Wolfgang (1995). "Cálculo de transformadas de Hartley multidimensionales mediante 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.
  14. ^ ab 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.
  15. ^ abc Boussakta, dijo; Holt, Alan GJ (1988). "Transformada de Hartley discreta multidimensional rápida utilizando la transformación de números de Fermat". Actas IEE G - Circuitos y sistemas electrónicos . 135 (6): 235–237. doi :10.1049/ip-g-1.1988.0036.

Lectura adicional