Content deleted Content added
→Evaluating the convolution: remove dubious claims (see Talk), which were unsourced anyway |
|||
| (24 intermediate revisions by 20 users not shown) | |||
Line 1:
{{Short description|Discrete Fourier transform for prime sizes}}
'''Rader's algorithm''' (1968),<ref>C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," ''Proc. IEEE'' 56, 1107–1108 (1968).</ref> 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 number|prime]] sizes by re-expressing the DFT as a cyclic [[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;<ref>S.
Winograd extended Rader's algorithm to include prime-power DFT sizes <math>p^m</math>,<ref>S.
==Algorithm==
[[File:FFT visual Rader 11.jpg|thumb|Visual representation of a [[DFT matrix]] in Rader's FFT algorithm. The array consists of colored clocks representing a DFT matrix of size 11. By permuting rows and columns (except the first of each) according to sequences generated by the powers of the primitive root of 11, the original DFT matrix becomes a [[circulant matrix]]. Multiplying a data sequence with a circulant matrix is equivalent to the [[cyclic convolution]] with the matrix's row vector. This relation is an example of the fact that the [[multiplicative group]] is cyclic: <math>(\mathbb Z/p\mathbb Z)^\times \cong C_{p-1}</math>.]]
Begin with the definition of the discrete Fourier transform:
:<math> X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk }
Line 15 ⟶ 16:
k = 0,\dots,N-1. </math>
If ''N'' is a prime number, then the set of non-zero indices
:<math> X_0 = \sum_{n=0}^{N-1} x_n,</math>
Line 23 ⟶ 24:
p = 0,\dots,N-2. </math>
(Recall that ''x''<sub>''n''</sub> and ''X''<sub>''k''</sub> are implicitly periodic in ''N'', and also that
The final summation, above, is precisely a cyclic convolution of the two sequences ''a''<sub>''q''</sub> and ''b''<sub>''q''</sub> (of length ''N''–1,
:<math>a_q = x_{g^q}</math>
Line 36 ⟶ 37:
This algorithm, then, requires O(''N'') additions plus O(''N'' log ''N'') time for the convolution. In practice, the O(''N'') additions can often be performed by absorbing the additions into the convolution: if the convolution is performed by a pair of FFTs, then the sum of ''x''<sub>''n''</sub> is given by the DC (0th) output of the FFT of ''a''<sub>''q''</sub> plus ''x''<sub>0</sub>, and ''x''<sub>0</sub> can be added to all the outputs by adding it to the DC term of the convolution prior to the inverse FFT. Still, this algorithm requires intrinsically more operations than FFTs of nearby composite sizes, and typically takes 3–10 times as long in practice.
If Rader's algorithm is performed by using FFTs of size ''N''–1 to compute the convolution, rather than by zero padding as mentioned above, the efficiency depends strongly upon ''N'' and the number of times that Rader's algorithm must be applied recursively. The worst case would be if ''N''–1 were 2''N''<sub>2</sub> where ''N''<sub>2</sub> is prime, with ''N''<sub>2</sub>–1 = 2''N''<sub>3</sub> where ''N''<sub>3</sub> is prime, and so on
==References==
<references/>
[[Category:FFT algorithms]]
| |||