Read Microsoft PowerPoint - Chap9-FFT.ppt text version

`Discrete Fourier Transform· Discrete Fourier transform (DFT) pairskn X [k ] =  x[n]WN , k = 0,1, K , N - 1 n =0 N -11 x[n] = N- X [k ]WN kn , n = 0,1, K , N - 1,  k =0 -j 2 kn NN -1N 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 Timetwiddle factorN+2(N/2)2 complex multiplications vs. N2 complex multiplication[email protected] 2[email protected]3Flow Graph of the DIT FFT[email protected]4[email protected]58-point DIT DFT[email protected]6Remarks· 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 22 complex multiplications 1 complex multiplications 2 complex additions 2 complex additions [email protected]78-point FFTBit-Reversed order[email protected]Normal order8In-Place ComputationThe same register array can be used in each stageX0[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 1Stage 2[email protected]Stage 398-point FFTNormal orderThe original from given by Cooly &amp; Tukey (DIT FFT)[email protected]Bit-reversed order10Normal-Order Sorting v.s. Bit-Reversed Sortingtop bottomeven oddNormal Order[email protected]Bit-reversed Order11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 FormNormal orderTwo complex storage arrays are necessary !![email protected]Normal order13Alternative FormParallel processing: 4 BF unitsX1[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 unitX1[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 usedTwo register arrays are required14[email protected]Alternative Form 2Bit-reversed order The geometry of each stage is identical[email protected]Normal order15Decimation in Frequency (DIF)· Recall that the DFT is X [k ] =  x[n ]WNnk , 0  k  N - 1n =0 N -1· DIT FFT algorithm is based on the decomposition of the DFT computations by forming small subsequences in time domain index &quot;n&quot;: 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]16DIF FFT Algorithm (1)is just N/2-point DFT. Similarly,[email protected]17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Remarks· The basic butterfly operations for DIT FFT and DIF FFT respectively are transposed-form pair.DIT BF unitDIF 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]21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`

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

462047

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