Biến đổi Fourier rời rạc (DFT) – Biến đổi Fourier nhanh (FFT)

Như đã học về khai triển Fourier, mỗi hàm f:[0, 1]\to\mathbb R đủ tốt (chẳng hạn liên tục hay liên tục từng đoạn) có khai triển Fourier

\dfrac{a_0}{2}+\sum\limits_{n=0}^\infty(a_n\cos{(2\pi nx)}+b_n\sin{(2\pi nx)})=\sum\limits_{n\in\mathbb Z}c_n e^{i2\pi nx}

trong đó a_n=2\int\limits_{0}^{1}f(x)\cos{(2\pi nx)}dx, b_n=2\int\limits_{0}^{1}f(x)\sin{(2\pi nx)}dx,

c_n=\int\limits_{0}^{1}f(x)e^{-inx}dx.

Như vậy trạng thái f(x) được hiểu thông qua dãy phổ a_n, b_n hay c_n.

Biến đổi Fourier rời rạc (DFT) là cách từ một số hữu hạn tín hiệu phổ c_n nhận được ta xác lập lại gần đúng trạng thái tại một số hữu hạn điểm. Cụ thể như sau

ta nhận được N tín hiệu x(0), x(2), \dots, x(N-1) ta xác lập trạng thái tại k=0, 1, \dots, N-1

X(k)=\sum\limits_{j=0}^{N-1}x(j)e^{i2\pi\frac{jk}{N}}.

Biến đổi Fourier nhanh (FFT) là đưa ra thuật toán nhằm tính nhanh các trạng thái X(k), k=0, 1, \dots, N-1 khi biết các tín hiệu x(j), j=0, 1, \dots, N-1.

Ý tưởng xuất phát từ việc nhận ra:

Nếu N=LM thì

+với mỗi k=0, 1, \dots, N-1k=Mq+p với q=0, 1, \dots, L-1, p=0, 1, \dots, M-1;

+ với mỗi j=0, 1, \dots, N-1k=Lm+l với m=0, 1, \dots, M-1, l=0, 1, \dots, L-1;

X(Mq+p)=\sum\limits_{m=0}^{L-1}\sum\limits_{l=0}^{M-1}x(Lm+l)e^{i2\pi\frac{(Mq+p)(Lm+l)}{LM}}

=\sum\limits_{l=0}^{M-1}\Big(e^{i2\pi\frac{lq}{L}}\big(\sum\limits_{m=0}^{M-1}x(Lm+l)e^{i2\pi\frac{mp}{M}}\big)e^{i2\pi\frac{pl}{LM}}\Big).

Chi tiết độc giả có thể tham khảo tài liệu sau của TS. Đinh Đức Anh Vũ

levnu0022-06

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s