Xử lý dữ liệu Tín hiệu số

Chương 66 Chương

BK TP.HCM

BIẾN ĐỔI FOURIER BIẾN ĐỔI FOURIER NHANH (FFT) NHANH (FFT)

T.S. Đinh Đức Anh Vũ

Faculty of Computer Science and Engineering HCMC University of Technology 268, av. Ly Thuong Kiet, District 10, HoChiMinh city (08) 864-7256 (ext. 5843) Telephone : Fax : (08) 864-5137 Email : anhvu@hcmut.edu.vn http://www.cse.hcmut.edu.vn/~anhvu

Nộidung Nộidung

TínhDFT & IDFT

Tínhtr ựcti ếp

Biến đổi WN

Chia-Trị

Lọctuy ếntính

Cơ số 2

Cơ số 4

Tách cơ số

Goertzel

Chirp-z

2 DFT & IDFT DFT & IDFT

§ Tính DFT: xác định chuỗi N giátr ị phức {X(k)} khi biết trước chuỗi

{x(n)} chiều dài N )

kX (

Wnx )

(

kn N

DFT

= (cid:229)

p2-= Nj e

0 N

1 -

nx )(

WkX )(

££

IDFT

- N

1 = (cid:229) N

§ Tính trực tiếp

cos(

[

)

(

)

(

)

sin(

)]

nx ( I

kn p N

(cid:229)

sin(

[

)

(

)

cos(

)]

kX ( I

nx ( I

kn p N

(cid:229)

“ N2 phép nhân phức “ N(N-1) phép cộng phức → Độ phức tạp: O(N 2)

§ Biến đổi WN

“ Giải thuật tính DFT cũng được áp dụng cho việc tính IDFT (cid:236) (cid:239) (cid:239) (cid:237) (cid:239) (cid:239) (cid:238)

Ñoái

xöùng

k W N

Giảithu ậttínhDFT t ối ưu mỗiphéptoán theonh ữngcáchkhácnhau 2/

Tuaàn

hoaøn

Nk + W N Nk + W N

k W N

“ 2N2 phép tính lượng giác “ 4N2 phép nhân số thực “ 4N(N-1) phép cộng số thực “ Một số phép toán chỉ số và địa chỉ để nạp x(n)

3 Phươngphápchia-tr ị Phươngphápchia-tr ị

§ Nguyên tắc: phân rã nhỏ việc tính DFT N điểm thành việc tính các DFT kích

thước nhỏ hơn → các giải thuật FFT

“ Giả sử N=L.M “ Lưu trữ x(n) vào mảng 2 chiều LxM (l: chỉ số hàng, m: chỉ số cột)

n →

…

N-1

x(0)

x(1)

x(2)

…

x(N-1)

…

M-1

x(0,0)

x(0,1)

…

x(0,M-1)

x(1,0)

x(1,1)

…

x(1,M-1)

“ Cách lưu trữ

x(2,0)

x(2,1)

…

x(2,M-1)

• Theo dòng n = Ml + m • Theo cột n = l + mL

…

L-1

x(L-1,0)

x(L-1,1)

x(L-1,M-1)

“ Tương tự, các giátr ị DFT X(k) tính được cũng sẽ được lưu trữ trong ma trận LxM

(p: chỉ số hàng, q: chỉ số cột)

• Theo dòng k = Mp + q • Theo cột k = p + qL

§ Phương pháp

4 Phươngphápchia-tr ị Phươngphápchia-tr ị

kX (

)

Wnx )

(

kn N

= (cid:229)

Với:

1 -

)(

)

qMp +

lmL +

qpX ( ),

(cid:229)(cid:229)

x(n) X(k)

: theo cột : theohàng

( NWmlx ,( ) W

Nmp N

)(

lmL

qMp +

) =+

( W N

mLq lq WWWW N N

MLmp N

Mpl N

mqL N

mq / LN

1 -

mq M W

Mpl N

pl / MN

pl L

)

),( qpX

lq N

mq ,( Wmlx M

(cid:229)

Ø Œ º

ø œ ß

(cid:236) W (cid:237) (cid:238)

(cid:252) lp W (cid:253) L (cid:254)

(1): TínhL DFT M điểm “Nhân phức : LM2 “Cộngph ức: LM(M-1)

(2): TínhG(l,q)

“Nhân phức: LM

(3): TínhX(p,q)

1 DFT M điểm F(l,q)

“Nhân phức: ML2 “Cộngph ức: ML(L-1)

Ł Độ phức tạp

2 G(l,q)

“Nhân phức: N(M+L+1) “Cộngph ức: N(M+L-2)

DFT L điểm X(p,q)

5 Phươngphápchia-tr ị Phươngphápchia-tr ị

§ Hiệu quả

PP chia-trị • Nhânph ức: N(M+L+1) • Cộngph ức: N(M+L-2) PP tínhtr ựcti ếp • Nhânph ức: N 2 • Cộngph ức: N(N-1)

N=1000 ﬁ L=2, M=500 106 nhân phức ﬁ 503,000 (~ N/2) N= r1r2r3…rv

“ Phân rã nhỏ hơn đến (v-1) lần

§ PP chia-trị rất hiệu quả khi

n = Ml + m k = qL+ p

n = l + mL k = Mp + q

§ Giải thuật

Giảithu ật 2

Giảithu ật 1

Lưutr ữ t/htheohàng

Lưutr ữ t/htheo c ột

1. 2. TínhDFT L điểm của mỗi cột 3. Nhânma tr ận kếtqu ả với hệ số pha WN 4. TínhDFT M điểm của mỗihàng 5. Đọcma tr ận kếtqu ả theo cột

1. 2. TínhDFT M điểm của mỗihàng 3. Nhânma tr ận kếtqu ả với hệ số pha WN 4. TínhDFT L điểm của mỗi cột 5. Đọcma tr ận kếtqu ả theohàng

6 Phươngphápchia-tr ị Phươngphápchia-tr ị

lq W6

x(4)

X(2)

x(5)

X(5)

x(2)

X(1)

T 3 điể

F D

x(3)

X(4)

x(0)

X(0)

m ể đ

x(1)

X(3)

2 T F D

§ Mô hình tính toán DFT 6 điểm thông qua việc tính DFT 3 điểm và DFT 2 điểm

“ Nếu N = r1r2r3…rv = rv → mô hình tính DFT có cấu trúc đều (chỉ dùng 1 DFT r điểm) “ r = 2 → FFT cơ số 2 “ Chọn M = N/2 và L = 2

x(N-1)

x(0)

x(1)

x(2)

…

m=0

m=1

m=M-1

Giảithu ật chiatheoth ờigian

l=0

x(N-2)

x(0)

x(2)

…

n= 0,1, …, N/2-1

f1(2n) f2(2n+1)

l=1

x(N-1)

x(1)

x(3)

…

§ Giải thuật tính FFT cơ số 2

7 FFT cơ số 2 FFT cơ số 2

kX (

)

Wnx )

(

,...,1,0

kn N

(cid:229)

Wnx )

(

Wnx )

(

kn N

(cid:229)

even

old

(

1)2/

(

1)2/

- Wmx )2(

- mx 2(

2 N

mk 2( N

(cid:229)

2 N WW =

(

1)2/ -

kX )(

(

)

(

Wmf ) 1

km N 2/

k N

Wmf 2

km N 2/

(cid:229)

m 0 = ,...,1,0 =

m 0 = kFWkF )( )( 1

k N

)

,...,1,0

‹

mf ( 1

kF )( 1

(cid:190)(cid:190)(cid:190) ﬁ DFT N

)

,...,1,0

‹

mf ( 2

kF )( 2

(cid:190)(cid:190)(cid:190) ﬁ DFT

)(

,..,1,0

)( kX

)( kFWkF + 1

k N

N 2

Nk + N

k N

)

)(

,..,1,0

( kX

)( kFWkF - 1

k N

N 2

(cid:236) (cid:239) (cid:237) (cid:239)(cid:238)

F1(k), F2(k) tuầnhoàn chu kỳ N/2 F1(k+ N/2) = F1(k) F2(k+ N/2) = F2(k)

8 FFT cơ số 2 FFT cơ số 2

,..,1,0

)( kF 1

N 2

)(

,..,1,0

k N

N 2

)( kG (cid:236) (cid:239) 1 (cid:237) )( kFWkG = (cid:239)(cid:238)

X(k)

G1(k)

DFT2

X(k+ N/2)

G2(k)

k=0,1,…,(N/2-1)

)(

,...,1,0

N 2

kX (

)(

)

,...,1,0

kGkGkX )( 1 =

2 kGkG )( -

N 2

(cid:236) (cid:237) (cid:238)

(N/2-1)

X(N/2-1)

F 1

DFT 2 điểm

(N/2-1) (N/2-1)

N/2-1 N

x(N-2) x(N-2)

F 2

x(4)

X(N-1)

(1)

X(1)

(0)G

DFT 2 điểm

X(0)

x(4)

(0) F 1

DFT 2 điểm

1 N

(2) (1) F 1 F 1 (2) (1) F 2 F 2

DFT 2 điểm

(0)

D F T N / 2 điể m D F T N / 2 điể m

0 N

x(0)x(2) x(1)x(3)

(0) F 2

X(N/2)X(N/2+1)

9 FFT cơ số 2 FFT cơ số 2

(

)

,...,1,0

)2( n

N 4

,...,1,0

)

(

1 f

N 4

,...,1,0

)

(

)2( n

N 4

,...,1,0

)

(

N 4

§ Tiếp tục phân f1(n) và f2(n) thành các chuỗi N/4 điểm (cid:236) (cid:239) (cid:239) (cid:237) (cid:239) (cid:239) (cid:238)

kVWkV

(

)

(

,...,1,0

k N

kF ( 1

N 4

kVWkV

(

)

(

)

,...,1,0

kF ( 1

k N

N 4

)

(

)

(

)

,...,1,0

VWkV +

N 4 =

kF ( 2

k N

N 4

)

(

)

,...,1,0

VWkV -

kF ( 2

k N

N 4

(cid:236) (cid:239) (cid:239) (cid:237) (cid:239) (cid:239) + = (cid:238) § Hiệu quả

Vij(k) vij(n) DFT N/4 điểm

Nhânph ức: N2 Cộngph ức: N2 – N

Nhânph ức: (N/2)log2N Cộngph ức: Nlog2N

DFT trựcti ếpN=2 v điểm CácDFT 2 điểm FFT cơ số 2

10 FFT cơ số 2 FFT cơ số 2

§ Ví dụ: tínhDFT 8 điểm

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

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

x(1) x(3) x(5) x(7)

[0,1,2,3,4,5,6,7]

P h â n t h e o t h ờ

i

x(0) x(4)

g i a n

x(2) x(6) [0,2,4,6] [1,3,5,7]

x(1) x(5)

[0,4] [2,6] [1,5] [3,7] x(3) x(7)

11 FFT cơ số 2 FFT cơ số 2

x(0) X(0)

x(4) X(1)

0 8W

-1

0 8W

x(2) X(2) -1

0 8W

2 8W

x(6) X(3) -1 -1

x(1) X(4)

0 8W

-1

0 8W

1 8W

x(5) X(5) -1 -1

x(3) X(6)

2 8W

0 8W

-1 -1

x(7) X(7)

2 8W

0 8W

3 8W

-1 -1 -1

12 FFT cơ số 2 FFT cơ số 2

§ Khốitínhtoán c ơ bảnchoDFT 2 điểm(hìnhcon b ướm)

a A = a+WN’b Độ phức tạp

•1 nhânph ức •2 c ộngph ức b B = a–WN’b

–1 W N’

N= 2v:

+ Log2N + N/2 : tầngtínhtoán : khốitínhtoán c ơ bảncho m ỗi lớp

Bộ nhớ:

: (a,b) – số phức + Vào + Ra : (A,B) – số phức + Cóth ể lưu(A,B) đèlên(a,b)

Ł Chỉ cầnN ô nh ớ phức(2N ô nh ớ thực) Ł Tínhtoán t ạich ỗ

13 FFT cơ số 2 FFT cơ số 2

§ Thứ tự chuỗi dữ liệu vào sau khi phân (v-1) lần

“ Biểu diễn các chỉ số ở dạng nhị phân “ Chuỗi sau khi phân chia sẽ là lấy theo thứ tự đảo các bit

Bộ nhớ

Phân Phân chia chia Phân Phân chia chia Địa chỉ Địa chỉ Địa chỉ

000 000 000 x(0) x(0) x(0)

001 010 100 x(1) x(2) x(4)

010 100 010 x(2) x(4) x(2)

011 110 x(3) x(6) x(6) 110

x(4) 100 x(1) 001 x(1) 001

x(5) 101 x(3) 011 x(5) 101

110 101 011 x(6) x(5) x(3)

111 111 111 x(7) x(7) x(7)

14 FFT cơ số 2 FFT cơ số 2

§ Phân chiatheo t ần số “ Phương phápchiavàtr “ M = 2, L = N/2 “ Chuỗi dữ liệunh ập được sắp xếptheo c ột “ Phân chiaX(k) thànhX(2k) vàX(2k+1) “ Sau đócóth ể phânchiati ếp tục mỗiX(kch ẵn) vàX(k l ẻ)

x(0)

X(0)

ị

x(1)

X(2)

DFT 4 điểm

x(2)

X(4)

a A = (a+b) WN’

x(3)

X(6)

x(4)

X(1)

-1

x(5)

X(3)

-1

DFT 4 điểm

X(5)

x(6)

-1

x(7)

X(7)

-1

0 8W 1 8W 2 8W 3 8W

b B = (a–b)WN’ –1 W N’

15 FFT cơ số 4 FFT cơ số 4

N = 4v

x(0) x(2) x(4) … … … x(N-1)

L = 4, M = N/4 l,p= 0,1,2,3 m,q= 0,1,…,N/4 – 1 n = 4m + l k = (N/4)p + q

m=0 m=1 m=(N/4)-1

l=0 x(4n) x(0) x(4) … … x(N-4)

l=1 x(1) x(5) … … x(N-3) x(4n+1)

n = 0,1,…,N/4-1

x(2) x(6) … … x(N-2) x(4n+2) l=2

x(3) x(7) … … x(N-1) x(4n+3) l=3

16 FFT cơ số 4 FFT cơ số 4

)

( qpX

Wmlx

mq M

lp L

lq N

(cid:229)

ø œ ß

(cid:252) W (cid:253) (cid:254)

(cid:236) W (cid:237) (cid:238)

3,2,1,0

( ), qpX

Ø Œ º ] [ ),( pWqlFW

lp 4

lq N

(cid:229)

3,2,1,0

)

),( qlF

,( Wmlx

mq N 4/

(cid:229)

,..,1,0

(

N 4

l (cid:236) (cid:237) (cid:238)

)

,( lmxmlx = +

(

)

),( qpX

qp +

N 4

(cid:236) (cid:237) (cid:238)

,0(

)

,0(

)

,1(

)

qFW

,1(

)

,2(

)

- 1

,2(

)

,3(

)

- j

,3(

)

Ø Œ Œ Œ Œ º

ø œ œ œ œ ß

1 Ø Œ 1 Œ Œ 1 Œ 1 º

ø œ œ œ œ ß

ø œ œ œ œ œ ß

0 Ø FW N Œ q Œ N Œ 2 q FW N Œ 3 q FW Œ º N

DFT N/4 điểm

17 FFT cơ số 4 FFT cơ số 4

0 NW

-j -1

q NW

-1 1

-1

NW 2

j -1

-j

NW 3

Dạngrút g ọn

18 FFT cơ số 4 FFT cơ số 4

Độ phức tạp:1 kh ốitínhtoán c ần

+ 3 nhânph ức + 12 cộngph ức

N=4v

+ Tầngtínhtoán + Mỗi tầngcó : v = log4N : N/4 khốitínhtoán

: Nhânph ức : Cộngph ức 3vN/4 = (3N/8)log2N 12vN/4 = (3N/2)log2N (giảm25% vsFFT 2) (tăng50% vsFFT 2)

,0(

)

,0(

)

,1(

)

,0(

)

- 0

,2(

)

- 0

,0(

)

,3(

)

- 0

,0(

)

ø œ œ œ œ 1 ß

Ø Œ Œ Œ Œ º

ø œ œ œ œ ß

Ø Œ Œ Œ Œ º

ø œ œ œ œ ß

Ø Œ Œ Œ Œ º

ø œ œ œ œ œ ß

0 Ø FW N Œ q FW Œ N Œ 2 q FW N Œ q 3 FW Œ º N

Biểudi ễn lạinhânma tr ận

: Nhânph ức : Cộngph ức (3N/8)log2N Nlog2N (giảm25% vsFFT 2) (bằngFFT 2)

19 Hiệnth ựccácgi ảithu ậtFFT Hiệnth ựccácgi ảithu ậtFFT

§ FFT cơ số 2

k: đượctính m ột lầnvà l ưutrong b ảng

• 4N nếumu ốn đơngi ảnhóacáctác v ụ chỉ số và điềukhi ển; đồngth ờichophép

chuỗinh ậpvàxu ấttheo đúngth ứ tự

1 -

§ IDFT

nx )(

WkX )(

££

- N

1 = (cid:229) N

“ Tínhtoánhình b ướm: (N/2)log2N lần “ Hệ số quay WN “ Bộ nhớ: 2N nếumu ốnvi ệctínhtoán đượcth ựchi ện tạich ỗ

“ Khácnhau c ơ bảngi ữavi ệctínhDFT vàIDFT là h ệ số 1/N và dấu của hệ số

• Đảochi ều sơđồ tínhDFT, đổi dấu hệ số pha, vàchia k ếtqu ả cuốicùngchoN ﬁ

IDFT

§ DFT với số điểmkhác 2 v hoặc 4v ﬁ đệmthêmcác s ố 0 § Độ phức tạp

pha WN

“ Tác vụ số học(nhânph ức, cộngph ức) “ Cấutrúchi ệnth ực củagi ảithu ật(qui t ắcvs b ấtqui t ắc) “ Kiếntrúc c ủacác b ộ DSPs(x ử lýsong songcáctác v ụ)

20 Ứng dụng củacácgi ảithu ậtFFT Ứng dụng củacácgi ảithu ậtFFT

§ TínhDFT c ủa2 chu ỗith ực

0 ≤ n ≤ N – 1

(tínhtuy ếntính c ủaDFT)

“ x1(n) và x2(n): chuỗith ực độ dàiN c ầntínhDFT “ Địnhngh ĩachu ỗix(n) = x 1(n) + jx2(n) “ X(k) = X1(k) + jX2(k)

)( nx

* )( nx

DFT

)( nx 1

[ nx )(

]

{ DFT

[ * nx )(

] }

kX )( 1

)( nx

DFT

[ nx )(

]

{ DFT

[ * nx

] })(

kX )( 2

)( nx 2

+ 2 - 2

* )( nx j

kNX

(

1 2

* nx )(

kNX

(

)

NDFT (cid:190)(cid:190) ﬁ‹

kNX

(

1 2 1 2 [ kX )( [ kX )(

] ) ])

kX )( 1 kX )( 2

1 2

21 Ứng dụng củacácgi ảithu ậtFFT Ứng dụng củacácgi ảithu ậtFFT

§ TínhDFT c ủachu ỗith ực2N điểm

0 ≤ n ≤ N-1 0 ≤ n ≤ N-1

)

kNX

(

kX ( 1

1 2

)

kNX

(

[ kX ( [ kX (

] ) ])

kX ( 2

1 2

1 -

kG )(

)2(

Wn )1 +

2 nk N 2

2( N 2

(cid:229)

1 -

Wnx )( 1

nk N

k N 2

Wnx )( 2

nk N

(cid:229)

kG )(

kXWkX )(

)(

,1,0

k N 2

(

)

)(

,1,0

)( kXWkX

NkG +

k 2 N

(tínhtuy ếntính c ủaDFT) “ g(n): chuỗith ực độ dài2N c ầntínhDFT “ Táchthành2 chu ỗi x1(n) = g(2n) và x2(n) = g(2n+1) “ Địnhngh ĩachu ỗix(n) = x 1(n) + jx2(n) “ X(k) = X1(k) + jX2(k)

22 Ứng dụng củacácgi ảithu ậtFFT Ứng dụng củacácgi ảithu ậtFFT

§ Lọctuy ếntínhcácchu ỗi dữ liệudài

§ Phương pháp

DFT + FFT “ Overlap-add “ Overlap-save

(Giảithu ậtFFT suygi ảmtheo t ần số)

“ h(n) – Đáp ứngxung đơn vị của bộ lọc(chi ềudàiM) • Được đệmthêmL-1 s ố khôngsaochoN = L + M –1 = 2 • H(k): DFT N điểm củah(n), theoth ứ tựđả o nếuh(n) được sắptheoth ứ tự thuận

• Được đệmthêmM–1 điểm(giátr ị tùytheoPP l ọc đượcdùng) • Xm(k): DFT N điểm của xm(n), cũngtheoth ứ tựđả o(Gi ảithu ậtFFT suygi ảm

theo tần số)

“ xm(n) –kh ối dữ liệuchi ềudàiL ( đã đượcphân c ắt)

• H(k) và Xm(k) cùngcóth ứ tựđả o → Ym(k) theoth ứ tự đảo • ym(n) = IDFTN{Ym(k)} sẽ đúngtheoth ứ tự thuận nếudùnggi ảithu ậtFFT suy

giảmtheoth ờigian

“ Ym(k) = H(k)Xm(k)

§ Tính tươngquan(t ương tự)

“ Không cầnthi ết đảo vị trícác d ữ liệutrongvi ệctínhDFT vàIDFT

23 Phương pháp lọc tuyến tính Phương pháp lọc tuyến tính

§ FFT khônghi ệuqu ả khitínhDFT (IDFT) t ại một số điểm(< log 2N) →

tínhtr ựcti ếp § Giảithu ậtGoertzel

k vàbi ểudi ễnvi ệctínhtoánDFT nh ư lọctuy ến

“ Dựavàotínhchu k ỳ của WN

1 -

mNk

(

)

WkX

)(

Wmx )

(

Wmx )

(

- N

km N

- N

(cid:229)

1 -

zH )( k

1 -

(

)

mnk -

1 k -- zW N

nyĐăt )(

Wmx )

(

*)(

- N

nh )( k

(cid:229)

đơn vị

vói

nuWnh )(

)(

- N

Mộtpole trênvòngtròn tại tần số ωk=2πk/N

kX )(

(cid:222)

k ny )( k

Nn =

Thayvìtính t ổngch ậptr ựcti ếp, tacóth ể dùngPTSP

ViệctínhDFT t ại một điểmk cóth ể đượcth ựchi ện bằngcáchchot/h đivào b ộ cộng hưởng mộtpole tại tần số ωk=2πk/N

)(

(

)1 +-

0)1( =-

nyWny k

- N

tính

24 Giảithu ậtGoertzel Giảithu ậtGoertzel

zH )( k

1 -

1 cos(

21 -

cos

)( nx

,...,1,0

§ Kết hợp từng cặpcác b ộ cộng hưởngcópole liên h ợpph ức k - zW - N 2 zNk ) / p

)( nv k

( nv k

nvWnv

)(

(

2p k N -

)( ny k

k N

Nn = vk(n)

§ Hiệnth ực bằng dạngchu ẩn tắc(d ạngII) ( nv k

“ Với đ/k đầu v )1( =-

0)2( =-

+ + x(n) yk(n) – Z–1

cos(

)

kp 2 N

k nW

v k vk(n) được lặp lạichon = 0, 1, …, N “ Mỗivòng c ần1 phépnhânth ực yk(n) đượctínhduynh ất một lầnchon = N

§ Z–1

–1

§ Nếux(n) làt/hth ực, cầnN+1 phépnhânth ực để tínhX(k) vàX(N-k) {do tính

đối xứng}

§ Giảithu ậtGoertzelch ỉ thích hợpkhi s ố giátr ị DFT cầntínhkhánh ỏ (≤ log2N)

25 Giảithu ật BĐ Chirp-z Giảithu ật BĐ Chirp-z

§ DFT N điểm~ X(z k) với zk = ej2πkn/N , k=0,1,…,N-1 (các điểmcách đềutrên

)

,...,1,0

( zX

( znx

vòngtròn đơn vị)

- k

= (cid:229)

§ BĐ Z củax(n) t ạicác điểm zk

)

[

)

(

]

1,0

,...,

( zX

rnx

= (cid:229)

“ ViệctínhDFT cóth ểđượ cth ựchi ện bằnggi ảithu ậtFFT chochu ỗix(n)r -n

j q 0

j f 0

§ Nếu zk = rej2πkn/N (zk là N điểmcách đềunhautrênvòngtrònbkr)

)

(

qjer 0 L , K

eR 0

er = 0 Im(z)

Im(z)

z = § Tổngquát, z k nằmtrêncungxo ắn ốc bắt đầu từ điểm 0 z k ,1,0 = Im(z)

Im(z)

Vòngtròn đơn vị

θ0

Re(z)

hoặc đira g ốc tạa độ) (đivào 1

R0 < 1 R0 > 1

R0 = 1, r0 < 1 Φ0 = θ0 = 0 R0 = r0 = 1 Φ0 = θ0 = 0

26 Giảithu ật BĐ Chirp-z Giảithu ật BĐ Chirp-z

)

,1,0

( zX

)( ky )( kh j f 0

eRV = 0

)( nh

j q 0

)

)( ng

( )( ernx 0

1 -

()(

)

,1,0

)( ky

nkhng

(cid:229)

( nj

)2/

nj w

nj f 0

f 0

)( nh

1 (cid:222)=

”

R 0

2/0fw n=

BĐ chirp-z

Tần số củat/h m ũ phứch(n), t ăngtuy ếntínhtheoth ờigian → h(n): chirp signal

27 Giảithu ật BĐ Chirp-z Giảithu ật BĐ Chirp-z

“ N-1 điểm đầulàcác điểm lặp lại “ M-(N-1) điểmcòn l ạich ứa kếtqu ả

1 -

ky )(

nkhng

()(

)

,1,0

= (cid:229)

§ Xác định tổngch ậpvòng c ủachu ỗig(n) N điểmvàchu ỗih(n) M điểm(M > N)

0 = § Giả sử M = L + (N-1) § M điểm củachu ỗih(n) đượcxác định–(N–1) ≤ n ≤ (L–1) § Địnhngh ĩachu ỗiM điểm h1(n) = h(n–N+1) § H1(k) = DFTM{h1(n)} § G(k) = DFTM{g(n)} (saukhi đã đệmthêmvàog(n) L-1 s ố 0) § Y1(k) = G(k)H(k) ﬁ y1(n) = IDFT{Y1(k)} n = 0,1,…,M–1 § N-1 điểm đầutiên c ủa y1(n) làcác điểm lặp ﬁ loại bỏ chúng § Các điểm kếtqu ả làgiátr ị của y1(n) khiN-1 ≤ n ≤ M–1

“ y(n) = y1(n+N-1)

n = 0,1,…,L-1 k = 0,1,…,L-1

n = 0,1,…,M–1

§ X(zk)= y(k)/h(k)