O algoritmo de Rader (1968),C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE 56, 1107–1108 (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 (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;<ref>S. Chu and C. Burrus, "A prime factor FTT [</nowiki>sic<nowiki>] algorithm using distributed arithmetic," IEEE Transactions on Acoustics, Speech, and Signal Processing 30 (2), 217–227 (1982).</ref> uma adaptação alternativa para DFTs de dados reais utiliza a transformada discreta de Hartley.Matteo Frigo and Steven G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005).
Winograd estendeu o algoritmo de Rader para incluir tamanhos de DFT que são potências de primos ,S. Winograd, "On Computing the Discrete Fourier Transform", Proc. National Academy of Sciences USA, 73(4), 1005–1006 (1976).S. Winograd, "On Computing the Discrete Fourier Transform", Mathematics of Computation, 32(141), 175–199 (1978). 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),R. Tolimieri, M. An, and C.Lu, Algorithms for Discrete Fourier Transform and Convolution, Springer-Verlag, 2nd ed., 1997. 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.
Algoritmo thumb|Representação visual de uma matriz DFT no algoritmo FFT de Rader. A matriz consiste em relógios coloridos representando uma matriz DFT de tamanho 11. Ao permutar as linhas e as colunas (exceto a primeira de cada) de acordo com sequências geradas pelas potências da raiz primitiva de 11, a matriz DFT original torna-se numa matriz circulante. Multiplicar uma sequência de dados com uma matriz circulante é equivalente à convolução cíclica com o vetor linha da matriz. Esta relação é um exemplo do facto de o grupo multiplicativo ser cíclico: . Comece com a definição da transformada discreta de Fourier:
Se for um número primo, então o conjunto de índices não nulos forma um grupo sob a multiplicação módulo . 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 melhoresDonald E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).). Este gerador é um número inteiro tal que para qualquer índice não nulo e para um único (formando uma bijeção de para não nulo). De modo análogo, para qualquer índice não nulo e para um único , onde o expoente negativo denota o inverso multiplicativo de . Isto significa que podemos reescrever a DFT usando estes novos índices e como:
(Recorde-se que e são implicitamente periódicos em , e também que (Identidade de Euler). Assim, todos os índices e expoentes são tomados em módulo , conforme exigido pela aritmética do grupo.)
O somatório final, acima, é precisamente uma convolução cíclica das duas sequências e (de comprimento , pois ) definidas por:
Avaliação da convolução Uma vez que é 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 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 de forma exata através do preenchimento com zeros (zero-padding) até atingir um comprimento de pelo menos , digamos para uma potência de dois, o que pode então ser avaliado num tempo de sem a aplicação recursiva do algoritmo de Rader.
Este algoritmo requer, portanto, adições mais de tempo para a convolução. Na prática, as adições podem frequentemente ser realizadas absorvendo-as na convolução: se a convolução for executada por um par de FFTs, então a soma de é dada pela saída DC (de ordem 0) da FFT de mais , e pode ser adicionado a todas as saídas somando-o ao termo DC da convolução antes da FFT inversa. Ainda assim, este algoritmo requer intrinsecamente mais operações do que as FFTs de tamanhos compostos próximos, e na prática demora tipicamente 3 a 10 vezes mais tempo a executar.
Se o algoritmo de Rader for executado utilizando FFTs de tamanho para calcular a convolução, em vez do preenchimento com zeros acima mencionado, a eficiência dependerá fortemente de e do número de vezes que o algoritmo de Rader tenha de ser aplicado recursivamente. O pior caso ocorreria se fosse onde é primo, com onde é primo, e assim por diante. Tais são chamados de primos de Sophie Germain, e essa sequência de primos é designada por cadeia de Cunningham do primeiro tipo. Contudo, a alternativa do preenchimento com zeros pode ser sempre empregada se apresentar um grande fator primo.
Ver também
Algoritmo FFT de Brunn
Referências
Categoria:Transformada rápida de Fourier