let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Fourier Transform 1 - Fourier Series

Fourier Transform 1 - Fourier Series

Lời nói đầu

Đây là bài đầu tiên của loạt bài viết về Fourier Transform. Nội dung được kham khảo từ trang web http://thefouriertransform.com.

Mục đích của Fourier Transform là tách tín hiệu dạng sóng thành các tần số riêng lẻ tạo ra nó. Cụ thể hơn, Fourier Transform tách hàm số thành tổng các hàm sincos, mỗi hàm có tần số khác nhau.

Ví dụ khi ta chơi đàn, nốt Đô có tần số 261.63Hz, nốt Rê có tần số 293.66Hz. Nếu ấn 2 nốt này cùng một lúc thì 2 tần số đó sẽ trộn lẫn vào nhau. Khi thu âm lại, ta có thể dùng Fourier Transform để tách âm thanh thu được thành 2 tần số Đô và Rê ban đầu.

Gần như mọi thứ trên thế giới đều có thể biểu diễn bằng dạng sóng (waveform - hàm số biễu diễn biên độ theo thời gian). Âm thanh, tín hiệu điện, ánh sáng, các tín hiệu radio, 3G, wifi,… tất cả đều là sóng. Thông qua Fourier Transform, ta sẽ thấy mọi tín hiệu đều có thể phân tách thành tổng các hàm sin, cos. Vì vậy, Fourier Transform đóng vai trò quan trọng trong khoa học nói chung chứ không phải chỉ trong Tin học. Nhà toán học Gilbert Strang gọi Fast Fourier Transform là thuật toán quan trọng nhất của thế kỷ 20.

Trong loạt bài sẽ sử dụng các kiến thức về tích phân, các hàm lượng giác, số phức và lũy thừa với số mũ phức. Ngoài ta, mình sẽ sử dụng ngôn ngữ lập trình R để minh họa code. Để dễ theo dõi, bạn đọc nên tải RRStudio.

Fourier Series

Dãy Fourier có nhiệm vụ tách hàm tuần hoàn thành tổng của các hàm sincos, có thể nói dãy Fourier là biến đổi Fourier cho các hàm tuần hoàn. Định nghĩa hàm tuần hoàn:

Hàm F được gọi là tuần hoàn với chu kì T (\(T > 0\)) nếu:

  • \(F(t + T) = F(t)\) với mọi \(t\)

Ta thấy, nếu F tuần hoàn với chu kì T thì cũng tuần hoàn với chu kì 2T. Vì vậy có thêm định nghĩa chu kì cơ bản, là chu kì ngắn nhất của F. Ví dụ, \(\sin{2x}\) là hàm tuần hoàn với chu kì cơ bản là \(T = \pi\).

Xét hàm số \(f(t)\) với chu kì cơ bản là T, ta có dãy Fourier của \(f\) là:

\[g(t) = a_0 + \sum_{m=1}^{\infty}a_m\cos\frac{2\pi m t}{T} + \sum_{n=1}^{\infty}b_n\sin\frac{2\pi n t}{T}\]

Với:

\[a_0 = \frac{1}{T} \int_0^T f(t)\,\mathrm{d}t\\ a_m = \frac{2}{T} \int_0^T f(t)\cos\frac{2\pi m t}{T}\,\mathrm{d}t\\ b_n = \frac{2}{T} \int_0^T f(t)\sin\frac{2\pi n t}{T}\,\mathrm{d}t\]

Ví dụ

Xét hàm \(f(t)\) với chu kì cơ bản \(T=2\) như sau:

f

Ta sẽ tính các hệ số của dãy Fourier của hàm trên:

Tính \(a_0\): \(a_0 = \frac{1}{T} \int_0^T f(t)\,\mathrm{d}t\\ = \frac{1}{2} \int_0^2 f(t)\,\mathrm{d}t\\ = \frac{1}{2} \int_0^1 f(t)\,\mathrm{d}t + \frac{1}{2} \int_1^2 f(t)\,\mathrm{d}t\\ = \frac{1}{2} \int_1^2 1\,\mathrm{d}t = \frac{1}{2}\)

Tính \(a_m\):

\[a_m = \frac{2}{T} \int_0^T f(t)\cos\frac{2\pi m t}{T}\,\mathrm{d}t\\ = \int_0^2 f(t)\cos \pi m t\,\mathrm{d}t = \int_1^2 \cos \pi m t\,\mathrm{d}t\\ = \frac{1}{\pi m} (\sin 2\pi m - \sin \pi m) = 0\]

Tính \(b_n\):

\[b_n = \frac{2}{T} \int_0^T f(t)\sin\frac{2\pi n t}{T}\,\mathrm{d}t\\ = \int_0^2 f(t)\sin \pi n t\,\mathrm{d}t = \int_1^2 \sin \pi n t\,\mathrm{d}t\\ = \frac{1}{\pi n} \cos \pi n - \frac{1}{\pi n} cos 2 \pi n\\ = \begin{cases} \Large{-\frac{2}{\pi n}} & \quad \text{khi } n \text{ lẻ}\\ 0 & \quad \text{khi } n \text{ chẵn} \end{cases}\]

Vậy:

\[g(t) = \frac{1}{2} - \frac{2}{\pi}\sin \pi t - \frac{2}{3\pi}\sin 3\pi t - \frac{2}{5\pi}\sin 5\pi t - \dots\]

Ta có thể thấy \(g\) ngày càng tiến gần đến \(f\):

gif

Code (R):

g = function(n) function(t) 1/2 + sum(sapply(0:n, function(i) -(2/(2*i+1)/pi)*sin((2*i+1)*pi*t)))

draw = function(n) {
  plot(function(x) floor(x) %% 2, type="l", xlab='', ylab='', xlim=c(-3, 3), ylim=c(-1,2))
  x = seq(-3, 3, by=0.01)
  y = sapply(x, g(n))
  lines(x, y)
}

for (i in 0:15) {
  draw(i)
  Sys.sleep(0.2)
}

Code

Sau đây là code tính dãy Fourier bằng công thức tổng quát ở trên, bạn đọc có thể dùng để thử nghiệm. Chỉ cần sửa hàm f, chu kì T, và độ chính xác n cho phù hợp:

coeff = function(f, T, m, g) integrate(function(x) f(x) * g(2*pi*m*x/T), 0, T)$value * 2 / T
coeff_a = function(f, T, m) coeff(f, T, m, cos)
coeff_b = function(f, T, m) coeff(f, T, m, sin)
g = function(f, T, m) {
  function(x) integrate(f, 0, T)$value / T + sum(sapply(1:m, function(i) coeff_a(f, T, i) * cos(2*pi*i*x/T))) + sum(sapply(1:m, function(i) coeff_b(f, T, i) * sin(2*pi*i*x/T)))
}
draw = function(f, T, n) {
  g = g(f, T, n)
  x = seq(-2*T, 2*T, by=0.05)
  yg = sapply(x, g)
  yf = sapply(x, f)
  plot(x, yf, type='l')
  lines(x, yg, col='blue')
}


f = function(x) x*x
draw(f, T=2, n=10)

Hiện tại thì đoạn code trên đang tính 1 phần của hàm \(f(t) = t^2\), chu kì được chọn là \(T=2\):

f

Comments