Rader's FFT algorithm

Rader's FFT algorithm

Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform.

Comment
enRader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform.
Depiction
FFT visual Rader 11.jpg
Has abstract
enRader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform. The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re-indexing/permutation to obtain two half-size cyclic convolutions of real data; an alternative adaptation for DFTs of real data uses the discrete Hartley transform. Winograd extended Rader's algorithm to include prime-power DFT sizes , and today Rader's algorithm is sometimes described as a special case of Winograd's FFT algorithm, also called the multiplicative Fourier transform algorithm (Tolimieri et al., 1997), which applies to an even larger class of sizes. However, for composite sizes such as prime powers, the Cooley–Tukey FFT algorithm is much simpler and more practical to implement, so Rader's algorithm is typically only used for large-prime base cases of Cooley–Tukey's recursive decomposition of the DFT.
Is primary topic of
Rader's FFT algorithm
Label
enRader's FFT algorithm
Link from a Wikipage to another Wikipage
Base case (recursion)
Big O notation
Bijection
Bluestein's FFT algorithm
Category:FFT algorithms
Composite number
Convolution
Convolution theorem
Cooley–Tukey FFT algorithm
Cunningham chain
Discrete Fourier transform
Discrete Hartley transform
Euler's identity
Fast Fourier transform
File:FFT visual Rader 11.jpg
Generating set of a group
Group (mathematics)
MIT Lincoln Laboratory
Modular arithmetic
Modular multiplicative inverse
Number-theoretic transform
Number theory
Power of two
Prime number
Primitive root modulo n
Recursion (computer science)
Sophie Germain prime
SameAs
4tuoz
m.01k0pk
Q7280126
Rader's FFT algorithm
الگوریتم تبدیل سریع فوریه ریدر
レーダーのFFTアルゴリズム
雷德演算法
Subject
Category:FFT algorithms
Thumbnail
FFT visual Rader 11.jpg?width=300
WasDerivedFrom
Rader's FFT algorithm?oldid=1097739627&ns=0
WikiPageLength
8034
Wikipage page ID
241408
Wikipage revision ID
1097739627
WikiPageUsesTemplate
Template:Dubious
Template:Short description