Read Microsoft PowerPoint - Chap9-FFT.ppt text version

Discrete Fourier Transform

· Discrete Fourier transform (DFT) pairs

kn X [k ] = x[n]WN , k = 0,1, K , N - 1 n =0 N -1

1 x[n] = N

- X [k ]WN kn , n = 0,1, K , N - 1, k =0 -j 2 kn N

N -1

N complex multiplications N-1 complex additions

- where WN kn = e

· DFT/IDFT can be implemented by using the same hardware · It requires N2 complex multiplications and N(N-1) complex additions

[email protected] 1

Decimation in Time

twiddle factor

N+2(N/2)2 complex multiplications vs. N2 complex multiplication

[email protected] 2

[email protected]


Flow Graph of the DIT FFT

[email protected]


[email protected]


8-point DIT DFT

[email protected]



· It requires v=log2N stages · Each stage has N complex multiplications and N complex additions · The number of complex multiplications (as well as additions) is equal to N log2N · By symmetry property, we have (butterfly operation)

r r r WN + N 2 = WNWNN 2 = WN e - j = -WNN 2

2 complex multiplications 1 complex multiplications 2 complex additions 2 complex additions [email protected]


8-point FFT

Bit-Reversed order

[email protected]

Normal order


In-Place Computation

The same register array can be used in each stage

X0[000] X0[001] X0[010] X0[011] X0[100] X0[101] X0[110] X0[111] X1[000] X1[001] X1[010] X1[011] X1[100] X1[101] X1[110] X1[111] X2[000] X2[001] X2[010] X2[011] X2[100] X2[101] X2[110] X2[111] X3[000] X3[001] X3[010] X3[011] X3[100] X3[101] X3[110] X3[111]

Stage 1

Stage 2

[email protected]

Stage 3


8-point FFT

Normal order

The original from given by Cooly & Tukey (DIT FFT)

[email protected]

Bit-reversed order


Normal-Order Sorting v.s. Bit-Reversed Sorting

top bottom

even odd

Normal Order

[email protected]

Bit-reversed Order


DFT v.s. Radix-2 FFT

· DFT: N2 complex multiplications and N(N-1) complex additions · Recall that each butterfly operation requires one complex multiplication and two complex additions · FFT: (N/2) log2N multiplications and N log2N complex additions · In-place computations: the input and the output nodes for each butterfly operation are horizontally adjacent only one storage arrays will be required

[email protected] 12

Alternative Form

Normal order

Two complex storage arrays are necessary !!

[email protected]

Normal order


Alternative Form

Parallel processing: 4 BF units

X1[000] X1[001] X1[010] X1[011] X1[100] X1[101] X1[110] X1[111] Stage 1 X2[000] X2[001] X2[010] X2[011] X2[100] X2[101] X2[110] X2[111]

Sequential processing: 1 BF unit

X1[000] X1[001] X1[010] X1[011] X1[100] X1[101] X1[110] X1[111] Stage 1 X2[000] X2[001] X2[010] X2[011] X2[100] X2[101] X2[110] X2[111]

The same register array can be used

Two register arrays are required


[email protected]

Alternative Form 2

Bit-reversed order The geometry of each stage is identical

[email protected]

Normal order


Decimation in Frequency (DIF)

· Recall that the DFT is X [k ] = x[n ]WNnk , 0 k N - 1

n =0 N -1

· DIT FFT algorithm is based on the decomposition of the DFT computations by forming small subsequences in time domain index "n": n=2 or n=2+1 · One can consider dividing the output sequence X[k], in frequency domain, into smaller subsequences: k=2r or k=2r+1:

Substitution of variables

[email protected]


DIF FFT Algorithm (1)

is just N/2-point DFT. Similarly,

[email protected]


DIF FFT Algorithm (2)

v=log2N stages, each stage has N/2 butterfly operation. (N/2)log2N complex multiplications, N complex additions

[email protected] 18


· The basic butterfly operations for DIT FFT and DIF FFT respectively are transposed-form pair.

DIT BF unit

DIF BF unit

· The I/O values of DIT FFT and DIF FFT are the same · Applying the transpose transform to each DIT FFT algorithm, one obtains DIF FFT algorithm

[email protected] 19

Implementation Issues

· Radix-2, Radix-4, Radix-8, Split-Radix,Radix-22, ..., · I/O Indexing · In-place computation

­ Bit-reversed sorting is necessary ­ Efficient use of memory ­ Random access (not sequential) of memory. An address generator unit is required. ­ Good for cascade form: FFT followed by IFFT (or vice versa)

· E.g. fast convolution algorithm

· Twiddle factors

­ Look up table ­ CORDIC rotator

[email protected] 20

Recall... Linear Convolution

[email protected]


Fast Convolution with the FFT

· Given two sequences x1 and x2 of length N1 and N2 respectively · Consider using FFT to convolve two sequences:

­ Direct implementation requires N1N2 complex multiplications

­ Pick N, a power of 2, such that NN1+N2-1 ­ Zero-pad x1 and x2 to length N ­ Compute N-point FFTs of zero-padded x1 and x2, one obtains X1 and X2 ­ Multiply X1 and X2 ­ Apply the IFFT to obtain the convolution sum of x1 and x2 ­ Computation complexity: 2(N/2) log2N + N + (N/2)log2N

[email protected] 22

Other Fast Algorithm for DFT

· Goertzel Algorithm

­ By reformulating DFT as a convolution ­ it is not restricted to computation of the DFT but any desired set of samples of the Fourier transform of a sequence

· Winograd Algorithm

­ An efficient algorithm for computing short convolutions ­ The number of multiplication complexity is of order O(N), however the number of addition complexity is significantly increased.

· Chirp Transform Algorithm

[email protected] 23


Microsoft PowerPoint - Chap9-FFT.ppt

23 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate


Notice: fwrite(): send of 195 bytes failed with errno=104 Connection reset by peer in /home/ on line 531