Fourier Transform & Discrete Fourier Transform notes & demo [VN]
Vấn đề thực tiễn
Trong đời sống hàng ngày, tín hiệu thông tin được truyền đạt dưới dạng sóng. Khi chúng ta nghe nhạc, xem truyền hình hay sử dụng điện thoại, các tín hiệu âm thanh, hình ảnh và dữ liệu đều được mã hóa thành dạng sóng. Quá trình truyền tín hiệu có thể được mô tả qua các bước chính:
Máy nguồn phát tín hiệu: Thiết bị này tạo ra tín hiệu bằng cách kết hợp, hay nói một cách khác, là tổng hợp của nhiều sóng hình sine có tần số khác nhau. Mỗi sóng sine đóng góp một phần vào cấu trúc tổng thể của tín hiệu, phản ánh những đặc tính riêng biệt như âm sắc trong âm nhạc hay màu sắc trong hình ảnh.
Máy đích nhận và giải mã: Tín hiệu khi đến nơi cần được lấy mẫu (sampling) và giải mã để chuyển hóa về dạng ban đầu, phục vụ cho quá trình xử lý hoặc hiển thị. Quá trình này yêu cầu phải phân tích được các thành phần tần số của tín hiệu để có thể tái tạo lại chính xác nội dung gốc.
Việc truyền tải và xử lý tín hiệu theo cách này đặt ra một yêu cầu thiết yếu: chúng ta cần một phương pháp để phân tích và biểu diễn tín hiệu dưới dạng các thành phần tần số. Đây chính là lúc Fourier Transform trở nên vô cùng hữu ích.
Chuỗi Fourier - Fourier Series
Trên lý thuyết, bất kỳ hàm khả tích tuần hoàn nào đều có thể được phân tích thành một chuỗi vô hạn các hàm lượng giác \(sin\) và \(\cos\). Công thức tổng quát của chuỗi Fourier cho hàm \(f(t)\) có chu kỳ \(T\) như sau:
$$f(t) = \frac {a_0} 2 + \sum_{n=1}^{\infty}\left[ a_n \cos\left(\frac {2\pi nt} T \right) + b_n \sin\left(\frac {2\pi nt} T \right) \right]$$
Trong đó:
$$a_n = \frac 2 T \int_{t_0}^{t_0+T} f(t) \cos \left( \frac {2 \pi nt} T \right ) dt, \quad b_n = \frac 2 T \int_{t_0}^{t_0+T} f(t) \sin \left( \frac {2 \pi nt} T \right ) dt$$
Ví dụ:
Ta có một hàm sóng vuông (square wave) \(f(t)\) với chu kỳ \(T=2\pi\) như sau:
$$f(t)= \begin{cases} 1, \quad 0 \lt t \lt \pi, \\ -1, \quad -\pi \lt t \lt 0, \\ \end{cases} ,\quad f(t+2\pi)=f(t), \forall t$$
Đây là hàm số lẻ nên các hệ số \(\cos\) đều bằng \(0\), chỉ còn các hệ số \(b_n\) cho hàm \(\sin\).
$$b_n = \frac 1 \pi \int_{-\pi}^{\pi} f(t) \sin(nt) dt$$
Do \(f(t)\) lẻ nên:
$$b_n = \frac 2 \pi \int_{0}^{\pi} \sin(nt)dt = \frac 2 \pi. \frac {1 - \cos(n\pi)} n$$
Với \(n \) chẵn, \(\cos(n\pi)=1 \implies b_n=0\), tương tự, \(n\) lẻ thì \(b_n = \frac 4 {n\pi}\). Từ đó, chuỗi fourier biểu diễn hàm \(f(t)\) trở thành:
$$f(t) = \frac 4 \pi \sum_{n=1, \text{ odd}} ^{\infty} \frac 1 n \sin(nt) = \frac 4 \pi \left( \sin(t) + \frac 1 3 \sin(3t) + \frac 1 5 \sin(5t) \dots \right)$$
Khái niệm
Fourier Transform là một phép biến đổi toán học giúp chuyển đổi một hàm từ miền thời gian (hoặc không gian) sang miền tần số. Nói một cách đơn giản, nếu bạn có một tín hiệu trong miền thời gian, Fourier Transform sẽ phân tích tín hiệu đó thành các thành phần cơ bản – cụ thể là các hàm sine và cosine trong dạng chuỗi Fourier như đã nêu ở trên. Bài viết này sẽ làm rõ điều đó.
Một số ứng dụng của Fourier Transform
Phân tích tín hiệu: Giúp xác định các tần số nào có mặt trong tín hiệu và mức độ đóng góp của mỗi tần số. Điều này rất quan trọng trong việc loại bỏ nhiễu, nén dữ liệu hay giải mã tín hiệu.
Thiết kế bộ lọc: Nhờ vào việc biết được thành phần tần số, chúng ta có thể thiết kế các bộ lọc để loại bỏ các tần số không mong muốn, cải thiện chất lượng tín hiệu.
Các ứng dụng khác: Fourier Transform không chỉ có ứng dụng trong truyền thông mà còn được sử dụng rộng rãi trong xử lý hình ảnh, giải phương trình vi phân, cơ học lượng tử và nhiều lĩnh vực khoa học khác.
Công thức và giải thích công thức
Công thức Fourier Transform cho một hàm \(f(t)\) theo biến thời gian \(t\) được định nghĩa như sau:
$$F(\omega) = \int_{-\infty}^{+\infty}f(t)e^{-i\omega t}dt$$
Trong đó:
\(f(t)\) - Là tín hiệu ban đầu của hàm thời gian theo biến \(t\)
\(F(\omega)\) - là hàm chuyển đổi biều diễn của tín hiệu trong miền tần số, với \(\omega\) là tần số tính bằng radian trên giây
Với công thức Euler: \(e^{i\theta} = \cos \theta + i\sin \theta\), ta có thể biểu diễn sang miền tần số
Tiếp đến, ta có công thức Inverse Fourier Transform để biến đổi ngược từ miền thời gian sang miền tần số như sau (cùng quy ước ký hiệu với công thức trên):
$$f(t)=\frac 1 {2\pi}\int_{-\infty}^{+\infty}F(\omega)e^{i\omega t}d\omega$$
Discrete Fourier Transform - Biến đổi Fourier rời rạc
Trong thực tế, mặc dù tín hiệu số là tín hiệu liên tục nhưng chúng ta chỉ có thể lấy mẫu một cách rời rạc, nghĩa là, sau một khoảng thời gian cố định, ta đo đạc để lấy giá trị của tín hiệu. Do đó, thay vì làm việc với một hàm liên tục \(f(t)\), chúng ta có một dãy các giá trị rời rạc \(x_n\) với \(n=0,1,2,\dots,N-1\). Để chuyển các giá trị của dãy số này sang miền tần số, ta sử dụng công thức Biến đổi Fourier Rời Rạc (Discrete Fourier Transform - DFT)
$$X_k = \sum_{n=0}^{N-1}x_n e^{-i \frac {2\pi}{N}kn}, \quad k=0,1,2,\dots,N-1$$
Trong đó
\(x_k\) - là các tín hiệu rời rạc đầu vào
\(X_k\) - là tần số của tương ứng với chỉ số \(k\)
\(N\) - là số lượng mẫu trong tín hiệu
Ví dụ:
Giả sử ta thu được 4 mẫu \((N=4)\)tín hiệu rời rạc như sau: \(x+0=1,x_1=2, x_2=3, x_3 = 4\). Áp dụng công thức DFT ta có:
$$X_n = \sum_{n=0}^3 x_n e^{-i \frac {2\pi} 4 kn} = \sum_{n=0}^3 x_n e^{-i \frac {\pi} 2 kn}, \quad k=0,1,2,3$$
Ta tính \(X_k\) cho các giá trị \(k\):
\(k=0: X_0 = x_0e^{-i \frac {\pi}2.0.0} + x_1e^{-i \frac {\pi}2.0.1} + x_2e^{-i \frac {\pi}2.0.2} + x_3e^{-i \frac {\pi}2.0.3} = 1+2+3+4= 10\)
Tương tự, \(k=1: X_1 = -2+2i\)
\(k=2: X_2 = -2\)
\(k=3: X_3=-2-2i\)
Chúng ta cũng có công thức Inverse Discrete Fourier Transform (IDFT) tương ứng để chuyển đổi một dãy các tín hiệu \(X_0,X_1,\dots,X_{N-1}\) từ miền tần số ngược về miền thời gian \(x_0,x_1,\dots,x_{N-1}\)
$$x_n = \frac 1 N \sum_{k=0}^{N-1}X_k e^{i \frac {2 \pi} N kn}$$
Vai trò của công thức Euler
Áp dụng công thức Euler: \(e^{i\theta} = \cos \theta + i\sin\theta\) với \(\theta = \frac {2\pi} N k n\), ta có:
$$e^{-i\frac {2\pi}{N} kn} = \cos \left( \frac {2\pi}{N} kn \right) - i\sin \left( \frac {2\pi}{N} kn \right)$$
Thay vào công thức:
$$X_k = \sum_{n=0}^{N-1} x_n \left[ \cos \left( \frac {2\pi}{N} kn \right) - i\sin \left( \frac {2\pi}{N} kn \right) \right]$$
Như vậy \(X_k\) chính là tổng của một dãy các số phức với thành phần thực là \(\cos \left( \frac {2\pi}{N} kn \right)\) và phần ảo là \(\sin \left( \frac {2\pi}{N} kn \right)\). Bây giờ mình sẽ trực quan hóa \(x_k\) dưới dạng tổng các hàm số có dạng \(A\sin(\omega + \varphi)\) như demo trong bài trước. Để làm điều này, chúng ta sẽ xem xét cách biểu diễn của số phức tổng quát \(a + bi\) trên mặt phẳng phức và ánh xạ các thành phần của nó sang các thành phần của hàm số \(A\sin(\omega + \varphi)\). Hãy xem hình vẽ dưới đây:
Như vậy, các thành phần tương ứng sẽ là:
Tần số \(k\)
Biên độ theo như hình vẽ sẽ là \(A=\sqrt{a^2+b^2} \)
Pha \(\varphi = \arctan (b, a)\)
DFT - Chuyển thành code
Từ công thức của DFT bên trên, mình xây dựng một function dft với các giá trị samples như sau:
function dft(xs) {
var N = xs.length;
const result = new Array(N);
for (let k = 0; k < N; k++) {
let sumRe = 0;
let sumIm = 0;
for (var n = 0; n < N; n++) {
var angle = (2 * Math.PI * k * n) / N;
sumRe += xs[n] * Math.cos(angle);
sumIm -= xs[n] * Math.sin(angle);
}
sumRe = sumRe / N;
sumIm = sumIm / N;
const freq = k;
const amp = Math.sqrt(sumRe * sumRe + sumIm * sumIm);
const phase = Math.atan2(sumIm, sumRe);
result[k] = { freq, amp, phase };
}
return result;
}
Xây dựng demo
Bạn hãy tưởng tượng có một bản vẽ, và bạn sẽ được vẽ lên đó. Hệ thống sẽ lưu lại tất cả các điểm mà bạn đã vẽ ra với thông tin tọa độ \(x\) và \(y\) cho mỗi điểm. Như vậy, mỗi bản vẽ sẽ bao gồm một danh sách các giá trị \(x\) và danh sách còn lại là giá trị \(y\) của tất cả các điểm. Bạn thực hiện biến đổi Fourier cho từng danh sách và nhận được hai danh sách các hàm sin là các bộ \([\text{amplitude, frequency, phase}]\). Từ đó mô tả lại bằng các đường tròn chuyển động.