Uma transformada discreta de Hartley (DHT) é uma transformada matemática relacionada à de Fourier para dados discretos e periódicos semelhante à transformada discreta de Fourier (DFT), com aplicações análogas no processamento de sinais e campos relacionados. A sua principal diferença em relação à DFT é que transforma entradas reais em saídas reais, sem o envolvimento intrínseco de números complexos. Assim como a DFT é o análogo discreto da transformada contínua de Fourier (FT), a DHT é o análogo discreto da transformada contínua de Hartley (HT), introduzida por Ralph V. L. Hartley em 1942.

Dado que existem algoritmos rápidos para a DHT análogos à transformada rápida de Fourier (FFT), a DHT foi originalmente proposta por Ronald N. Bracewell em 1983 como uma ferramenta computacional mais eficiente no caso comum em que os dados são puramente reais. Posteriormente, no entanto, argumentou-se que algoritmos de FFT especializados para entradas ou saídas reais podem normalmente ser encontrados com um número ligeiramente menor de operações do que qualquer algoritmo correspondente para a DHT.

Definição

Formalmente, a transformada discreta de Hartley é uma função linear e invertível (onde denota o conjunto dos números reais). Os números reais são transformados nos números reais de acordo com a fórmula:

A combinação é por vezes denotada como , e não deve ser confundida com , ou , que aparece na definição da DFT (onde é a unidade imaginária).

Assim como na DFT, o fator de escala global à frente da transformada e o sinal do termo do seno são uma questão de convenção. Embora estas convenções variem ocasionalmente entre os autores, não afetam as propriedades essenciais da transformada.

Propriedades A transformada pode ser interpretada como a multiplicação do vetor por uma matriz ; portanto, a transformada discreta de Hartley é um operador linear. A matriz é invertível; a transformação inversa, que permite recuperar os a partir dos , é simplesmente a DHT de multiplicada por . Ou seja, a DHT é a sua própria inversa (involutória), a menos de um fator de escala global.

A DHT pode ser usada para calcular a DFT, e vice-versa. Para entradas reais , a saída da DFT possui uma parte real e uma parte imaginária . Inversamente, a DHT é equivalente a calcular a DFT de multiplicada por , tomando depois a parte real do resultado.

À semelhança da DFT, uma convolução cíclica de dois vetores e para produzir um vetor , todos de comprimento , torna-se numa operação simples após a DHT. Em particular, suponha que os vetores , e denotam a DHT de , e respetivamente. Então, os elementos de são dados por:

onde assumimos que todos os vetores são periódicos em (, etc.). Assim, do mesmo modo que a DFT transforma uma convolução numa multiplicação ponto a ponto de números complexos (pares de partes reais e imaginárias), a DHT transforma uma convolução numa combinação simples de pares de componentes de frequência reais. A DHT inversa produz então o vetor desejado. Desta forma, um algoritmo rápido para a DHT (ver abaixo) proporciona um algoritmo rápido para a convolução. (Isto é ligeiramente mais custoso que o procedimento correspondente para a DFT, não incluindo os custos das transformadas abaixo, porque a operação em pares acima requer 8 operações aritméticas reais em comparação com as 6 de uma multiplicação complexa. Esta contagem não inclui a divisão por 2, que pode ser absorvida, por exemplo, na normalização de da DHT inversa.)

Algoritmos rápidos Tal como para a DFT, avaliar diretamente a definição da DHT exigiria operações aritméticas (ver Notação Grande-O). No entanto, existem algoritmos rápidos semelhantes à FFT que calculam o mesmo resultado em apenas operações. Quase todos os algoritmos FFT, desde o de Cooley-Tukey ao de fatores primos, passando pelos de Winograd (1985) e Bruun (1993), possuem um análogo direto para a transformada discreta de Hartley. (No entanto, alguns dos algoritmos FFT mais exóticos, como a QFT, ainda não foram investigados no contexto da DHT.)

Em particular, o análogo do algoritmo de Cooley-Tukey para a DHT é habitualmente conhecido como o algoritmo da transformada rápida de Hartley (FHT), e foi descrito pela primeira vez por Bracewell em 1984. Este algoritmo FHT, pelo menos quando aplicado a tamanhos que sejam potências de dois, é objeto da patente número 4.646.256 dos Estados Unidos, concedida em 1987 à Universidade Stanford. A Universidade de Stanford colocou esta patente no domínio público em 1994 (Bracewell, 1995).

Conforme mencionado acima, os algoritmos DHT são tipicamente um pouco menos eficientes (em termos do número de operações de vírgula flutuante) do que o algoritmo DFT correspondente (FFT) especializado para entradas (ou saídas) reais. Isto foi argumentado pela primeira vez por Sorensen et al. (1987) e Duhamel & Vetterli (1987). Estes últimos autores obtiveram o que parece ser a contagem de operações mais baixa publicada para a DHT de tamanhos potência de dois, empregando um algoritmo split-radix (divisão de base, análogo à FFT split-radix) que divide uma DHT de comprimento numa DHT de comprimento e duas DFTs de entrada real (não DHTs) de comprimento . Deste modo, argumentaram que uma DHT com comprimento potência de dois pode ser calculada com, na melhor das hipóteses, mais 2 adições do que o número correspondente de operações aritméticas para a DFT de entrada real.

Nos computadores atuais, o desempenho é determinado mais por questões de cache e de pipeline do processador do que por contagens estritas de operações, e é improvável que uma ligeira diferença no custo aritmético seja significativa. Como os algoritmos de FHT e os algoritmos de FFT de entrada real possuem estruturas computacionais semelhantes, nenhum parece ter uma vantagem de velocidade a priori substancial (Popović e Šević, 1994). Na prática, bibliotecas de FFT para entradas reais altamente otimizadas estão disponíveis a partir de várias fontes (ex. de fabricantes de CPUs como a Intel), ao passo que bibliotecas DHT altamente otimizadas são menos comuns.

Por outro lado, as computações redundantes nas FFTs devidas a entradas reais são mais difíceis de eliminar para primos grandes, apesar de existirem algoritmos de para dados complexos em tais casos, porque as redundâncias encontram-se ocultas atrás de intrincadas permutações e/ou rotações de fase nesses algoritmos. Em contraste, um algoritmo FFT de tamanho primo padrão, o algoritmo de Rader, pode ser diretamente aplicado à DHT de dados reais exigindo aproximadamente metade da computação em comparação com a FFT complexa equivalente (Frigo e Johnson, 2005). Alternativamente, uma adaptação não baseada na DHT do algoritmo de Rader para DFTs de entrada real também é possível (Chu & Burrus, 1982).

Transformada Discreta de Hartley Multidimensional (MD-DHT) A rD-DHT (MD-DHT com "r" dimensões) é dada por

com e onde

De forma semelhante ao caso 1-D, como uma transformada real e simétrica, a MD-DHT é mais simples do que a MD-DFT. Em primeiro lugar, a DHT inversa é idêntica à transformada direta, com a adição de um fator de escala; centre|frameless|400x400px e, em segundo lugar, como o núcleo é real, evita a complexidade computacional inerente aos números complexos. Adicionalmente, a DFT pode ser obtida diretamente da DHT através de uma simples operação aditiva (Bracewell, 1983).

A MD-DHT é amplamente utilizada em áreas como processamento de imagem e sinais óticos. Aplicações específicas incluem a visão computacional, televisão de alta definição e teleconferência, áreas que processam ou analisam imagens em movimento (Zeng, 2000).

Algoritmos rápidos para a MD-DHT À medida que a velocidade de computação continua a aumentar, problemas multidimensionais de maior escala tornam-se computacionalmente viáveis, exigindo a necessidade de algoritmos multidimensionais rápidos. Abaixo, apresentam-se três destes algoritmos.

Em busca de separabilidade para obtenção de eficiência, considera-se a seguinte transformada (Bracewell, 1983):

Foi demonstrado em Bortfeld (1995) que as duas podem ser relacionadas através de algumas adições. Por exemplo, em 3-D,

Para , podem então ser implementados algoritmos linha-coluna (R-C). Esta técnica é habitualmente utilizada devido à simplicidade dos algoritmos R-C, mas não estão otimizados para espaços multidimensionais (M-D) de uma forma geral.

Outros algoritmos rápidos foram desenvolvidos, tais como os algoritmos de base 2, base 4 e split-radix. Por exemplo, Boussakta (2000) desenvolveu a base vetorial 3-D,

Foi também exposto em Boussakta (2000) que este algoritmo de base vetorial 3D requer multiplicações e adições, comparado com as multiplicações e adições da abordagem linha-coluna. A desvantagem é que a implementação deste tipo de algoritmos baseados em decomposição de raízes é difícil de generalizar para sinais de dimensões arbitrárias.

Também foram utilizadas transformadas teóricas dos números para resolver a MD-DHT, uma vez que estas executam convoluções extremamente rápidas. Em Boussakta (1988), foi demonstrado como decompor a transformada MD-DHT numa forma que consiste em convoluções:

Para o caso 2-D (o caso 3-D também é coberto na referida referência),

,

pode ser decomposto em convoluções circulares 1-D e 2-D da seguinte forma:

onde

Desenvolvendo ainda ,

Neste momento, introduzimos a transformada de números de Fermat (FNT). O t-ésimo Número de Fermat é dado por , com . Os números de Fermat bem conhecidos são para ( é primo para ), (Boussakta, 1988). A transformada de números de Fermat é dada por:

com . e são raízes da unidade de ordem e respetivamente .

Voltando à decomposição, o último termo para será denotado como , de modo que

Se e forem raízes primitivas de e (que se garante existirem caso e sejam primos), então e mapeiam em Logo, ao mapear e em e , obtém-se o seguinte:

Isto agora é uma convolução circular. Com , , e , obtém-se:

onde denota a multiplicação termo a termo. Foi ainda mencionado em (Boussakta, 1988) que este algoritmo diminui o número de multiplicações por um fator entre 8 e 20 em relação a outros algoritmos DHT, mediante o ligeiro aumento no número de operações de deslocamento e adição, as quais são tidas como mais simples computacionalmente que as multiplicações. A principal desvantagem deste algoritmo é a restrição de que cada dimensão da transformada tem de possuir uma raiz primitiva.

Referências

Leitura adicional

(Nota: Contém uma vasta bibliografia.)

Categoria:Transformadas discretas Categoria:Análise de Fourier