FFT Tutorial 1 Getting to Know the FFT What is the FFT? FFT = Fast Fourier Transform The FFT is a faster version of the Discrete Fourier Transform (DFT)
| Previous PDF | Next PDF |
[PDF] (FFT) Algorithm - Department of Electrical Engineering - IIT Madras
Introduction to the Fast-Fourier Transform (FFT) Algorithm C S Ramalingam Department The Discrete Fourier Transform (DFT) DFT of an N-point sequence
[PDF] FFT Tutorial
FFT Tutorial 1 Getting to Know the FFT What is the FFT? FFT = Fast Fourier Transform The FFT is a faster version of the Discrete Fourier Transform (DFT)
[PDF] The Fourier Transform
Review: Fourier Trignometric Series (for Periodic Waveforms) Agbo Sadiku Source: Agilent Technologies Application Note 150, “Spectrum Analyzer Basics”
[PDF] FFT Algorithms
Many software packages for the FFT are available, so many DSP users will never need to write their own FFT N = 8-point decimation-in-time FFT algorithm
[PDF] (DFT) and Fast Fourier Transform (FFT)
Lab 8 Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) ( Theory and Implementation) Page 2 Learning Objectives ◇ DFT algorithm
[PDF] Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm
What is its impulse response? We know that the impulse response is the inverse Fourier transform of the frequency response, so taking off our signal processing
[PDF] Frequency Domain Signal Processing and Analysis - Department of
Basic concepts in frequency domain signal processing and analysis ▫ Fourier Transform ▫ FFT (Fast Fourier Transform) □ Implementation of FFT in MATLAB
[PDF] Fast Fourier Transform: Theory and Algorithms - MIT
Twiddle factor FFTs (non-coprime sub-lengths) ❑ 1977 Kolba and Parks ( Prime Factor Algorithm – PFA) If not, then inner sum is one stap of radix-r FFT
[PDF] fft code for arduino
[PDF] fft code in c
[PDF] fft code in verilog
[PDF] fft code python
[PDF] fft codechef
[PDF] fft complex number
[PDF] fft complex number frequency
[PDF] fft complex number input
[PDF] fft complex number meaning
[PDF] fft complex number result
[PDF] fft convolution complexity
[PDF] fft eigenvalues
[PDF] fft example arduino
[PDF] fft example by hand
Introduction to the Fast-Fourier
Transform (FFT) Algorithm
C.S. Ramalingam
Department of Electrical Engineering
IIT Madras
C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT1 / 30The Discrete Fourier Transform (DFT)
DFT of anN-point sequencexn,n= 0;1;2;:::;N1 is
dened as X k=N1X n=0x nej2kN nk= 0;1;2;;N1AnN-point sequence yields anN-point transformX kcan be expressed as aninner product: X k=h1ej2kN
ej2kN2:::ej2kN
(N1)i2 6666664x
0 x 1 x N13 7777775C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT2 / 30
The Discrete Fourier Transform (DFT)
Notation:WN=ej2N
. Hence, X k=h1WkNW2kN:::W(N1)k
Ni2 6666664x
0 x 1 x N13 7777775By varyingkfrom 0 toN1 and combining theNinner
products, we get the following:X=WxWis anNNmatrix, called as the \DFT Matrix"C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT3 / 30
The DFT Matrix
W=2 66666666641 1 11
1WNW2NWN1
N1W2NW4NW2(N1)
N... 1WN1NW2(N1)
NW(N1)(N1)
N3 7777777775
NNThe notationWNis used if we want to make the size of theDFT matrix explicit
C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT4 / 30How Many Complex Multiplications Are Required?
Each inner product requiresNcomplex multiplicationsThere areNinner productsHence we requireN2multiplicationsHowever, the rst row and rst column are all 1s, andshould
not be counted as multiplicationsThere are2 N1such instances Hence, the number of complex multiplications isN22N+1,
i.e., ( N1)2C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT5 / 30How Many Complex Additions Are Required?
Each inner product requiresN1complex additions There areNinner productsHence we requireN(N1)complex additions C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT6 / 30
Total Operation Count
No. of complex multiplications:
( N1)2No. of complex additions:N(N1)The operation count for multiplications and additions assumesthatWkNhas been computed oine and is available in memoryIf pre-computed values ofWkNare not available, then the
operation count will increaseWe will assume that all the requiredWkNhave been pre-computed and are available C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT7 / 30Operation Count Makes DFT Impractical
For largeN,
(N1)2N2N(N1)N2Hence both multiplications and additions areO(N2)IfN=10 3, thenO(N2) =10 6, i.e., a million!This makes the straightforward methodslo wand imp ractical
even for a moderately long sequence C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT8 / 30The Divide and Conquer Approach
SupposeNiseven and w esplit the sequence into t wohalves. Each sequence hasN/2 p ointsSuppose
w ecompute the N2 point DFT of each sequence Multiplications: 2N2 2=N22Suppose
w ea reable to combine the ind ividualDFT results to get the originally required DFTSome computationaloverhead will b econsume dto combine the two resultsIf N22 + overhead2+ overhead, i.e.,32 + overhead multiplications Questions:
Can the two DFTs be combined to get the original DFT?If so, how? What is the overhead involved?
Will 32 + overhead be less than 64?
C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT10 / 30The Decimation in Time (DIT) Algorithm
Fromfxngform two sequences as follows:
fgng=fx2ng fhng=fx2n+1gfgngcontains theeven -indexed samples, whilefhngcontains the o dd -indexed samplesThe DFT offxngisX k= N1X n=0x nWnkN= N2 1X r=0x2rW(2r)k
N+N2 1X r=0x2r+1W(2r+1)k
N= N2 1X r=0g rW(2r)kN+WkNN2
1X r=0h rW(2r)k N C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT11 / 30The Decimation in Time (DIT) Algorithm
But, W2rkN=ej2N
(2rk)=ej2N=2(rk)=WrkN=2and hence X k=N2 1X r=0g rWrkN=2+WkNN2 1X r=0h rWrkN=2 =Gk+WkNHkk= 0;1;:::;N1fGkgandfHkgareN2 point DFTsTheoverhead fo rcombining the t wo N2 point DFTs is the multiplicative factorWkNfork= 0;1;:::;N1W kNis called \twiddle factor"C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT12 / 30The Decimation in Time (DIT) Algorithm
TheN=2 point DFTsfGkgandfHkgare periodic with period N=2G k+N2 =Gk H k+N2 =HkW k+N2N=WkNHence, ifXk=Gk+WkNHk, thenXk+N2
=GkWkNHkW kNHkneeds to be computed only once fork= 0 toN21Thus, themultiplication overhead due to the t widdlefacto rsis
only N2 C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT13 / 30Butter
y Diagram W kNWkNG k H kX k X k+N2 X k=Gk+WkNHkX k+N2 =Gk+N2 +Wk+N2NHk+N2
=GkWkNHkC.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT14 / 30The Decimation in Time (DIT) Algorithm
Figure 9.4 Flowgraph of Decimation in Time algorithm forN= 8 (Oppenheim and Schafer,Discrete-Time Signal
Processing, 3rd edition, Pearson Education, 2010, p. 726)C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT15 / 30
\Divide and Conquer" Results in Savings!ForN= 8, the straightforward approach requires,
approximately,64 multiplications The \Divide and Conquer" approach, after the rst stage, requires 32 + 4 =36 multiplications Thus, this approach clearly reduces the number of additions
and multiplications required C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT16 / 30Reusing the \Divide and Conquer" Strategy
The same idea can be applied for calculating the
N2 point DFT of the sequencesfgrgandfhrgComputational savings can be obtained by dividingfgrgand fhrgintotheirodd- and even-indexed halvesThis idea can be applied recursively log2Ntimes ifNis a
power of 2Such algorithms are calledradix 2 algo rithmsIfN= 2
, then the nal stage sequences are all of length 2For a 2-point sequencefp0;p1g, the DFT coecients are
P0=p0+p1P1=p0p1C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT17 / 30
DIT Flowgraph forN= 8Figure 9.11 Flowgraph of Decimation in Time algorithm forN= 8 (Oppenheim and Schafer,Discrete-Time Signal
Processing, 3rd edition, Pearson Education, 2010, p. 730)C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT18 / 30
Overall Operation Count
The direct method requiresN2multiplicationsAfter the rst split,N2!2N2 2+N2 N 2 is due to thetwiddle factorsAfter the second split, N2 2!2N4 2+N4Hence,
N 2!2N2 2+N2 |{z} rst stage!4N4 2+N2 +N2 |{z} second stageGeneralizing, if there are log2Nstages, the number of
multiplications needed will be,approximately,N2 log2NC.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT19 / 30Overall Operation Count
IfWk+N2
N=WkNis not considered, theoverhead count will
beNandnot N2In this case,
N 2!2N22+N|{z}
rst stage!4N42+N+N|{z}
second stageHence the overall multiplication count will beNlog2NForN= 1024 N2= 1;048;576Nlog2N= 10;240
Savings of
t woo rdersof magnitude! C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT20 / 30Input Sequence Order
Recall that, forN= 8, the rst split requires the data to be arranged as follows: x0;x2;x4;x6;x1;x3;x5;x7In the second and nal split, the data appear in the following
order: x0;x4;x2;x6;x1;x5;x3;x7The nal order is said to be in \bit reversed" form:
OriginalBinary FormReversed FormFinal
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117
C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT21 / 30An Algorithm For Sequence Reversal
Consider the card sequence7, 8, 9, 10, J, Q, K, AFirst, reverse pairwise:8, 7, 10, 9, Q, J, A, K
Then swap the adjacent pairs:
10, 9, 8, 7, A, K, Q, J
Finally, swap the two groups of 4 (each group is half the original size):A, K, Q, J, 10, 9, 8, 7Done!C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT22 / 30How To Use It For Bit Reversal
The rst step of swapping of bits pairwise can be done with bitwise AND/OR and bit shif t op eratorsPick out the even and odd bits by using masksABCDEFGH & 01010101 = 0B0D0F0H
ABCDEFGH & 10101010 = A0C0E0G0Left shift the rst result and right shift the second resultB0D0F0H0
0A0C0E0G
Bitwise OR the above results
B0D0F0H00A0C0E0G = BADCFEHGPairwise bit swapping accomplished! C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT23 / 30C Code For Bit Reversal
unsigned reverse_bits(unsigned input) //works on 32-bit machine input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2; input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4; input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8; input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16; return input; }Bit reversal for the entire arrayc antak ea la rgeoverhead if performed inecientlyThere are several ecient algorithms for sorting an array in bit-reversed orderBit reversal on uniprocessorsby Alan H. Karp, SIAM Review, Vol. 38, March 1996, pp. 1{26http://www-graphics.stanford.edu/ ~seander/ bithacks.html#BitReverseTable C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT24 / 30In-Place Computation
Notation:
First stage:X(0)
k=xkLast stage:X(log2N) k=XkFor them-th stage butter yInput:X(m1)p,X(m1)qOutput:X(m)p,X(m)qThe corresponding equations are X (m)p=X(m1)p+WrNX(m1)q X (m)q=X(m1)pWrNX(m1)qC.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT25 / 30In-Place Computation
W rNX (m1)p X (m1)qX (m)p X (m)qWrNX (m1)pandX(m1)qare needed for computingX(m)pandX(m)qThey are not needed for any other pair Hence X (m)p X(m1)p X (m)q X(m1)qThis is called \in-place computation" C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT26 / 30In-Place Computation
x0andx4are not needed once that butter
y is computedHence they can be overwritten with the results of the butter y computationSame is true for other pairs also C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT27 / 30The Decimation in Frequency (DIF) Algorithm
Another method of splitting the input sequence into half is as follows: x0;x1;x2;x3;x4;x5;x6;x7Similar savings are obtained in this case also
The outputXkwill now appear inbit reversed o rderThis method is called as theDecimation in F requency
algorithm C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT28 / 30DIF Flowgraph forN= 8Figure 9.22 Flowgraph of Decimation in Frequency algorithm forN= 8 (Oppenheim and Schafer,Discrete-Time
Signal Processing, 3rd edition, Pearson Education, 2010, p. 740)C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT29 / 30