# 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$^n$ -> R$^n$ (onde R denota o conjunto dos números reais). A sequência de N valores reais originais x$_0$, ...., x$_{N-1}$ é transformada na sequência de N valores reais H$_0$, ..., 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$_0$, ...., 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$_0$ 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$^2$) (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).