Luận văn: Biến đổi Fourier Nhanh và Ứng dụng

Khám phá Luận văn về Biến đổi Fourier Nhanh (FFT) và các ứng dụng thực tiễn, từ lý thuyết đến triển khai trong các lĩnh vực khác nhau.

• Tác giả: Trần Quốc Hội
• Người hướng dẫn: TS. Nguyễn Văn Ngọc
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Toán học
• Đề tài: Biến đổi Fourier Nhanh: Nguyên lý và Ứng dụng
• Loại tài liệu: luận văn
• Năm xuất bản: 2010
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: Biến đổi Fourier rời rạc
• 1.1. Căn bậc N của đơn vị và các tính chất
• 1.2. Các tính chất của WN
• 1.3. Hàm rời rạc tuần hoàn trong không gian Unita CN
• 1.4. Không gian Unita CN
• 1.5. Biến đổi Fourier rời rạc của dãy tuần hoàn
• 1.6. Các tính chất của biến đổi Fourier rời rạc đối với dãy tuần hoàn
• 1.7. Biến đổi Fourier rời rạc của dãy không tuần hoàn có chiều dài hữu hạn
• 1.8. Biến đổi cosine và sine rời rạc
• 1.9. Định nghĩa biến đổi rời rạc tổng quát
• 2. CHƯƠNG 2: Biến đổi Fourier nhanh
• 2.1. Thuật toán biến đổi Fourier nhanh rút gọn theo thời gian đối với N = 2k
• 2.2. Hiệu quả tính toán của thuật toán FFT
• 2.3. Thuật toán Fourier nhanh rút gọn theo tần số
• 2.4. Biến đổi Fourier nhanh đối với trường hợp N = RC
• 2.5. Dạng nhân tử FFT tổng quát
• 2.6. Một số ứng dụng
• 3. CHƯƠNG 3: Một số ứng dụng
• Tài liệu tham khảo

Tóm tắt

I. Biến đổi Fourier rời rạc

Chương này trình bày lý thuyết của Biến đổi Fourier rời rạc (DFT) cho dãy số tuần hoàn. DFT là một công cụ quan trọng trong xử lý tín hiệu, cho phép chuyển đổi tín hiệu từ miền thời gian sang miền tần số. Định nghĩa DFT được đưa ra như sau: với hàm tuần hoàn f(n) chu kỳ N, DFT được tính bằng công thức F(n) = Σ f(k) * WN^(-kn), với WN = e^(2πi/N). Các tính chất của DFT như tính tuyến tính, đẳng thức Parseval, và tính tuần hoàn được trình bày chi tiết. Đặc biệt, tính tuyến tính cho phép kết hợp nhiều tín hiệu, trong khi đẳng thức Parseval liên kết năng lượng của tín hiệu trong miền thời gian và miền tần số. Điều này cho thấy sự quan trọng của DFT trong việc phân tích và xử lý tín hiệu.

1.1. Định nghĩa và tính chất của DFT

DFT được định nghĩa thông qua công thức F(n) = Σ f(k) * WN^(-kn), n = 0, 1, ..., N-1. Tính chất tuyến tính của DFT cho phép nếu f1(n) và f2(n) là hai tín hiệu, thì DFT của tổng chúng là tổng DFT của từng tín hiệu: F(f1 + f2) = F(f1) + F(f2). Đẳng thức Parseval cho thấy rằng tổng bình phương của các hệ số DFT tương đương với tổng bình phương của tín hiệu gốc, tức là năng lượng tín hiệu được bảo toàn khi chuyển đổi giữa hai miền. Tính tuần hoàn của DFT cũng rất quan trọng, vì nó cho phép xử lý các tín hiệu tuần hoàn một cách hiệu quả.

1.2. Biến đổi Fourier nhanh FFT

Biến đổi Fourier nhanh (FFT) là một thuật toán tối ưu hóa cho DFT, giúp giảm độ phức tạp tính toán từ O(N^2) xuống O(N log N). Thuật toán FFT được phát triển bởi Cooley và Tukey vào năm 1965, và nó đã trở thành một công cụ không thể thiếu trong xử lý tín hiệu số. FFT hoạt động bằng cách chia nhỏ bài toán DFT thành các bài toán nhỏ hơn, từ đó giảm thiểu số phép toán cần thiết. Điều này không chỉ tiết kiệm thời gian tính toán mà còn cho phép xử lý các tín hiệu lớn một cách hiệu quả. Các ứng dụng của FFT rất đa dạng, từ phân tích tần số trong âm thanh đến xử lý hình ảnh và truyền thông.

II. Thuật toán FFT

Thuật toán FFT được chia thành hai loại chính: FFT phân tích theo thời gian và FFT phân tích theo tần số. Trong thuật toán phân tích theo thời gian, tín hiệu được chia thành các tầng lớp nhỏ hơn, mỗi tầng lớp được xử lý độc lập. Điều này cho phép giảm thiểu số phép toán cần thiết, từ đó tăng tốc độ tính toán. Trong khi đó, thuật toán phân tích theo tần số tập trung vào việc tối ưu hóa các phép toán nhân và cộng, giúp giảm thiểu thời gian xử lý. Đặc biệt, thuật toán Cooley-Tukey là một trong những thuật toán phổ biến nhất, cho phép xử lý các tín hiệu có chiều dài N không phải là lũy thừa của 2 bằng cách sử dụng các phương pháp biến đổi khác nhau.

2.1. Sơ đồ thuật toán FFT

Sơ đồ thuật toán FFT cho N = 2^k cho thấy cách mà tín hiệu được phân tích thành các tầng lớp nhỏ hơn. Mỗi tầng lớp tương ứng với một phép biến đổi Fourier nhỏ hơn, và quá trình này được lặp lại cho đến khi đạt được các tín hiệu có kích thước nhỏ nhất. Điều này cho phép giảm thiểu số phép toán cần thiết, từ đó tăng tốc độ tính toán. Sơ đồ này không chỉ giúp hiểu rõ hơn về cách thức hoạt động của FFT mà còn cung cấp cái nhìn tổng quan về cách mà các tín hiệu được xử lý trong thực tế.

2.2. Hiệu quả tính toán của thuật toán FFT

Hiệu quả tính toán của thuật toán FFT được thể hiện rõ qua việc giảm thiểu số phép toán cần thiết để tính DFT. Thay vì cần O(N^2) phép toán, FFT chỉ cần O(N log N) phép toán, điều này đặc biệt quan trọng khi xử lý các tín hiệu lớn. Sự cải thiện này không chỉ giúp tiết kiệm thời gian mà còn cho phép xử lý các tín hiệu trong thời gian thực, điều này rất quan trọng trong các ứng dụng như truyền thông và xử lý âm thanh. Các nghiên cứu đã chỉ ra rằng FFT có thể giảm thời gian xử lý xuống còn một phần trăm so với các phương pháp truyền thống.

III. Ứng dụng của Biến đổi Fourier nhanh

Biến đổi Fourier nhanh (FFT) có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Trong xử lý tín hiệu, FFT được sử dụng để phân tích tần số của các tín hiệu âm thanh, giúp nhận diện và xử lý âm thanh một cách hiệu quả. Trong lĩnh vực hình ảnh, FFT được áp dụng để nén và xử lý hình ảnh, cho phép giảm kích thước tệp mà không làm giảm chất lượng hình ảnh. Ngoài ra, FFT còn được sử dụng trong các ứng dụng radar và viễn thám, nơi mà việc phân tích tần số của tín hiệu là rất quan trọng. Các ứng dụng này cho thấy giá trị thực tiễn của FFT trong việc cải thiện hiệu suất và độ chính xác của các hệ thống xử lý tín hiệu.

3.1. Xử lý âm thanh

Trong xử lý âm thanh, FFT cho phép phân tích tần số của tín hiệu âm thanh, giúp nhận diện các thành phần tần số khác nhau trong âm thanh. Điều này rất quan trọng trong các ứng dụng như nhận diện giọng nói, nơi mà việc phân tích tần số giúp cải thiện độ chính xác của hệ thống. Ngoài ra, FFT cũng được sử dụng trong các ứng dụng như lọc âm thanh, nơi mà việc loại bỏ các tần số không mong muốn có thể cải thiện chất lượng âm thanh. Các nghiên cứu đã chỉ ra rằng việc sử dụng FFT trong xử lý âm thanh có thể cải thiện đáng kể hiệu suất của các hệ thống nhận diện âm thanh.

3.2. Xử lý hình ảnh

Trong xử lý hình ảnh, FFT được sử dụng để nén và xử lý hình ảnh, cho phép giảm kích thước tệp mà không làm giảm chất lượng hình ảnh. Việc sử dụng FFT trong nén hình ảnh giúp giảm băng thông cần thiết cho việc truyền tải hình ảnh, điều này rất quan trọng trong các ứng dụng truyền thông. Ngoài ra, FFT cũng được sử dụng trong các ứng dụng như khôi phục hình ảnh, nơi mà việc phân tích tần số giúp cải thiện chất lượng hình ảnh. Các nghiên cứu đã chỉ ra rằng việc sử dụng FFT trong xử lý hình ảnh có thể cải thiện đáng kể hiệu suất của các hệ thống xử lý hình ảnh.

Nội dung chính

Tổng quan nghiên cứu

Biến đổi Fourier rời rạc (Discrete Fourier Transform - DFT) và thuật toán biến đổi Fourier nhanh (Fast Fourier Transform - FFT) là những công cụ toán học quan trọng trong xử lý tín hiệu số, được ứng dụng rộng rãi trong nhiều lĩnh vực khoa học và kỹ thuật. Theo ước tính, việc tính toán DFT trực tiếp với độ dài dãy tín hiệu lớn sẽ đòi hỏi số phép toán nhân phức lên đến $N^2$, gây tốn kém về thời gian và tài nguyên tính toán. Thuật toán FFT, được phát triển bởi Cooley và Tukey năm 1965, đã giảm đáng kể số phép toán cần thiết xuống còn khoảng $N \log_2 N$, mở ra khả năng xử lý tín hiệu nhanh và hiệu quả hơn.

Mục tiêu nghiên cứu của luận văn là trình bày cơ sở lý thuyết của biến đổi Fourier rời rạc và thuật toán biến đổi Fourier nhanh, đồng thời khảo sát các ứng dụng thực tiễn của chúng trong giải phương trình vi phân thường, bài toán biên Dirichlet của phương trình Poisson, xử lý tín hiệu tiếng hót trong Rada và lý thuyết tín hiệu số. Phạm vi nghiên cứu tập trung vào các thuật toán FFT cho các trường hợp chiều dài dãy tín hiệu là lũy thừa của 2 và trường hợp tổng quát khi chiều dài có dạng $N=RC$, với R, C không nhất thiết là lũy thừa của 2.

Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp tài liệu tiếng Việt đầy đủ, hệ thống về DFT và FFT, giúp các kỹ sư, nhà toán học và nhà vật lý có thể áp dụng hiệu quả trong các bài toán thực tế, đồng thời nâng cao hiệu suất tính toán và mở rộng ứng dụng trong các hệ thống xử lý tín hiệu số hiện đại.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai khung lý thuyết chính:

1. Biến đổi Fourier rời rạc (DFT): Được định nghĩa cho dãy tuần hoàn chu kỳ $N$ theo công thức $$ F(n) = \sum_{k=0}^{N-1} f(k) W_N^{-kn}, \quad W_N = e^{\frac{2\pi i}{N}}, $$ với các tính chất cơ bản như tính tuyến tính, tính tuần hoàn, đẳng thức Parseval, và các phép dịch chuyển thời gian và tần số. DFT cho phép phân tích tín hiệu rời rạc thành các thành phần tần số.

2. Thuật toán biến đổi Fourier nhanh (FFT): Là thuật toán tối ưu để tính DFT, đặc biệt hiệu quả khi $N = 2^s$. Thuật toán dựa trên nguyên tắc phân tích dãy tín hiệu thành các dãy con nhỏ hơn, tính DFT trên các dãy con này và kết hợp kết quả. Hai dạng thuật toán chính được trình bày là:

   • FFT rút gọn theo thời gian (Decimation in Time)
   • FFT rút gọn theo tần số (Decimation in Frequency)

Ngoài ra, luận văn còn mở rộng thuật toán FFT cho trường hợp chiều dài dãy tín hiệu có dạng $N=RC$, trong đó R hoặc C không phải là lũy thừa của 2, giúp tăng tính linh hoạt trong ứng dụng.

Các khái niệm chuyên ngành quan trọng bao gồm: căn bậc N của đơn vị, không gian Unita $\mathbb{C}^N$, hàm tuần hoàn rời rạc, biến đổi cosine và sine rời rạc (DCT, DST), tích chập trong không gian rời rạc, và các hệ thống tuyến tính trong lý thuyết tín hiệu số.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu chủ yếu là các tài liệu học thuật, sách chuyên khảo và các bài báo khoa học liên quan đến lý thuyết biến đổi Fourier và xử lý tín hiệu số. Phương pháp nghiên cứu bao gồm:

• Phân tích lý thuyết: Trình bày chi tiết các định nghĩa, tính chất, và chứng minh các định lý liên quan đến DFT và FFT.
• Phát triển thuật toán: Mô tả và phân tích các thuật toán FFT, bao gồm thuật toán rút gọn theo thời gian, theo tần số và thuật toán tổng quát cho trường hợp $N=RC$.
• Ứng dụng thực nghiệm: Áp dụng các thuật toán vào giải phương trình vi phân thường, bài toán biên Dirichlet, xử lý tín hiệu tiếng hót trong Rada và phân tích các hệ thống tuyến tính trong lý thuyết tín hiệu số.
• Timeline nghiên cứu: Quá trình nghiên cứu được thực hiện trong khoảng thời gian học tập tại Trường Đại học Khoa học - Đại học Thái Nguyên, với sự hướng dẫn của TS. Nguyễn Văn Ngọc và sự hỗ trợ từ các đơn vị liên quan.

Cỡ mẫu nghiên cứu là các dãy tín hiệu rời rạc có chiều dài từ vài chục đến vài trăm điểm, phù hợp với các bài toán thực tế và minh họa thuật toán. Phương pháp chọn mẫu dựa trên các tín hiệu tuần hoàn và không tuần hoàn có chiều dài hữu hạn, nhằm đánh giá hiệu quả và tính ứng dụng của các thuật toán.

Phương pháp phân tích sử dụng các công cụ toán học, biến đổi ma trận, và các phép biến đổi Fourier rời rạc, kết hợp với phân tích số liệu và so sánh hiệu suất tính toán giữa các thuật toán.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả tính toán của thuật toán FFT: Với chiều dài dãy tín hiệu $N=2^k$, số phép nhân phức cần thiết để tính DFT giảm từ khoảng $N^2$ xuống còn khoảng $2N \log_2 N$. Ví dụ, với $N=64$, số phép nhân giảm từ 3969 xuống còn 192, tức giảm khoảng 20 lần; số phép cộng giảm từ 4032 xuống còn 384, giảm khoảng 10 lần.

2. Thuật toán FFT cho trường hợp $N=RC$: Thuật toán tổng quát cho phép tính DFT với số phép nhân khoảng $N(R+C)$, giảm đáng kể so với tính trực tiếp. Ví dụ, với $N=900=30 \times 30$, số phép nhân giảm từ 810000 xuống còn 54000, tương đương giảm khoảng 15 lần.

3. Ứng dụng giải phương trình vi phân thường: Sử dụng biến đổi Fourier rời rạc để rời rạc hóa và giải gần đúng phương trình vi phân tuần hoàn, với công thức sai phân cấp hai và biến đổi Fourier rời rạc giúp tìm nghiệm gần đúng hiệu quả.

4. Bài toán biên Dirichlet cho phương trình Helmholtz: Áp dụng phương pháp sai phân kết hợp biến đổi Fourier nhanh để giải bài toán biên trong miền hình chữ nhật, giúp giảm thiểu khối lượng tính toán và tăng độ chính xác.

5. Xử lý tín hiệu tiếng hót trong Rada: Định nghĩa biến đổi Fourier rời rạc tiếng hót (DCFT) và chứng minh các tính chất cơ bản, đặc biệt khi chiều dài tín hiệu là số nguyên tố, giúp phân tích tín hiệu phức tạp trong hệ thống Rada.

Thảo luận kết quả

Các kết quả trên cho thấy thuật toán FFT không chỉ giảm đáng kể số phép toán cần thiết mà còn mở rộng khả năng xử lý các tín hiệu có chiều dài không phải là lũy thừa của 2 thông qua thuật toán tổng quát cho trường hợp $N=RC$. Điều này phù hợp với các nghiên cứu trước đây và khẳng định vai trò trung tâm của FFT trong xử lý tín hiệu số.

Việc áp dụng biến đổi Fourier rời rạc vào giải phương trình vi phân và bài toán biên Dirichlet cho thấy tính linh hoạt và hiệu quả của phương pháp trong các bài toán toán học ứng dụng. Các biểu đồ so sánh số phép toán giữa DFT trực tiếp và FFT minh họa rõ ràng sự vượt trội về hiệu suất của FFT.

Ngoài ra, nghiên cứu về biến đổi Fourier rời rạc tiếng hót cung cấp công cụ phân tích tín hiệu đặc thù trong Rada, góp phần nâng cao chất lượng xử lý và nhận dạng tín hiệu trong các hệ thống radar hiện đại.

Tổng thể, luận văn đã cung cấp một hệ thống kiến thức toàn diện, từ lý thuyết đến ứng dụng, đồng thời đề xuất các thuật toán tối ưu giúp nâng cao hiệu quả tính toán trong xử lý tín hiệu số.

Đề xuất và khuyến nghị

1. Triển khai thuật toán FFT trong phần mềm xử lý tín hiệu: Khuyến nghị các đơn vị nghiên cứu và phát triển phần mềm tích hợp thuật toán FFT rút gọn theo thời gian và tần số để tối ưu hóa hiệu suất xử lý tín hiệu, đặc biệt với các dãy tín hiệu có chiều dài lớn. Thời gian thực hiện: 6-12 tháng.

2. Phát triển thuật toán FFT tổng quát cho trường hợp $N=RC$: Khuyến khích nghiên cứu mở rộng và tối ưu thuật toán FFT cho các trường hợp chiều dài tín hiệu không phải lũy thừa của 2, nhằm tăng tính linh hoạt và ứng dụng trong thực tế. Chủ thể thực hiện: các nhóm nghiên cứu toán học ứng dụng và kỹ thuật điện tử.

3. Ứng dụng biến đổi Fourier rời rạc trong giải các bài toán vi phân và bài toán biên: Đề xuất áp dụng phương pháp này trong các bài toán mô phỏng vật lý và kỹ thuật, giúp giảm thời gian tính toán và nâng cao độ chính xác. Thời gian thực hiện: 1-2 năm.

4. Nâng cao đào tạo và phổ biến kiến thức về DFT và FFT: Tổ chức các khóa học, hội thảo chuyên sâu về biến đổi Fourier rời rạc và thuật toán FFT cho sinh viên và kỹ sư, nhằm nâng cao năng lực ứng dụng trong công nghiệp và nghiên cứu. Chủ thể thực hiện: các trường đại học và viện nghiên cứu.

Đối tượng nên tham khảo luận văn

1. Sinh viên và nghiên cứu sinh ngành Toán ứng dụng, Kỹ thuật điện tử và Công nghệ thông tin: Luận văn cung cấp kiến thức nền tảng và nâng cao về biến đổi Fourier rời rạc và thuật toán FFT, hỗ trợ học tập và nghiên cứu chuyên sâu.

2. Kỹ sư phát triển phần mềm xử lý tín hiệu số: Các thuật toán và ứng dụng được trình bày giúp kỹ sư tối ưu hóa các hệ thống xử lý tín hiệu trong thực tế, từ radar đến truyền thông.

3. Nhà nghiên cứu trong lĩnh vực toán học ứng dụng và vật lý: Tài liệu cung cấp phương pháp giải các bài toán vi phân và bài toán biên bằng biến đổi Fourier, hỗ trợ nghiên cứu lý thuyết và thực nghiệm.

4. Giảng viên và chuyên gia đào tạo: Luận văn là nguồn tài liệu tham khảo quý giá để xây dựng giáo trình, bài giảng và tổ chức các khóa đào tạo về xử lý tín hiệu số và toán học ứng dụng.

Câu hỏi thường gặp

1. Biến đổi Fourier rời rạc (DFT) là gì và tại sao nó quan trọng?
   DFT là phép biến đổi chuyển tín hiệu rời rạc từ miền thời gian sang miền tần số, giúp phân tích thành phần tần số của tín hiệu. Nó quan trọng vì ứng dụng rộng rãi trong xử lý tín hiệu, nén dữ liệu và phân tích phổ.

2. Thuật toán FFT có ưu điểm gì so với tính DFT trực tiếp?
   FFT giảm số phép toán từ $O(N^2)$ xuống còn $O(N \log_2 N)$, giúp tăng tốc độ tính toán đáng kể, đặc biệt với các dãy tín hiệu lớn, tiết kiệm tài nguyên và thời gian xử lý.

3. Làm thế nào để áp dụng FFT khi chiều dài dãy tín hiệu không phải là lũy thừa của 2?
   Luận văn trình bày thuật toán FFT tổng quát cho trường hợp $N=RC$, trong đó R và C không nhất thiết là lũy thừa của 2, giúp mở rộng khả năng áp dụng FFT cho nhiều dạng tín hiệu khác nhau.

4. Biến đổi Fourier rời rạc tiếng hót (DCFT) là gì?
   DCFT là biến đổi Fourier rời rạc đặc biệt áp dụng cho tín hiệu tiếng hót trong hệ thống Rada, có tính chất và cấu trúc riêng biệt, giúp phân tích và xử lý tín hiệu phức tạp trong radar.

5. Ứng dụng của biến đổi Fourier rời rạc trong giải phương trình vi phân là gì?
   DFT giúp rời rạc hóa và giải gần đúng các phương trình vi phân tuần hoàn bằng cách chuyển đổi bài toán sang miền tần số, từ đó giải hệ phương trình đại số dễ dàng hơn, nâng cao hiệu quả và độ chính xác.

Kết luận

• Luận văn đã hệ thống hóa lý thuyết biến đổi Fourier rời rạc và thuật toán biến đổi Fourier nhanh, làm rõ các tính chất và phương pháp tính toán hiệu quả.
• Thuật toán FFT giảm đáng kể số phép toán so với DFT trực tiếp, đặc biệt với các dãy tín hiệu có chiều dài lớn hoặc dạng tổng quát $N=RC$.
• Các ứng dụng thực tiễn trong giải phương trình vi phân, bài toán biên Dirichlet, xử lý tín hiệu tiếng hót và lý thuyết tín hiệu số được triển khai thành công, chứng minh tính hiệu quả của phương pháp.
• Đề xuất phát triển và ứng dụng rộng rãi các thuật toán FFT trong phần mềm xử lý tín hiệu và nghiên cứu khoa học.
• Khuyến khích các nhà nghiên cứu, kỹ sư và sinh viên tiếp tục khai thác và mở rộng các ứng dụng của biến đổi Fourier rời rạc trong các lĩnh vực kỹ thuật và khoa học.

Next steps: Triển khai các giải pháp đề xuất, tổ chức đào tạo chuyên sâu và phát triển phần mềm ứng dụng FFT.

Các chuyên gia và nhà nghiên cứu được mời tham khảo và áp dụng các kết quả nghiên cứu để nâng cao hiệu quả xử lý tín hiệu trong công việc và nghiên cứu của mình.

Trích đoạn nội dung tài liệu

1 Mục lục Mục lục . Biến đổi Fourier rời rạc 6 1. Căn bậc N của đơn vị và các tính chất . Các tính chất của WN . Hàm rời rạc tuần hoàn trong không gian Unita CN . Hàm rời rạc tuần hoàn . Không gian Unita CN . Biến đổi Fourier rời rạc của dãy tuần hoàn . Định nghĩa biến đổi Fourier rời rạc . Công thức biến đổi Fourier rời rạc ngược của dãy tuần hoàn 13 1. Các tính chất của biến đổi Fourier rời rạc đối với dãy tuần hoàn . Tính tuyến tính. Đẳng thức Parseval . Tính tuần hoàn . Dịch chuyển và biến điệu . Biến đổi Fourier rời rạc của dãy không tuần hoàn có chiều dài hữu hạn . Biến đổi cosine và sine rời rạc . Định nghĩa biến đổi rời rạc tổng quát . Các phép biến đổi DCT - 1 và DCT - 2 . 23 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 2 Chương 2. Biến đổi Fourier nhanh 25 2. Thuật toán biến đổi Fourier nhanh rút gọn theo thời gian đối với N = 2k . Mô tả thuật toán FFT . Sơ đồ thuật toán FFT theo thời gian đối với N = 23 28 2. Hiệu quả tính toán của thuật toán FFT . Thuật toán Fourier nhanh rút gọn theo tần số . Nội dung của thuật toán rút gọn theo tần số . Sơ đồ thuật toán FFT theo tần số với N = 23 . Biến đổi Fourier nhanh đối với trường hợp N = RC . Trường hợp N = 6 = 3. Dạng nhân tử FFT tổng quát . Một số ứng dụng 39 3. Giải phương trình vi phân thường . Bài toán biên Dirichlet cho phương trình Helmholz . Đặt bài toán . Rời rạc hóa bài toán . Fourier rời rạc cà Fourier nhanh . Các tính chất cơ bản . Một số hệ thống tuyến tính trong lý thuyết tín hiệu số . 61 Tài liệu tham khảo . 62 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 3 Mở đầu Lợi ích của xử lý số các tín hiệu ngày càng được khẳng định rõ ràng. Nó cũng được ứng dụng ở nhiều dạng khác nhau với những hiệu quả đặc biệt là trong các ngành khoa học chứ không phải chỉ là một môn học. Với mức độ phát triển ngày càng cao về cơ bản, về phương pháp và khả năng ứng dụng nó đã lôi cuốn được nhiều kỹ sư, các nhà vật lý cũng như các nhà toán học quan tâm nghiên cứu. Trong lĩnh vực xử lý tín hiệu, biến đổi Fourier rời rạc (DFT) chiếm vị trí hàng đầu nhờ sự tồn tại các thuật toán hiệu quả của biến đổi Fourier rời rạc. Biến đổi Fourier nhanh (FFT) là công cụ hữu hiệu để tính các biến đổi Fourier rời rạc và Fourier rời rạc ngược. Thuật toán F F T được ứng dụng trong nhiều lĩnh vực khác nhau, từ các phép toán số học của số phức đến lý thuyết tín hiệu, lý thuyết nhóm và lý thuyết số. Từ khi Cooley và Tukey phát hiện ra thuật toán tính nhanh các biến đổi Fourier rời rạc vào năm 1965 (người ta quen gọi là biến đổi Fourier nhanh - FFT), thuật toán này ngày càng khẳng định vai trò của mình, đặc biệt là xử lý tín hiệu số. Để tính DFT chiều dài N cần số phép nhân là N 2 và N (N − 1) phép toán cộng. Thời gian tính toán sẽ rất đáng kể nếu N đủ lớn. Một thuật toán nhanh hơn nhiều đã được phát triển bởi Cooley và Tukey khoảng năm 1965 gọi là thuật toán FFT. Đòi hỏi bắt buộc thuật toán này là chiều dài N phải là lũy thừa của 2, tức là N có dạng N = 2s . Thuật toán này dựa vào trên việc khai triển biến đổi Fourier rời rạc của dãy có chiều dài N = 2s thành các tầng lớp nhỏ hơn. Cách mà trong đó nguyên tắc này thực hiện đưa đến nhiều thuật toán khác nhau, tất cả đều có mục đích là cải thiện khả năng tăng tốc độ tính toán. Đó là thuật toán FFT phân tích theo thời gian, thuật toán FFT phân tích theo tần số. Đối với các thuật toán FFT chiều dài N thì N chỉ cần log2 N phép toán nhân và N log2 N phép cộng. Ngoài ra, còn 2 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 4 trình bày thuật toán biến đổi Fourier nhanh cho trường hợp N = RC, trong đó R hoặc C không phải là lũy thừa của 2. Đối với thuật toán biến đổi Fourier nhanh cho trường hợp N = RC thì chỉ cần N (R + C) phép nhân. Luận văn trình bày cơ sở lý thuyết của biến đổi Fourier rời rạc và của thuật toán Fourier nhanh. Ngoài ra, cũng giới thiệu một số ứng dụng của biến đổi trên vào các bài toán về phương trình vi phân thường, bài toán biên Dirichlet của phương trình Poisson trong hình chữ nhật, xử lý tín hiệu tiếng hót trong Rada. Ngoài ra, luận văn trình bày một số bài toán về hàm hệ và tín hiệu đầu ra của các hệ thống tuyến tính trong lý thuyết tín hiệu số. Hiện nay tài liệu bằng tiếng Anh về DFT và FFT rất phong phú. Tuy nhiên, tài liệu bằng tiếng Việt về lĩnh vực này còn rất hạn chế và chủ yếu được trình bày trong các sách kỹ thuật dành cho các kỹ sư. Ngoài phần mở đầu, phần kết luận, luận văn gồm 3 chương. Chương 1 Biến đổi Fourier rời rạc. Trong chương này trình bày lý thuyết của biến đổi Fourier rời rạc cho dãy số tuần hoàn. Chương 2 Biến đổi Fourier nhanh. Trong chương này trình bày hai thuật toán biến đổi Fourier nhanh, đó là thuật toán biến đổi Fourier nhanh rút gọn theo thời gian và thuật toán biến đổi Fourier nhanh rút gọn theo tần số. Ngoài ra, trình bày thuật toán biến đổi Fourier nhanh cho trường hợp N = RC, trong đó R hoặc C không phải là lũy thừa của 2. Chương 3 Một số ứng dụng. Trong chương này trình bày một số ứng dụng của biến đổi Fourier rời rạc vào các bài toán về phương trình vi phân thường, bài toán biên Dirichlet của phương trình Poisson trong hình chữ nhật. Xử lý tín hiệu tiếng hót trong Rada và một số bài toán về hàm hệ và tín hiệu đầu ra của các hệ thống tuyến tính trong lý thuyết tín hiệu số. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 5 Luận văn này được hoàn thành với sự hướng dẫn và chỉ bảo tận tình của TS. Nguyễn Văn Ngọc - Viện Toán Học Hà Nội. Từ đáy lòng mình, em xin được bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm, động viên và sự chỉ bảo hướng dẫn của thầy. Tôi xin cảm ơn tới các Thầy Cô trong Trường Đại Học Khoa Học - Đại Học Thái Nguyên, phòng Đào Tạo Trường Đại Học Khoa Học. Đồng thời tôi xin gửi lời cảm ơn tới tập thể lớp Cao Học Toán K2 Trường Đại Học Khoa Học đã động viên giúp đỡ tôi trong quá trình học tập và làm luân văn này. Tôi xin cảm ơn tới Sở GD - ĐT Tỉnh Lạng Sơn, Ban Giám hiệu, các đồng nghiệp Trường THPT Vũ Lễ - Bắc Sơn, Trường THPT Việt Bắc - TP. Lạng Sơn đã tạo điều kiện cho tôi học tập và hoàn thành kế hoạch học tâp. Tuy nhiên do sự hiểu biết của bản thân và khuôn khổ của luận văn thạc sĩ, nên chắc rằng trong quá trình nghiên cứu không tránh khỏi những thiếu sót, tôi rất mong được sự chỉ dạy và đóng góp ý kiến của các Thầy Cô và độc giả quan tâm tới luận văn này. Thái Nguyên, ngày 10 tháng 9 năm 2010 Tác giả Trần Quốc Hội Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 6 Chương 1 Biến đổi Fourier rời rạc Trong chương này trình bày lý thuyết của biến đổi Fourier rời rạc cho dãy số tuần hoàn. Nội dung chủ yếu của chương này được hình thành từ các tài liệu [1], [2], [3] và [8]. Mở đầu Biến đổi tích phân Fourier của hàm f (t) ∈ L1 (R) thường được định nghĩa bởi công thức Z ∞ fˆ(ω) = f (t)e−iωt dt, ω ∈ R, −∞ còn biến đổi Fourier ngược được cho bởi công thức Z ∞ 1 f (t) = fˆ(ω)eiωt dω. 2π −∞ Một trong các phương pháp tính gần đúng các tích phân trên có thể tiến hành như sau. Trước hết ta giả thiết rằng với các số a, b có trị tuyệt đối đủ lớn: a < 0, b > 0 tích phân Z b f (t)e−iωt dt, a là xấp xỉ tốt của tích phân Fourier. Từ đó đi đến định nghĩa biến đổi Fourier rời rạc. Trong chương này trình bày một số tính chất của biến đổi Fourier rời rạc. Từ nay về sau ta luôn luôn hiểu N là số nguyên dương, z là số phức liên hợp của số phức z, còn Z là tập các số nguyên. Ký hiệu RN và CN tương ứng là các không gian vectơ thực và phức. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www. Căn bậc N của đơn vị và các tính chất 1. Định nghĩa Định nghĩa 1. Nghiệm của phương trình z N − 1 = 0 được gọi là căn bậc N của đơn vị. Trong lý thuyết số phức ta biết rằng đơn vị có N căn bậc N khác nhau và chúng được xác định bởi công thức εk = WNk , (k = 0, 1, .1) 2πi 2π 2π WN = e N = cos + i sin , (1.2) N N trong đó i là đơn vị ảo: i2 = −1. Dễ thấy rằng ε1 = WN .2), như chúng biết là công thức Euler. Sau này chúng ta sẽ gọi WN là hạch Euler. Các tính chất của WN Mệnh đề 1. Hạch Euler WN có các tính chất cơ bản sau đây 1) WNkN = 1, (1.4) −k N −k 3) WNk = WN = WNN +k = WN , (1.6) k(n+N ) (k+N )n 5) WNkn = WN = WN , (1. Các tính chất từ 1) đến 5) là hiển nhiên. Tính chất 6) là trường hợp đặc biệt của tính chất 7), vì vậy ta chỉ cần chứng minh tính chất 7). Thật vậy, ta có WNN = e2πi = 1. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.vn 8 N −1 N −1 N −1 1 X mpN 1 X N mp 1 X W = (W ) = 1 = 1. N m=0 N N WN − 1 Vậy công thức (1.9) được chứng minh. Hàm rời rạc tuần hoàn trong không gian Unita CN 1. Hàm rời rạc tuần hoàn Cho N là một số nguyên dương cố định. Khi đó mọi số nguyên m ∈ Z đều có thể biểu diễn ở dạng m = n + kN, n = 0, 1, . Cho hàm rời rạc f (m) với m ∈ Z.