Introduction to the Fast-Fourier Transform (FFT) Algorithm
Intro to FFT. 1 / 30. Page 2. The Discrete Fourier Transform (DFT) Figure 9.4 Flowgraph of Decimation in Time algorithm for N = 8 (Oppenheim and Schafer ...
Module 4: Frequency Domain Signal Processing and Analysis
Basic concepts in frequency domain signal processing and analysis. ? Fourier Transform. ? FFT (Fast Fourier Transform). ? Implementation of FFT in MATLAB
DIGITAL SIGNAL PROCESSING.pdf
To understand the basic concepts and techniques for processing signals and To acquaint in FFT algorithms Multi-rate signal processing techniques and ...
OFDM Basics
Introduction to OFDM. • Discussion of receivers for OFDM and MC-CDMA. • Intercarrier Interference FFT Leakage. • New receiver designs.
Fast Fourier Transforms (FFTs) and Windowing
FFT Basics: Alias and Frequency Resolution. 3. 1. FFT assumes time domain continues forever. 2. Number of points in time domain equals.
Spectrum Analysis - SKF
Introduction. A vibration FFT (Fast Fourier Transform) spectrum is an incredibly useful tool for machinery vibration analysis. If a machinery problem exists
Implementing the Radix-4 Decimation in Frequency (DIF) Fast
in Frequency (DIF) Fast Fourier. Transform (FFT) Algorithm Using a. TMS320C80 DSP. APPLICATION REPORT: SPRA152. Author: Charles Wu.
PowerPoint Template
Fast Fourier Transform (FFT) is an efficient algorithm to compute Fig.1-2. shows the basic unit used for implementing FFT algorithm the.
A Guide to Otoacoustic Emissions
Test result display – basic advanced or FFT view? short introduction to OAE testing in ... the cochlea during stimulus presentation .
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
Prime Factor Algorithms
WhenNis not a power of 2 but is a composite number, it can be expressed in terms of its p rimefacto rsExample:N= 6 = 32We can now split the given sequence into 3 segments of 2 samples eachx0;x3;x1;x4;x2;x5Three 2-point DFTs are computed and combined to get the
nal DFTSignicant computational savings is obtained, as before Ecient algorithms exist even whenNis prime!http://en.wikipedia.org/wiki/Rader's_FFT_algorithm C.S. Ramalingam (EE Dept., IIT Madras)Intro to FFT30 / 30quotesdbs_dbs17.pdfusesText_23[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