0 évaluation 0% ont trouvé ce document utile (0 vote) 0 vues 21 pages DSP Module 2Vvce
Le document traite des algorithmes de Transformée de Fourier Rapide (FFT), en se concentrant sur les algorithmes Radix-2 pour le calcul de la DFT et de l'IDFT, ainsi que sur les facteurs de twiddle et leurs propriétés. Il explique les algorithmes de décimation dans le temps (DIT) et dans la fréquence (DIF), en illustrant les étapes de calcul avec des exemples pratiques. Enfin, il aborde l'adressage normal et inversé pour simplifier l'accès aux tableaux lors des calculs FFT.
Description améliorée par l'IA
Copyright
© All Rights Reserved
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Go to previous items Go to next items
MODULE - II
FFT Analysis: Fast-Fourier-Transform (FFT) algorithms: Radix-2 FFT algorithms for the
computation of DFT, IDFT-decimation-in-time and decimation-in- frequency algorithms.
Self study component: Twiddle factor and its Properties.
2.1 Introduction
‘The fast Fourier transform (FFT) is an algorithm used in DSP and mathematics to efficient
compute the DFT and its inverse. The FFT is a crucial tool for analyzing and manipulating
signals in the frequency domain. Its efficiency in computing the DFT has made it a foundation
'n analyzing and manipulating signals in various domains, from audio and image processing
to communication systems and scientific research. The main idea of FFT algorithms is to
Gecompose an N-point DFT into transformations of smaller length. For example, if we devise
2 hypothetical algorithm which can decompose a 1024-point DET into two 512-point DFTs.
2.2 Twiddle factor and its properties
‘Twiddle factors are a set of values that is used to speed up DFT and IDFT calculations
Twidcle factors are mathematically represented as: Wy = e7J2"/N,
2.2.1 Properties of Phase factor/twiddle factor
1. Periodicity property of Wy: WAT" = wi
WAN a eB e Git 9 GM _ 6 ioe
eP?* = cos2n — jsin2n =1-jx0=1
Wit = enti = wh
2. Symmetry property of Wy: WAtN/2
-Ws
40 Digital Signal Processing |
Fe Sit =o Sit goin
eM" = cosm—jsing = -1-jx0=-1
; i oh
3. Wh= Wo
Wa =e P8? = FE = Wyp
2.2.2 Radix-2 DIT-FFT Algorithm
The radix-2 decimation-in-time algorithm rearranges the DFT equation into two parts: a
sum over the even-numbered discrete-time indices n = (0,2, 4,
odd-numbered indices n = (1,3,5, ..., N— 1).
Let x(n) be a N-point sequence where N is assumed to be power of 2. Decimate/break the
sequence into 2 sequences of length N/2, where one is even indexed values of x(n) and other
is odd indexed values of x(n). i
.N—2) and a sum over the
Xe(n) = x(2n); n= 0, N/2-1.
Xo(n) = x(2n +1); 2 =0,1,.....4.N/2—1.
Na
X(k) = SO x(n
n=0 :
(N/2)~1 (N/2)-1
X(k)= YO x(amywa+ SO x(2ne ywierrne
=O m0
(N/2)-1 (N/2)-1
X(k) = YO x(anywak/2+ wm So x(2n-+ 1ywat/2
mo n=O
X(k) = Xe(k) + WEXo(k): O N/2; WiK*N/) = wie ae) Module-2
We can write,
X(k) = Xe(k = N/2) — WA") Xa(k = N/2); k= N/2, 00, N= 1
Let us consider N = 8
X(k) = Xe(k) + WEXo(k)
X(k) = Xe(k — 4) — WE*X0(k — 4)
k =0;X(0) = X¢(0) + WEX,(0)
k =1;X(1) = Xe(1) + WAX0(1)
k = 2;X(2) = Xe(2) + WEXo(2)
k = 3;X(3) = Xe(3) + WeXo(3)
k= 4:X(4) = Xe(0) — WEX0(0)
k = 5;X(5) = Xe(1) — W3X0(1)
k = 6;X(6) = Xe(2) — WeXo(2)
k =T7;X(T) = Xe(3) — WeXo(3)
This is called a decimation in time because the time samples are rearranged in alternating
groups, and a radix-2 algorithm because there are two groups. Fig. 2.1 graphically illustrates
the DIT-FFT computation for N = 8.
x0) (0)
xt)
x) 4-point oy
x2) DFT vo
#3)
wt ma)
ae) [i xs)
xt) —) 4-point |
xa —| DFT [+ x6)
*(3) —— te 7)
Fig. 2.1. Decimation-in-time (DIT) of a length N-DFT into two length-N/2 DFTs fol-
lowed by a combining stage. Digital Signal Processing in
= padix-2 DIF-FFT Algorithm
N
Wenow that, X(K) = >
_
x(n)W4!", Decimate it into 2 sequences,
N/2—1
x(k) = SO x(n)wh + * x(n) wh"
m0 n=N/2
Let m= n— N/2
n= N/2; m= N/2-N/2=0
n=N-~1; m=(N~1)-N/2=N/2-1
N/2-1 N/2-1
X(k) = SO x(n) + SO xCm-+ Navy?)
m0 mo
since m is dummy variable, replace m by n
N/2-1 N/2-1
X(k) = YO x(nywh+ x x(n N/2ywelnr/2)
3
ae ee 1
X(k) = SD x(n)wyr + & x(n N/2)WAr We?
m0
WEN gr /2TkNIND = emt =(-1)
N/2-1 NA
2 X(k) = SO x(my WAP + (= 1)" SO x(n + N/2) Gi
nao no
N/2~1
Xk) = > [x(n) + (-1)*x(0 + N/2)] WH?
n=O 7
Let us split even and odd sequences,
wat
X(2k) = % [x(n) + (-1)?*x(n + N/2)])wekr
N21
X(2k-+ 1) = S> (x(n) + (=1)4 x(n + N/2)) Wer?
mo
since, (~1)?* = 1 & (~1)?*+! = -1
N/2=1
X(2k) => b(n) + xn + N/2)WZk
no 44
Module.
pee (2k+1)0
X(2k +1) = YO [x(n) — x(n N/2)] WP
n=O
Let gi(n) = x(n) + x(n + N/2)
gan) = [x(n) — x(n + N/2)]Wa,
N21
X(2k) = gn (n) wir,
n=0
Nana
X(2k 41) = x g2(n) Whip
Let, N=8
gin) = x(n) + x(n+ 4); gon) = [x(n) — x(n 4) We
(0) = x(0) + x(4): 92(0) = [x(0) — x(4)]We
S1(1) = x(2) + x(8); g2(1) = [x(1) — x(5)]w3
91(2) = x(2) + x(6); 90(2) = [x(2) — x(6)]W3
94(3) = x(3) + x(7);, 923) = [x(3) — x(7)]We
This is called a decimation in frequency because the frequency samples are computed sep-
arately in alternating groups, and a radix-2 algorithm because there are two groups. Fig. 2.2
graphically illustrates this form of the DFT computation.
x0) x10)
xa) 4-point wey
ta) DFT | gy
x0) iecceeae
x)
x4)
ats) 4-point x5)
DFT | x)
x6)
x7)
x0)
Fig. 2.2. Decimation-in-frequency (DIF) of a ten:
7 igth N-DFT into two length-N/2 DFTS
preceded by a pre-processing stage, Digital signal Processing
Normal and Bit reversed Addressing
Vominn ——
_Normal input Bit reversed output
000 =0
001 =1
o10=2
011=3
100=4
101=5
110=6
111=7
000 =0
100 =
010 = 2
110=6
001
101=
011=3
1l=7
45
Peer ee
Bit-reversed addressing is used for simplifying and speeding-up the access to the arrays in
* 101+(N/2)=1014+100=011; bit reversed output = 011.
* 011+(N/2)=011+100=111; bit reversed output = 111.
Example 21:
{1,2,~1,2, 4,2,-1,2}
* Normal input = 000; bit reversed output = 000.
* 000+(N/2)=000+100=100; bit reversed output = 100.
100+(N/2)=100+100=010; bit reversed output = 010.
010+(N/2)=0104 f90=110; bit reversed output = 110.
110+(N/2)=110+4100=001; bit reversed output = 001.
001+(N/2)=0014100=101; bit reversed output = 101.
\
Using DIF-FFT algorithm compute DFT of the sequence, x(n)
FET algorithms. In bit reversed addressing, transposed the original binary bits representing the
normal index order by reversing their positions. The most significant bit becomes the least
significant bit and the least significant bit becomes the most significant bit, the next to the
| Most significant bit becomes the next to the least significant bit, and the next to the least
| Significant bit becomes the next to the most significant bit, and so on.
Let, N=23 = 8. -. N/2= 4 = 100. Perform the addition from left to right (—). 46
t= Solution:
Modlle-p
Given, x(0) = 1, x(1) = 2, x(2) = —1, x(3) = 2, x(4) = 4, x(5) = 2, x(6) = -1, (7) =2
(i) N/2 twiddle factors. Here N = 8
a 3 = 4 twiddle factors. W2 = 1;W = 0.707 — j0.707: Wg = —j; We = -0.707 — j0.707
(ii) Input is normal and output is bit reversed.
(iii) Butterfly operation
x0) xO
a x®
x) x2)
x3)
xo
x)
xa)
x
Fig. 2.3. Signal flow graph of Example 1.26. | Processing AT
Digital 5i9%!
Az x(0) + x(4) = § 1=A4+C =3 | X(0) =/4+J=11
Bea x(1) + (5) = 4 jJ=B+D=8 X(4) = (= We = =5
= x(2) + x(6) = =2 K=|A~ClWp=7 |XQ2)=K+L=7
D= x(3) + (7) =4 X(6) = (K - L)We =7
x(0) — x(4)|We = -3 X(1)=M+N=-3
x(1) — x(5)]Wg =0 |N=F+H=0 X(5) = (M-N)We =
¥(2) = x(6)|Wg =0_| P=[E - GlWe = -3 | X(3) = P+ Q = -3
ia)— (WS =O [Q=[F-H\MZ=0 [X(7) =(P- QW =-3
X(k)=(11, -3, 7, -3, -5, -3, 7, -3}
Example 22: Obtain &-point DFT of the sequence x(n) = {2,1,2,1} using radix-2 DIF-FFT
algorchm. Show all the results along signal flow graph.
| Solution:
| Given, (0) = 2, x(1) = 1, x(2) = 2, x(3) = 1, x(4) = 0, x(5) = 0, x(6) = 0, x(7) = 0.
(i) N/2 twiddle factors. Here N = 8
1.3 = 4 twiddle factors. WE = 1; We = 0.707 - j0.707; W3 = -j: W3 = -0.707 - j0.707
(\)) Input is normal and output is bit reversed.
| (il) Butterfly operation
>< _
b - d=(a-b) Wo
(iv) Number of stages = loga N = logy 8 = log 2? = 3logg2 = 3x 1= 3. ie Module
x0)
x1)
x2)
x3)
aa)
x5)
26)
x7
[Rane xa=2
+i=6 ]
Tea xay>x5)=1 = JW@ = 2
t (ay axl6) 22 X@)=K+L=0 |
K- Uwe =0 |
|
+N=2-73.414
M = NWR = 2 ~ 70.586
XG) = P+Q=2 +0586 |
X@)=(P- Que =27 73 418 |
707 = j0.707
2
0.707 — j0.707,
X(k)={6, 253.414, 0, 2+j0.586, 2, 2-j0.586, 0, 2+j3.414}
Example 2.3: Obtain 8-point DFT of the sequence x(n) = {1,1,1,1,0,0.0, 0} using radix2
DIT-FFT algorithm, Show all the results along signal flow graph.
*@ Solution:
Given, x(0) = 1, x(1) = 1, x(2) = 1, x(3) = 1, x(4) = 0, x(5) = 0, x(6) = 0, x(7)
(i) N/2 twiddle factors. Here N = 8
8
+13 = 4 twiddle factors. Wi = 1, Wd = 0.707 — 0.707; W3 = J; We = -0.707 — j0.707
(ii) Input is bit reversed and output is normal
(iii) Butterfly operation eaenal Processing
a cmat+Wrtb
b d=a-We'b
Wer 71
(w) Number of stages = logy N = log, 8 = log, 2? = 3log,2=3x1=
(0) + We x6 1] 1=A+wec =2 X(0) =1+WeM=4
weray=1 [T= B+WZ0 [RG)= T+ WN = 1-24
ZWwer6)=1 | K=A-Wee X(2)=K +WgP=0
=Wir(6)=1 | b= B-Wz0
X(5) = J-WIN = 1470414
X(6) = K=WP =0
X= b—W3Q= 1472414
X(0)
No ALT nc
Self
x@)
x)
xo)
x(6)
xm
Fig. 2.5. Signal flow graph of Example 1.28.
X(k) = (4, 1-j2.414, 0, 1-J0.414, 0, 14+j0.414, 0, 1+)2.414}
Evert 24. Chtain & point OFT of the sequence x(n) = {1,1,0,0, 1, ~1,0,0) using radix?
CAT-FET aicceithm, Show all the results along signal flow graph. 50 Modus;
= Solution:
Given, x(0) = 1, x(1) = 1, x(2) = 0, x(3) = 0, x(4) = -1, x(5) = -1, x(6) = 0, x(7) =0
x(0) ‘X(0)
x(a) xD
x(2) XQ)
x(6) x)
x(t) x
x6) x)
x0) x6)
x) x
Fig. 2.6. Signal flow graph of Example 1.29.
(i) N/2 twiddle factors. Here N = 8
wo ; = 4 twiddle factors. W2 = 1:Wg = 0.707 - j0.707: Wg = —j: W = -0.707 — j0.707
(ii) Input is bit reversed and output is normal.
(iii) Butterfly operation
a c=atWa'b
b d=a-Watb
(iv) Number of stages = log, N = logy 8 = 10g, 2? = 310g)? = 3x 1
A= x0) + Wexta) =O
B= x(0) — Wox(a)
EOEIAG
[= x(2)— wx
Bax) + wens
F = xl) ~ WoxG5
G = x(3) + Wox(7,
H=x(@)~Wex@) 0
1=A+WeC=0 [X(0)=1+WEM
414 —j1.414
586 — 71414
586 +1414 -
XM) =L- Wid = sales fi a4 processing
Digital 5¥ a
igh
X(K) 7
wi
Example? ion and FFA
+t computation 2
using dire
quired
&& Solution: _
irect computation:
a multiplication = N2 = 4096.
Complex addition = N(N — 1) = 4032
FET algorithm:
Compiex multiplication = # logy N = 192
Complex addition = Nlogs N = 384
ne
r=
Speed improvement factor = ios ¥
Number of real registers required for FFT:
Registers required for real part; N = 64
Registers required for imaginary part; N = 64
Registers required for twiddle factor; N = 64
Total registers required = 3N = 64 x 3 = 192.
Example 2.6: Calculate the IDFT of X(k) =
algorithm
(0.3414 - /1.414, 0, 0.586 ~ j1.414,0,0
hat is the speed improvement factor in ¢:
algorithm? Also mention the nu
51
586 + 1.414, 0,3 414+ j1 414}.
‘alculating 64-point DFT of a Sequence
Imbert of real registers re-
096 _
408 = 21.33
(32, —4,0,4) using inverse radie-2 DIT-FFT 52 Modules
‘xO
x0) = Z
xo 7 &
2h
10) = 10
xa)
x@)
Fig. 2.7, IDFT of X(k) (Example 1.31) using DIT-FFT algorithm.
Un) = PAG) AM Al) XB “48, Ge io}
Example 2.7: Compute the IDFT of the sequence X(k) = {48, 0,0, 0} using DIT-FFT algo.
nthm,
"= Solution:
Given, X(0) = 3, X(1) = 0, X(2) = 0, X(3) = 0.
A= X(0)+X(2) = 2 x(0) = 3[A+ 8] = 2
B=X(1)+X(3) =0 x(2) = }[A— BIW? =
= [X(0) — X(2)]We? = # | x(1) = FIC + D] =
0
= [X(1) - X(3)]W,* =0 | x(3) = LIC - DJW,? or
xo a
x02)
x)
30)
ome 28: Calculate the IDFT of X(k) = {8,0,0,0} using inverse radix-2 DIF-EFT algo
rithm
"© Solution: nal Processing
Digital Sig 53
Given, X(0) = 8, X(1) = 0. X(2) = 0, X(3) = 0.
A= X(0) + 4 °X(2) = 8 | x(0) = J[A + wy, %]
fe _A\4 x(1)
C= X(1) + Wy °X(3) = 0 |
d=X(1
Fig. 2.9. IDFT of X(k) (Example 1.33) using DIF-FFT algorithm.
x(n) = {2,2,2,2}.
se cecenrrenonnegrape
pie 2.9: Compute the IDFT of the sequence X(k) = {6,-2 + 2j,-2,-2 - 2/} using
s& Solution:
Given, X(0) = 6, X(1) = —2 + 2j, X(2) = -2, X(3) = -2 - 2).
A= X(0)+W,°X(2)=4 | x(0) = HA +We °C]
B=X(0) -W,°X(2)=8 [x)= HB +W,*O|=1
C = X(1) + W, °X(3) x(2) = }[A-W, °C] = 2
D= X(1) — Wy °X(3) = 47 | x(3) = 318 - Wa] = 3
x(n) = {0,1,2,3}
:
| Example 2.10: Bring out differences between DIT-FFT and DIF-FFT.
| «& Solution: 54
Fig. 2.10. IDFT of X(k) (Example 1.34) using DIF-FFT algorithm.
xa)
xa)
xe)
x00)
(0)
xD)
x)
x03)
(ii)
(iii)
(iv)
)
DIT-FFT
Reducing samples in time do-
main
Input is bit reversed while the
output is in normal order
Splits the two DFTs into even
and odd indexed input samples
Multiplication is done before
addition
Butterflies are defined on the
last pass of FFT
DIF-FFT
Reducing samples in frequency
domain
Input is in natural order while
the output is bit reversed.
Splits the two DFTs into first
half and last half of the input
samples
Multiplication is done after ad-
dition
Butterflies are defined on the
first pass of FFT
2.3 Memory Requirement and In Place Computations
Mody,
Consider the butterfly structure used for the computation of FET. From input values, x(")
new values A, B, C, etc. are calculated. Once these values are computed, there is no nee
to store input values, x(n). Thus, A, B, C, etc. values are stored in place of inputs, x(”)
This is called in-place computation. An “in place” FFT is simply an FFT that is calculate?
entirely inside its original sample memory. In other words, calculating an “in place” FFT does
not require any additional buffer memory. The main benefit of in place computation is that
reduces memory requirement,
2.4 Conclusions
In this chapter on FFT Analysis, the focus is on the essential elements that underlie thé
efficient computation of the DFT, The chapter commences by illuminating the concept of the ral Processing 55
ital Sig!
Digita <* and its pivotal role in FET algorithms. These tw:
“twiddle f2°%O" the bedrock of FFT techniques. The FET algorith
oe vets on the Radix-2 FFT algorithms, which h
a specific €
cessing. These algorithms, categorized into decin
al pro :
ddle factors, complex roots
ms are then unveiled, with
ave revolutionized the landscape
Mation-in-time and decimation-in-
of sign ts, offer a substantial reduction in computational complexity compared to the
tre en DET compotation. The chapter's exploration equips readers with the knowledge
straighter iently harness the power of the FET in transforming signals between the time
a aa pe a fundamental skill in the realm of DSP.
and frequen Fast Fourier Transform
3.7 Comparison between radix-2 DIT-FFT and DIF-FFT algorithms
algorithin
i | The time domain sequence n(n) is
decimated.
2 | Phe inpnt is in bit reversed order
| whereas the output is in normal
ordet
3. Incach stage of computation, the
phase factors Wy are multiplied
before addition.
4 If N = 2", then the algorithm
consists of v stages of
computations.
Total number of arithmetic
operations required are, a log, N
complex multiplications and
N log, V complex additions.
FT algorithm
‘The frequency domain sequence
X (h) is decimated.
‘The input is in normal order
in bit
whereas the output
reversed order
In each stage of computation, the
phase factors Wy are multiplied
cr addition. |
If N = 2", then the algorithm
consists of v stages of |
computations.
Total number of arithmeti¢
operations required are, 5 logy N
complex multiplications and
Nog, N complex additions.
3.8 Inverse-DFT using FFT
In the previous sections, we discussed the FFT algorithms for computing the DFT efficiently
These FFT algorithms can also be used to compute the inverse DFT (IDFT).
We have.
IDFT 2(n) =
N-1
& DPT x(k) = So a(uyive"
By comparing
two equations is the factor
algorithm for computing the DI
IDFT by making the following, changes.
Not
SY xcowy
ms
(3.40)
SkSN-1 (a)
“an (3.40) and Eqn. (3.41), we find that the only difference between th
and the sign of the power of the factor Wy. ‘Therefore an EFT
can be converted to an FET algorithm for computing t? igital Signal Processing ,
@ (i) Reverse the direction of flow-praph
@ (ii) Change the sign of the power of the factor Wy
«# (iii) Replace a(n) by N(F) and view versa
@ (iv) Multiply the output by factor
By performing, these steps on DIF-FF'T algorithin for computing DET, we obtain DIT-FET
algorithm for computing IDET.
The complete fHow-graph for computing IDF
3.12 below
using DI'T-FFT algorithin for N = 8 is shown
in F
We > > > — x(0)
1/8
xa ae x(4)
1/8
xe ae x(2)
18
xe ae x(6)
1/8
kde s—e x(1)
1/8
ore >—e x(5)
1/8
X(6)¢ ae x(3)
18
X70 > x(7)
Us
r using DIF-FFT algorithm for
Similarly, the complete flow-graph for computing UDI
3 below.
= 8 is shown in Fig. 3. 3, Vast Fourier Transform
X(0) 0——@e
x(0)
BY
ue KX
XR
Ny /XXN
pemmmeee Xs //\\
No /
x(7)
2(6
1 1 “1 1/8
Fig. 3.13: Flow-graph of DIF-FFT algorithm for IDFT computation for N = 8
4% Solution. The DIT-FFT algorithm is shown in Fig, B3.8.
Wy? = 1; Wy’ = 0.707 +30,707; Wy? = J, We* = -0.707 + 0.707
*, a(n) = {1,1,1,1,0,0, 0,0} 2 3-29
Digital Signal Processing
ges “Bid
@ Hiv2l+1=(L)Xx
@ 0 =(9)X
o=
@ FIFO +1 = (8)
mee © 0=(F)X
0=(9)t & @ IROL —1= (€)X
1=(@t@
@ Hirel-1= (Dx
r=(0)X ors wy
© PIPZEHE T= ()X
= (2)
mM
0=(9)r * PIFOL—1=(€)x
o=()r oe * FIFOL+1=(9)x
om
8
0=(r)t e~ © FIReo- T= (UY
T=(g) x 0=(9)x
L= (zt o= (OX
t= (pr o= (x
r= (ON
T= (ot
9-30.
Vous aimerez peut-être aussi