Transformada discreta de Hartley

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde agosto de 2012)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

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[editar | editar código-fonte]

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

H_k = \sum_{n=0}^{N-1} x_n \left[ \cos \left( \frac{2 \pi}{N} n k \right) + \sin \left( \frac{2 \pi}{N} n k \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[editar | editar código-fonte]

A transformada pode ser interpretada como o produto do vetor (x0, ...., xN-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 xn a partir de Hk. A transformada inversa, como se pode ver, é simplesmente a DHT de Hk 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 xn, a saída DFT Xk tem uma parte real (Hk + HN-k)/2 e uma parte imaginária (HN-k - Hk)/2. Reciprocamente, para obter-se a DHT, basta calcular a DFT de xn, 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 = (xn) e y = (yn), que produz o vetor z = (zn), 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 (XN = X0 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[editar | editar código-fonte]

Da mesma maneira que com a DFT, calcular a DHT directamente a partir da definição possui uma complexidade O(N2) (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[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

  • 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).