| << Chapter < Page | Chapter >> Page > |
In order to get some idea of the “best" radix, the number of multiplications to compute a length-R DFT is assumed to be . If this is used with [link] , the optimal R can be found.
For this gives , with the closest integer being three.
The result of this analysis states that if no other arithmetic saving methods other than index mapping are used, and ifthe length-R DFT's plus TFs require multiplications, the optimal algorithm requires
multiplications for a length DFT. Compare this with for a direct calculation and the improvement is obvious.
While this is an interesting result from the analysis of the effects of index mapping alone, in practice, index mapping is almostalways used in conjunction with special algorithms for the short length- DFT's in [link] . For example, if or 4, there are no multiplications required for the short DFT's. Only theTFs require multiplications. Winograd (see Winorad's Short DFT Algorithms ) has derived some algorithms for short DFT's that require multiplications. This means that and the operation count in "Efficiencies Resulting from Index Mapping with the DFT" is independent of . Therefore, the derivative of is zero for all . Obviously, these particular cases must be examined.
It is possible to formulate the DFT so a length-N DFT can be calculated in terms of two length-(N/2) DFTs. And, if , each of those length-(N/2) DFTs can be found in terms of length-(N/4) DFTs. This allows the DFT to be calculated bya recursive algorithm with recursions, giving the familiar order arithmetic complexity.
Calculate the even indexed DFT values from [link] by:
and a similar argument gives the odd indexed values as:
Together, these are recursive DFT formulas expressing the length-N DFT of in terms of length-N/2 DFTs:
This is a “decimation-in-frequency" (DIF) version since it gives samples of the frequency domain representation in terms of blocksof the time domain signal.
A recursive Matlab program which implements this is given by:
function c = dftr2(x)
% Recursive Decimation-in-Frequency FFT algorithm, csb 8/21/07L = length(x);
if L>1
L2 = L/2;TF = exp(-j*2*pi/L).^[0:L2-1];c1 = dftr2( x(1:L2) + x(L2+1:L));
c2 = dftr2((x(1:L2) - x(L2+1:L)).*TF);cc = [c1';c2'];c = cc(:);
elsec = x;
end
DIF Recursive FFT for
A DIT version can be derived in the form:
which gives blocks of the frequency domain from samples of the signal.
A recursive Matlab program which implements this is given by:
function c = dftr(x)
% Recursive Decimation-in-Time FFT algorithm, csbL = length(x);
if L>1
L2 = L/2;ce = dftr(x(1:2:L-1));
co = dftr(x(2:2:L));TF = exp(-j*2*pi/L).^[0:L2-1];c1 = TF.*co;
c = [(ce+c1), (ce-c1)];
elsec = x;
end
DIT Recursive FFT for
Similar recursive expressions can be developed for other radices and and algorithms. Most recursive programs do not execute as efficiently as looped or straight code,but some can be very efficient, e.g. parts of the FFTW.
Note a length- sequence will require recursions, each of which will require multiplications. This give the formula that the other approaches also derive.
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|