Rader's FFT algorithm: Difference between revisions

Revision as of 15:16, 8 July 2017

Revision as of 09:37, 14 October 2017

Line 8:

==Algorithm==

[[File:FFT visual Rader 11.pdfjpg|thumb|upright=1.5|Visual representation of [[DFT matrix]] in Rader's FFT algoritm, The array consists of colored clocks represent DFT matrix of size 11. By permuting rows and columns using a sequence generated by primitive root of 11 (which is 2) except the 1st row and column, the original DFT matrix becomes a [[circulant matrix]]. Multiplying a circulant matrix to a data sequence is equivalent to the [[cyclic convolution]].]]

]]

:<math> X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk }

\qquad