Transformada discreta de Hartley

A transformada discreta de Hartley (DHT) é a versão da transformada de Hartley aplicável a sequências de valores, da mesma forma que a transformada discreta de Fourier (DFT) é a versão da transformada de Fourier para valores discretos periódicos. A DHT é, por conseguinte, uma transformada integral bastante relacionada às transformadas citadas e encontra aplicações similares. A principal vantagem da DHT sobre a DFT é que ela transforma uma sequência de valores reais em outra sequência de valores reais, evitando a necessidade de se trabalhar com números complexos.

Como existe um algoritmo bastante eficiente para cálculo da DHT, a transformada rápida de Hartley (FHT), a DHT foi proposta originalmente por Bracewell em 1983 como uma ferramenta mais eficiente para o tratamento dos casos em que os dados de entrada são puramente reais e periódicos, casos esses muito comuns. Posteriormente, no entanto, descobriu-se que era possível encontrar algoritmos baseados na transformada rápida de Fourier (FFT) um pouco mais eficientes (ver abaixo), o que limitou o uso da DHT.

Sequências de valores aparecem quando funções contínuas são amostradas a determinados intervalos, situação frequente em análise harmônica, estatística e campos relacionados.

Definição

Formalmente, a transformada discreta de Hartley é a função H : Rⁿ -> Rⁿ (onde R denota o conjunto dos números reais). A sequência de N valores reais originais x₀, ...., x_N-1 é transformada na sequência de N valores reais H₀, ..., H_N-1 de acordo com a fórmula

H_{k}=\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

A expressão $\cos(z)+\sin(z)\!$ $={\sqrt {2}}\cos(z-{\frac {\pi }{4}})$ é algumas vezes denotada $\mathrm {cas} (z)\!$ . Contraste-se com a expressão $e^{-iz}=\cos(z)-i\sin(z)\!$ (onde i é a unidade dos números imaginários), que aparece na definição da DFT.

Como acontece com a DFT, o fator de escalamento e o sinal do termo do seno são matéria convencional e, embora variem entre os diversos autores, não afetam as propriedades essenciais da transformada.

Propriedades

A transformada pode ser interpretada como o produto do vetor (x₀, ...., x_N-1) por uma matriz $M$ de dimensões N x N; portanto, a transformada discreta de Hartley é um operador linear. Essa matriz $M$ é inversível; a matriz inversa $M$ ^-1 representa a DHT inversa, que permite recuperar x_n a partir de H_k. A transformada inversa, como se pode ver, é simplesmente a DHT de H_k multiplicada por 1/N. Em outras palavras, a DHT é a inversa de si mesma, a menos de um fator de escalamento, o que em matemática se chama uma involução.

A DHT pode ser usada para computar-se a DFT, e vice versa. Para entradas reais x_n, a saída DFT X_k tem uma parte real (H_k + H_N-k)/2 e uma parte imaginária (H_N-k - H_k)/2. Reciprocamente, para obter-se a DHT, basta calcular a DFT de x_n, multiplicar por 1+i e tomar a parte real.

Da mesma forma que com a DFT, a convolução z = x*y de dois vetores x = (x_n) e y = (y_n), que produz o vetor z = (z_n), todos de comprimento N, transforma-se numa operação muito mais simples após a transformação. Em particular, supondo que os vetores X, Y e Z denotam as DHTs de x, y e z, respectivamente, Z é dado por

{\begin{matrix}Z_{k}&=&\left[X_{k}\left(Y_{k}+Y_{N-k}\right)+X_{N-k}\left(Y_{k}-Y_{N-k}\right)\right]/2\\Z_{N-k}&=&\left[X_{N-k}\left(Y_{k}+Y_{N-k}\right)-X_{k}\left(Y_{k}-Y_{N-k}\right)\right]/2\end{matrix}}

onde assumimos que todos os vetores sejam periódicos em N (X_N = X₀ etc.). Assim, da mesma forma que a DFT transforma uma convolução em um produto ponto a ponto de números complexos, a DHT transforma uma convolução em uma simples combinação de pares de componentes de frequência real. A transformada inversa, então, retorna o vetor desejado z. Dessa forma, um algoritmo rápido para a DHT resulta num algoritmo rápido também para o cálculo de convoluções. Note-se que este é um pouco menos eficiente que o procedimento análogo para a DFT, ainda que não se inclua o custo das transformadas abaixo, porque a operação ponto a ponto acima requer 8 operações com números reais, e a multiplicação de dois números complexos, apenas 6. Essa conta não inclui a divisão por dois, que pode ser absorvida, por exemplo, na normalização 1/N da DHT inversa.

Algoritmos rápidos

Da mesma maneira que com a DFT, calcular a DHT directamente a partir da definição possui uma complexidade O(N²) (ver notação Grande-O). Existem algoritmos rápidos similares à FFT, contudo, que computam o resultado com complexidade O(N log N). Quase todos os algoritmos de FFT (e.g. o algoritmo de Cooley-Tukey, o algoritmo dos fatores primos, o algortimo de Winograd e o algoritmo de Bruun) possuem um análogo para a transformada discreta de Hartley. Apenas alguns mais exóticos, como a QFT, não foram ainda investigados no contexto da DHT.

Em particular, o algoritmo rápido para a DHT baseado no algoritmo de Cooley-Tukey é comumente chamado de Fast Hartley Transform (FHT), e foi descrito primeiramente por Bracewell em 1984. Esse algoritmo, pelo menos quando aplicado a sequências de comprimento N, sendo N uma potência de 2, recebeu a patente número 4.646.256 nos Estados Unidos em 1987, e colocado em domínio público em 1994 (Bracewell, 1995).

Como mencionado acima, algoritmos para cálculo da DHT são ligeiramente menos eficientes, em termos de custo de operações com números reais, que o algoritmo FFT/DFT correspondente, quando este é otimizado para tratar entradas e saídas reais. Isso foi demonstrado primeiramente por Sorensen et al. (1987) e Duhamel & Vetterli (1987). Estes últimos obtiveram o que parece ser o menor custo conhecido para cálculo da DHT para sequências de comprimento N, sendo N uma potência de 2, através do emprego de um algoritmo baseado no algoritmo de raízes separadas, que quebra uma DHT em uma outra DHT de comprimento N/2 e mais duas DFTs de cvomprimento N/4. Por isso eles defenderam que uma DHT pode ser computada com, no melhor caso, 2 adições a mais que a DFT correspondente. Nos computadores atuais (2006), o desempenho é determinado predominantemente pelos tamanhos e tecnologias de cache e pipeline das CPUs do que pelo número de operações envolvidas, e uma pequena diferença no custo aritmético seria provavelmente irrelevante. Como a FHT e os algoritmos FFT têm estruturas computacionais similares, nenhum parece exibir uma vantagem substancial a priori sobre os demais (Popović & Šević, 1994). Em casos práticos, bibliotecas para cálculo da FFT, otimizadas para entradas reais, estão disponíveis a partir de diversas fontes (e.g. da Intel), ao passo que bibliotecas otimizadas para cálculo da DHT são menos comuns.

Por outro lado, as operações redundantes nas FFTs devido a entradas reais são difíceis de eliminar para grandes valores primos de N, a despeito da existência de algoritmos de complexidade O(N log N) para tais casos, porque essas redundâncias estão ocultas atrás de intrincadas permutações e/ou rotações de fase nesses algoritmos. Em contraste, um algoritmo padrão de FFT, o algoritmo de Rader, pode ser diretamente aplicado à DHT, resultando em cerca de duas operações a menos que a FFT correspondente (Frigo & Johnson, 2005). Entretanto, uma adaptação do algoritmo de Rader para calcular DFTs de sequências reais também é possível (Chu & Burrus, 1982).

Ver também

Bibliografia

R. N. Bracewell, "Discrete Hartley transform," J. Opt. Soc. Am. 73 (12), 1832–1835 (1983).
R. N. Bracewell, "The fast Hartley transform," Proc. IEEE 72 (8), 1010–1018 (1984).
R. N. Bracewell, The Hartley Transform (Oxford Univ. Press, New York, 1986).
R. N. Bracewell, "Computing with the Hartley Transform," Computers in Physics 9 (4), 373–379 (1995).
R. V. L. Hartley, "A more symmetrical Fourier analysis applied to transmission problems," Proc. IRE 30, 144–150 (1942).
H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman, "On computing the discrete Hartley transform," IEEE Trans. Acoust. Speech Sig. Processing ASSP-33 (4), 1231–1238 (1985).
H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35 (6), 849–863 (1987).
Pierre Duhamel and Martin Vetterli, "Improved Fourier and Hartley transform algorithms: application to cyclic convolution of real data," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35, 818–824 (1987).
Mark A. O'Neill, "Faster than Fast Fourier", Byte 13(4):293-300, (1988).
J. Hong and M. Vetterli and P. Duhamel, "Basefield transforms with the convolution property," Proc. IEEE 82 (3), 400-412 (1994).
D. A. Bini and E. Bozzo, "Fast discrete transform by means of eigenpolynomials," Computers & Mathematics (with Applications) 26 (9), 35–52 (1993).
Miodrag Popović and Dragutin Šević, "A new look at the comparison of the fast Hartley and Fourier transforms," IEEE Trans. Signal Processing 42 (8), 2178-2182 (1994).
Matteo Frigo and Steven G. Johnson, "The Design and Implementation of FFTW3," Proc. IEEE 93 (2), 216–231 (2005).
S. Chu and C. Burrus, "A prime factor FTT [sic] algorithm using distributed arithmetic," IEEE Transactions on Acoustics, Speech, and Signal Processing 30 (2), 217–227 (1982).