Bài tập biến đổi fourier theo thời gian rời rạc năm 2024

1. DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONGỂU DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONG MIỀN TẦN SỐ RỜI RẠCMIỀN TẦN SỐ RỜI RẠC BÀI 1 KHÁI NiỆM DFT BÀI 2 BIẾN ĐỔI FOURIER RỜI RẠC (DFT) BÀI 3 CÁC TÍNH CHẤT DFT BÀI 4 BiẾN ĐỔI FOURIER NHANH (FFT)
2. NIỆM DFTBÀI 1 KHÁI NIỆM DFT X(X(ωω) có các hạn chế khi xử lý trên thiết bị, máy tính:) có các hạn chế khi xử lý trên thiết bị, máy tính: Tần sốTần số ωω liên tụcliên tục Độ dài x(n) là vô hạn:Độ dài x(n) là vô hạn: nn biến thiên -biến thiên -∞ đến ∞∞ đến ∞ Biến đổi Fourier dãy x(n): ∑ −∞ ∞= − = n nj enxX ω ω )()( Khi xử lý X(Khi xử lý X(ΩΩ) trên thiết bị, máy tính cần:) trên thiết bị, máy tính cần: Rời rạc tần sốRời rạc tần số ωω ->-> ωωKK Độ dài x(n) hữu hạn là N:Độ dài x(n) hữu hạn là N: nn = 0= 0 ÷÷ N -1N -1 ⇒⇒ BBiến đổi Fourier của dãy có độ dài hữu hạn theo tầniến đổi Fourier của dãy có độ dài hữu hạn theo tần số rời rạc, gọi tắt làsố rời rạc, gọi tắt là biến đổi Fourier rời rạc – DFTbiến đổi Fourier rời rạc – DFT (Discrete Fourier Transform)(Discrete Fourier Transform)
3. 2 BIẾẾNN ĐỔIĐỔI FOURIER RỜI RẠC - DFTFOURIER RỜI RẠC - DFT DFTDFT củacủa x(n) có độ dài N định nghĩa:x(n) có độ dài N định nghĩa:      −≤≤ = ∑ − = − :0 10:)( )( 1 0 2 k Nkenx kX N n kn N j π còn lại r N r N jmNr N j mNr N WeeW === −+− + ππ 2 )( 2 )(      −≤≤ = ∑ − = :0 10:)( )( 1 0 k NkWnx kX N n kn N còn lại N j N eW π2 − = WWNN tuần hòan với độ dàituần hòan với độ dài N:N:
4. dưới dạng modun & argument: )( )()( kj ekXkX ϕ = Trong đó:Trong đó: )(kX - phổ rời rạc biên độ- phổ rời rạc biên độ )](arg[)( kXk =ϕ - phổ rời rạc pha- phổ rời rạc pha IDFT:      −≤≤ = ∑ − = :0 10:)( 1 )( 1 0 2 n NnekX Nnx N k kn N j π còn lại        −≤≤= −≤≤= ∑ ∑ − = − − = 10:)( 1 )( 10:)()( 1 0 1 0 NnWkX N nx NkWnxkX N k kn N N n kn N Cặp biến đổi Fourier rời rạc:
5. Tìm DFT của dãy: { }4,3,2,1)( ↑ =nx ∑= = 3 0 4)()( n kn WnxkX jWWjeW j =−=−== − 3 4 2 4 4 2 1 4 ;1; π 10)3()2()1()0()()0( 3 0 0 4 =+== ∑ = xxxxWnxX n 22)3()2()1()0()()1( 3 4 2 4 1 4 3 0 4 jWxWxWxxWnxX n n +−=+== ∑ = 2)3()2()1()0()()2( 6 4 4 4 2 4 3 0 2 4 −=+== ∑ = WxWxWxxWnxX n n 22)3()2()1()0()()3( 9 4 6 4 3 4 3 0 3 4 jWxWxWxxWnxX n n −−=+== ∑ =
6. TÍNH CHẤT DFTBÀI 3. CÁC TÍNH CHẤT DFT a) Tuyến tính N DFT N kXnx )()( 11  →← NN DFT NN kXakXanxanxa )()()()( 22112211 + →←+ Nếu:Nếu: Thì:Thì: N DFT N kXnx )()( 22  →← b) Dịch vòng: )()( N DFT N kXnx  →←Nếu:Nếu: )()( 0 0 N kn N DFT N kXWnnx  →←−Thì:Thì: Với:Với: (n)rect)(~)( N00 NN nnxnnx −=− gọi là dịch vòng của x(n)N đi n0 đơn vị 21 21 xx LNNL =≠=Nếu:Nếu: Chọn:Chọn: },max{ 21 NNN =
7. Cho: a) Tìm dịch tuyến tính: x(n+3), x(n-2) b)Tìm dịch vòng: x(n+3)4, x(n-2)4 { }4,3,2,1)( ↑ =nx x(n)x(n) nn 0 1 2 30 1 2 3 44 33 22 11 a) nn x(n-2)x(n-2) 0 1 2 3 4 50 1 2 3 4 5 44 33 22 11nn x(n+3)x(n+3) -3 -2 -1 0-3 -2 -1 0 44 33 22 11
8. 30 1 2 3 44 33 22 11 N x(n-1)4 nn 0 1 2 3 44 33 22 11 x(n+1)x(n+1)44 nn 0 1 2 30 1 2 3 44 33 22 11
9. kXnx )()( 11  →← NN DFT NN kXkXnxnx )()()()( 2121  →←⊗ Nếu:Nếu: Thì:Thì: N DFT N kXnx )()( 22  →← ∑ − = −=⊗ 1 0 2121 )()()()( N m NNNN mnxmxnxnxVới:Với: Chập vòng 2 dãy x1(n) & x2(n) 21 21 xx LNNL =≠=Nếu:Nếu: Chọn:Chọn: },max{ 21 NNN = Chập vòng có tính giao hóan:Chập vòng có tính giao hóan: NNNN nxnxnxnx )()()()( 1221 ⊗=⊗ )()(~)( 22 nrectmnxmnx NNN −=−Và:Và: Dịch vòng dãy x2(-m) đi n đ/vị
10. Tìm chập vòng 2 dãy 30:)()()()()( 3 0 4241424143 ≤≤−=⊗= ∑ = nmnxmxnxnxnx m 4},max{4,3 2121 ==⇒== NNNNN  Đổi biến n->m:  Xác định x2(-m)4:  Chọn độ dài N:
11. 0 1 2 3 4-3 -2 -1 0 1 2 3 4 44 33 22 11 )(~ 2 mx − xx22(m)(m) mm 0 1 2 30 1 2 3 44 33 22 11 xx22(-m)(-m) mm -3 -2 -1 0-3 -2 -1 0 44 33 22 11 mm 0 1 2 30 1 2 3 44 33 22 11 )()(~)( 4242 nrectmxmx −=− mm 0 1 2 30 1 2 3 44 33 22 11 )()(~)( 4242 nrectmxmx −=−
12. x2(n-m) là dịch vòng của x2(-m) đi n đơn vị n>0: dịch vòng sang phải, n<0: dịch vòng sang trái xx22(1-m)(1-m)44 mm 0 1 2 30 1 2 3 44 33 22 11 xx22(2-m)(2-m)44 mm 0 1 2 30 1 2 3 44 33 22 11 mm 0 1 2 30 1 2 3 44 33 22 11 xx22(3-m)(3-m)44 mm 0 1 2 30 1 2 3 44 33 22 11 x2(-m)4
13. n=0:  Nhân các mẫu x1(m) & x2(n-m) và cộng lại: 26)0()()0( 3 0 424143 =−= ∑ =m mxmxx  n=1: 23)1()()1( 3 0 424143 =−= ∑ =m mxmxx  n=2: 16)2()()2( 3 0 424143 =−= ∑ =m mxmxx  n=3: 25)3()()3( 3 0 424143 =−= ∑ =m mxmxx Vậy:
14. ĐỔI FOURIER NHANH FFTBÀI 4. BiẾN ĐỔI FOURIER NHANH FFT 1. KHÁI NiỆM BiẾN ĐỔI FOURIER NHANH FFT1. KHÁI NiỆM BiẾN ĐỔI FOURIER NHANH FFT  Vào những năm thập kỷ 60, khi công nghệ vi xử lý phát triển chưa mạnh thì thời gian xử lý phép tóan DFT trên máy tương đối chậm, do số phép nhân phức tương đối lớn.  DFT của x(n) có độ dài N: 10:)()( 1 0 −≤≤= ∑ − = NkWnxkX N n kn N  Để tính X(k), với mỗi giá trị k cần có N phép nhân và (N-1) phép cộng, vậy với N giá trị k thì cần có N2 phép nhân và N(N-1) phép cộng.  Để khắc phục về mặt tốc độ xử lý của phép tính DFT, nhiều tác giả đã đưa ra các thuật tóan riêng dựa trên DFT gọi là FFT (Fast Fourier Transform).
15. FFT CƠ SỐ 22. THUẬT TOÁN FFT CƠ SỐ 2 a. THUẬT TOÁN FFT CƠ SỐ 2 PHÂN THEO THỜI GIANa. THUẬT TOÁN FFT CƠ SỐ 2 PHÂN THEO THỜI GIAN Thuật tóan dựa trên sự phân chia dãy vào x(n) thành các dãy nhỏ, do biến n biểu thị cho trục thời gian nên gọi là phân chia theo thời gian. ∑ − = = 1 0 )()( N n kn NWnxkX ∑∑ − = − = += 1 3,5...,1n 1 2,4...,0n )()( N kn N N kn N WnxWnx ∑∑ − = + − = ++= 1)2/( 0r )12( 1)2/( 0r 2 )12()2()( N rk N N kr N WrxWrxkX Thay n=2r với n chẵn và n=2r+1 với n lẽ: Giả thiết dãy x(n) có độ dài N=2M , nếu không có dạng lũy thừa 2 thì thêm vài mẫu 0 vào sau dãy x(n).
16. của N/2 điểm ứng với chỉ số n chẵn X1(k) – DFT của N/2 điểm ứng với chỉ số n lẽ ∑ − = = 1)2/( 0r 2/0 )2()( N kr NWrxkX ∑ − = += 1)2/( 0r 2/1 )12()( N kr NWrxkXĐặt: )(.)()( 10 kXWkXkX k N+= Lấy ví dụ minh họa cho x(n) với N=8 ∑∑ − = − = ++= 1)2/( 0r 2/ 1)2/( 0r 2/ )12(.)2()( N kr N k N N kr N WrxWWrxkX kr N kr N jrk N j rk N WeeW 2/ 2/ 2 2 2 2 === ππ Do:
17. Phân chia DFT- N điểm -> 2 DFT- N/2 điểm; Qui ước cách tính X(k) theo lưu đồ: - Nhánh ra của 1 nút bằng tổng các nhánh vào nút đó - Giá trị mỗi nhánh bằng giá trị nút xuất phát nhân hệ số
18. lại chỉ số theo thứ tự các mẫu x(n), tiếp tục phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm theo chỉ số n chẵn và lẽ và cứ thế tiếp tục phân chia cho đến khi nào còn DFT 2 điểm thì dừng lại. Ví dụ X0(k) được phân chia: ∑∑ − = − = == 1)2/( 0r 2/ 1)2/( 0r 2/0 )()2()( N kr N N kr N WrgWrxkX ∑∑ − = − = += 1)2/( ...5,3,1r 2/ 1)2/( ...4,2,0r 2/ )()( N kr N N kr N WrgWrg ∑∑ − = − = ++= 1)4/( 0l 4/2/ 1)4/( 0l 4/ )12()2( N kl N k N N kl N WlgWWlg )(.)( 012/00 kXWkX k N+=
19. DFT- N/2 điểm -> 2 DFT- N/4 điểm của X0(k) DFT N/4 x(0) x(4) W0 N/2 W1 N/2 X00(0) X00(1) X0(0) X0(1) DFT N/4 x(2) x(6) X0(2) X0(3) X01(0) X01(1) W2 N/2 W3 N/2  Phân chia X1(k) tương tự: )(.)()( 112/101 kXWkXkX k N+= DFT N/4 x(1) x(5) W0 N/2 W1 N/2 X10(0) X10(1) X1(0) X1(1) DFT N/4 x(3) x(7) X1(2) X1(3) X11(0) X11(1) W2 N/2 W3 N/2
20. DFT dãy x(n) sau 2 lần phân chia với N=8 DFT N/4 x(0) x(4) x(2) x(6) X(0) X(1) X(2) X(3) x(1) x(5) x(3) x(7) X(4) X(5) X(6) X(7) W0 W1 W2 W3 W4 W5 W6 W7 DFT N/4 DFT N/4 DFT N/4 W0 W2 W4 W6 X00(0) X00(1) X01(0) X01(1) X10(0) X10(1) X11(0) X11(1) W0 W2 W4 W6 x(0) x(4) W0 N = 1 WN N/2 =-1 X00(0) X00(1)  Lưu đồ DFT 2 điểm:
21. DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) x(4) x(2) x(6) X(0) X(1) X(2) X(3) x(1) x(5) x(3) x(7) X(4) X(5) X(6) X(7) W0 W1 W2 W3 W4 W5 W6 W7 W0 W2 W4 W6 W0 W2 W4 W6 -1 -1 -1 -1 Xm(p) Xm(q) -1 Xm+1(p) Xm+1(q) Wr N Xm(p) Xm(q) Xm+1(p) Xm+1(q) Wr N WN (r+N/2) = - WN r
22. DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) x(4) x(2) x(6) X(0) X(1) X(2) X(3) x(1) x(5) x(3) x(7) X(4) X(5) X(6) X(7) W0 W1 W2 W3 -1 -1 -1 -1 W0 W2 -1 -1 -1 -1 W0 W2 -1 -1 -1 -1 Đảo bít Với N=2M -> M lần phân chia Số phép nhân = số phép cộng = NM/2=(N/2)log2N
23. phaân chöa ñaûo (n2 ,n1 ,n0 ) Soá nhò phaân ñaûo (n0 ,n1 ,n2 ) Chæ soá ñaûo 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7  Bảng mô tả qui luật đảo bít:
24. Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/g x(0) x(2) x(1) x(3) X(0) X(1) X(2) X(3) W0 W1 -1 -1 -1 -1  k=0: X(0) = [x(0) + x(2)] + W0 [x(1) + x(3)] = 10.  k=1: X(1) = [x(0) - x(2)] + W1 [x(1) - x(3)] = - 2 + j2.  k=2: X(2) = [x(0) + x(2)] - W0 [x(1) + x(3)] = - 2.  k=3: X(3) = [x(0) - x(2)] - W1 [x(1) - x(3)] = - 2 - j2.
25. FFT CƠ SỐ 2 PHÂN THEO TẦN SỐb. THUẬT TOÁN FFT CƠ SỐ 2 PHÂN THEO TẦN SỐ Thuật tóan dựa trên sự phân chia dãy ra X(k) thành các dãy nhỏ, do biến k biểu thị cho trục tần số nên gọi là phân chia theo tần số. ∑ − = = 1 0 )()( N n kn NWnxkX ∑∑ − = − = += 1 2/n 1)2/( 0n )()( N N kn N N kn N WnxWnx ∑∑ − = + − = = 1)2/( 0n )2/( 1)2/( 0n )2/()( N Nnk N N kn N WNnxWnx ∑∑ − = − = = 1)2/( 0n 2/ 1)2/( 0n )2/()( N kn N kN N N kn N WNnxWWnx [ ]∑ − = +−+= 1)2/( 0n )2/()1()( N kn N k WNnxnx
26. thay k=2r: [ ]∑ − = = 1)2/( 0n 2/)2/()()2( N rn NWNnxnxrX Với k lẽ, thay k=2r+1 [ ]{ }∑ − = +−=+ 1)2/( 0n 2/)2/()()12( N rn N n N WWNnxnxrX )2/()()();2/()()( NnxnxnhNnxnxng +−==Đặt: ∑ − = = 1)2/( 0n 2/)()2( N rn NWngrX [ ]∑ − = =+ 1)2/( 0n 2/)()12( N rn N n N WWnhrX X(2r) – DFT của N/2 điểm ứng với chỉ số k chẵn X(2r+1) – DFT của N/2 điểm ứng với chỉ số k lẽ
27. DFT N=8 điểm -> 2 DFT N/2= 4 điểm k chẵn k lẻ DFT N/2 điểm x(0) x(1) x(2) x(3) X(0) X(2) X(4) X(6) DFT N/2 điểm x(4) x(5) x(6) x(7) X(1) X(3) X(5) X(7) W0 W1 W2 W3 g(0) g(1) g(2) g(3) h(0) h(1) h(2) h(3) -1 -1 -1 -1
28. lại chỉ số theo thứ tự các mẫu X(k), tiếp tục phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm theo chỉ số k chẵn và lẽ. Tiếp tục phân chia cho đến khi nào còn DFT 2 điểm thì dừng lại. Dữ liệu ra X(k) được sắp xếp theo thứ tự đảo bít, còn dữ liệu vào được sắp theo thứ tự tự nhiên. Số phép nhân và phép cộng trong lưu đồ phân theo tần số bằng với số phép nhân và cộng trong lưu đồ phân theo thời gian.
29. DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) x(1) x(2) x(3) X(0) X(4) X(2) X(6) x(4) x(5) x(6) x(7) X(1) X(5) X(3) X(7) W0 W1 W2 W3 -1 -1 -1 -1 W0 W2 -1 -1 -1 -1 W0 W2 -1 -1 -1 -1 Đảo bít
30. [x(0) + x(2)] + [x(1) + x(3)] = 10. k=2: X(2) = [x(0) + x(2)] - [x(1) + x(3)] = - 2. k=1: X(1) = [x(0) - x(2)] + W1 [x(1) - x(3)] = - 2 + j2. k=3: X(3) = [x(0) - x(2)] - W1 [x(1) - x(3)] = - 2 - j2. Ví dụ 2: Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/s x(0) x(1) x(2) x(3) X(0) X(2) X(1) X(3) W0 W1 -1 -1-1 -1
31. FFT VỚI N=N3. THUẬT TOÁN FFT VỚI N=N11NN22 Giả thiết dữ liệu vào được sắp xếp vào trong mảng theo thứ tự từng cột với số cột N1 và số hàng N2: Giả thiết độ dài dãy x(n) có thể phân tích N=N1N2, nếu độ dài không thể biểu diễn dưới dạng trên thì thêm vài mẫu 0 vào sau dãy x(n). nn2 nn11 00 11 …… NN11-1-1 00 x(0)x(0) x(Nx(N22)) …… x[Nx[N22(N(N11-1)]-1)] 11 x(1)x(1) x(Nx(N22+1)+1) …… x[Nx[N22(N(N22-1)+1]-1)+1] …… …… …… …… …… NN22-1-1 x(Nx(N22-1)-1) x(2Nx(2N22-1)-1) …… x[Nx[N11NN22-1]-1]
32. sắp xếp dãy x(n) với N=12, chọn N1=3 và N2=4 n2 n1 0 1 2 0 x(0)x(0) x(4)x(4) x(8)x(8) 1 x(1)x(1) x(5)x(5) x(9)x(9) 2 x(2)x(2) x(6)x(6) x(10)x(10) 3 x(3)x(3) x(7)x(7) x(11)x(11) Các chỉ số n của x(n), k của X(k) xác định: n = n1N2 + n2 0 ≤ n1 ≤ N1 0 ≤ n2 ≤ N2 k = k1 + k2N1 0 ≤ n1 ≤ N1 0 ≤ n2 ≤ N2
33. dãy x(n) được phân tích: ∑ ∑ − = − = ++ +=+= 1 0 1 0 ))(( 212121 2 2 1 1 212121 )()()( N n N n NnnNkk NWNnnxNkkXkX ∑ ∑ − = − = += 1 0 1 0 2 212 2 2 1 1 21211222111 )( N n N n NNkn N Nkn N Nkn N kn N WWWWNnnx 1;;:Do 212122122 2 11 1 211 === NNkn N kn N Nkn N kn N Nkn N WWWWW ∑ ∑ − = − =               +=⇒ 1 0 1 0 212 2 2 22 2 12 1 1 11 1 )()( N n kn N kn N N n kn N WWWNnnxkX
34. bước tiến hành thuật tóan:Các bước tiến hành thuật tóan: Sắp xếp dữ liệu vào theo thứ tự từng cột, mảng x Tính DFT theo từng hàng mảng x, được F(n2,k1) Tính mảng hệ số WN n2k1 Nhân mảng F(n2,k1) với WN n2k1 , được G(n2,k1) Tính DFT theo từng cột mảng G(n2,k1), được X(k) Đọc dữ liệu ra theo thứ tự từng hàng X(k).
35. Nêu các bước tính và vẽ lưu đồ thuật tóan FFT dãy x(n) với N=N1N2=12, chọn N1=3 và N2=4 Sắp xếp dữ liệu vào theo thứ tự từng cột như bảng: nn2 nn11 00 11 22 0 x(0)x(0) x(4)x(4) x(8)x(8) 1 x(1)x(1) x(5)x(5) x(9)x(9) 2 x(2)x(2) x(6)x(6) x(10)x(10) 3 x(3)x(3) x(7)x(7) x(11)x(11)
36. từng hàng mảng x, được F(n2,k1): nn2 kk11 0 1 2 00 F(0,0)F(0,0) F(0,1)F(0,1) F(0,2)F(0,2) 11 F(1,0)F(1,0) F(1,1)F(1,1) F(1,2)F(1,2) 22 F(2,0)F(2,0) F(2,1)F(2,1) F(2,2)F(2,2) 33 F(3,0)F(3,0) F(3,1)F(3,1) F(3,2)F(3,2) ∑ − = += 1 0 21212 1 1 11 1 )(),( N n kn NWNnnxknF
37. số WN n2k1 nn2 kk11 0 1 2 00 WWNN 00 WWNN 00 WWNN 00 11 WWNN 00 WWNN 11 WWNN 22 22 WWNN 00 WWNN 22 WWNN 44 33 WWNN 00 WWNN 33 WWNN 66
38. tử mảng F(n2,k1) với các hệ số của mảng WN n2k1 tương ứng, được G(n2,k1) : nn2 kk11 0 1 2 00 G(0,0)G(0,0) G(0,1)G(0,1) G(0,2)G(0,2) 11 G(1,0)G(1,0) G(1,1)G(1,1) G(1,2)G(1,2) 22 G(2,0)G(2,0) G(2,1)G(2,1) G(2,2)G(2,2) 33 G(3,0)G(3,0) G(3,1)G(3,1) G(3,2)G(3,2) Phần tử: G(ni,kj) = F(ni,kj). WN nikj
39. từng cột mảng G(n2,k1), được X(k): kk2 kk11 0 1 2 00 X(0)X(0) X(1)X(1) X(2)X(2) 11 X(3)X(3) X(4)X(4) X(5)X(5) 22 X(6)X(6) X(7)X(7) X(8)X(8) 33 X(9)X(9) X(10)X(10) X(11)X(11) ∑ − = =+= 1 0 12211 2 2 22 2 ),()()( N n kn NWknGkNkXkX Đọc dữ liệu ra theo thứ tự từng hàng X(k)
40. FFT dãy x(n) N=N1N2, với N1=3, N2=4: DFT N1 điểm x(0) x(4) x(8) W0 W1 W2 DFT N1 điểm x(1) x(5) x(9) DFT N1 điểm x(2) x(6) x(10) DFT N1 điểm x(3) x(7) x(11) W0 W2 W4 W0 W3 W6 DFT N2 điểm DFT N2 điểm DFT N2 điểm X(0) X(3) X(6) X(9) X(1) X(4) X(7) X(10) X(2) X(5) X(8) X(11)

Bài tập biến đổi fourier theo thời gian rời rạc năm 2024

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội