1 Đánh Giá Cách Tính Trực Tiếp DFT - Tài Liệu Text - 123doc

1. Trang chủ >
2. Kỹ thuật >
3. Điện - Điện tử - Viễn thông >

1 Đánh giá cách tính trực tiếp DFT

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.18 MB, 33 trang )

 ∑x(n) = IDFT [X(k)]= N −12.21−X ( k )WN kn 0 ≤ n ≤ N −1N k =00Theo các biểu thức (1.1) và (1.2) ở trên chúng ta có những nhận xét sau đây:- x(n) và X(k) là phức (về tổng quát)- Cả hai biểu thức trên chỉ khác nhau bởi một hệ số nhân tỷ lệ 1/N và dấu của hàmmũ WN.Để thấy rõ điều này chúng ta thử xây dựng thủ tục tính trực tiếp DFT ngược như sau:11− kn*kn x(n) = ∑ X (k )WN =  ∑ X (k )WN N k =0N  k =0N −1N −1*2.3(*: là dấu hiệu liên hợp phức) dẫn đến:N −1N .x* (n) = ∑ X * (k )WNkn2.4k =0So sánh hai biểu thức (1.1) và (1.3) thấy rằng chúng gần như giống nhau. Như thếta có thể thấy rằng các thuật toán FFT được sử dụng cho cả biến đổi Fourier rời rạc thuận.Sau đây chúng ta tiến hành nghiên cứu hiệu quả của cách tính trực tiếp DFT thuận thôngqua việc tính số lượng phép nhân và cộng phức và thực.- Tính toán số lượng phép nhân và cộng phứcNhìn vào biểu thức (10.2.1.1) ta thấy ngay rằng đối với mỗi giá trị của k, cách tínhtrực tiếp DFT phải thực hiện N phép nhân phức và N - 1 phép cộng phức. Nhưng k lấy Ngiá trị từ 0 đến N – 1:X(0), X(1),…,X(N-1)Vậy cách tính trực tiếp DFT phải thực hiện: N 2 phép nhân phức và N(N-1) phép cộngphức (khi- Tính toán số lượng phép nhân và cộng số thựcTổng quát ta thấy rằng x(n) là phức và là phứcVậy ta có thể viết DFT như sau:42.5Từ đây ta thấy rằng số lượng phép nhân và phép cộng số thực sẽ được tính như sau:phép nhân số thực- N [4(N-1)+3]=N(4N-1) phép cộng số thực khiNhận xét:- Việc tính toán trực tiếp N mẫu của X(k)N đòi hỏi số lượng các phép toán cỡ N 2phép- Khi N rất lớn thì N2 sẽ là con số quá lớn như vậy thời gian tính toán sẽ quá dài vàdung lượng nhớ của máy tính sẽ phải rất lớn. Ta thấy rằng phải tìm ra các phươngpháp tính nhanh DFT thì ta mới có thể sử dụng DFT một cách hiệu quả trong quátrình xử lý tín hiệu.2.2. Các tính chất củaHầu như tất cả các phương pháp tính DFT một cách hiệu quả đều phải dựa trên haitính chất của , đó là tính tuần hoàn và tính đối xứng.Sau đây chúng ta sẽ xét hai tính chất này:• Tính tuần hoàn( k ' n' + iN )Nk 'n 'NW =WknN=W2.6(Hoặc ta có thể viết: theo modulo N)• Tính đối xứng( N − k '' n'' )NW =WknNk 'n 'NW− k ''n''N=W− k '' n''N=W WNN=12.7k ''n'' *N= (W)Nhận xét:- Tất cả các thuật toán tính nhanh DFT đều dựa trên cùng một nguyên tắc là phânviệc tính toán DFT của một dãy có chiều dài N thành nhiều DFT có chiều dài nhỏhơn bằng cách khai thác các tính chất đối xứng và tính chất tuần hoàn của hàm mũphức .- Việc đưa nguyên tắc này vào tính DFT sẽ dẫn đến một số phương pháp khác nhaumà hiệu quả của các phương pháp đó có thể so sánh với nhau được.53. Biến đổi Fourier nhanh phân thời gian (FFT)3.1 Định nghĩaThuật toán tính nhanh biến đổi Fourier rời rạc dựa trên việc phân dãy x(n) thànhcác dãy con có chiều dài ngắn hơn được gọi là thuật toán biến đổi Fourier nhanh phânthời gian. Để minh họa thuật toán này trước hết chúng ta nghiên cứu trường hợp đặc biệtmà (N là chiều dài của dãy x(n)).3.2 Thuật toán FFT phân tần thời gian trong truờng hợpa. Thủ tục tổng quátNếu , thì N sẽ là một số nguyên chẵn.Vậy chúng ta có thể phân chia dãy x(n) N thành hai dãy có chiều dài N/2 là hai dãy x(n) Nnhư sau:- Dãy thứ nhất được hình thành bởi các giá trị chẵn,- Dãy thứ hai được hình thành bởi các giá trị lẻ.Về mặt toán học, ta có thể viết hai dãy này như sau:x(2r ) N và x(2r + 1) N22Vậy ta có thể viết:2.8Chúng ta đặt:62.9Ở đây:x(2r ) = g (r )x(2r + 1) = h(r )2.10Hoặc ta có thể viết:2.11Ở đây:-là biến đổi Fourier rời rạc có chiều dàilà biến đổi Fourier rời rạc có chiều dàiVà:là biến đổi Fourier rời rạc của các mẫu lẻ của x(n)là biến đổi Fourier rời rạc của các mẫu chẵn của x(n)Nhận xét+ Như vậy các phép toán được tiến hành với và chỉ trong khoảng , tức là:-7

Xem Thêm

Tài liệu liên quan

• TIỂU LUẬN XỬ LÝ TÍN HIỆU SỐ NÂNG CAO BIẾN ĐỔI FOURIER NHANH
  • 33
  • 949
  • 3
• Hoàn thiện công tác kế toán nguyên vật liệu ở Công ty Đồng Tháp
  • 72
  • 153
  • 0
• Công tác tổ chức hạch toán kế toán tại Công Ty Thương Mại và Dịch Vụ Nhựa
  • 0
  • 4
  • 0

Tải bản đầy đủ (.docx) (33 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.94 MB) - TIỂU LUẬN XỬ LÝ TÍN HIỆU SỐ NÂNG CAO BIẾN ĐỔI FOURIER NHANH-33 (trang) Tải bản đầy đủ ngay ×