Algoritmo FFT de Rader
O algoritmo de Rader (1968), 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.
Comece com a definição da transformada discreta de Fourier: X k = ∑ n = 0 N − 1 x n e − 2 π i N n k k = 0 , … , N − 1. {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.} Se N {\displaystyle N} for um número primo, então o conjunto de índices não nulos n ∈ { 1 , … , N − 1 } {\displaystyle n\in \{1,\dots ,N-1\}} forma um grupo sob a multiplicação módulo N {\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). Este gerador é um número inteiro g {\displaystyle g} tal que n = g q ( mod N ) {\displaystyle n=g^{q}{\pmod {N}}} para qualquer índice não nulo n {\displaystyle n} e para um único q ∈ { 0 , … , N − 2 } {\displaystyle q\in \{0,\dots ,N-2\}} (formando uma bijeção de q {\displaystyle q} para n {\displaystyle n} não nulo). De modo análogo, k = g − p ( mod N ) {\displaystyle k=g^{-p}{\pmod {N}}} para qualquer índice não nulo k {\displaystyle k} e para um único p ∈ { 0 , … , N − 2 } {\displaystyle p\in \{0,\dots ,N-2\}} , onde o expoente negativo denota o inverso multiplicativo de g p ( mod N ) {\displaystyle g^{p}{\pmod {N}}} . Isto significa que podemos reescrever a DFT usando estes novos índices p {\displaystyle p} e q {\displaystyle q} como:
Avaliação da convolução
Uma vez que N − 1 {\displaystyle N-1} é um número composto, esta convolução pode ser realizada diretamente através do teorema da convolução e de algoritmos FFT mais convencionais. No entanto, isso pode não ser eficiente se o próprio N − 1 {\displaystyle N-1} tiver fatores primos grandes, exigindo o uso recursivo do algoritmo de Rader. Em vez disso, é possível calcular uma convolução cíclica de comprimento ( N − 1 ) {\displaystyle (N-1)} de forma exata através do preenchimento com zeros (zero-padding) até atingir um comprimento de pelo menos 2 ( N − 1 ) − 1 {\displaystyle 2(N-1)-1} , digamos para uma potência de dois, o que pode então ser avaliado num tempo de O ( N log N ) {\displaystyle O(N\log N)} sem a aplicação recursiva do algoritmo de Rader.
