Algoritmo FFT de Bruun

Recorde-se que a DFT é definida pela fórmula: 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.} Por conveniência, denotemos as N {\displaystyle N} raízes da unidade por ω N n {\displaystyle \omega _{N}^{n}} ( n = 0 , … , N − 1 {\displaystyle n=0,\dots ,N-1} ): ω N n = e − 2 π i N n {\displaystyle \omega _{N}^{n}=e^{-{\frac {2\pi i}{N}}n}} e defina-se o polinómio x ( z ) {\displaystyle x(z)} cujos coeficientes são x n {\displaystyle x_{n}} : x ( z ) = ∑ n = 0 N − 1 x n z n . {\displaystyle x(z)=\sum _{n=0}^{N-1}x_{n}z^{n}.} A DFT pode então ser compreendida como uma redução deste polinómio; isto é, X k {\displaystyle X_{k}} é dado por: X k = x ( ω N k ) = x ( z ) mod ( z − ω N k ) {\displaystyle X_{k}=x(\omega _{N}^{k})=x(z)\mod (z-\omega _{N}^{k})} onde mod denota a operação de resto polinomial (teorema do resto polinomial). A chave para algoritmos rápidos como o de Bruun ou Cooley-Tukey advém do facto de que é possível executar este conjunto de N {\displaystyle N} operações de resto em fases recursivas.

Para calcular a DFT, precisamos de avaliar o resto de x ( z ) {\displaystyle x(z)} módulo N {\displaystyle N} polinómios de grau 1, tal como descrito acima. Avaliar estes restos um a um é equivalente a avaliar a fórmula habitual da DFT diretamente, e requer O ( N 2 ) {\displaystyle O(N^{2})} operações. Contudo, é possível combinar estes restos recursivamente para reduzir o custo, utilizando o seguinte truque: se quisermos avaliar x ( z ) {\displaystyle x(z)} módulo dois polinómios U ( z ) {\displaystyle U(z)} e V ( z ) {\displaystyle V(z)} , podemos primeiro obter o resto módulo o seu produto U ( z ) V ( z ) {\displaystyle U(z)V(z)} , o que reduz o grau do polinómio x ( z ) {\displaystyle x(z)} e torna as operações de módulo subsequentes menos dispendiosas computacionalmente. O produto de todos os monómios ( z − ω N k ) {\displaystyle (z-\omega _{N}^{k})} para k = 0 … N − 1 {\displaystyle k=0\dots N-1} é simplesmente z N − 1 {\displaystyle z^{N}-1} (cujas raízes são claramente as N {\displaystyle N} raízes da unidade). Pretende-se então encontrar uma fatorização recursiva de z N − 1 {\displaystyle z^{N}-1} em polinómios de poucos termos e de grau cada vez menor. Para calcular a DFT, toma-se x ( z ) {\displaystyle x(z)} módulo cada nível desta fatorização, recursivamente, até se chegar aos monómios e ao resultado final. Se cada nível da fatorização dividir cada polinómio num número O ( 1 ) {\displaystyle O(1)} (limitado por uma constante) de polinómios menores, cada um com um número O ( 1 ) {\displaystyle O(1)} de coeficientes não nulos, então as operações de módulo para esse nível demoram um tempo O ( N ) {\displaystyle O(N)} ; uma vez que haverá um número logarítmico de níveis, a complexidade global é O ( N log ⁡ N ) {\displaystyle O(N\log N)} .

O algoritmo básico de Bruun para potências de dois N = 2 n {\displaystyle N=2^{n}} fatora z 2 n − 1 {\displaystyle z^{2^{n}}-1} recursivamente através das regras: z 2 M − 1 = ( z M − 1 ) ( z M + 1 ) {\displaystyle z^{2M}-1=(z^{M}-1)(z^{M}+1)\,} z 4 M + a z 2 M + 1 = ( z 2 M + 2 − a z M + 1 ) ( z 2 M − 2 − a z M + 1 ) {\displaystyle z^{4M}+az^{2M}+1=(z^{2M}+{\sqrt {2-a}}z^{M}+1)(z^{2M}-{\sqrt {2-a}}z^{M}+1)} onde a {\displaystyle a} é uma constante real com | a | ≤ 2 {\displaystyle |a|\leq 2} . Se a = 2 cos ⁡ ( ϕ ) {\displaystyle a=2\cos(\phi )} , ϕ ∈ ( 0 , π ) {\displaystyle \phi \in (0,\pi )} , então 2 + a = 2 cos ⁡ ϕ 2 {\displaystyle {\sqrt {2+a}}=2\cos {\tfrac {\phi }{2}}} e 2 − a = 2 cos ⁡ ( π 2 − ϕ 2 ) {\displaystyle {\sqrt {2-a}}=2\cos({\tfrac {\pi }{2}}-{\tfrac {\phi }{2}})} . Na etapa s {\displaystyle s} , s = 0 , 1 , 2 , n − 1 {\displaystyle s=0,1,2,n-1} , o estado intermédio consiste em 2 s {\displaystyle 2^{s}} polinómios p s , 0 , … , p s , 2 s − 1 {\displaystyle p_{s,0},\dots ,p_{s,2^{s}-1}} de grau 2 n − s − 1 {\displaystyle 2^{n-s}-1} ou inferior, em que: p s , 0 ( z ) = p ( z ) mod ( z 2 n − s − 1 ) e p s , m ( z ) = p ( z ) mod ( z 2 n − s − 2 cos ⁡ ( m 2 s π ) z 2 n − 1 − s + 1 ) m = 1 , 2 , … , 2 s − 1 {\displaystyle {\begin{aligned}p_{s,0}(z)&=p(z)\mod \left(z^{2^{n-s}}-1\right)&\quad &{\text{e}}\\p_{s,m}(z)&=p(z)\mod \left(z^{2^{n-s}}-2\cos \left({\tfrac {m}{2^{s}}}\pi \right)z^{2^{n-1-s}}+1\right)&m&=1,2,\dots ,2^{s}-1\end{aligned}}}