Xử Lý Số Tín Hiệu - Chương 8: Biến đổi DFT Và FFT - Tài Liệu, Ebook
Có thể bạn quan tâm
- Đăng ký
- Đăng nhập
- Liên hệ
Thư viện tài liệu, ebook tổng hợp lớn nhất Việt Nam
Website chia sẻ tài liệu, ebook tham khảo cho các bạn học sinh, sinh viên
- Trang Chủ
- Tài Liệu
- Upload
Khi đã thực hiện xong việc tính toán cho 1 tầng thì ta không cần lưu kết quả của tầng trước nữa. Do đó, tổng cộng ta chỉ cần 2N thanh ghi để lưu giá trị phức của ngõ vào, kết quả cũng như toàn bộ quá trình tính toán -> có thể thực hiện tính toán tại chỗ. Giải thuật dựa vào sự chia nhỏ chuỗi thời gian rời rạc x(n) được gọi là giải thuật chia nhỏ trên miền thời gian (decimation-in-time). Cho phép ghép nối nhiều khối FFT N điểm để tính FFT nhiều điểm hơn.
34 trang | Chia sẻ: nguyenlam99 | Lượt xem: 3313 | Lượt tải: 0 Bạn đang xem trước 20 trang tài liệu Xử lý số tín hiệu - Chương 8: Biến đổi DFT và FFT, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trênChương 8: Biến đổi DFT và FFT Xử lý số tín hiệu 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) Công thức DTFT cho chuỗi thời gian rời rạc x(n): Nhận xét: X(ω) là hàm liên tục -> không thể thực hiện trên phần cứng các phép biến đổi tín hiệu trong miền tần số. Cần rời rạc phổ của tín hiệu trong miền tần số hay lấy mẫu tần số. Lấy mẫu bao nhiêu là “đủ” để có thể khôi phục lại được tín hiệu x(n) hay X(ω) ban đầu? n njenxX )()( Discrete Time Fourier Transform 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) (tt) Do phổ X(ω) lặp lại với chu kỳ 2, ta chỉ cần lấy mẫu X(ω) trong khoảng [0,2]. Giả sử trong khoảng tần số này ta lấy N mẫu cách đều nhau ω=2/N thì các mẫu này được cho bởi: Đổi biến n=m-lN với m=0,1,,N-1, l=- ∞,,∞ 1,...,1,0 ,)( 2 2 Nkenxk N X n kn N j 1,...,1,0 ,)( 2 1 0 2 )( NkelNmxk N X N m km N j mx l p 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) (tt) có thể tính được từ x(n) bằng cách lặp lại x(n) sau mỗi N mẫu. Giả sử x(n) dài L mẫu, ta có 2 trường hợp: lp lNnxnx )()( 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) (tt) Nhận xét: Nếu N≥L: ta có thể khôi phục hoàn toàn x(n) từ xp(n) bằng cách chọn Nếu N<L: ta không thể khôi phục x(n) từ xp(n). 10 ),()( Nnnxnx p 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) (tt) Cách khôi phục lại x(n) từ X(k): do xp(n) tuần hoàn nên có thể được biểu diễn bằng khai triển chuỗi Fourier: Trong đó: So sánh ck với X(2k/N): Suy ra: 10 ,)( 1 0 /2 Nnecnx N k Nknj kp 10 ,)( 1 1 0 /2 Nkenx N c N k Nknj pk 10 ,)( 2 1 0 2 Nkenxk N X N n kn N j p 10 , 21 Nkk N X N ck 1. Lấy mẫu tần số: Biến đổi Fourier rời rạc (DFT) (tt) Thế vào công thức của khai triển chuỗi Fourier ta suy ra cách khôi phục x(n) từ X(ω): Kết luận: Phổ của tín hiệu rời rạc bất kỳ có chiều dài L có thể được khôi phục chính xác từ các mẫu của nó ở các tần số ωk=2k/N nếu N ≥L. 10 , 21 )( 1 0 /2 Nnek N X N nx N k Nknj 2. Biến đổi DFT Do X(k) được lấy từ X(ω) bằng cách lấy mẫu ở N tần số cách đều nhau nên biến đổi giữa X(k) và x(n) được gọi là biến đổi Fourier rời rạc (DFT). Công thức DFT N điểm của x(n): IDFT Tính chất của biến đổi DFT: (đọc thêm) 1,...,1,0 ,)()( 1 0 /2 NkenxkX N n Nknj 1,...,1,0 , 1 )( 1 0 /2 NnekX N nx N k Nknj 2. Biến đổi DFT (tt) Ảnh hưởng của chiều dài N(số điểm DFT): Giả sử x(n) có chiều dài L, ta thực hiện DFT N điểm cho tín hiệu này (N≥L). Do x(n) chỉ có L điểm, ta cần thêm vào N-L zero. ⇒ Phổ X(k) thay đổi như thế nào khi tăng N? Ví dụ: Tìm biến đổi DFT N điểm của x(n) cho bởi: khác 0 101 )( n Ln nx 2. Biến đổi DFT (tt) Giải: Biến đổi Fourier của tín hiệu x(n): )2/sin( )2/sin( )( 2/)1( 1 1 L eeX Lj L n nj 2. Biến đổi DFT (tt) Biến đổi DFT N điểm cho x(n) Nếu N=L, X(k) trở thành: 1,...,2,10 0 )( Lk kL kX )/sin( )/sin( )( /)1( 1 1 /2 Nk NkL eekX NLkj L n Nknj 2. Biến đổi DFT (tt) Tăng N: N=50. N=100. ⇒ Tăng N sẽ giúp ta có được biểu diễn tốt hơn của X(ω). 2. Biến đổi DFT (tt) Phân tích phổ tần số của tín hiệu sử dụng biến đổi DFT – Độ phân giải tần số. Giả sử ta có một tín hiệu rời rạc x(n) là kết quả của quá trình lấy mẫu x(t) ở tần số lấy mẫu fs. Giả sử x(n) và fs thoả định lý lấy mẫu ⇒ tần số cao nhất của x(n) là fs/2. Chọn L mẫu trong x(n) (0≤n≤L-1) để phân tích DFT. ⇒ Việc giới hạn chiều dài x(n) tương đương với nhân x(n) với cửa sổ chữ nhật chiều dài L: Với )()()( nwnxnx khác 0 101 )( n Ln nw 2. Biến đổi DFT (tt) Giả sử x(n)=cos(ω0n), phổ của x’(n) là Với Nhận xét: Theo lý thuyết, phổ X(ω) là 2 xung diract ở ±ω0. Phổ của X’(ω) tập trung ở ±ω0 nhưng rải trong 1 khoảng tần số chứ ko tập trung tại 1 tần số như X(ω). Độ phân giải tần số hay khoảng cách tối thiểu của 2 tần số nằm gần nhau có thể phân biệt đc trên phổ DFT chính bằng ½ độ rộng của cửa sổ chữ nhật 2/L hay fs/L. )()( 2 1 )( 00 WWX 2/)1( )2/sin( )2/sin( )( Lje L W 2. Biến đổi DFT (tt) VD: Tín hiệu gồm 2 thành phần tần số được phân tích DFT với cửa sổ có chiều dài 64. ⇒ Độ phân giải tần số: /32 Khi khoảng cách giữa 2 tần số thu hẹp nhỏ hơn độ phân giải tần số của cửa sổ chữ nhật thì trên phổ DFT không phân biệt được 2 tần số này. 3. Biến đổi FFT Nhu cầu: cần một giải thuật thực hiện DFT hiệu quả về mặt tính toán và đơn giản, dễ ứng dụng trên phần cứng số. Công thức DFT: đặt WN=e -j2/N. Để tính N điểm X(k), ta cần thực hiện: N2 phép nhân phức. N(N-1) phép cộng phức. ⇒ Chi phí tính toán lớn! 1,...,1,0 ,)()( 1 0 NkWnxkX N n kn N 3. Biến đổi FFT (tt) Giải thuật FFT Radix-2: Giả sử N=2v, DFT N điểm của x(n) có thể được tính theo phương pháp chia nhỏ khối tính DFT thành nhiều khâu như sau: F1(k), F2(k) là DFT N/2 điểm của chuỗi x(2m) và x(2m+1) odd even 1 0 )()( n kn N n kn N N n kn N x(n)Wx(n)WWnxkX 12/ 0 )12(12/ 0 2 )12()2( N m mk N N m mk N WmxWmx )( 12/ 0 2/ )( 12/ 0 2/ 21 )12()2( kF N m km N k N kF N m km N WmxWWmx 3. Biến đổi FFT (tt) So sánh chi phí tính toán: DFT N điểm: N2 phép nhân phức. 2 DFT N/2 điểm: N2/2+N/2 phép nhân phức. Khi N lớn: độ lợi tính toán: ⇒ Khi chia nhỏ khối DFT N điểm thành 2 khối DFT N/2 điểm, ta giảm được ½ chi phí tính toán! ⇒ Càng chia nhỏ càng tiết kiệm được chi phí tính toán! 2 122lim 2 2 N NN N 3. Biến đổi FFT (tt) Cách thực hiện FFT: giả sử ta cần tính DFT 8 điểm: 8-point DFT x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 3. Biến đổi FFT (tt) Chia khối DFT 8 điểm thành 2 khối DFT 4 điểm: 4-point DFT x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 4-point DFT F1(0) F1(1) F1(2) F1(3) F2(0) F2(1) F2(2) F2(3) W80 W81 W82 W83 W85 W86 W87 W84 3. Biến đổi FFT (tt) Chia khối DFT 4 điểm thành 2 khối DFT 2 điểm: 2-point DFT x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) W80 W81 W82 W83 W85 W86 W87 W84 2-point DFT 2-point DFT 2-point DFT W80 W82 W84 W86 W82 W84 W86 W80 3. Biến đổi FFT (tt) Tính các khối DFT 2 điểm x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) W80 W81 W82 W83 W85 W86 W87 W84 W80 W82 W84 W86 W82 W84 W86 W80 W80 W84 W80 W84 W80 W84 W80 W84 3. Biến đổi FFT (tt) Do WN r+N/2=WN rWN N/2=-WN r, ta rút gọn được: x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) -1 -1 -1 -1 W80 W82 W82 W80 W80 W80 W80 W80 W80 W81 W82 W83 -1 -1 -1 -1 -1 -1 -1 -1 3. Biến đổi FFT (tt) Nhận xét: Ở mỗi tầng, phép tính toán cơ bản được cho bởi sơ đồ bướm: Mỗi sơ đồ bướm gồm 1 phép nhân phức và 2 phép cộng phức. Với N=2v, ta có log2N=v tầng, mỗi tầng có N/2 sơ đồ bướm. Như vậy chi phí tính toán là: (N/2)log2N phép nhân phức. (Tính trực tiếp cần N 2) Nlog2N phép cộng phức. (Tính trực tiếp cần N(N-1)) a b A=a+WNrb B=a-WNrb WNr -1 3. Biến đổi FFT (tt) 3. Biến đổi FFT (tt) Nhận xét (tt): Khi đã thực hiện xong việc tính toán cho 1 tầng thì ta không cần lưu kết quả của tầng trước nữa. Do đó, tổng cộng ta chỉ cần 2N thanh ghi để lưu giá trị phức của ngõ vào, kết quả cũng như toàn bộ quá trình tính toán -> có thể thực hiện tính toán tại chỗ. Giải thuật dựa vào sự chia nhỏ chuỗi thời gian rời rạc x(n) được gọi là giải thuật chia nhỏ trên miền thời gian (decimation-in-time). Cho phép ghép nối nhiều khối FFT N điểm để tính FFT nhiều điểm hơn. 27 0 4 1w 1 4 w j 1 11 1 0 1x 2 3x 1 2x 3 4x 0 X 1 X 2 X 3 X 4 -2 6 -2 10 -2+2j -2 -2-2j 3. Biến đổi FFT (tt) VD: Tính DFT 4 điểm x(n)=[1,2,3,4] 3. Biến đổi FFT (tt) Giải thuật chia nhỏ trên miền tần số (Decimation-in- frequency) Chia X(k)thành các mẫu chẵn và lẻ thì: 1 2/ 12/ 0 )()()( N Nn kn N N n kn N WnxWnxkX 12/ 0 2/12/ 0 )2/()( N n kn N kN N N n kn N WNnxWWnx 12/ 0 )2/()1()( N n kn N k WNnxnx 1-N/20,1,...,k ,)2/()()2( 12/ 0 2/ )( N n kn N ng WNnxnxkX 1-N/20,1,...,k ,)2/()()12( 12/ 0 2/ )( N n kn N n N nh WWNnxnxkX 3. Biến đổi FFT (tt) Sơ đồ thực hiện: 3. Biến đổi FFT (tt) Chia đôi 3. Biến đổi FFT (tt) Chia đôi lần nữa! 3. Biến đổi FFT (tt) VD: Tính DFT 4 điểm x(n)=[1,2,3,4] 0 1x 2 3x 1 2x 3 4x 0 X 1 X 2 X 3 X 1 1 1 1 0 4 w 1 4 w 4 6 2 2 j 10 2 2 2 j 2 2 j 4. Biến đổi IFFT Tính IFFT bằng giải thuật FFT 1 0 1 1 0 0 1 1 * * ( ) ( ) ( ) ( ) ( ) ( ) N kn N n N N kn kn N N k k X k x n w x n X k w x n X k w N N X* X*DFT 1/NX(k) X *(k) x(n) 4. Biến đổi IFFT VD: Tính IDFT 4 điểm X(k)=[10,-2+2j,-2,-2-2j] X*(k)=[10,-2-2j,-2,-2+2j] 1 1 1 1 0 4 w 1 4 w 10 -2 -2-2j -2+2j 8 -4 12 -4 4 12 8 16 1 x(0) 3 x(2) 2 x(1) 4 x(3) 1/4 1/4 1/4 1/4 4 2 1( ) ( )n n n nw j w Các file đính kèm theo tài liệu này:
- dsp_chuong_8_bien_doi_dft_va_fft_053.pdf
- Bài giảng Cấu trúc cổng nối tiếp
89 trang | Lượt xem: 2106 | Lượt tải: 4
- Bài giảng Kỹ thuật chuyển mạch - Chương 1: Chuyển mạch kênh (Circuit switching) - Bài 3: Chuyển mạch PAM 4 dây dùng trung kế âm tần cùng nhóm
35 trang | Lượt xem: 296 | Lượt tải: 0
- Chương 4: Mạch điện đơn giản: Rl và RC
17 trang | Lượt xem: 5236 | Lượt tải: 4
- Giáo trình môn Xử lý tín hiệu số - Phần 2
179 trang | Lượt xem: 77 | Lượt tải: 0
- Giải pháp báo hiệu tập trung của viettel
61 trang | Lượt xem: 2354 | Lượt tải: 2
- Bài giảng môn Xử lý số tín hiệu - Chương 1: Lấy mẫu và khôi phục tín hiệu
31 trang | Lượt xem: 478 | Lượt tải: 0
- Xử lý số tín hiệu - Chương 5: Thiết kế mạch lọc số
22 trang | Lượt xem: 3119 | Lượt tải: 0
- Giáo trình Thông tin quang (Trình độ: Trung cấp)
171 trang | Lượt xem: 66 | Lượt tải: 0
- Xử lý số tín hiệu - Chương 1: Lấy mẫu và khôi phục tín hiệu
62 trang | Lượt xem: 1472 | Lượt tải: 0
- Bài giảng Báo hiệu và điều khiển kết nối
91 trang | Lượt xem: 2685 | Lượt tải: 1
Từ khóa » Tính Dft
-
[PDF] BIẾN ĐỔI FOURIER RỜI RẠC (DFT) F - KHVT
-
Biến đổi Fourier Rời Rạc – Wikipedia Tiếng Việt
-
Tính DFT 8 điểm Bằng Thuật Toán FFT Theo Thời Gian _ PTIT - YouTube
-
Xử Lý Số Tín Hiệu -Chuong 4 - Slideshare
-
[PDF] Phép Biến đổi Fourier Rời Rạc Và ứng Dụng
-
Biến đổi Fourier Rời Rạc (DFT). Biến đổi Fourier Rời Rạc
-
[PDF] Biến đổi Fourier Nhanh (fft)
-
1 Đánh Giá Cách Tính Trực Tiếp DFT - Tài Liệu Text - 123doc
-
Biến đổi Fourier Rời Rạc(DFT) Trong Nhận Diện Mặt Người Sử Dụng ...
-
Bài Giảng Xử Lý Số Tín Hiệu - Chương 8: Biến đổi DFT Và FFT
-
Chương5 - PHÉP BIẾN ĐỔI FOURIER RỜI RẠC VÀ ỨNG DỤNG
-
Dft Là Gì Trong Tiếng Việt? Sự Khác Biệt Giữa Fft Và Dft (Toán ...
-
7 DFT LÀ GÌ Mới Nhất 2023