1 6. Analiza Fourier a semnalelor definite in timp discret Conceptele legate de timpul discret si metodele de investigare sunt proprii analizei numerice. Inca de pe timpul lui Newton (anii 1600) s-au cautat formule pentru rezolvarea numerica (aproximativa) a unor probleme de interpolare, integrare si derivare. Observatiile astronomice asupra miscarii corpurilor ceresti, permiteau determinarea pozitiei acestora la anumite momente de timp. Fiind data o secventa de observatii facute, se punea problema determinarii pozitiei viitoare a corpului ceresc. Problema a impulsionat studiul serilor temporale si printre altele, a condus la conceptul de eroare medie patratica minima.
Transcript
1
6. Analiza Fourier asemnalelor
definite in timp discret
Conceptele legate de timpul discret si metodelede investigare sunt proprii analizei numerice. Inca de pe timpul lui Newton (anii 1600) s-au cautat formule pentru rezolvarea numerica(aproximativa) a unor probleme de interpolare, integrare si derivare.
Observatiile astronomice asupra miscariicorpurilor ceresti, permiteau determinareapozitiei acestora la anumite momente de timp. Fiind data o secventa de observatii facute, se punea problema determinarii pozitiei viitoare a corpului ceresc. Problema a impulsionatstudiul serilor temporale si printre altele, a condus la conceptul de eroare medie patraticaminima.
2
Ca urmare a aparitiei si a dezvoltariicalculatoarelor electronice numerice, in anii '40 si mai ales în anii '50 s-au realizat progreseimportante în tehnicile de prelucrare a semnalelordiscrete în general si in utilizarea analizei Fourier în timp discret în special.
Pe masura ce impactul calculatorului numeric in prelucrarea semnalelor a crescut, s-a realizat o intrepatrundere si unificare a metodelor specificetimpului discret si timpului continuu.
Aparitia, la mijlocul anilor '60 a algoritmuluiFFT, de transformare rapida, a facut prelucrareanumerica deosebit de eficienta.
Astazi, practic nu se poate concepe prelucrareasemnalelor fara ajutorul calculatoruluielectronic numeric, devenit mai mult "bun de larg consum" decat un instrument de cercetareteoretica.
3
5.1 Raspunsul sistemelordiscrete liniare si invariante in timp la exponentiala complexa
de modul unitar[ ] [ ]
[ ] [ ] [ ] ( ) [ ]
( ) [ ] [ ] ( ) ( ) ( )
0
00 0 0
0 00
0
0 0
j n
j n kj n j n j k
k k
j nj nj k
k
x n e n
y n h n e h k e e h k e
H h k e y n e H H e
ΔΩ
∞ ∞Ω −Ω Ω − Ω
=−∞ =−∞∞ ⎡ ⎤Ω +Φ ΩΩ− Ω ⎣ ⎦
=−∞
= =Φ
= ∗ = ⋅ = ⋅ ⋅
Ω = ⋅ ⇒ = ⋅ Ω = Ω ⋅
∑ ∑
∑
Exponentiala complexa discreta este functieproprie pentru SLITD.
( )
[ ] [ ] [ ]
[ ] ( ) [ ]
0 00
; k
j n j nd
j nk k k
k
k k kk
S e H e
n e x n a n
y n a H n
Ω Ω
Ω
= Ω
Φ = = Φ ⇒
= Ω Φ
∑
∑
4
5.2 Seria Fourier in timpdiscret pentru semnale discrete
periodice[ ]
[ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] ( ) ( )
Intr-o perioada a semnalului exista numai valori:
Semnalul discret este periodic de perioada
daca ,
0 1 1 , 0 1 1 etc.
unde este reprezentarea lui
inN N
x n N
x n N x n n Z.
x ,x ,...,x N x N x , x N x
x n x n n n
N+ = ∀ ∈
− = + =
⎡ ⎤= ⎣ ⎦
( )
clase de resturi modulo Pentru 0 restul trebuie sa fie pozitiv.N
N.n n<
[ ]2
Spatiul semnalelor discrete si periodice de perioada are dimensiunea Bazele din acest spatiu sunt
Multimea , 0 1
este o baza ortogonala in spatiul f
dimensionale
n
.
u cti
jk nNk n e k
N.
N
N
N
N
kπ⎧ ⎫
⎪ ⎪φ = ∈ ≤ ≤ −⎨ ⎬⎪ ⎪⎩ ⎭
ilor discreteperiodice de perioada N.
5
[ ] [ ] ( )( )( )
( )
( )
( )
[ ] [ ]
[ ] [ ]
00 0
0
0 0
0 0
0
1 1
0 02
1
0
Demonstratie2 Se noteaza
1 1 , 1 1
Pentru :
Deci:
0
Ortogonalitatea.
nN N j k ljk n jl nk l
n nj k l N j k l
j k l j k l
N jk n jk nk k
n
k l
.N
n , n e e e
e e l ke e
k l
n , n e e N.
N , k ln , n
,
− − − ΩΩ − Ω
= =− Ω − π
− Ω − Ω
− Ω − Ω
=
πΩ =
φ φ = = =
− −= = ≠
− −=
φ φ = =
=φ φ =
∑ ∑
∑
[ ] [ ]2 22si in 0 1k n N l ,N .
k l⎧
φ = −⎨ ≠⎩
[ ]
( ) ( )
01
0
0 0
Orice semnal periodic de perioada se poate exprima in forma
Sistemul de ecuatii liniare cu necunoscute are determinantul :
1 ...
1 ...
1 ...=
NN -
N -
N -
N N N
N Nc ,c ,...,c
. . . . .
. . . . .
. . . . .
... ... .
−
− − −
φ φ φ
φ φ φ
φ φ φΔ =
φ −φ φ −φ φ −φ φ −φ φ −φ
Nici una dintre diferentele pentru nu estenula, in consecinta 0 si sistemul are solutie unica.Deci multimea considerata este In consecinta ea e
si compste o baza ortogon
leta
.l
aa.
k l , k lφ −φ ≠
Δ ≠
-1 0 1φ =
01
je Ωφ =
Im φ
Re φ( )0 1
1j N
N e Ω −−φ =
( )( ) ( )( ) ( )
1 0 2 0 1 0
2 1 1 2 N
N N
...
...−
− −
Δ = φ −φ φ −φ φ −φ
φ −φ φ −φ
7
[ ]
[ ] [ ][ ] 2
2
Descompunerea semnalului in baza consideratapoate fi privita ca si descompunerea acestui semnalperPentru calculul coeficientilor poate fi folosita si re
iodic in serilat
e Fourier.ia:
1k
k
k
x n
cx n , n
n
φ= =
φ[ ]
[ ] [ ]( )
[ ]
( ) ( ) ( )
0
21
021 2
0
1
0 ;
1 ; =
1 , 0 1
Diagramele spectrale de modul
si de faza su
sau
nt periodice de perioada
N
N j k N nNk k N
n
N jk n j NN kn
k
N jk n
n
k k N k
k
k
x n c c x n eN
x n e e c k N -N
c
x n eN
c c c
Arg c N.
c .
π− − ++
=π− − − π
− − Ω
=
=
+
↔ = ⋅
= ⋅ ⋅ = ≤ ≤
=
⋅
=
∑
∑
∑
Exemple[ ]
( )
1
2 2 21
1
2
2
1 1 , , toti ceilalti coefici
1. Semnalul are perioada .
2 1 1 1 1 =2 2 2
enti fiind nuli.2 2
2
j n j n j n j N nN N N N
N
N
sin n e e e eN j j j
x n sinN
c cj j
j
n
π
−
π π π− −
π⎛ ⎞= ⎜ ⎟⎝
= −
⎠
=
π−
= −
k
k
5 1c c− = 1 5c c− = 1c5
12
c = 7 5c c=
5 1arg argc c− =
1 5arg argc c− =
1arg2
c π= −
5arg2
c π=
-6 -2 0 1 5 6 12
-6 -2 0 1 5 6 12
8
Raspunsul sistemelor discrete liniare si invariante in timp la
semnale armonice ( )
[ ] [ ] [ ]
[ ] ( ) [ ]
[ ]
[ ] ( ) ( )
[ ] ( ) ( ) ( )
0 0
0 0
0 0
0
0 0
0
0 0
0 00 0
0 0 0
;
2 2
2 2
k
j n j nd
j nk k
k
kk
j n j n
j n j
k
n
k
k
S e H e
n e n
n
A Ae e
A Ay n H
x n a
y n a H
x n A cos n
y n A H
e H
co
e
s n arg H
Ω Ω
Ω
Ω − Ω
Ω − Ω
= Ω
Φ = = Φ ⇒
= Φ
= ⋅ + ⋅
= Ω ⋅ + ⋅
Ω
= Ω
= ⋅ Ω Ω + Ω
−Ω ⋅
⋅
∑
∑
Raspunsul in frecventa al sistemelor linare si invariante in
timp discret de tip RFI
( ) [ ] j k
kH h k e
∞ − Ω
=−∞Ω = ⋅∑
[ ] kh k b=
D D D
+
[ ]x n [ ]1x n − [ ]2x n − [ ]x n M−
b1 b2 b0 bM-1 bM
[ ]y n
9
[ ]
[ ]( ) ( )
( )
2 2 2 21 1
2 22
2
2
0 1
2
1 2
2
2.
1 11 2 22 2
1 12
2 2 41 42
1 11
2
2 ; ; ; 22 2 2 2
j n j N n j n j N nN N N N
j n j N nj jN
N
N
N
x n e e e ej j
e
x n sin n cos n cos nN N N
j jc ; c c c c
e e e
.j j
π π π π− −
π π−
− −
π π −
π π π π⎛ ⎞ ⎛ ⎞ ⎛ ⎞= + + + +⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
=
= + − +
= + = = − = −
+ +
+ +
Exemple de descompunere
3.
1 11
1
2 2 22
0
1
10
1 1 ; 0 1
Pentru 0 cei 2 1 termeni ai sumei sunt egali cu 1 si deci:2 1.
nN Njk n jk N jk
N N Nkn N n
c e e e k NN N
k NNcN
π π π− −
=− =
⎛ ⎞⎜ ⎟= ⋅ = ⋅ ⋅ ≤ ≤ −⎜ ⎟⎝ ⎠
= ++
=
∑ ∑
10
( )
( ) ( ) ( )
( )
1 1 1
1 1 1
2 2 22 1
2
2 1 2 1 2 1
11
Pentru 1 1 :
1
1
sau :2 12 2 1
1 12 222 2
jk N jk N jk NN N N
kjk
N
jk N jk N jk NN N N
jk jk jkN N N
k
k N
e e ecN N
e
e e e
,
e e e
Nsin k sin NNc
N Nsin k sinN
π π π− +
π−
π π π− + + − +
π π π− −
≤ ≤ −
−= ⋅ = ⋅
−⎡ ⎤⎢ ⎥−⎢ ⎥⎣ ⎦⋅
⎡ ⎤⎢ ⎥−⎢ ⎥⎣ ⎦
+π Ω⎛ ⎞ ⎡ ⎤+⎜ ⎟ ⎢ ⎥⎝ ⎠ ⎣ ⎦= ⋅ = ⋅π Ω⎛ ⎞
⎜⎝
2 ; 1 1k
N
k N .πΩ=
≤ ≤ −
⎟⎠
-1 0 1 2 3 4
h[n]
n
1/4
[ ] [ ] [ ]
( )( )
2sin
212sin
;1 ,1,..., ,1
1
1111
Ω
⎥⎦⎤
⎢⎣⎡ Ω
+=Ω
−−σ−+σ=−−==
NH
NnNnnhNNkN
bk
11
Trunchiind seria unui semnal periodic discret, se obtine o aproximare a acestuia. Ea devine cu atat mai buna cu cat numarul de termeni insumati se apropie de N. Atunci cand se insumeaza toti cei Ntermeni, semnalul obtinut este chiar x[n], fara nicio eroare. Pentru ilustrarea efectului trunchieriiseriei, fie semnalul dreptunghiular din exemplul 3, în cazul particular N = 9 si 2N1+1 = 5 . Se obtine : c0 = 0,556 , c1 = c8 =0,32 , c2 = c7 = -0,059 ,
c3 = c6 = -0,111, si c4 = c5 = 0,073.
[ ]
[ ]
[ ]
[ ]
[ ]
29
1
2
3
4
Pentru 1, 2, 3 si 4 avem:20 556 0 6492 40 556 0 64 0 118 ,9 9
2 40 556 0 64 0 1189 9
60 222 ,9
2 40 556 0 64 0 1189 9
60 222
M jk nM k
k Mx n c e
M
x n , , cos n,
x n , , cos n , cos n
x n , , cos n , cos n
, cos n
x n , , cos n , cos n
, cos
π−
=−= ⋅
=π
= +
π π= + −
π π= + −
π−
π π= + − −
π
∑
80 1469 9
n , cos n.π+
12
Proprietatile seriei Fourier in timp discret
[ ] [ ] [ ] [ ]
[ ]
[ ] ( )
[ ]
02
0
1. Liniaritatea
;
2. Translatarea in ti
mp
3. Conjugarea complexa
4. Reflectarea semnalului
*
yxk k
jk n xNk
*
y
x x
k
xk
x
k
k k
ax n by n ac bc
x n
x n c y n
n e c
x n C c c
x n c
c
π−
−
−
+ ↔ +
⎧ ⎫⎪ ⎪− ↔ ⎨ ⎬⎪ ⎪⎩ ⎭
−
↔
↔
↔ ⇒
∈ =
13
( ) [ ] [ ] [ ]
( ) [ ]
( ) [ ] ( )
[ ]
este perio
5. Modifica
dic de peri
rea scarii timpului
; daca ; - periodic de perioada
0 ; in rest
; da
oad
ca
0 ; in rest
; da
a
ca 0 ;
m
m
N ' mN
m
x n / m n mx n
x n N ' mN
x n N.
x n N ' / m n N ' mx n N '
x n
.
/ m N n m=
⎧= ⎨⎩
⎧ + +⎡ ⎤⎪ ⎣ ⎦+ = ⎨⎪⎩+
=
=
M
M
M
[ ]( ) [ ]
( )
in rest
; daca 0 ; in rest
1mx xkk
m
c c .m
x n / m n mx n .
⎧=⎨
⎩⎫⎧ ⎪= =⎨ ⎬
⎩
=
⎪⎭
M
[ ]
[ ] [ ]
[ ] [ ] [ ]
[ ] ( )
[ ] [ ][ ] [ ]
0
0
2
1
0
6. Modularea semnalului
7. Produsul a doua semnale
8. Convolutia periodica
jk n xNk k
yxk k
N
Nk
yxk k
e x n c .
x n y n c c .
z n
z n N z n
x n y n .
x k y n k .
x n y n Nc
.
c .
π
−
−
=
↔
⋅ ↔ ⊗
= ⊗
⎡ ⎤= −⎣ ⎦
=
↔
+
⊗
∑
14
9. Diferentierea discreta
[ ] [ ]2
1 1 .jk xN
kx n x n e cπ
−⎧ ⎫⎛ ⎞⎪ ⎪− − ↔ −⎜ ⎟⎨ ⎬⎪ ⎪⎝ ⎠⎩ ⎭
10. Insumarea in domeniul timp
[ ] [ ] [ ]0 020; 0.1
y n ; , xn
x yk
j km N
cc x m y n ce
π−=−∞
⎧ ⎫⎪ ⎪= = ↔ =⎨ ⎬⎪ ⎪−⎩ ⎭
∑
11. Proprietati specifice semnalelor reale
[ ] [ ] [ ] ( ) ( )
[ ] [ ]
* **
Re Re Im Im .
Re Im .
; ; ;
;
x x xk k k
x x x x x xk k k k k k k k
x xp k i k
x n R x n x n c c c
c c Arg c Arg c c c c c
x n c x n j c
−
− − − −
∈ ⇒ = ⇒ = =
= = − = = −
↔ ↔
[ ] [ ]21 12 2
20 0
12
0
Relatia lui ParsevalN N
kn k
N
kk
x n x n N c ;
P c .
− −
= =−
=
= =
=
∑ ∑
∑
15
Transformarea Fourier în timpdiscret pentru semnale discrete
[ ] [ ]k
x n x n kN∞
=−∞= −∑%
[ ] [ ] [ ]
( ) [ ] ( )
[ ] ( ) ( )
( )( )
0 0
2 2 2
0
0
1
0
0 0
1 1 ;
1 2 ; , ;
1
2
2
1
1
2
2
jk n jk n jk nN N N
k kk N k N n
j nk
n
jk n jk n
k N k N
x n c e c x n e x n e
sin NX .
s
N N
X x n e c X kN N
x n X k e eN
in
X k
π π π∞− −
∈< > ∈< > =−∞∞
− Ω
=−∞
Ω Ω
∈< > ∈< >
Ω⎡ ⎤+⎢ ⎥⎣ ⎦Ω =
= = =
πΩ = = Ω Ω =
= Ω = Ω Ωπ
Ω
∑ ∑ ∑
∑
∑ ∑
% %
%
Un termen al sumei reprezinta o arieelementara. Suma intreaga aproximeaza aria de sub curba intre abscisele –π si π.
[ ]x n%
16
[ ] ( )
[ ] [ ] ( )
( ) [ ]
( ) [ ] [ ] [ ]
( )
( ) ( ) [ ] ( )
00 0
2
1
1 ; 2
Transformata Fourier in tim
1 ;2
Functia este
p di
continua.
scret
1
0
jk n
k N
j n
n
j n
n n
j n j
j n
n
n
N
x n X k e
X x n e
X x n e x n x n
X X x n
x n lim
e
x n X e d
X
e
X
Ω
∈< >
∞− Ω
=−∞
∞ ∞− Ω
=−∞ =−∞
∞− Ω − ΔΩ
=−∞
Ωπ→∞
= Ω Ωπ
Ω =
Ω ≤ ⋅ = =
Ω + ΔΩ − Ω
= = Ω
= −
≤ Ω
π
Ω
+
Ω
∑
∑
∑ ∑
∑
∫
%
%
( ) ( ) [ ]( ) ( )
[ ]
( ) ( )
1
0
0
0
2 ;
0
1 0;j n
n
X x n
lim X X
x n
l
l
im X X .
im e
ΔΩ→∞
− ΔΩ
ΔΩ
ΔΩ→
→=−∞
ΔΩ − Ω ≤
≤ Ω+
Ω+
ΔΩ
ΔΩ
− Ω ≤
− =
=
≤
Ω
∑
( )0kNc X k= Ω
( ) [ ] ( ) [ ] ( )
[ ] ( ) [ ]
( ) [ ]
2
2
2
2 ;
Cazul semnalelor de energie finita
0
2 j n j
Nj n
N n N
n j n
n n
Nj n
N n N
X X
x n
x n e x n e e
lim X x n e ,l
X l.i.m x n e .− Ω
→∞ =−
∞ ∞− Ω+ π − Ω − π
=−∞ =−∞
− Ω
→∞ =−
Ω+ π Ω
∈
Ω =
=
Ω − ⋅ =
⋅
= =
∑
∑ ∑
∑
17
[ ] [ ] [ ]
( )( )
1 1
1
1 1
2 12
2
. x n n N n N ;
sin NX
sin
= σ + −σ − −
Ω⎡ ⎤+⎢ ⎥⎣ ⎦Ω =Ω
Tema de curs
Reprezentati grafic spectrul obtinut pentru N1=3.
Exemple
[ ] [ ]
( ) [ ]
[ ] [ ]
( ) [ ] ( )
( ) ( )( )2
0
0
1
, 1
1
2. ;
3.
, 11
1 ; 11 2
n
j
j n
n
nn j n j
n n
x n n
X .
x n a n a ,
Xae
a sinX Arg X arctga cosa
n e e
a n e ae a
o a
.
c s
∞− Ω
=−∞
∞ ∞− Ω − Ω
=−∞− Ω
=
= δ
Ω =
= σ <
Ω−
Ω
= δ =
=
⎛ ⎞Ω = Ω = ⎜ ⎟Ω −⎝ ⎠− Ω+
σ = = <
∑
∑ ∑
18
( ) ( )( )2
1 ; 11 2
a sinX Arg X arctga cosa cos a
Ω⎛ ⎞Ω = Ω = ⎜ ⎟Ω −⎝ ⎠− Ω +
Transformarea Fourier in timpdiscret pentru semnale discrete
Raspunsul in frecventa al sistemelor discrete liniare si
invariante in timp
[ ] ( ) h n H .↔ Ω
h[n]x[n] [ ] [ ] [ ]y n x n h n= ∗
H(Ω)X(Ω) ( ) ( ) ( )Y X HΩ = Ω Ω
Calculul raspunsului unui sistemdiscret liniar si invariant in timp la
un semnal de intrare discret si periodic
[ ] [ ] ( )
[ ]
[ ] ( ) ( ) [ ] ( ) ( )
[ ] ( )
0 0
0 00 0
0 0 0 0
1 1
00 0
2 2
0 1 1 1
0 0
0
;
2 ; si 2 2 2
2 2
2
N Njk n jk n
k kk k
j jj jN N
N
j j n j j n *
x n c e y n c H k e
A A Ax n Acos e e c e c c e .N
A Ay n e H e e H e ; h n R H H .
Ay n H e
− −Ω Ω
= =
π π⎛ ⎞ ⎛ ⎞+ϕ − +ϕ⎜ ⎟ ⎜ ⎟ ϕ − ϕ⎝ ⎠ ⎝ ⎠− −
ϕ Ω − ϕ − Ω
= ⇒ = Ω
⎛ ⎞π⎛ ⎞ ⎜ ⎟= + ϕ = + = = =⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎜ ⎟⎝ ⎠
= Ω + −Ω ∈ ⇒ Ω = −Ω
= Ω
∑ ∑
( ) ( ) ( )
[ ] ( ) ( )
0 0 0 0 0 00
0 0 0 0
2j n j nA H e ,
y n A H cos n .
⎡ ⎤ ⎡ ⎤Ω +Φ Ω +ϕ − Ω +Φ Ω +ϕ⎣ ⎦ ⎣ ⎦+ Ω
⎡ ⎤= Ω Ω +Φ Ω + ϕ⎣ ⎦
24
Cazul sistemelor caracterizatede ecuatii cu diferente finite
liniare si cu coeficienti constanti
[ ] [ ]
( ) ( ) ( ) ( )
( ) ( )( )
( )
( )
00 0
00 0
00
0
, 0 ,
0
; 0
N N
k kk k
k kN Nj j
k kk k
M kjk
kN kj
kk
a y n k b x n k a
Y a e X b e , a .
b eY
H a .X
a e
= =
− Ω − Ω
= =
− Ω
=
− Ω
=
− = − ≠
Ω = Ω ≠
ΩΩ = = ≠
Ω
∑ ∑
∑ ∑
∑
∑
Exemple
[ ] [ ] [ ] [ ] [ ]
( ) ( )( )
( )
( )
[ ] ( ) [ ] [ ]
2 1 2
41,2
1 21 2
1 2
1 1 2 2
i)
2 11 2 1 .2 4
1 1 ,2 1 1 11
2 4
2 114 2
1 2 2 1 ; .2 21 1
2 1 24 42
j j
j jj j
j
,j j
n nn
y n y n y n x n x n
e eHe ee e
j e .
A AH A je e
n nh n A A n ... cos sin n .
− Ω − Ω
− Ω − Ω− Ω − Ω
π±
− Ω − Ω
− − + − = − −
− −Ω = =
−α −α− +
α = ± =
−Ω = + = ±
−α −α
+ π⎛ ⎞= α + α σ = = π − σ⎜ ⎟⎝ ⎠
25
( )
( )
[ ] [ ]3
ii)3
1 11 12 84 1 ;1 11 1
2 81 142 2
j j
j j
n n
H .e e
He e
h n n .
− Ω − Ω
− Ω − Ω
Ω =⎛ ⎞⎛ ⎞− −⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠
Ω = −− −
⎛ ⎞= − σ⎜ ⎟⎝ ⎠
[ ] [ ] [ ]
( ) [ ] [ ]
iii)1 , 1
1 .1
nj
y n ay n x n a .
H h n a nae− Ω
− − = <
Ω = ⇒ = σ−
26
[ ] ( ) ( ) ( )
[ ] [ ]
2
poate fi determinata aplicand proprietatea P9 de insumare in domeniul Transformata Fourier in timp discret a treptei un
timp:
01
Pentru membrul drept al re
it
latiei ante
are
r
n
jk
Xx k X .
ex k k
π− Ω=−∞
Ω↔ + π δ Ω
−
= δ
∑
( ) ( ) ( ) ( ) ( )
( ) ( )( ) ( )
( ) ( )
[ ] [ ] [ ] [ ]
2
2
1
2
ioare devine:
;
111 1
1 1 11 11 1
1
1 11 1 1
1
j j
j j
nn
j , S H X
S .aae e
aS ... ;a aae e
a as n a n n n .a a
Xe
a
σ
π− Ω − Ω
π− Ω
σ π
+
Ω
− Ω
− Ω = Ω Ω
πΩ = + δ Ω
−− −
⎡ ⎤Ω = = − + + πδ Ω⎢ ⎥− −− −⎣ ⎦
−= −
Ω = + πδ Ω−
σ + σ = σ− − −
Raspunsul indicial
Sisteme discrete liniare si invariante in timp de ordinul
intai si doi
( )( )
( )
( ) ( )
( ) ( )
( )
22
1 20 0 1 1
20 2
1 20 1 1
20 1
21 11 2
1 1 =
1 1
Fie
1 1
P M PM k j j jjk k kk
k k kN Q N Qkj j j j
k k k kk k k
jQ N QN k k k
j j jN k kk k k
e e eb ebHa
a e e e e
M N.
b e AHa e e e
−− Ω − Ω − Ω− Ω
= = =−
− Ω − Ω − Ω − Ω
= = =
− Ω −
− Ω − Ω − Ω= =
+ β +β + μΩ =
+ α + α + η
=
γ + γΩ = + +
+ α + α + η
∑ ∏ ∏
∑ ∏ ∏
∑ ∑
27
Sisteme de ordinul intai[ ] [ ] [ ] ( ) [ ] [ ]
[ ] [ ]1
11 , 1 . ; .1
1 (conform exemplului iii))1
nj
n
y n ay n x n a H h n a nae
as n n .a
− Ω
+
− − = < Ω = = σ−
−= σ
−
28
Sisteme de ordinul doi
[ ] [ ] [ ] [ ]
( ) ( )( )[ ] [ ]
( ) [ ] ( )
[ ]( ) ( )
2
2 2
1
i)
2 1 2 , 0< <1 , 01 1 =
1 2 1 1
21
, 0,
1 1
2 21
j j j j j j
jj n jn j n jn
n
nj jj j
j
y n cos y n y n x n ,
Hcos e e - e e - e e
eh n e e e e nj sin
sin nn .
sin
e ee es nj sin j sine
− Ω − Ω θ − Ω − θ − Ω
θθ θ − θ − θ
+θ − θθ − θ
θ
− ρ θ − + ρ − = ρ ≤ θ ≤ π
Ω =− ρ θ + ρ ρ ρ
⎡ ⎤= ρ − ρ σ =⎣ ⎦θ
+ θ= ρ σ θ∈ π
θ
− ρ − ρ= −
θ θ−ρ[ ] ( )
1
; 0,1
n
j n .e
+
− θ
⎡ ⎤⎢ ⎥σ θ∈ π⎢ ⎥− ρ⎢ ⎥⎣ ⎦
( ) ( )( )
( )( )
[ ] ( ) [ ]
( )( ) ( ) ( ) ( )
( )
[ ]( ) ( )
( ) [ ]
2
22 2 2 2
2 2
11 1
01 1 .
1
1 1 1 11 1 11 1 11
1 111 1
j j j j
n
j
j jj
n n
H- e e - e e
.
H h n n ne
S .e ee
s n n n .
θ − Ω − θ − Ω
− θ
π− Ω − Ω− Ω
Ω =ρ ρ
θ =
Ω = ⇒ = + ρ σ−ρ
ρ ρ πΩ = − − + + δ Ω
−ρ −ρ −−ρ −ρ −ρ−ρ
⎡ ⎤ρ ρ⎢ ⎥= − ρ − + ρ σ−ρ⎢ ⎥− ρ −ρ⎣ ⎦
29
( )( )
[ ] ( )( ) [ ]
[ ]( ) ( )
( ) ( )( ) [ ]
2
2 2
1
1
1 ,
1 111 1
j
n
n n
.
H .e
h n n n
s n n n .
− Ω
θ = π
Ω =+ ρ
= + −ρ σ
⎡ ⎤ρ ρ⎢ ⎥= + −ρ + + −ρ σ+ ρ⎢ ⎥+ ρ + ρ⎣ ⎦
[ ] ( ) [ ]1 .nh n n n= + ρ σ
[ ] ( ) [ ]1n sin nh n n .
sin+ θ
= ρ σθ
[ ] ( )( ) [ ]1 nh n n n .= + −ρ σ
30
( )( ) ( )
( ) ( )
22 2 2 2 2 2
2
1
4 4 1 1 4
21 2 2
H .cos cos cos cos
r sin a r cosarctg .
r cos cos r cos
Ω =ρ Ω− ρ + ρ θ Ω + −ρ + ρ θ
θ − ΩΦ Ω = −
− θ Ω + Ω
[ ] ( ) [ ] [ ] [ ]
( )( ) ( )( )
[ ] [ ]
[ ] ( )( )
1 2 1 2 1 2 1 2
21 2 1 2 1 1
1 21 2
1 2 1 21 21 1
1 2
1 2
2 22 11 2
1 2 1 2 1 2
ii)1 2 , 1 1
1 11 1 1
1 1 ,1 1
1 11 11 1
j j j j
j j
n n
n n
y n a a y n a a y n x n a ,a R, a ; a ,
Ha a e a a e a e a e
a a a aa a a aa e a e
a ah n n .a a
a as n a aa a a a a a
− Ω − Ω − Ω − Ω
− Ω − Ω
+ +
+ +
− + − + − = ∈ < <
Ω = = =− + + − −
= − ≠− −− −
−= σ
−
− −= + −
− − − −[ ]
( )( )
[ ] ( ) [ ]
[ ]( ) ( )
( ) [ ]
1 2
2
2 2
1 ; , 11
1 ,
1 111 1
j
n
n n
n .
a a a
H a R a ,ae
h n n a n
a as n a n a n .aa a
− Ω
⎡ ⎤σ⎢ ⎥
⎣ ⎦= =
Ω = ∈ <−
= + σ
⎡ ⎤⎢ ⎥= − + + σ
−⎢ ⎥− −⎣ ⎦
31
Functia de corelatie. Densitateaspectrala de putere si de
energie a semnalelor discrete
[ ] [ ] [ ]
[ ]
[ ] [ ] ( )0 000 0
1
0
1
0 0
12 1
Daca semnalul este periodic de perioada
Semnale de energie infinita dar de putere medie finita.
atunci:
12 1
N Njm njk n jl n*
k x l mNk l
N
xN n N
R k lim x* n x n k .N
x n N ,
x n c e ,R k lim c e c eN
− −Ω +Ω − Ω
=
→= =
∞
∞
→ −=
=+
+
=
+
∑ ∑
∑
( )( )( )
0
0 00 0
1
0
1 1
0 0
12 1
NNk
n N mN N N
j m l n jm k*l m
N l m n Nlim c c e e .
N
−
=− =
− −− Ω Ω
→∞ = = =−
⎛ ⎞=⎜ ⎟⎜ ⎟
⎝ ⎠⎛ ⎞
= ⎜ ⎟⎜ ⎟+ ⎝ ⎠
∑ ∑
∑ ∑ ∑
( )
( )
[ ] ( )
0
0 00 0
00
0
0
1 1
0 01
2
0
Dar:
2 12
22 1
12 1
Nj m l n
n N
N N Nj m l n jm k*
x l mNl m n N
Njm k
mm
m lsin N, m l
m le sin
N , m l
R k c c lim e eN
c e .
− Ω
=−
− −− Ω Ω
→∞= = =−
−Ω
=
⎧ −⎡ ⎤Ω +⎪ ⎢ ⎥⎣ ⎦⎪ ≠⎪ −= ⎛ ⎞⎨ Ω⎜ ⎟⎪ ⎝ ⎠⎪+ =⎪⎩
⎛ ⎞= =⎜ ⎟⎜ ⎟+ ⎝ ⎠
=
∑
∑ ∑ ∑
∑
32
[ ] [ ] ( )
( )
0 0 0 000
0 0 00 0
1 1 1 1
0 00 0 0 0
1 1 1
0 0 0 0
Un alt semnal, cu aceasi descompunere in serie Fourier este:
1 1
1
N N N Njm n kjl n
l mn n l m
N N Nj m l n jm k
l m ml m n
x* n x n k c *e c eN N
c *c e e cN
− − − −Ω +− Ω
= = = =
− − −− Ω Ω
= = =
⎛ ⎞⎛ ⎞+ = ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟
⎝ ⎠⎝ ⎠⎛ ⎞
= =⎜ ⎟⎜ ⎟⎝ ⎠
∑ ∑ ∑ ∑
∑ ∑ ∑
[ ]
00
0
12
0
deoarece suma dupa reprezinta dezvoltarea in serie Fourier a lui
Njm k
m
N
e .
n m l .
−Ω
=
δ −
∑
[ ]
[ ] [ ] ( )
[ ]
0 00
0
01 1
0 0
2
2
0
Teorema Wiener-Hin
Functia este periodica de perioada
cin
si:
1
xN N
jm kx mN
m
n m
x
R k N
R k x* n x
R c .
n k c eN
k
− −Ω
= =
⎡ ⎤
↔
= + =⎢ ⎥⎣ ⎦∑ ∑
33
Proprietati ale functiei de corelatie a semnalelor discrete
periodice
[ ] [ ]
[ ]
[ ] ( )
0
0
12
00
12
00
0
22
N
x x mm
x
N
x x mm
R R lN P c ;
R k P;
R k S c k .N
−
=
−
=
= = =
≤
⎛ ⎞π↔ Ω = π δ Ω −⎜ ⎟
⎝ ⎠
∑
∑
34
Proprietati ale functiei de corelatie a semnalelor discrete neperiodice de energie infinita
dar de putere medie finita
( ) [ ]
[ ] ( )2
102
x x
x x
S R k ,
P R S d .π
Ω ↔
= = Ω Ωπ ∫
Functia de intercorelatiepentru semnalele discrete de energie infinita dar de putere
medie finita[ ] [ ] [ ]
[ ] [ ]
[ ] [ ] [ ]0
0
0
1
0 0
In cazul a doua semnale periodice de aceasi perioada
Definitia intercorelatiei semnalelor discrete, periodice de aceasi
12 1
pe
1
rioada:
N
xyN n N
xy xy
N
xyn
R k lim x* n y n k .N
R k N R k .
R k x* n y n k .N
N :→∞ =−
−
=
= ++
+ =
= +
∑
∑
35
Proprietati
[ ] [ ]
[ ] [ ] [ ]20 0
Pentru functia de autocorelatie.
*xy yx
xy x y x y
xy xx x
R k R k .
R k R R P P .
x y R R R
− =
≤ =
= = =
Functia de corelatie pentrusemnalele discrete de energie
finita
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] ( ) ( ) ( )
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
Masoara gradul de asemanare a celor doua semnale.
- densitate interspectrala de energie,
functia de autocorelatie-
xyn
xy XY
xn
R k x* n y n k x* k y k x* k y k .
R k X * Y S
x n y n , R k x* n x n k x k x k .
∞
=−∞
∞
=−∞
= + = − ∗ = ∗
↔ Ω Ω = Ω
= = + = ∗
∑
∑
(
(
36
Proprietati ale functiei de autocorelatie a semnalelordiscrete de energie finita
[ ] ( ) ( )
[ ] ( )
[ ]
2
2
2
Teorema Wiener-Hincin
102
Functia este para si isi atinge maximul in origine.
x x
x x
x
R k X S .
W R X d .
R kπ
↔ Ω = Ω
= = Ω Ωπ ∫
37
Relatia intre densitatile spectrale de putere si de
energie ale semnalelor ce trecprin sisteme discrete, linare si
invariante in timp[ ] [ ] [ ]( ) ( ) ( )
[ ] [ ] [ ]
sau
2
densitate spectrala de putere (pentru semnalele de putere medie finita)sau densitate spectrala de energie (pentru semnalele de energie finita).
X Y
Y X
y x h
y n x n h
S H S .
R n R n R n
n .
S
Ω = Ω Ω
= ∗
= ∗
−
Tipuri de transformări Fourier
Semnal TFAnalogic periodic Secvenţă aperiodicăAnalogic aperiodic Funcţie continuă aperiodicăDigital periodic Secvenţă periodicăDigital aperiodic Funcţie continuă periodică
Pentru a putea face analiza spectrala a unui semnal cu ajutorul calculatorului e necesar ca acesta să fie digital şi aperiodic iar transformata sa Fourier să fie o secvenţă aperiodică.
38
Transformata Fourier discreta(TFD)
Semnal digital aperiodic[ ] 1 20, pentru si x n n N n N= < >
[ ] [ ]2
1
1 22 1
2
, cu 1
0, in rest
N jk nN
n Nx n e N k N
X k N N N
π−
=
⎧≤ ≤⎪= = − +⎨
⎪⎩
∑
[ ] [ ]2
1
21 NN jk n
k Nx n X k e
N
π−
== ⋅∑
CZx →:
Secvenţă aperiodică
[ ] [ ]2
1
1 22cos ,
Re 0, in rest
N
n Nx n k n N k N
NX k =
⎧ π⎛ ⎞⋅ ≤ ≤⎪ ⎜ ⎟= ⎝ ⎠⎨⎪⎩
∑
[ ] [ ]2
1
1 22sin ,
Im 0, in rest
N
n Nx n k n N k N
NX k =
⎧ π⎛ ⎞− ⋅ ≤ ≤⎪ ⎜ ⎟= ⎝ ⎠⎨⎪⎩
∑
39
Exemplu[ ] [ ]1 20 ; 63; 1N N x n n= = = δ −
[ ] 1 22cos ,
Re0, in rest
k N k NX k N
⎧ π⎛ ⎞ ≤ ≤⎪ ⎜ ⎟= ⎝ ⎠⎨⎪⎩
[ ] 1 22sin ,
Im 0, in rest
k n N k NX k N
⎧ π⎛ ⎞− ≤ ≤⎪ ⎜ ⎟= ⎝ ⎠⎨⎪⎩
Exprimari alternative
[ ] [ ]m
x n x n mN∞
=−∞= −∑%
2
1, - radacina complexa de ordinul a unitatiiNN N N
jNe w w w Nπ−= → =
[ ] [ ] knN
n NX k x n w
== ∑% %
[ ] [ ] 1 2, X k X k N k N= ≤ ≤%
Prelungire prin periodicitate
TFD este restrictia la perioada principala a transformarii Fourier in timp discret a prelungitei prin periodicitate a semnalului considerat.
40
Proprietati
a) Liniaritatea
[ ] [ ] [ ] [ ]1 2 1 2 , ,ax n bx n aX k bX k a b+ ↔ + ∈% %% %
b) Teorema întârzierii
[ ] [ ]00 0, knx n n w X k n− ↔ ∈%%
c) Teorema deplasării
d) Teorema convoluţiei circulare
[ ] [ ]00 0, k nw x n X k k k Z− ↔ − ∈%%
[ ] [ ] [ ] [ ]1 2 1 2x n x n X k X k↔ ⋅% %% %
41
e) Teorema produsului
f) Teorema lui Parseval
[ ] [ ] [ ] [ ]1 2 1 21x n x n X k X kN
⋅ ↔ % %% %
[ ] [ ] 22 1n N k N
x n X kN= =
=∑ ∑ %%
Algoritmul TFR (FFT) pentru calculul TFD
Dezvoltarea prelucrării numerice a semnalelor a început odată cu elaborarea algoritmului de transformare Fourier rapidă (TFR, FFT conform iniţialelor din limba engleză). Acesta exploatează anumite proprietăţi ale exponenţialelor complexe. Implementarea algoritmului TFR este eficientă când lungimea suportului secvenţei de transformat, respectiv a perioadei semnalului periodizat este o putere a lui 2. Când această cerinţă nu este îndeplinită, se prelungeşte intervalul din pe care se face transformarea până ce lungimea sa devine o putere a lui 2, completând semnalul cu eşantioane nule.
Z
42
[ ] [ ]2
1
1 22 1
, cu 1
0, in rest
knN
N
n Nx n w N k N
X k N N N=
⎧⋅ ≤ ≤⎪= = − +⎨
⎪⎩
∑
O implementare naiva ar presupune calculul produsului vectorilor[ x[N1] x[N1+1]… x[N2] ] si [ wN
kN1 wNk(N1+1)… wN
kN2 ]T. Deoarececalculul fiecarui produs necesita N inmultiri si N adunari, numarultotal de operatii este proportional cu N2 (este un algoritm de tipulO(N2)). Printr-o rearanjare inteligenta a acestor operatii se poateobtine un algoritm de tipul O(N log2(N)), ceea ce, pentru valorimari ale lui N reprezinta o mare diferenta. Aceasta variantaoptimizata a algoritmului se numeste TFR (FFT).
Sa presupunem ca vrem sa calculam TFD a semnalului sonorinregistrat pe un CD. Frecventa de esantionare folositapentru generarea acestui semnal este de 44 kHz, iar rezolutiasa este de 8 biti/esantion. Sa presupunem ca folosim un registru cu capacitatea de 1 koctet pentru memorarea datelorde pe CD in vederea redarii semnalului sonor. Acesta vatrebui sa fie citit si reincarcat de 44 de ori pe secunda. La fiecare citire trebuie calculata TFD a unui semnal continand1000 de esantioane (N=1000).
In acest caz: N2=1000000 si Nlog2(N)=9965,8. Deci utilizarea algoritmului TFR face posibila reducerea
numarului de operatii de peste 100 de ori.
43
Varianta Cooley-Tukey
Descompune iterativ o TFD de dimensiune N = N’1N’2 in mai multe TFD-uri de dimensiuni N’1 si N’2, efectuand O(N) inmultiri cu radacini complexe ale unitatii.In utilizarea sa cea mai comuna, la fiecare pas al algoritmului FFT se alege N’1= N’2=N / 2, motiv pentru care N trebuie sa fie o putere a lui 2. Aceasta varianta se numeste radix-2.
Bazele matematice[ ] [ ]
2
1
knN
N
n NX k x n w
== ⋅∑
[ ] [ ] [ ] [ ] [ ]
[ ] [ ]
(2 1) (2 )
(2 ) (2 )
1 1 / 2 1 / 2 1
0 0 0 0parimpar
/ 2 1 / 2 1
0 0
2 1 2 =
2 1 + 2
kn kn k r k rN N N N
k r k k rN N N
N N N N
n n r rnn
N N
r r
X k x n w x n w x r w x r w
x r w w x r w
+− − − −
= = = =−−
− −
= =
= ⋅ + ⋅ = + ⋅ + ⋅
= + ⋅ ⋅ ⋅
∑ ∑ ∑ ∑
∑ ∑
Fara a reduce din generalitate putem considera ca N1=0. Descompunemmembrul drept in 2 sume, prima continand valorile impare ale indicelui n iar ceade a doua valorile pare.
Dar: ( )( ) ( ) 222
2 2 2/ 2
2j k r j krk r N N
k r krN N
jNw e e e w
π π− −
⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
π−⎛ ⎞= = = =⎜ ⎟⎝ ⎠
[ ] [ ] [ ]/ 2 1 / 2 1
/ 2 / 20 0
2 2 1N N
kr k krN N N
r rX k x r w w x r w
− −
= =
= ⋅ + + ⋅∑ ∑
44
[ ] [ ] [ ]/ 2 1 / 2 1
/ 2 / 20 0
2 2 1N N
kr k krN N N
r rX k x r w w x r w
− −
= =
= ⋅ + + ⋅∑ ∑
Cele 2 sume din membrul drept reprezinta TFD a douasecvente de durata N/2.
Daca N este o putere a lui 2, aceasta divizare poate fi aplicatarecursiv pana cand se ajunge la calculul TFD a unor secventeformate din 2 esantioane.
[ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ]
2 / 2 1 2 / 2 1
2 / 2 2 2 / 20 0
0 02 20 01 12 2
0 02 21 11 12 2
2 2 1
0 0 1 0 1
1 0 1 0 1
kr k kr
r r
j j
j j
Y k y r w w y r w
Y y e w y e y w y
Y y e w y e y w y
− −
= =
π π− −
π π− −
= ⋅ + + ⋅ ⇒
⎛ ⎞ ⎛ ⎞= ⋅ + ⋅ ⋅ = +⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
⎛ ⎞ ⎛ ⎞= ⋅ + ⋅ ⋅ = +⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
∑ ∑
[ ] [ ] [ ][ ] [ ] [ ]
02
12
0 0 1
1 0 1
Y y w y
Y y w y
= +
= +
Aceste TFD pot fi implementate cu structuri de tip fluture:
In continuare, folosind aceeasi strategie TFD a unei secvente care contine 4 esantioane poate fi redusa la calculul a doua TFD ale unorsecvente avand cate 2 elemente, prima corespunzand esantioanelorpare si cea de a doua esantioanelor impare. Secventacorespunzatoare esantioanelor impare va fi inmultita cu w4
k.
45
Tema de curs. Verificati daca aceasta schema este corecta. Apoidesenati ordinograma algoritmului pentru cazul N=8.
Cazul general
Structurile de tip fluture din schema de implementare a algoritmului sunt de forma:
Aceasta structura poate fi incasimplificata tinand seama deidentitatea: / 2 / 2 .s N s N s
N N N Nw w w w+ = ⋅ = −
46
Cazul N=4
⇔
Schema din dreapta reprezinta esenta algoritmului TFR. Nu se calculeaza separat fiecare componenta a TFD. Calculul se efectueaza in etape. Fiecare etapa incepe cu N numere (in general complexe) carora li se aplica structura de tip fluture, obtinandu-se o noua secventa de N numere complexe, care reprezinta intrareapentru cea de a doua etapa. In cazul N=4 sunt necesare 2 etape.
Iesirea celei de a doua etape estecompusa din cele 4 componente ale TFD. Fiecare etapa presupuneefectuarea a N/2 inmultiri de numerecomplexe (adica a N inmultiri de numere reale), a N/2 schimbari de semn (inmultiri cu -1), si a N adunaride numere complexe.
Deci fiecare etapa poate fi implementata cu un algoritm de tipul O(N). Numarul etapelor este log2N (care, deoarece N este o putere a lui 2, reprezinta exponentul m din ecuatia N = 2m). Rezulta ca algoritmulTFR este de tipul O(Nlog2N).
Mai mult calculele pot fi efectuate in asa fel incat sa fie ocupat un spatiu de memorie corespunzator la doar N numere complexe. Truculcare permite obtinerea acestei performante este initializarea acestuispatiu de memorie cu esantioane ale semnalului de intrare distribuitecorespunzator.
47
Pentru N=4, ordinea esantioanelortrebuie sa fie v[0], v[2], v[1], v[3]. In general, la inceput esantioanele se impart in 2 grupuri unul continandesantioanele pare si celalalt continandesantioanele impare.
Aplicand aceasta impartire in mod recursiv se poate de exempluobtine impartirea grupului de esantioane pare ai caror indici sunt(0, 2, 4, 6, 8, 10, ... 2N-2) in doua noi grupuri de esantioane ale caror indici sunt (0, 4, 8, ...) si (2, 6, 10, ...). Daca se exprima acestiindici in binar se poate constata ca prima impartire (in esantioaneimpare si pare) este facuta pe baza bitului cel mai putinsemnificativ; cea de a doua impartire este facuta pe baza bituluiimediat mai semnificativ si asa mai departe.
Daca de exemplu N=8, atunci se va folosimultimea de indici :
000, 001, 010, 011, 100, 101, 110 si 111. La prima iteratie vor fi obtinuti indicii:[pari] (000, 010, 100, 110), [impari] (001, 011, 101, 111)Dupa cea de a doua iteratie se vor obtine
multimile de indici:((000, 100), (010, 110)), (001, 101), (011, 111))care dau rezultatul: 000, 100, 010, 110, 001, 101, 011, 111Algoritmul de impartire a esantioanelor semnalului de intrare care tocmai a fost descris este echivalent cu sortarea esantioanelor in ordine inversa a bitilor indicilor lor (bit-reversed order—daca se inverseaza ordinea bitilor fiecarui indice (de exemplu, 110 se transforma in 011, si asa mai departe), se va obtine o multime de numere binare consecutive.
48
Forma finala a algoritmului1. Se selecteaza N astfel incat sa fie o putere a lui 2. 2. Esantioanele semnalului de intrare se memoreaza intr-o zona de
memorie de dimensiune N.3. Se ordoneaza esantioanele in ordine inversa a bitilor indicilor lor si
se salveaza intr-o zona de memorie avand o capacitate suficientapentru memorarea a N numere complexe (partile imaginare se anuleaza).
4. Se aplica prima structura de tip fluture folosindu-se perechiadiacente de numere din cea de a doua zona de memorie.
5. Se aplica cea de a doua structura de tip fluture folosindu-se perechide numere separate cu 2.
6. Se continua cu aplicarea urmatoarelor structuri de tip fluture panacand se ajunge la o separare cu N/2.
7. Zona de memorie va contine TFD a semnalului considerat.
