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

©flickr: Gage	How well do you know Ross Lynch? By Brianna Beck Start Quiz
	3 Week 3 Social Psych By Yacoub Jayoghli Start Quiz
	25 AP 25 Urinary System MCQ By OpenStax Start Quiz
	Time and Stress Management MCQ By Dionne Mahaffey Start Quiz
	Spreadsheets MCQ By Ryan Lowe Start Quiz
	Are you a 5sos fan? By Rylee Minllic Start Quiz
©flickr: BK	Self Confidence By Miranda Reising Start Quiz
	Algebra and trigonometry By OpenStax Read Online Course
	Anthropology Politics Culture By Richley Crapo Start Assignment
	Power Enigeering types of bearing lubrication By Sam Luong Start Quiz