Algoritmo FFT de Rader

O algoritmo de Rader (1968),^[1] nomeado em homenagem a Charles M. Rader do MIT Lincoln Laboratory, é um algoritmo de transformada rápida de Fourier (FFT) que calcula a transformada discreta de Fourier (DFT) de tamanhos primos ao reexpressar a DFT como uma convolução cíclica (o outro algoritmo para FFTs de tamanhos primos, o algoritmo de Bluestein, também funciona reescrevendo a DFT como uma convolução).

Uma vez que o algoritmo de Rader depende apenas da periodicidade do núcleo da DFT, é diretamente aplicável a qualquer outra transformada (de ordem prima) com uma propriedade semelhante, tal como uma transformada teórica dos números ou a transformada discreta de Hartley.

O algoritmo pode ser modificado para obter uma poupança de um fator de dois no caso de DFTs de dados reais, utilizando uma reindexação/permutação ligeiramente modificada para obter duas convoluções cíclicas de metade do tamanho de dados reais;^[2] uma adaptação alternativa para DFTs de dados reais utiliza a transformada discreta de Hartley.^[3]

Winograd estendeu o algoritmo de Rader para incluir tamanhos de DFT que são potências de primos ${\displaystyle p^{m}}$,^[4][5] e hoje o algoritmo de Rader é por vezes descrito como um caso especial do algoritmo FFT de Winograd (também referido em Fast Fourier transform#Other FFT algorithms), igualmente chamado de algoritmo da transformada de Fourier multiplicativa (Tolimieri et al., 1997),^[6] que se aplica a uma classe ainda maior de tamanhos. No entanto, para tamanhos compostos tais como potências de primos, o algoritmo FFT de Cooley-Tukey é muito mais simples e prático de implementar, pelo que o algoritmo de Rader é tipicamente usado apenas para casos base de grandes primos na decomposição recursiva de Cooley-Tukey da DFT.^[3]

Comece com a definição da transformada discreta de Fourier:

$${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$$

Se ${\displaystyle N}$ for um número primo, então o conjunto de índices não nulos ${\displaystyle n\in \{1,\dots ,N-1\}}$ forma um grupo sob a multiplicação módulo ${\displaystyle N}$. Uma consequência da teoria dos números desses grupos é a de que existe um gerador do grupo (por vezes chamado de raiz primitiva, que pode ser encontrado através de pesquisa exaustiva ou por algoritmos ligeiramente melhores^[7]). Este gerador é um número inteiro ${\displaystyle g}$ tal que ${\displaystyle n=g^{q}{\pmod {N}}}$ para qualquer índice não nulo ${\displaystyle n}$ e para um único ${\displaystyle q\in \{0,\dots ,N-2\}}$ (formando uma bijeção de ${\displaystyle q}$ para ${\displaystyle n}$ não nulo). De modo análogo, ${\displaystyle k=g^{-p}{\pmod {N}}}$ para qualquer índice não nulo ${\displaystyle k}$ e para um único ${\displaystyle p\in \{0,\dots ,N-2\}}$, onde o expoente negativo denota o inverso multiplicativo de ${\displaystyle g^{p}{\pmod {N}}}$. Isto significa que podemos reescrever a DFT usando estes novos índices ${\displaystyle p}$ e ${\displaystyle q}$ como:

$${\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}$$

$${\displaystyle X_{g^{-p}}=x_{0}+\sum _{q=0}^{N-2}x_{g^{q}}e^{-{\frac {2\pi i}{N}}g^{-(p-q)}}\qquad p=0,\dots ,N-2.}$$

(Recorde-se que ${\displaystyle x_{n}}$ e ${\displaystyle X_{k}}$ são implicitamente periódicos em ${\displaystyle N}$, e também que ${\displaystyle e^{2\pi i}=1}$ (Identidade de Euler). Assim, todos os índices e expoentes são tomados em módulo ${\displaystyle N}$, conforme exigido pela aritmética do grupo.)

O somatório final, acima, é precisamente uma convolução cíclica das duas sequências ${\displaystyle a_{q}}$ e ${\displaystyle b_{q}}$ (de comprimento ${\displaystyle N-1}$, pois ${\displaystyle q\in \{0,\dots ,N-2\}}$) definidas por:

$${\displaystyle a_{q}=x_{g^{q}}}$$ $${\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}.}$$

• Algoritmo FFT de Brunn