Transformada de Fourier Discreta

24

3

Transformada de Fourier Discreta
Cl´assica

A DFT desempenha papel fundamental em diversos campos da ciˆencia, como o processamento digital de sinais, a resolu¸c˜ao de equa¸c˜oes diferenciais parciais, bem como a multiplica¸c˜ao r´apida de polinˆomios e inteiros grandes. Por muitos anos, entretanto, pensou-se que a DFT exigisse O(N 2 ) opera¸c˜oes, onde N ´e o n´ umero de pontos do vetor de entrada. Esta id´eia parecia ´obvia, j´a que a Transformada de
Fourier pode ser vista como uma multiplica¸c˜ao de uma matriz N × N por um vetor.
A situa¸c˜ao mudou dr´asticamente quando Cooley e Tukey (1965) descreveram um algoritmo para c´alculo da DFT que realizava apenas O(N log N ) opera¸c˜oes. A este algoritmo, bem como `as suas variantes, d´a-se o nome de Transformada de Fourier
R´apida (FFT). O trabalho de Cooley e Tukey, apesar de revolucion´ario, foi na verdade uma redescoberta de resultados anteriores, os quais curiosamente n˜ao chamaram a aten¸c˜ao da comunidade cient´ıfica. De fato, apenas um ano ap´os a publica¸c˜ao do artigo de Cooley e Tukey, Rudnick (1966) j´a apresentava um programa de computador para o c´alculo da DFT, tamb´em de complexidade O(N log N ), baseando-se em um m´etodo desenvolvido anteriormente por Danielson e Lanczos (1942). O trabalho de Danielson e Lanczos, por sua vez, baseava-se em trabalhos anteriores de
Runge (1903, 1905). At´e mesmo Gauss, no in´ıcio do s´eculo XIX, j´a havia descoberto um m´etodo eficiente para c´alculo de DFT em um caso particular.
Informa¸c˜oes hist´oricas mais detalhadas podem ser encontradas a partir do artigo de Cooley, Lewis e Welch (1967).

3.1 A transformada exata

3.1

25

A transformada exata

Defini¸ c˜ ao 3.1. As N -´esimas ra´ızes complexas da unidade s˜ao os n´ umeros complexos k ωN
, 0 ≤ k < N , onde ωN ≡ exp

2πi
N

´e chamado raiz principal da unidade.

Quando o contexto estiver claro pode-se omitir a indica¸c˜ao de N na raiz principal da unidade, de