Transformada de Hartley discreta

Una transformada de Hartley discreta (DHT) és una transformada relacionada amb Fourier de dades discretes i periòdiques similars a la transformada discreta de Fourier (DFT), amb aplicacions anàlogues en el processament de senyals i camps relacionats. La seva principal distinció amb la DFT és que transforma les entrades reals en sortides reals, sense implicació intrínseca de nombres complexos. De la mateixa manera que la DFT és l'anàleg discret de la transformada contínua de Fourier (FT), la DHT és l'analògic discret de la transformada contínua de Hartley (HT), introduïda per Ralph VL Hartley el 1942.

Com que hi ha algorismes ràpids per al DHT anàlegs a la transformada ràpida de Fourier (FFT), el DHT va ser proposat originalment per Ronald N. Bracewell el 1983 com una eina computacional més eficient en el cas comú on les dades són purament reals. Posteriorment, es va argumentar, però, que normalment es poden trobar algorismes FFT especialitzats per a entrades o sortides reals amb una mica menys d'operacions que qualsevol algorisme corresponent per al DHT.

Definició

Formalment, la transformada de Hartley discreta és una funció lineal invertible H: Rⁿ → Rⁿ (on R denota el conjunt de nombres reals). Els N nombres reals x₀, ..., x_N−1 es transformen en els N nombres reals H₀, . . ., H_{N −1} segons la fórmula

$H_{k}=\sum _{n=0}^{N-1}x_{n}\operatorname {cas} \left({\frac {2\pi }{N}}nk\right)=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}nk\right)+\sin \left({\frac {2\pi }{N}}nk\right)\right]\quad \quad k=0,\dots ,N-1.$

La combinació $\cos(z)+\sin(z)$$={\sqrt {2}}\cos \left(z-{\frac {\pi }{4}}\right)$ De vegades es denota cas(z) i no s'ha de confondre amb cis(z) = e^iz = cos(z) + i sin(z), o e^−iz = cis(−z) que apareix a la definició DFT (on i és la unitat imaginària).

Igual que amb la DFT, el factor d'escala general davant de la transformada i el signe del terme sinus són una qüestió de convenció. Tot i que aquestes convencions varien de tant en tant entre autors, no afecten les propietats essencials de la transformació.

Algoritmes ràpids

Igual que per a la DFT, avaluar directament la definició de DHT requeriria operacions aritmètiques O(N²) (vegeu la notació Big O). Hi ha algorismes ràpids similars a la FFT, però, que calculen el mateix resultat només en operacions O(N log N). Gairebé tots els algorismes FFT, des de Cooley–Tukey fins al factor primer fins a Winograd (1985) fins al de Bruun (1993), tenen un anàleg directe per a la transformada de Hartley discreta. (No obstant això, alguns dels algorismes FFT més exòtics, com ara el QFT, encara no s'han investigat en el context del DHT).

En particular, l'anàleg DHT de l'algorisme de Cooley-Tukey es coneix comunament com l'algoritme de transformada ràpida de Hartley (FHT), i va ser descrit per primera vegada per Bracewell el 1984. Aquest algorisme FHT, almenys quan s'aplica a la potència de dues mides N, és objecte de la patent dels Estats Units número 4.646.256, emesa el 1987 a la Universitat de Stanford. Stanford va col·locar aquesta patent en el domini públic el 1994 (Bracewell, 1995).