Đề tài Tính đáp ứng thời gian cho mạng hai cửa tuyến tính bất biến (bằng cách dùng thuật toán FFT)

Lấy mẫu và khôi phục tín hiệu liên tục theo thời gian Phương pháp tạo ra tín hiệu rời rạc (và tín hiệu số )thông dụng nhất là lấy mẫu tín hiệu tương tự xn(t) .Thông thường các mẫu được lấy cách điều nhau với chu kỳ lấy mẫu là Ts ( tần số lấy mẫu Fs =1/Ts ).Với mọi Ts thế nào đi nữa thì tín hiệu nhận được sau khi lấy mẫu luôn luôn là tín hiệu rời rạc. Định lý lấy mẫu Shannon : Một tín hiệu tương tự xn(t) có dải phổ hửu hạn vớigiới hạn trên là Fmax(Hz) ( Tức phổ bằng 0 khi f nằm ngoài dải -Fmax,…,Fmax) .Ta sẽ chỉ có thể khôi phục lại xa(n,Ts) nếu như FsFmax Hay Ts 1/(2Fmax) Định lý lấy mẫu có một vai trò hết sức quan trọng .Đó là cái nối giữa hai ngành hổ trợ nhau : Xử lý tín hiệu tưong tự và Xử lý tín hiệu rời rạc (số ) .Nó đảm bảo cho tất cả các tất cả các phương pháp và hệ thống xử lý tín hiệu số có thể xâm nhập vào các hệ thống xử lý tín hiệu tương tự .Tính linh hoạt trong sử dụng và tính đa dạng của các kỹ thuật xử lý tính hiệu số . cho phép ta có thể thao tác các xử lý ngày càng hoàn thiện hơn và đôi khi không thể thực hiện đựơc bằng các biện pháp xử lý tín hiệu tương tự . Để hiểu sâu sắc mối quan hệ giữa tín hiệu rời rạc x(n.Ts) được lấy mẫu từ tín hiệu tương tự xa(t) và bản thân tín hiệu tương tự xa(t),chúng ta hãy xem xét kỹ thêm. Ta có cặp phân tích Fourier đối xuvoi71tin1 hiệu tương tự xa(t): Xa( ) = xa(t) = Thay t bằng n.Ts,các mẩu có thể tính : x(n) = xa(n.Ts) = Song từ biến đổi Fourier của tín hiệu rời rạc ta cũng nhận được : x(n) = Khôi phục lại tín hiệu tương tự từ tín hiệu lấy mẫu. Ta có thể khôi phục lại tín hiệu xa(t) bằng cách cho tín hiệu lấy mẫu đi qua một mạch lọc (tương tự ) thông thấp lý tưởng có đáp ứng tần số Hlp(f) với tần số cắt là fc =Fs/2.Phổ của tín hiệu xa(t) sẽ được chính xác chỉ với điều kiện : 2Fmax nghĩa là thoả mãn định lý lấy mẩu. Khi đó không gian tần số : Xa(f) = X(f).Hlp(f) Còn trong không gian thời gian: xa(t) = x(nTs)*hlp(t) trong đó :hlp(t) là đáp ứng xung của mạch lọc thông thấp lý tưởng.( lp:low-pass filter) có biên độ trong dải thông là Ts hlp(t) = = Ts = Ts. = Sự cần thiết của mạch trích và giữ mẫu. Phần trên chúng ta đã xác lập quan hệ giữa tín hiệu tương tư và tín hiệu rời rạc(lấy mẫu).Trên thực tế chúng ta phải thu nhận tín hiệu số để xử lý chứ không hẳn là tín hiệu rời rạc bằng cách cho tín hiệu tương tự qua bộ biến đổi ADC .Lúc này chúng ta còn phải tính đến tốc độ chuyển đổi của bộ ADC và để tăng khả năng tốc độ lấy mẩu cực đại ,ta cần phải mắc thêm bộ trích và giử mẩu vào mạch. Để đơn giản,chúng ta giả thiết tín hiệu vào bộ biến đổi A/D là x(t) =E.sinwt.Đạo hàm của hàm này là = wE.coswt cho ta tốc độ biến thiên ,cực đại của hàm là wE tại thời điểm t=2n với n nguyên . II. Phương pháp tích chập. Việc tính toán DFT được ứng dụng rất nhiều trong thực tế ,đặc biệt là việc phân tích phổ như trong các ngành xử lý tính hiệu tiếng nói ,đia chất ,vật lý,y tế ,ra đa. . . Vì vậy người ta đã quan tâm nhiều đến việc rút ngắn thời gian tính toán.Đặc biệt năm 1965 ,Cooley và Tukey đã tìm ra thuật toán tính DFT một cách nhanh chóng và hiệu quả được gọi là phép biến đổi nhanh Fourier hay còn thường được gọi tắt qua tiếng Anh là FFT .Cần nói rõ là đây không phải là một phép biến đổi mới ,nó thực chất là DFT nhưng được thực hiện với một thuật toán nhanh ,gọn .Kể từ khi ra đời FFT đả tạo ra một bước ngoặt lớn và thực sự đóng vai trò hết sức quan trọng trong việc phân tích ,thiết kế và thực hiện các thuật toán xử lý tín hiệu số cũng như tín hiệu tưong tự. Từ đó đến nay cũng xuất hiện nhiều loại thuật toán FFT mới. Chúng ta biết DFT của dãy x(n) là: X(k) = Với k =0,1,. . .,N-1 Trong đó : = = =Cos(2kn/N) – j.Sin(2kn/N) (Đôi khi để cho tiện ,người ta không cần viết chỉ số N trong hệ số W,khi cần chỉ số này được viết rỏ ra). Phép biến đổi Fourier rời rạc ngược (IDFT) của X(k) là: x(n) = với n= 0,1,2, . . ,N-1 Trước hết chúng ta xem xét qua cách tính trực tiếp DFT với một số nhận xét và lưu ý sau : . Một phép nhân phức tương đương với bốn phép nhân số thực . . Số phép tính chỉ là tương đối : Ví dụ phép nhân đối với W = 1 trong thực tế không cần thực hiện nhưng ta vẫn tính vì với giá trị N lớn ,các phép tính đơn giản kiểu này sẽ là không đáng kể. . Thời gian làm một phép nhân Tn lớn hơn rất nhiều thời gian làm một phép cộng Tc đối với các máy tính vạn năng .Vì vậy chúng ta phải quan tâm giảm nhỏ số phép nhân là chính .Thời gian phụ Tp làm các công việc khác như chuyển số liệu ,đọc các hệ số sẽ có thể tạm bỏ qua .Do vậy độ phức tạp tính số học (số phép nhân là chính và số phép cộng). Việc tính X(k) tương đương với việc tính phần thực A(k) và phần ảo B(k).Ta thấy rằng đối với mỗi giá trị của k ,việc tính toán trực tiếp X(k) cần 4N phép nhân số thực và (4N-2) phép cộng số thực .Vì X(k) phải tính cho N giá trị khác nhau của k ,cho nên cách tính trực tiếp DFT của một dãy x(n) cần có 4N2 phép tính nhân thực và N(4N-2) phép cộng thực hoặc nói cách khác cần có N2 phép nhân số phức và N(N-1) phép cộng phức .Do số lần tính toán và thời gian tính tỷ lệ gần đúng với N2 nên rõ ràng rằng số phép tính số học cần có để tính trực tiếp DFT sẽ trở nên rất lớn khi N tăng.Do vậy các thuật toán đều cố gắng làm giảm số phép tính,đặc biệt là phép nhân ,trong các thuật toán xử lý tính hiệu số nói chung và tính DFT nói riêng .Cooley và Tukey đã công bố một thuật toán tính DFT được áp dụng khi N là một số phức hợp tức N là tích của 2 hay nhiều số nguyên.Thuật toán này đã làm đảo lộn hoạt động ứng dụng của DFT trong XLTHS và dẫn đến việc xuất hiện một số các thuật toán duoc975 mọi ngưòi biết đến với tên FFT. Nguyên tắc cơ bản của tất cả các thuật toán này là dựa trên việc phân tích cách tính DFT của một dãy N số (gọi tắt là DFT N điểm) thành các phép tính DFT của các dãy nhỏ hơn .Nguyên tắc này đã dẫn đến nhiều thuật toán khác nhau và tất cả đều giảm đáng kể thời gian tính toán .= Chúng ta xem xét nhiều vài thuật toán DFT ,hiệu quả của các thuật toán này khác nhau rất nhiều .Song nói chung chúng điều nhanh hơn cách tính trực tiếp . I.1 Thuật toán Goertzel Đây là một thuật toán cho thấy DFT có thể được tính một cách hiệu quả hơn một chút nhờ sử dụng tính tuần hoàn của các hệ số W.Chúng ta sẽ thấy rằng DFT có thể xem như đáp ứng của một mạch lọc số được xây dựng theo một cách thích hợp để giảm các phép tính. Trước hết ta thấy ngay : = Ta có thể nhân hai vế phải của phương trình (1) với mà không có gì ảnh hưởng gì . (7) Ta hãy đặt : (8) Do đó X(k) = Ta thấy rõ ràng (8) là tích chập rời rạc của dãy hửu hạn x(n) với dãy .Do đó yk(n) có thể coi là đáp ứng của một hệ thống có đáp ứng xung là dãy W-kn với tác động vào là x(n) .Ta có thể mở rộng ra coi x(n) là dãy vô hạn các phần tử n= 0,1,. . . + trong đó x(n) =0 với mọi n N.Vậy X(k) là giá trị ra khi n=N(lưu ý là lúc đó x(N) đã lấy giá trị bằng 0).Đáp ứng xung này có dạng an và nó tương tự như hàm truyền H(z): H(z) = (9) Hệ thống này được thực hiện theo sơ đồ minh hoạ trên hình dưới dạng mạch lọc truy hồi bậc nhất. Thực ra số phép tính này làm theo phưong pháp này cũng giống như khi tính DFT trực tiếp .Song nó có lọi hơn một chút ở chổ là đối với phép tính trực tiếp ta phải tính và lưu trử N hệ số W với các giá trị n khác nhau đối với mỗi lần X(k).Tổng cộng tất cả cần N2 lần tính W .Với phương pháp này ta chỉ dùng một ô nhớ chứa giá trị W* cho mỗi nột lần tính X(k) .Khi này tổng cộng tất cả số phép tính W là N lần. Trong các lý do làm chon thuật toán này chua tối ưu là do vòng hồi tiếp phải nhân với hệ số W là một số phức ,việc đó tương đương với 4 phép nhân số thực .Tiếp theo, ta có thể thay đổi sơ đồ tính toán trên để giảm phép nhân đi thêm 2 lần nữa.Nhân tử số và mẩu số của biểu thức với (9) với 1-WK.z-1: H(z) = H(z) = Quan hệ ra vào hay biến đổi ngựơc DFT của H(z) có thể được viết lại như sau : yk(n) = x(n) - Wk.x(n-1) + 2.Cos().yk(n-1) – yk(n-2) Đây là một hệ truy hồi bậc hai với sơ đồ tính toán được vẽ trên hình .Ta thấy phần truy hồi (tương đương với mẩu số của H(z) ) có hai pháp nhân số thực trong đó không kể có một phép nhân với hệ số đặc biệt là -1,còn số phép cộng để thực hiện mẩu số là 4 lần đối với mổi nhịp .Do ta chỉ tính yk(n) tại n=N nên phép nhân phức và cộng ở tử số với W không cần làm với mọi n mà chỉ cần tính duy nhất một lần khi n=N,tức là chỉ cần thêm 4 phép nhân thực và 4 phép cộng thực nữa .Vậy tổng số phép nhân thực và là N(2N+4),tổngsố phép cộng phức là N(4N+4).Chúng ta vẫn giữ được ưu điểm của sơ đồ trước là hệ số cos (2pik/N) và cũng chỉ cần tính có một lần ứng dụng với mỗi giá trị k để tính X(k). [Hinh ] Một ưu điểm của hai phhương pháp trên (phương pháp tính trực tiếp và phương pháp theo thuật toán Goertzel ) ,là ta có thể không cần tính toán toàn bộ X(k) .Chúng ta có thể tính M giá trị X(k),tức là k lấy M giá trị bất kỳ nào đó trong khoảng từ 0 đến N-1 theo nguyên tắc cần X(k) nào thì ta cần tính cụ thể X(k) đó ,không cần tính tất cả các X(k) ,Khi đó số phép tính tỉ lệ với N.M.Với M nhỏ thì các phương pháp này có tác dụng hiệu . II.2 Thuật toán FFT cơ số 2 phân chia theo thời gian Nguyên tắc chung: Nguyên tắc cơ bản của tất cả các thuật toán FFT là dựa trên việc phân tách DFT N điểm thành DFT nhỏ hơn .Theo cách này chúng ta sẽ khai thác cả tính đối xứng và tính tuần hoàn của hàm W. Tính đối xứng : Wk(N-n) =(Wkn)* Tính tuần hoàn: Wkn= Wk(n+N) = W(k+N)n = W(k+N)(n+N) Thuật toán này dựa trên việc phân chia dãy x(n) thành các dãy nhỏ hơn được gọi là thuật toán phân chia theo thơi gian vì chỉ số n thường được gắn liền với thời gian .Nguyên tắc của thuật toán này được minh hoạ rõ nhất khi ta xem xét trường hợp N lấy giá trị đặc biệt : N là luỹ thừa của 2 N=2M Do N là một số chẵn nên ta có thể tính X(k) bằng cách tách x(n) thành 2 dãy ,mỗi dãy có N/2 điểm ,một dãy chứa các điểm lẻ của x(n) một dãy chứa các điểm chẳn của x(n). Cụ thể là công thức tính X(k) ta có: X(k) = với k=0,1,2, . . .,N-1 Sau khi tách dãy x(n) thành các dãy đánh số chẳn và các dãy số lẽ,ta có : X(k) = Hoặc bằng cách thay thế biến n=2r đối với n chẳn và n=2r+1 đối với n là lẻ: X(k) = = III.Cách tính FFT ngược (IFFT : Inverse FFT) Cặp công thức biến đổi Fourier rời rạc thuận và ngược : X(k)= Với k=0,1,2,. . .,N-1 x(n) = Với n=0,1,. . .,N-1. Ngay tuu72 đầu chúng ta nhận xét cặp công thức biến đổi Fourier thuận và ngược có sự tương tự nhau đáng kể.Chúng chỉ khác nhau ở hệ số tỉ lệ 1/N và dấu của hàm exp tức là dấu mũ của hệ số W .Do đó hoàn toàn ta có thể dùng thuật toán FFT thuận để tính FFT ngược bằng cách sau: Lấy liên hợp phức cả hai vế công thức * và chuyển hệ số tỉ lệ N sang trái ta có: N.x*(n) = Vế phải của công thức trên chính là DFT của dãy X*(k) nên ta có thể dùng bất kỳ một chương trình tính FFT nào để tính .Sau đó dãy x(n) có thể nhận được bằng cách lấy liên hợp phức hai vế công thức * và chia cho N để có: x(n) = Như vậy một chương trình tính FFT có thể dùng để tính cả FFT thuận lẫn FFT ngược.Việc tính FFT ngược bằng chương trình tính FFT thuận có thể được tóm lại bằng các bước sau: Cho dãy X(k) ,lấy liên hợp phức của X(k) bằng cách đổi dấu phần ảo của X(k). Gọi chương trình tính FFT để tính FFT của dãy X(k) dã đổi dấu phần ảo . Lấy liên hợp phức của kết quả thu được bằng cách đổi dấu phần ảo .sau đó chia cả dãy cho hệ số tỉ lệ N để thu được kết quả mong muốn . IV. Thực hiện các thuật toán FFT bằng chương trình Trong hai mục trên chúng ta đã trình bày hai thuật toán tính FFT .Điều đó cho phép chúng ta nhìn được tổng quát thuật toán mà không bị sa vào các công thức qua phức tạp.Các thuật toán này có thể được thực hiện bằng các mạch cứng chuyên dụng hoặc bằng các chương trình máy tính .Vì cách làm thứ hai là phổ biến nhất