0.2 Multidimensional index mapping (Page 6/6)

Fast fourier transforms Page 6 / 6

In order to get some idea of the “best" radix, the number of multiplications to compute a length-R DFT is assumed to be $F (R) = R^{x}$ . If this is used with [link] , the optimal R can be found.

d F / d R = 0 = > R = e^{1 / (x - 1)}

For $x = 2$ this gives $R = e$ , 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 $F = R^{2}$ multiplications, the optimal algorithm requires

F = 3 N {log}_{3} N

multiplications for a length $N = 3^{M}$ DFT. Compare this with $N^{2}$ 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- $N_{i}$ DFT's in [link] . For example, if $R = 2$ 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 $O (N)$ multiplications. This means that $F (N_{i}) = K N_{i}$ and the operation count $F$ in "Efficiencies Resulting from Index Mapping with the DFT" is independent of $N_{i}$ . Therefore, the derivative of $F$ is zero for all $N_{i}$ . Obviously, these particular cases must be examined.

The fft as a recursive evaluation of the dft

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 $N = 2^{M}$ , 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 $M$ recursions, giving the familiar order $N log (N)$ arithmetic complexity.

Calculate the even indexed DFT values from [link] by:

C (2 k) = \sum_{n = 0}^{N - 1} x (n) W_{N}^{2 n k} = \sum_{n = 0}^{N - 1} x (n) W_{N / 2}^{n k}

C (2 k) = \sum_{n = 0}^{N / 2 - 1} x (n) W_{N}^{2 n k} + \sum_{n = N / 2}^{N - 1} x (n) W_{N / 2}^{n k}

C (2 k) = \sum_{n = 0}^{N / 2 - 1} {x (n) + x (n + N / 2)} W_{N / 2}^{n k}

and a similar argument gives the odd indexed values as:

C (2 k + 1) = \sum_{n = 0}^{N / 2 - 1} {x (n) - x (n + N / 2)} W_{N}^{n} W_{N / 2}^{n k}

Together, these are recursive DFT formulas expressing the length-N DFT of $x (n)$ in terms of length-N/2 DFTs:

C (2 k) = {DFT}_{N / 2} {x (n) + x (n + N / 2)}

C (2 k + 1) = {DFT}_{N / 2} {[x (n) - x (n + N / 2)] W_{N}^{n}}

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
 $N = 2^{M}$

A DIT version can be derived in the form:

C (k) = {DFT}_{N / 2} {x (2 n)} + W_{N}^{k} {DFT}_{N / 2} {x (2 n + 1)}

C (k + N / 2) = {DFT}_{N / 2} {x (2 n)} - W_{N}^{k} {DFT}_{N / 2} {x (2 n + 1)}

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
 $N = 2^{M}$

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- $2^{M}$ sequence will require $M$ recursions, each of which will require $N / 2$ multiplications. This give the $N log (N)$ formula that the other approaches also derive.

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?

Ask

	13 AP Key Terms 13 Anatomy of the Nervous System By OpenStax Start Key Terms
	Advertising Promotion BUS210 By Melinda Salzer Start Quiz
	2 Physiotherapy Flashcards Set 2 By Rhodes Start Flashcards
	Real Estate Finance By Mldelatte Start Quiz
	3 AP 03 Cellular Level of Organization MCQ By OpenStax Start Quiz
©flickr: Luis	Final Exam Review By Madison Christian Start Exam
	Macroeconomics MCQ By Candice Butts Start Quiz
	24 Biology 24 Fungi MCQ By OpenStax Start Quiz
	10 Neuroanatomy 10 Corticospinal Tract By Stephen Voron Start Quiz
	Professional Writing MCQ By Mary Cohen Start Quiz