Bài giảng Xử lý tín hiệu số: Chương 3 - TS. Đặng Quang Hiếu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

64
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Xử lý tín hiệu số - Chương 3: Các thuật toán FFT và ứng dụng" cung cấp cho người học các kiến thức: Ứng dụng của DFT, các thuật toán FFT. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Xử lý tín hiệu số: Chương 3 - TS. Đặng Quang Hiếu

ET4020 - Xử lý tín hiệu số Chương 3: Các thuật toán FFT và ứng dụng TS. Đặng Quang Hiếu http://dsp.edabk.org Trường Đại học Bách Khoa Hà Nội Viện Điện tử - Viễn thông Năm học 2012 - 2013 Outline Ứng dụng của DFT Các thuật toán FFT
Thực hiện hệ thống FIR Xét hệ thống LTI với đáp ứng xung h(n) có chiều dài hữu hạn P. Khi đầu vào x(n) chiều dài L, ta có: y (n) = x(n) ∗ h(n) = x(n)N (∗)M h(n)N trong đó N ≥ L + P − 1, các dãy x(n)N , h(n)N được chèn thêm 0 vào cuối. x(n) DFT IDFT y (n) h(n) DFT Trên thực tế, đầu vào x(n) rất dài so với đáp ứng xung h(n) (có thể coi dài tới vô hạn): L ≫ P. Khi đó, chia x(n) thành các đoạn nhỏ trước khi chập → chập phân đoạn. Chập phân đoạn: Xếp chồng & cộng (overlap-add) đầu vào x1 (n) x2 (n) (P − 1) điểm x3 (n) đầu ra y1 (n) + y2 (n) + y2 (n) +
Chập phân đoạn: Đặt kề nhau (overlap-save) đầu vào x1 (n) (P − 1) điểm 0 x2 (n) x3 (n) đầu ra y1 (n) y2 (n) y3 (n) Bỏ Phân tích phổ của tín hiệu thời gian thực Nguyên lý: Chia tín hiệu thành các đoạn (thường là chồng lên nhau), thực hiện biến đổi FFT trên từng đoạn, với các loại cửa sổ khác nhau. Các bước thực hiện trên một đoạn dữ liệu: 1. Rời rạc hóa tín hiệu x(t) → x(n), xét trên một đoạn N mẫu 2. Nhân với hàm cửa sổ xd (n) = x(n)w (n) 3. Thực hiện FFT M-điểm cho xd (n), với M ≥ N (thêm các điểm 0 vào cuối ko làm thay đổi phổ tín hiệu!). 4. Chuẩn hóa tần số, biên độ khi vẽ |X (k)| Lưu ý: ◮ Ảnh hưởng của cửa sổ: Rò rỉ công suất (leakage) ◮ Độ phân giải tần số ◮ Các đoạn chồng lên nhau (overlapping)
Outline Ứng dụng của DFT Các thuật toán FFT Độ phức tạp tính toán của DFT N−1 X X (k) = x(n)WNkn , 0≤k ≤N −1 n=0 trong đó, WN = e −j2π/N . Để tính trực tiếp mỗi giá trị của X (k): ◮ N phép nhân phức (4N phép nhân thực và 2N phép cộng thực) ◮ N − 1 phép cộng phức (2N − 2 phép cộng thực) ◮ 2N phép tính giá trị các hàm sin, cos. Độ phức tạp tính toán của DFT - N điểm: O(N 2 ).
DIT Radix-2 FFT (phân chia theo thời gian, cơ số 2) Xét N = 2v , chia x(n) thành hai dãy chỉ số chẵn x(2m) và chỉ số lẻ x(2m + 1): N−1 X X (k) = x(n)WNkn , k = 0, 1, · · · , (N − 1) n=0 N/2−1 N/2−1 X X k(2m+1) = x(2m)WNk2m + x(2m + 1)WN m=0 m=0 Với k = 0, 1, . . . , N/2, ta có: N/2−1 N/2−1 X X km X (k) = x(2m)WN/2 + WNk km x(2m + 1)WN/2 m=0 m=0 = F1 (k) + WNk F2 (k) DIT Radix-2 FFT: Độ phức tạp tính toán Nhận xét: F1 (k + N/2) = F1 (k) F2 (k + N/2) = F2 (k) k+N/2 WN = −WNk do vậy, N X (k + ) = F1 (k) − WNk F2 (k) 2 X (k) = F1 (k) + WNk F2 (k) Nếu tính toán trực tiếp F1 (k) và F2 (k), tổng số phép nhân phức là: 2(N/2)2 + N/2
DIT Radix-2 FFT: Chia để trị F1 (0) x(0) b b b X (0) WN0 F1 (1) x(2) b b b X (1) DFT WN1 N/2 - điểm F1 (2) x(4) b b b X (2) WN2 F1 (3) x(6) b b b X (3) WN3 F2 (0) x(1) b b b X (4) −WN0 F2 (1) x(3) b b b X (5) DFT −WN1 N/2 - điểm F2 (2) x(5) b b b X (6) −WN2 F2 (3) x(7) b b b X (7) −WN3 DIT Radix-2 FFT: Rút gọn x(0) b b b X (0) x(2) b b b X (1) DFT N/2 - điểm x(4) b b b X (2) x(6) b b b X (3) WN0 x(1) b b b X (4) −1 WN1 x(3) b b b X (5) DFT −1 N/2 - điểm WN2 x(5) b b b X (6) −1 WN3 x(7) b b b X (7) −1
DIT Radix-2 FFT: Tiếp tục phân chia x(0) b b b b b X (0) DFT N/4 - điểm x(4) b b b b b X (1) WN0 x(2) b b b b b X (2) DFT −1 N/4 - điểm WN2 x(6) b b b b b X (3) −1 WN0 x(1) b b b b b X (4) DFT −1 N/4 - điểm WN1 x(5) b b b b b X (5) −1 WN0 WN2 x(3) b b b b b X (6) DFT −1 −1 N/4 - điểm WN2 WN3 x(7) b b b b b X (7) −1 −1 DIT Radix-2 FFT: Lưu đồ tín hiệu hoàn chỉnh x(0) b b b b b b b X (0) WN0 x(4) b b b b b b b X (1) −1 WN0 x(2) b b b b b b b X (2) −1 WN0 WN2 x(6) b b b b b b b X (3) −1 −1 WN0 x(1) b b b b b b b X (4) −1 WN0 WN1 x(5) b b b b b b b X (5) −1 −1 WN0 WN2 x(3) b b b b b b b X (6) −1 −1 WN0 WN2 WN3 x(7) b b b b b b b X (7) −1 −1 −1
DIT Radix-2 FFT: Sơ đồ cánh bướm Xm−1 (p) b b Xm (p) WNr Xm−1 (q) b b Xm (q) −WNr Hình: Sơ đồ cánh bướm cơ bản Xm−1 (p) b b b Xm (p) Xm−1 (q) b b b Xm (q) WNr −1 Hình: Sơ đồ cánh bướm rút gọn Tính toán tại chỗ và đảo bit Xm (p) = Xm−1 (p) + WNr Xm−1 (q) Xm (q) = Xm−1 (p) − WNr Xm−1 (q) Không cần có bộ nhớ trung gian! Khi đó, cần đảo thứ tự tại đầu vào (chặng 0): Thứ tự Nhị phân Đảo bit Giá trị X0 (0) 000 000 x(0) X0 (1) 001 100 x(4) X0 (2) 010 010 x(2) X0 (3) 011 110 x(6) X0 (4) 100 001 x(1) X0 (5) 101 101 x(5) X0 (6) 110 011 x(3) X0 (7) 111 111 x(7)
DIF Radix-2 FFT (phân chia theo tần số, cơ số 2) N−1 X X (k) = x(n)WNkn , k = 0, 1, · · · , (N − 1) n=0 N/2−1 N−1 X X = x(n)WNkn + x(n)WNkn m=0 n=N/2 N/2−1 N/2−1 X X kN/2 = x(n)WNkn + x(n + N/2)WN WNkn m=0 n=0 N/2−1 X = [x(n) + (−1)k x(n + N/2)]WNkn m=0 DIF Radix-2 FFT: Độ phức tạp tính toán Tách X (k) thành hai dãy có chỉ số chẵn, lẻ: N/2−1 X kn X (2k) = [x(n) + x(n + N/2)]WN/2 m=0 N/2−1 X X (2k + 1) = [x(n) − x(n + N/2)]WNn WN/2 kn m=0 Độ phức tạp tính toán: (N/2) log 2 N phép nhân phức và N log2 N phép cộng phức. Xm−1 (p) b b b Xm (p) Xm−1 (q) b b b Xm (q) −1 WNr Hình: Sơ đồ cánh bướm
DIF Radix-2 FFT: Lưu đồ tín hiệu hoàn chỉnh x(0) b b b b b b b X (0) WN0 x(1) b b b b b b b X (4) −1 WN0 x(2) b b b b b b b X (2) −1 WN2 WN0 x(3) b b b b b b b X (6) −1 −1 WN0 x(4) b b b b b b b X (1) −1 WN1 WN0 x(5) b b b b b b b X (5) −1 −1 WN2 WN0 x(6) b b b b b b b X (3) −1 −1 WN3 WN2 WN0 x(7) b b b b b b b X (7) −1 −1 −1 Bài về nhà 1. Vẽ lưu đồ tín hiệu cho thuật toán FFT trường hợp N = 16, phân chia theo tần số / thời gian, cơ số 2. 2. Tìm hiểu thuật toán FFT cơ số 4. 3. Triển khai các thuật toán FFT đã học bằng ngôn ngữ C, so sánh tốc độ. 4. Sử dụng bộ DFT N-điểm để tính DFT 2N-điểm của dãy số thực. 5. Tính toán tối ưu DFT N-điểm của hai dãy số thực (cùng chiều dài hữu hạn N).