digital signal procescingprocessing dsp.

DSP

1. CHU'ONG 4: BIEU DIEN TIN HIEU VA HE THONG
TRONG MIEN TAN SO ROI RAC
4.1. Me dau
4.2. DFT cúa day tuán hoán
4.3. DFT cúa day có chiéu dai hu han
4.4. FFT phan thoi gian
4.5. FFT phan tan só
4.6. Tóng két chuong va bai tap

2. 4.1. MO DAU

Y nghia:
Vi du: Chia 8 phan, tre lá thay o,=—k,
Mién bién st Mién tán sú
10 Puto)
0 で =|, 0| +2, a
Bién d6i Px(n) À x(e*)
Fourier 本 二
0 E 0 36 | À 20 385 ae の
2

3. 4.2. DFT CUA DAY TUAN HOAN
3.2.1. Dinh nghia bién dôi Fourier roi rac cúa day tuán hoán

IN Fije

is 2 gq A
rong 00: の. =—k v
oi: n=02N-1
; En ， TE
Dát: wi =e Me で Wy = lon =8 7 で
E ye
Wy=e NW ニア: Wy=1

Tacó: X(k)= DROLE

Ky higu: DFT | *( ヵ ) |= そ (4): £(n) 5X(k)

4. 4.2.2. Dinh nghia bién dói IDFT cúa day tuán hoan
Bien dói Fourier 707 rac nguoc IDFT duoc dinh nghia nhw sau:
NA ¡2% in
z(n)=~ > X(k)e®
Na
Hay viét lai cho gon:
1
(n)=— OX (k) I"
Nia
Ky hieu: IDFT| X (k) |=&(n)

Toan ti: À (k)—2 5 x(n)

5. 4.2.3. Dang ma tran cia DFT

(0) (0)
ㆍ *() (1)
#@=| XQ) |, §(n)=| 30)
X(k)=&(n)W, 8(N-D 3(N-1)
We We = Wy Wy
We Wy WW
E WS ee 80"

m we war 7 wee)
4.2.4. Cac tinh chat co ban
Tich chap tuán hoan (lay 0008 mót chu ky)

x; (2), = ñ (n), (*), も 00, = Ys (m), % (n -m),

6. Miën n

Mienk

Na

wm

LOC

aX, (1), +63, (n),

aX, (k), +bX,(k),,

&(n-n,), Wwe X(k)
2300) X(k+1)
&(n), (5), BO), Alk) &(,

(0), %(")y

RERO HED,

X (4), (4),

&(n) thuc

X(k)=X (-k)

Re X (£)]=Re[ X (-)]

Im[ X(k) ]= Im[ X(-4)]

00000)

ws]--ww[YC4]

7. 4.3. DFT CUA DAY CHIEU DAI HÜU HAN
4.3.1. Dinh nghia

Bién a xuôi DFT
We 0<k<N-1
a kt
Ky hieu: DFT| x(n) | = X(k):x(n) => x (x)
Bien dôi ngwoc IDFT
X(k)W;” 0<n<N-1
x(n) =1N ¢ +2 (kW; 게츠
0 n#
Ky hiéu: IDFT[ X (k) ]=x(n);X(k) => x(n)
4.3.2. Tinh chat: Néu coi day có chièu dai hitu han là 1 chu ky cua day
tuán hoan thi DFT cúa day có chiéu dai hitu han có moi tinh chat cúa DFT cúa
day tuan hoan.

7

8. 4.4. FFT phan thoi gian

= Vao nhitng nam thap ky 60, khi cóng nghe vi x ly phat
trién chua manh thi thoi gian xi ly phep toan DFT tren
may twong 001 cham, do só phép nhan phúc tuong döi lon.

N=1
= DFT cúa x(n) có 00 daiN: X(k)= Ex(n)Wi": 0<Sk<N-1
n=)

= Dé tinh X(k), voi mdi gia tri k can có N phep nhän va (N-1)
phep cóng, vay vói N gia tri k thi can có N? phep nhan va
N(N-1) phép cóng.

・ Dé khäc phuc vé mat 166 06 xi ly 008 phép tinh DFT,
nhiéu tac gia dá dua ra các thuat tóan rieng dwa tren DFT
goi là FFT (Fast Fourier Transform).

9. 4.4, FFT phan thoi gian

E Gia thiét day x(n) có dó dai N=2™, neu khóng có dang lüy thua 2 thi
thém vai mau 0 vao sau day x(n).

E Thuat tóan dua trén su phan chia dáy váo x(n) thanh các day nhó,
do bién n biéu thi cho truc 나이 gian nén 901 lá phan chia theo 내이

gian.
Na N-1 N-1
X(k)= Ex = SExy" + Lx"
n=0 n=0,2,4... n=1,3,5...

E Thay n=2r vói n chan va n=2r+1 vói n lé:

(N/2)-1 (N/2)-1
X(k)= Y) xQnwy + % x(Qr+ wiser?
r=0 r=0

10. 4.4. FFT phan thoi gian

25 Fr ¡a de
Do: Wi" =e 85» =e N!2 =Win
(N/2)-1 (N/2)-1
D x®= Y AE A. Y xr,
r=0 r=0

NI12)-1 (N/2)-1

Bat XUD= Y x0WE, 지 00= 개
r=0

DO) X(k)=X,(4)+W).X,(k)

E X,(k) — DFT cúa N/2 diem tng voi chi só n chan
E Xi(k) — DFT cúa N/2 diem ng voi chi só n lé

11. 4.4, FFT phan thoi gian
E Láy vi du minh hoa cho x(n) voi N=8
Phan chia DFT- N diém -> 2 DFT- N/2 diém
x(0)
x(2)
x(4)
Ux(6)

nchan 2

rx()
x(3)
<
x(5)
x(7)

E Qui udc cách tinh X(k) theo luu dô:
- Nhänh ra cua 1 nut bang tóng các nhanh vao nut dé
- Gia tri m6i nhanh bang gia tri nt xuát phat nhán he só

1

12. 4.4. FFT phan thoi gian
E Sau 06 danh lai chi só theo tht? tw 030 mau x(n), tiép tuc phan chia
DFT cúa N/2 diém thanh 2 DFT cúa N/4 diém theo chi só n chan va
lé va 00 thé tiép tuc phan chia cho 060 khi nao con DFT 2 diém thi
dürng lai.
E Vi du X。(k) duoc phan chia:
(N/2)-1 (N/2)-1

X= Y xarWin= >, 90007.
r=0 r=0
(NN be (W/2)-1 =
= > EW y), + y gCWY
r=0,2,4... r=1,3,5...
+ 1 (N/4)-1

a> gZQIW, 020 개 g(27+1P%。

= w(K) + W 2-Xoi(k)

13. 4.4. FFT phan thoi gian

Phan chia DFT N/2 diem -> 2 DFT- N/4 diem cúa X。(k)

Xo(0)
Xo(1)

Xo(2)
XoG3)

X1(0)
X,(1)
X,(2)
X1(3)

14. 4.4. FFT phan thoi gian

Luu 00 DFT day x(n) sau 2 län phan chia voi N=8

1x(0) X(0)
1X(4) X(1)
32) 一 To x(2)
x(6) X(3)
x(1) X(4)
x(5) X(5)
x(3) X(6)
x(7) X(7)

15. 4.4. FFT phan thoi gian

Luu d6 DFT day x(n) sau 3 län phan chia vói N=8

x(0)
x(4)
x(2)
x(6)

Xn(p) E Xn+1(P)
Xm(q) io À

WEN?) = - WN

Xn(P)

Xm(Q)

=

X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)

Xm+1(P)
Xm+1(q)

16. 4.4. FFT phan thoi gian

Luu dö DFT day x(n) sau 3 län phan chia vói N=8

Dao

bit <

x(0) X(0)
x(4) X(1)
x(2) X(2)
x(6) X(3)
x(1) X(4)
x(5) X(5)
x(3) X(6)
x(7) X(7)

E VOi N=2™ -> M län phan chia
E 50 phép nhan = só phép 0009 = NM/2=(N/2)log。N

17. 4.4, FFT phan thoi gian

Bónhó
(decimal)

Dia chi
(binary)
000
001
010
011
100
101
110

111

Só liéu tháp phan 1 Sólicu tháp phan 2

Trät ty bit bj dio nguoc

Bang mó tá qui luát dao bit:

(000)
(001)
(010)
(011)
(100)
(101)
(110)
(111)

せよ すり せよ しょ

(000)
(100)
(001
(101
(010)
(110)
(011)
(111)

)
)

YI bb vie

(000)
(100)
(010)

(nznino)j 一 (nonznl) 一 (noninz)

17

18. 4.5. FFT phan theo tán só

® Thuät toán dua trén su phan chia day ra X(k) thanh các day nhö, do bién k
biéu thi cho truc tán só nén goi lá phan chia theo tán só.

N-1 (N/2)-1 パー
\( わ = x(a" = Y x(a)" + て (の を
n=0 n=0 n=N/2
(N/2)-1 (N/2)-1
= Y) MP >; AMAN ID
n=0 n=0
(N/2)-1 (N/2)-1
= Y) ADAN? Y x(n+N/2 Wy
n=0 n=0

“yn > [xm+ (x(n +N /2) re"

2

19. 4.5. FFT phan theo tán só
m Vói k chan, thay k=2r:

(N/2)-1

X(2r)= 2 [x(n) + x(n+ N/D,

E VOikIe, thay k=2r+1
(W/2)-1

X(2r+1)= 2 {x x(n+N/2) Wwe Nr

E Dat: g(n)=x(n)+x(n+N/2); h(n)=x(n)—x(n+N/2)

(N/2)-1 (N/2)-1
=) XQr)= Y gw, XQr+l)=
n=0
E X(2r) -DFT cua N/2 diem ting 101 chi só k chan
看 X(2r+1) — DFT cua N/2 diem ng vói chi 50 k lé

> 14000 pr:

20. 4.5. FFT phn theo tán só
Phan chia DFT N=8 diém -> 2 DFT N/2= 4 diém

x(0) X(0)
x(1) x) k chan
x(2) X(4)
x(3) X(6)
x(4) X(1)
X(3
xe) si k le
x(6) X(5)
x(7) X(7)

E Sau do danh lai chi só theo tht tw 080 mau X(k), tiép 140
phan chia DFT cúa N/2 diém thanh 2 DFT cúa N/4 diém
theo chi só k chan va lé. Tiép tuc phan chia cho dén khi

nao con DFT 2 diém thi durng lai.
20

21. 4.5. FFT phan theo tán só

E D 1164 ra X(k) duoc säp xép theo thw tw dao bit, cn
d lieu vao duoc sap theo thú tu tw nhién.

E SG phep nhán va phép cóng trong 144 00 phan theo tán
só bang vói só phép nhán va cóng trong 144 00 phan
theo thOi gian.

x(0) x(0)

x(1) X(4)

x(2) X(2)

x(3) X(6) Däo
bit

x(4) X(1)

x(5) X(5)

x(6) X(3)

x(7) X(7)

Luu 06 DFT day x(n) sau 3 130 phan chia voi N=8
21