Biến đổi fourier rời rạc, fourier nhanh và ứng dụng.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN THỊ THU THỦY

BIẾN ĐỔI FOURIER RỜI RẠC,

FOURIER NHANH VÀ ỨNG DỤNG

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 60.46.40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2015

Công trình được ho n thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: TS. Phan Đức Tuấn

Phản ện : TS. Lê Hải Trung

Phản ện : PGS. TS. Hu nh Th Phùng

Luận v n đ được ảo vệ tr c Hội đồng chấm Luận văn

tốt nghiệp thạc s ho h c h p tại Đại h c Đ Nẵng vào ngày

11 tháng 01 năm 2015

Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin - H c li u, i học Đà Nẵng

- Trung tâm Học liệu, Đại h c Đà Nẵng

1

MỞ ĐẦU

1. Tính cấp thiết của đề tài

Nhiều vấn đề trong khoa học và công nghệ đưa đến việc giải phương trình

vi phân hay phương trình đạo hàm riêng. Những bài toán về tính độ lệch đứng

của dầm, các dao động của dây, sóng âm, sóng tạo ra do thủy triều, sóng đàn

hồi, sóng điện trường và tìm phương trình đường đi cho các phương trình sóng.

Vấn đề đặt ra ở đây là tìm lời giải cho các bài toán đó. Có nhiều phương pháp

khác nhau để giải quyết vấn đề, trong số đó không thể không nói đến vai trò đặc

biệt quan trọng của phép biến đổi Fourier.

Một khái niệm không kém tầm quan trọng của phép biến đổi Fourier là biến

đổi Fourier rời rạc (DFT). Trong toán học, biến đổi Fourier rời rạc còn được

gọi là phép biến đổi Fourier hữu hạn, là một biến đổi trong giải tích Fourier với

các tín hiệu trong thời gian rời rạc. Nó là công cụ lý tưởng để xử lý thông tin và

được sử dụng rộng rãi trong xử lý tín hiệu và các ngành liên quan đến phân tích

tần số, tìm hình dạng đi lý tưởng cho phương trình truyền sóng, các bài toán sơ

cấp, ma trận và các phép toán như tích chập.

Việc ứng dụng hiệu quả biến đổi Fourier rời rạc trong thực tế đặc biệt là

việc phân tích phổ như trong các ngành xử lý tín hiệu tiếng nói, địa chất, vật lý,

y tế, sóng âm, các bài toán về ma trận,phép nhân đa thức. . . người ta đã quan

tâm đến việc rút ngắn thời gian và độ phức tạp tính toán. Năm 1965, Cooley và

Tukey đã tìm ra thuật toán tính các biến đổi Fourier rời rạc nhanh chóng và hiệu

quả hơn được gọi là biến đổi Fourier nhanh (FFT). Biến đổi Fourier nhanh là

thuật toán cho phép tính DFT nhanh chóng bằng cách giảm độ phức tạp và thời

gian tính toán. Kể từ khi ra đời, biến đổi FFT đã tạo ra một bước ngoặc lớn và

thực sự đóng một vai trò hết sức quan trọng trong việc xử lý tín hiệu, các bài

toán ma trận và bài toán sơ cấp.

2. Mục tiêu nghiên cứu

Mục tiêu của đề tài là nhằm giúp người đọc hiểu đúng bản chất của biến đổi

2

Fourier rời rạc, hiệu quả của biến đổi Fourier rời rạc và thuật toán FFT của nó.

Qua đó có thể áp dụng để tìm lời giải cho một số bài toán sơ cấp, những bài

toán liên quan đến ma trận và phương trình truyền sóng. Một số điểm cố gắng

đưa vào trong luận văn là:

- Một số định nghĩa liên quan đến biến đổi DFT, chứng minh chặt chẽ các

định lí liên quan.

- Làm rõ tính hiệu quả của biến đổi nhanh FFT, đi sâu một số thuật toán cụ

thể.

- Đưa nhiều ví dụ và bài tập áp dụng để làm nổi bật tính hiệu quả, tính nhanh

chóng của biến đổi DFT và FFT.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của đề tài là phép biến đổi Fourier. Phạm vi nghiên

cứu của đề tài là biến đổi Fourier rời rạc, Fourier nhanh và ứng dụng.

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

Thu thập các bài báo khoa học và tài liệu của các tác giả nghiên cứu liên

quan đến biến đổi DFT, vấn đề quan trọng trong khi áp dụng biến đổi DFT và

FFT vào giải toán.

Tham gia các buổi seminar của thầy hướng dẫn để trao đổi các kết quả đang

nghiên cứu. Trao đổi qua email, blog, forum với các chuyên gia về các ứng dụng

của biến đổi DFT và FFT trong giải toán.

5. Bố cục của đề tài

Luận văn gồm phần mở đầu, hai chương, kết luận và phụ lục.

Chương 1 trình bày một số tích chất cơ bản của biến đổi Fourier rời rạc,

Fourier nhanh.

Chương 2 đưa ra một số ứng dụng cơ bản của biến đổi Fourier rời rạc và

biến đổi Fourier nhanh.

6. Tổng quan tài liệu nghiên cứu

Luận văn đã tham khảo một số tài liệu khoa học tiếng Việt và tiếng Anh về

biến đổi Fourier đặc biệt là biến đổi Fourier rời rạc và Fourier nhanh. Hiện tại

trong và ngoài nước đã có các công trình nghiên cứu về biến đổi Fourier rời rạc,

biến đổi Fourier nhanh và các ứng dụng thực tế hữu ích của chúng.

Tuy nhiên các công trình khoa học vẫn chưa tổng hợp được nhiều các ứng

3

dụng của biến đổi Fourier rời rạc, biến đổi Fourier nhanh trong sơ cấp và trong

thực tế hoặc có nhưng vẫn còn hạn chế.

Vì vậy việc nghiên cứu, tổng hợp các ứng dụng của phép biến đổi Fourier

rời rạc, Fourier nhanh một cách rõ ràng, hệ thống là cần thiết. Kết quả nghiên

cứu của đề tài sẽ giúp người học toán dễ dàng hơn trong việc hình dung tính

hữu ích của phép biến đổi Fourier trong toán học cũng như trong thực tiễn.

4

CHƯƠNG 1

KIẾN THỨC CHUẨN BỊ

1.1 BIẾN ĐỔI FOURIER RỜI RẠC

1.1.1 Định nghĩa

Định nghĩa 1.1.1. Cho dãy x(n),n = 0,1,..,N −1. Khi đó biến đổi Fourier

rời rạc của dãy x(n), viết tắt là DFT được xác định bởi công thức:

X(k) =

N−1

∑

n=0

x(n)Wkn

N

, k = 0,1,...,N −1. (1.1)

Biến đổi Fourier rời rạc ngược viết tắt là IDFT được xác định bởi công thức:

x(n) = 1

N

N−1

∑

k=0

X(k)W−kn

N

, n = 0,1,...,N −1. (1.2)

Ở đây Wkn

N = e

−i2π.kn

N và e

ia = cosa+isina.

Ví dụ 1.1.1.

1.1.2 Biểu diễn DFT dưới dạng ma trận

Định nghĩa ma trận Fourier

Một ma trận vuông cấp N mà phần tử thứ (k,n) là Wkn(0 ≤ k,n ≤ N − 1)

được gọi là ma trận Fourier cấp N, ký hiệu WN. Tức là:

WN =





1 1 1 ... 1

1 W1

N W2

N

... WN−1

N

.

.

.

.

.

.

.

.

. ...

.

.

.

1 WN−1

N W

2(N−1)

N

... W

(N−1)(N−1)

N





.

5

Biến đổi DFT dưới dạng ma trận

Đặt: xN =





x(0)

x(1)

.

.

.

x(N −1)





; XN =





X(0)

X(1)

.

.

.

X(N −1)





W∗

N =





1 1 1 ... 1

1 W−1

N W−2

N

... W

−(N−1)

N

.

.

.

.

.

.

.

.

. ...

.

.

.

1 W

−(N−1)

N W

−(2(N−1))

N

... W

−(N−1)(N−1)

N





.

Khi đó biến đổi DFT của XN và biến đổi ngược IDFT được viết lại:

XN = WN.xN; xN =

1

N

W∗

N

.XN.

Mệnh đề 1.1.1. Gọi W−1

N

là ma trận nghịch đảo của ma trận WN. Khi đó:

W−1

N =

1

N

.W∗

.

Ví dụ 1.1.2.

Ví dụ 1.1.3. Giải Ví dụ 1.1.1 bằng cách sử dụng ma trận Fourier.

Mệnh đề 1.1.2. Cho vectơ x(n,1)

, tích WN.x được gọi là phép biến đổi Fourier

rời rạc của vectơ x và W−1

N

.x là phép biến đổi nghịch đảo của x. Phần tử ở vị trí

k trong WN.x và W−1

N

.x được xác định bởi công thức:

[WN.x]k =

N−1

∑

i=0

xiw

ik; [W−1

N

.x]k =

1

N

N−1

∑

i=0

xiw

−ik

.

Ví dụ 1.1.4.

1.1.3 Biến đổi DFT cho toán tử unita

Trước kia, biến đổi DFT và biến đổi ngược IDFT của dãy x(n) được viết

dưới dạng:

X(k) = 1

√

N

N−1

∑

n=0

x(n)Wkn

N

, k = 0,1,...,N −1. (1.5)

6

x(n) = 1

√

N

N−1

∑

k=0

X(k)W−kn

N

, n = 0,1,...,N −1. (1.6)

1.1.4 Tính chất của biến đổi DFT

Tính tuần hoàn

Cho X(k) ↔ x(n), khi đó X(k) và x(n) tuần hoàn với chu kỳ N tức là:

X(k +N) = X(k),∀k = 0,1,...,N −1.

x(n+K) = x(n),∀n = 0,1,...,N −1.

Ví dụ 1.1.5.

Tính tuyến tính

Cho x1(n) ↔ X1(k) và x2(n) ↔ X2(k) thì với mọi a1,a2 ta có:

a1x1(n) +a2x2(n) ↔ a1X1(k) +a2X2(k).

Dịch vòng

Cho x(n) ↔ X(k) thì x(n + h) ↔ X(k).W−hk

. Khi đó x(n + h) được dịch

chuyển theo vòng tròn về bên trái bởi khoảng thời gian h trong miền thời gian.

Ở đây xn+k = (xh, xh+1,...,xN−1, x0,...,xh−1).

Ví dụ 1.1.6.

Độn không

Về nguyên tắc, chiều dài L và chiều dài N của biến đổi DFT có thể khác

nhau. Hầu hết các vấn đề về DFT đều giả sử L = N. Tuy nhiên không nhất thiết

điều này luôn xảy ra.

Nếu L < N ta có thể độn N - L số 0 ở cuối của bản ghi dữ liệu để nó có chiều

dài N. Độn bất kỳ số 0 nào vào phần đuôi của tín hiệu đều không ảnh hưởng gì

đến biến đổi DFT.

Nếu L > N ta có thể giảm chiều dài của bản ghi thành N theo kỹ thuật rút

gọn modN.

Để có được phép chập không tròn hoặc không tuần hoàn của hai dãy (một

dãy có chiều dài L và dãy khác có chiều dài M) bằng cách sử dụng phương pháp