Giáo trình xử lý tín hiệu và lọc số 20

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

Thêm vào BST

Báo xấu

100
lượt xem 8
download

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

Các tín hiệu có thể được mô tả duy nhất bằng một biểu diễn toán học rõ ràng như là đồ thị, bảng dữ liệu... được gọi là tín hiệu xác định (deterministic signal). Từ “xác định” ý muốn nhấn mạnh là ta biết rõ và chắc chắn các giá trị của tín hiệu trong quá khứ, hiện tại và tương lai.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình xử lý tín hiệu và lọc số 20

Chương V Có nhiều thuật toán FFT khác nhau bao gồm FFT phân chia theo thời gian và FFT phân chia theo tần số. Trong phần này ta tập trung vào thuật toán FFT cơ số 2 ( N = 2i where i is an integer ) phân chia theo thời gian. 5.4.2 Nguyên tắc của FFT Nguyên tắc cơ bản mà các thuật toán FFT đều dựa vào là phân chia DFT N mẫu thành các DFT nhỏ hơn một cách liên tục: Với N = 2i, đầu tiên ta phân chia DFT N mẫu thành các DFT N mẫu, sau đó phân chia DFT 2 2 mẫu thành DFT 4 mẫu và cứ tiếp tục như thế cho đến khi được các DFT dài N = 2. Việc N N tính DFT nhỏ hơn rõ ràng sẽ cần ít phép tính nhân và cộng phức hơn. Trước tiên, chia x[n] thành các dãy con chẵn và lẻ: ∑ x[n]W + ∑ x[n]W kn X [k ] = kn neven nodd Đặt n = 2m với n chẵn và n = 2m + 1 với n lẻ: N −1 N −1 2 2 X [k ] = ∑ x[2m]W + ∑ x[2m + 1]W k (2 m +1) = 2 mk m=0 m=0 N −1 −1 N 2 2 ∑ x[2m](W ) ∑ x[2m + 1](W +W = 2 mk k 2 mk ) m=0 m =0 X [k ] = X e [k ] + W k X o [k ] = G[k ] + W k H [k ] X e [k ] và X o [k ] là DFT mẫu. N 2 mẫu là x[2m] làm đôi bằng cách đặt m = 2 p : Tiếp theo chia dãy con N 2 N −1 −1 N 4 4 X e [k ] = ∑ x[4 p](W ) + W ∑ x[4 p + 2](W )= 4 kp 2k 4 kp p =0 p =0 Thực hiện tương tự như vậy cho dãy con x[2m+1] Ví dụ: N = 8 Quá trình phân chia DFT 8 mẫu thành các DFT nhỏ hơn được minh họa trên lưu đồ. Đầu tiên, chia x[n] thành 2 dãy con, dãy thứ nhất là dãy chẵn x[0], x[2], x[4], x[6] và dãy thứ hai là dãy lẻ x[1], x[3], x[5], x[7]. Tiếp theo, chia dãy chẵn thành 2 dãy con, dãy thứ nhất là x[0], x[4] và dãy thứ hai là x[2], x[6]. Tương tự, dãy lẻ được chia thành 2 dãy con, là dãy x[1], x[5] và dãy x[3], x[7]. Các DFT 2 mẫu được tính đơn giản như sau: 2π 1 −j G[k ] = ∑ g[n ]W , 0 ≤ k ≤ 1, W = e = −1 nk 2 n =0 ⇒ G[0] = g[0]W 0.0 + g[1]W 1.0 = g[0] + g[1] (chỉ cần phép cộng và trừ) G[1] = g[0]W + g[1]W = g[0] − g[1] 0.1 1.1 - 108 -
Chương V - 109 -
Chương V FFT cơ sở: A “Butterfly” 0 WNr WN(r + N/2) Lưu ý: WN(r + N/2) = WN N/2 WNr = -1 WNr = - WNr , do đó có thể vẽ lại lưu đồ FFT đơn giản như sau: - 110 -
Chương V Phụ lục 1 Summary: The Common Types of Fourier Transforms Continuous in Time x(t ) Discrete in Time x[n] = Aperiodic in Frequency = Periodic in Frequency Fourier Series (FS): Discrete Fourier Series (DFS) and Discrete Fourier Transform Periodic in (DFT): 1 ∫T x(t )e 0 dt − jkω t Time, ak = T N −1 X [k ] = ∑ x[n]WNkn , 0 ≤ k ≤ N − 1 = Discrete ∞ ∑ae jkω0t x(t ) = n=0 in k k =−∞ Frequency N −1 1 ∑ X [k ]W − kn x[n] = , 0 ≤ n ≤ N −1 N N k =0 π − j 2N where WN = e . Aperiodic Fourier Transform (FT): Discrete-Time Fourier in Time, Transform (DTFT): ∞ X (ω ) = ∫ x(t )e − jωt dt −∞ ∞ = ∑ x[n]e − jΩn X (Ω) = ∞ x(t ) = ∫ X (ω )e − jωt dt Continuous n =−∞ −∞ 1 in ∫ π X (Ω)e jΩn x[n] = dΩ 2π Frequency 2 - 111 -
Chương V Phụ lục 2 Some Fourier Relationships The Fourier transform is the Laplace transform evaluated on the j∞ axis. X (ω ) = ∫ x(t )e − jωt dt = X ( s ) s = jω = ⎡ ∫ x(t )e− st dt ⎤ ∞ ∞ ⎢ −∞ ⎥ s = jω ⎣ ⎦ −∞ The discrete-time Fourier transform is the z-transform evaluated around the unit circle. ⎡∞ ⎤ ∞ ∑ x[n]e − jΩn = X ( z ) z =e jΩ = ⎢ ∑ x[n]x − n ⎥ X (Ω) = ⎣ n =−∞ ⎦ z = e jΩ n =−∞ Discrete-time periodic signals can also be described by a Fourier Series expansion: ∑ ak e jk Ω0 n x[n] = synthesis equation k∈< N > and 1 ∑ x[n]e − jk Ω0 n ak = analysis equation N n∈< N > then using the DTFT of the impulse train, P (Ω) that we previously found, the DTFT of an arbitrary discrete-time periodic signal can be found from X 0 (Ω) the DTFT of one period x0 [n] ⎛ 2π 2π k ⎞ ∑ δ (Ω − X (Ω) = X 0 (Ω) ⎜ ) N⎟ ⎝N ⎠ k 2π 2π k 2π k ∑X )δ (Ω − = ( ) 0 N N N k The DFT is simply a scaled version of the terms of one period of the discrete time Fourier transform for a periodic sequence: 2π k N −1 ) = ∑ x[n]WN , 0 ≤ k ≤ N − 1 X [k ] = X 0 ( kn N n=0 for Ω = , k = 0,1,…, N − 1 , i.e. only look at the N distinct sampled frequencies of X 0 (Ω) . 2π k N Also important, the orthogonality of exponentials: N −1 ∑W = Nδ [k ] kn N n=0 π − j 2N where WN = e . - 112 -