Transformada discreta de Hartley – Wikipédia, a enciclopédia livre

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Agosto de 2012)

 Nota: Este artigo é sobre a transformada discreta de Hartley. Para outros usos da sigla DHT, veja DHT.

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.

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

${\displaystyle 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 ${\displaystyle \cos(z)+\sin(z)\!}$ ${\displaystyle ={\sqrt {2}}\cos(z-{\frac {\pi }{4}})}$ é algumas vezes denotada ${\displaystyle \mathrm {cas} (z)\!}$. Contraste-se com a expressão ${\displaystyle 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.

A transformada pode ser interpretada como o produto do vetor (x₀, ...., x_N-1) por uma matriz ${\displaystyle M}$ de dimensões N x N; portanto, a transformada discreta de Hartley é um operador linear. Essa matriz ${\displaystyle M}$ é inversível; a matriz inversa ${\displaystyle 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

${\displaystyle {\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.

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