Biến đổi Fourier là gì? Thuật toán FFT trong MP3, JPEG, 5G
Biến đổi Fourier là gì, vì sao một ý tưởng về nhiệt năm 1807 nằm trong Shazam, MP3, JPEG, Wi-Fi và máy MRI, và thuật toán FFT nhanh hơn hàng vạn lần ra sao.

Mục lục
Bạn đang ngồi quán cà phê, loa phát một bài hát nghe quen mà không nhớ tên. Bạn mở Shazam, đưa điện thoại lên, ba giây sau màn hình hiện tên bài và ca sĩ. Giữa tiếng cốc chén, tiếng người nói và tiếng xe ngoài đường, chiếc điện thoại vẫn “nghe” ra đúng bản nhạc. Thứ làm được việc đó, và cũng là thứ nằm trong file MP3, trong bức ảnh JPEG, trong sóng Wi-Fi và trong máy chụp cộng hưởng từ ở bệnh viện, là biến đổi Fourier.
Câu trả lời ngắn cho câu hỏi “biến đổi Fourier là gì”: đó là cách tách một tín hiệu phức tạp thành tổng của những sóng đơn giản, rồi cho biết mỗi sóng có tần số bao nhiêu và mạnh tới đâu. Một đoạn nhạc, một bức ảnh hay một tín hiệu radio đều có thể viết lại như vậy. Còn FFT (fast Fourier transform, biến đổi Fourier nhanh) là thuật toán giúp máy tính làm việc tách ấy nhanh tới mức một chiếc điện thoại làm được hàng nghìn lần mỗi giây.
Bài này đi theo ba chặng. Đầu tiên là người đàn ông đứng sau cái tên: một kỹ sư theo Napoleon sang Ai Cập rồi bị các nhà toán học lớn nhất nước Pháp chê là thiếu chặt chẽ. Tiếp theo, phần dài nhất, là những nơi Fourier đang làm việc mỗi ngày quanh bạn. Cuối cùng là thuật toán: máy tính tính biến đổi Fourier thế nào, và vì sao một mẹo “chia đôi” năm 1965 lại được xếp vào nhóm thuật toán quan trọng nhất thế kỷ 20.
Biến đổi Fourier là gì? Nếm bát phở, đoán ra công thức
Hãy tưởng tượng một đầu bếp giỏi nếm một thìa nước phở rồi nói: “Nhiều quế, hồi vừa phải, gừng nướng một chút, hơi nhiều đường phèn.” Bát nước dùng là một thứ hòa quyện, không tách rời được bằng mắt. Nhưng cái lưỡi được luyện đủ lâu có thể đọc ngược ra công thức: mỗi gia vị bao nhiêu.
Biến đổi Fourier làm đúng việc ấy với tín hiệu. Đầu vào là “bát nước dùng”: một đường ngoằn ngoèo mà micro ghi lại, mỗi thời điểm một con số. Đầu ra là “công thức”: danh sách các tần số, mỗi tần số kèm một liều lượng.
Tần số là số lần một sóng lặp lại trong một giây, đo bằng hertz (Hz). Dây đàn rung 262 lần mỗi giây cho ta nốt Đô giữa đàn piano. Rung nhanh hơn, 330 lần, ta nghe nốt Mi. Âm cao nghĩa là tần số cao, giống như cánh quạt quay càng nhanh thì tiếng vù vù càng the thé.
Khi bạn bấm cùng lúc ba phím Đô, Mi, Sol (hợp âm Đô trưởng), không khí không rung theo ba sóng riêng rẽ. Ba sóng cộng lại thành một đường duy nhất, trông lộn xộn như nửa trên của Hình 1. Tai bạn vẫn nghe ra ba nốt, vì trong ốc tai có hàng nghìn tế bào lông, mỗi nhóm nhạy với một dải tần số, giống một dãy âm thoa nhỏ. Biến đổi Fourier là phiên bản toán học của cái ốc tai ấy: nó nhìn đường ngoằn ngoèo và trả về ba vạch rõ ràng ở 262, 330 và 392 Hz, như nửa dưới của hình.

Điều quan trọng là phép tách này đảo ngược được. Có công thức trong tay, ta nấu lại đúng bát nước dùng: cộng các sóng lại theo đúng liều lượng là ra tín hiệu ban đầu. Nhờ vậy, ta có thể sang “phía tần số” để làm việc (bỏ bớt, sửa, so sánh), rồi quay về. Gần như mọi ứng dụng phía dưới đều theo một nhịp: sang phía tần số, làm một việc ở đó thì dễ hơn hẳn, rồi quay về.
Người thầy giáo nghiên cứu nhiệt
Jean-Baptiste Joseph Fourier sinh ngày 21/3/1768 ở Auxerre, miền trung nước Pháp, con một người thợ may. Mẹ ông qua đời khi ông chín tuổi, năm sau tới lượt cha. Cậu bé mồ côi được các tu sĩ đưa vào trường quân sự trong thành phố, học giỏi toán và về sau quay lại chính ngôi trường ấy dạy học [1].
Cách mạng Pháp kéo ông vào chính trị địa phương. Tháng 7/1794, giữa thời kỳ Khủng bố, ông bị bắt giam và có lúc lo sẽ lên máy chém. Robespierre bị lật đổ ngay sau đó, tình thế chính trị thay đổi và Fourier được thả [1]. Ông về Paris, dạy ở trường Bách khoa (École Polytechnique) mới thành lập.
Năm 1798, Napoleon đem quân sang Ai Cập và mang theo hơn một trăm nhà khoa học. Fourier là một trong số đó, làm thư ký của Viện Ai Cập ở Cairo, phụ trách gom lại các phát hiện khoa học và khảo cổ của đoàn. Về Pháp năm 1801, ông được Napoleon cử làm tỉnh trưởng tỉnh Isère, đóng ở Grenoble. Ban ngày ông lo tát cạn đầm lầy và làm đường sang Turin. Buổi tối, ông nghiên cứu một câu hỏi tưởng như rất đời thường: nhiệt lan trong một thanh kim loại như thế nào?
Hãy hình dung bạn hơ nóng vài chỗ trên một thanh sắt, chỗ nóng chỗ nguội lởm chởm, rồi nhấc ra khỏi lửa. Vài phút sau, các vết nóng nhòe vào nhau, nhiệt độ dọc thanh trở nên mịn màng, rồi cả thanh nguội dần đều. Fourier nhận ra cách dễ nhất để mô tả quá trình ấy: viết hình dạng nhiệt độ ban đầu thành tổng của những đường hình sin. Mỗi đường hình sin nguội theo cách riêng, rất đơn giản: nó giữ nguyên hình dạng và chỉ thấp dần. Đường càng lượn sóng dày (tần số càng cao) thì tắt càng nhanh. Đó là lý do các vết nóng lởm chởm biến mất trước, chỉ còn lại một vòm cong thoai thoải. Bài toán khó (một hình dạng bất kỳ biến đổi theo thời gian) trở thành nhiều bài toán dễ (từng sóng sin thấp dần), cộng lại.
Ngày 21/12/1807, ông trình bày bản thảo Về sự lan truyền nhiệt trong vật rắn tại Viện Hàn lâm Paris. Trong đó có một khẳng định táo bạo: hàm số bất kỳ, kể cả hàm có góc nhọn hay bước nhảy, đều viết được thành tổng các sóng sin. Lagrange và Laplace, hai tên tuổi lớn nhất của toán học Pháp lúc ấy, phản đối [1]. Với họ, sóng sin là thứ trơn tru tuyệt đối. Làm sao cộng những thứ tròn trịa lại mà ra được một bức tường dựng đứng?

Hình 2 cho thấy câu trả lời. Một sóng sin còn xa sóng vuông. Ba sóng đã ra dáng bậc thang. Hai mươi lăm sóng thì gần như dựng đứng. Cộng vô hạn sóng thì tổng tiến tới sóng vuông, dù từng sóng đều trơn. Giống như xếp đủ nhiều viên gạch nhỏ, ta dựng được một bức tường thẳng góc.
Năm 1811, Viện chọn đúng đề tài lan truyền nhiệt cho giải thưởng lớn. Fourier nộp bài và thắng, nhưng bản nhận xét viết rằng cách ông đi tới các phương trình “không tránh khỏi khó khăn” và phép giải tích “còn để lại điều mong muốn về tính tổng quát, thậm chí cả tính chặt chẽ” [1]. Vì những dè dặt đó, bài không được in. Phải đến năm 1822 tác phẩm mới ra đời dưới tên Lý thuyết giải tích về nhiệt (Théorie analytique de la chaleur) [2], cùng năm ông trở thành thư ký thường trực của Viện Hàn lâm. Năm 1824, ông còn viết bài về nhiệt độ của Trái Đất, được nhiều sử gia coi là một trong những mô tả sớm nhất về thứ ngày nay gọi là hiệu ứng nhà kính [3].
Fourier qua đời ở Paris ngày 16/5/1830. Ít tuần trước đó, trên bàn ông là bài dự thi của một chàng trai 18 tuổi tên Évariste Galois. Bản thảo ấy thất lạc theo ông. Còn khẳng định “thiếu chặt chẽ” năm 1807 thì sau này được Dirichlet, Riemann và nhiều thế hệ khác làm cho chặt chẽ, và trở thành một nhánh lớn của toán học: giải tích Fourier.
Biến đổi Fourier đang ở đâu trong điện thoại của bạn?
Hai thế kỷ sau, phần lớn thời gian Fourier làm việc không phải với nhiệt mà với âm thanh, hình ảnh và sóng radio. Dưới đây là sáu nơi bạn chạm vào nó mỗi ngày, mỗi nơi theo đúng nhịp “sang phía tần số, làm một việc, rồi quay về”.
Shazam: nhận ra bài hát bằng một chòm sao
Shazam không so sánh đường sóng âm thanh với kho nhạc. Hai bản ghi của cùng một bài hát, một bản sạch trong studio và một bản thu qua loa quán cà phê, có đường sóng khác nhau hoàn toàn. Thứ giữ nguyên là những nốt nào vang mạnh vào lúc nào.
Vì thế, ứng dụng cắt đoạn thu âm thành những khung rất ngắn, mỗi khung một phần nhỏ của giây, rồi tính biến đổi Fourier cho từng khung. Xếp các kết quả cạnh nhau theo thời gian, ta được một phổ đồ (spectrogram): trục ngang là thời gian, trục dọc là tần số, độ sáng là độ mạnh. Phổ đồ giống bản nhạc in trên giấy: nhìn vào là biết lúc nào nốt nào vang lên.
Theo bài báo năm 2003 của Avery Wang, người thiết kế thuật toán của Shazam, hệ thống chỉ giữ lại những đỉnh nổi bật nhất trên phổ đồ, tức những điểm to hơn hẳn xung quanh [4]. Phần còn lại, gồm phần lớn tiếng ồn, bị bỏ. Cái còn lại trông như một bầu trời sao, và Wang gọi nó là “bản đồ chòm sao”. Mỗi cặp sao gần nhau được mã hóa thành một “dấu vân tay” nhỏ: tần số sao thứ nhất, tần số sao thứ hai, và khoảng cách thời gian giữa chúng.
Khi bạn bấm nút, đoạn thu vài giây cũng được biến thành một loạt dấu vân tay như thế, rồi đem tra trong kho dấu vân tay của hàng triệu bài hát. Bài nào có nhiều dấu vân tay trùng nhất, xếp đúng thứ tự thời gian, là bài cần tìm. Tiếng ồn quán cà phê có thể che mất nhiều ngôi sao, nhưng chỉ cần đủ số sao còn lại khớp đúng nhịp là đủ, giống nhận ra chòm sao Bắc Đẩu dù trời có mây che bớt.
MP3 và AAC: bỏ đi những gì tai không nghe thấy
Một phút nhạc CD tốn khoảng 10 MB: 44.100 mẫu mỗi giây, hai kênh trái phải, mỗi mẫu 16 bit, tức khoảng 1.411 kilobit mỗi giây. File MP3 phổ biến ở mức 128 kilobit mỗi giây, nhỏ hơn khoảng 11 lần, mà phần lớn người nghe khó phân biệt. Phần dữ liệu biến mất đi đâu?
Câu trả lời nằm ở cách tai người hoạt động. Khi bạn nói chuyện cạnh một người đang khoan tường, tiếng nói của bạn bị lấn át: nó vẫn ở đó, nhưng não không nghe thấy. Hiện tượng này gọi là che lấp (masking). Một âm to ở một tần số làm những âm nhỏ hơn ở các tần số lân cận “tàng hình”.
Bộ mã hóa MP3 [5] cắt nhạc thành từng khung ngắn và đưa sang phía tần số. Một mô hình tâm lý âm học, cũng dựa trên phân tích Fourier, ước tính trong khung ấy tần số nào đang che tần số nào. Những thành phần bị che hoặc quá nhỏ được ghi rất thô hoặc bỏ hẳn, còn bit được dành cho những gì tai thật sự nghe thấy. Ở đầu kia, máy nghe nhạc làm phép biến đổi ngược để dựng lại âm thanh. Đây là phép nén mất dữ liệu: bạn không lấy lại được bản gốc, nhưng thứ mất đi là thứ bạn vốn không nghe được.
JPEG: ảnh cũng là sóng
Nghe có vẻ lạ, nhưng một bức ảnh cũng có “tần số”. Một mảng trời xanh, độ sáng thay đổi rất chậm từ chỗ này sang chỗ khác, là vùng tần số thấp. Những sợi tóc, nét chữ, cạnh lá cây, nơi độ sáng đổi đột ngột trong vài điểm ảnh, là vùng tần số cao. Biến đổi Fourier hai chiều tách bức ảnh thành tổng của những “vân sóng” sáng tối với độ dày khác nhau, giống những mảnh vải kẻ sọc có sọc thưa sọc dày, chồng lên nhau theo đủ hướng.
Mắt người nhạy với các vùng mảng lớn hơn nhiều so với chi tiết li ti. Đó là cơ hội nén. Hình 3 làm một thí nghiệm thô: tính biến đổi Fourier của chân dung Fourier, chỉ giữ lại một phần nhỏ các tần số mạnh nhất, vứt hết phần còn lại, rồi biến đổi ngược.

Chỉ với 10% con số, bức ảnh gần như không đổi. Với 2%, vẫn nhận ra rõ khuôn mặt. Chuẩn JPEG năm 1992 [6] làm việc này tinh tế hơn. Nó chia ảnh thành từng ô 8×8 điểm ảnh, mỗi ô biến đổi bằng biến đổi cosin rời rạc (DCT, một người họ hàng gần của biến đổi Fourier, công bố năm 1974 [7]) thành 64 con số. Con số đầu tiên là độ sáng trung bình của ô, các số sau là các vân sóng càng lúc càng dày. Các số ứng với vân dày bị làm tròn mạnh tay, phần lớn thành 0. Thanh trượt “chất lượng” khi bạn lưu ảnh chính là mức làm tròn này. Kéo nó xuống quá thấp, bạn sẽ thấy ảnh vỡ thành những ô vuông nhỏ: đó là các khối 8×8 lộ ra.
Lần tới khi Zalo hay Facebook nén ảnh bạn gửi đi, hãy nhớ rằng thứ bị bỏ bớt trước tiên là những vân sóng dày nhất, những chi tiết mà mắt bạn ít để ý nhất.
Wi-Fi, 4G, 5G: chia một con đường thành nghìn làn
Muốn gửi thật nhiều dữ liệu qua sóng radio, cách ngây thơ là đổi tín hiệu thật nhanh trên một tần số. Vấn đề là sóng radio dội vào tường nhà, cao ốc, xe cộ, nên tới máy thu theo nhiều đường dài ngắn khác nhau. Các bản sao đến muộn chồng lên nhau như tiếng vọng trong hang. Khi tín hiệu đổi quá nhanh, bit này đè lên bit kia và không ai đọc nổi.
Giải pháp mà Wi-Fi, 4G và 5G cùng dùng tên là OFDM (orthogonal frequency-division multiplexing). Thay vì một làn xe chạy cực nhanh, nó chia dải tần thành hàng trăm, hàng nghìn làn hẹp, gọi là sóng mang con, mỗi làn chở một phần dữ liệu và chạy chậm. Chạy chậm nên tiếng vọng gần như không làm hỏng gì. Giống như thay vì một người phát tờ rơi chạy thật nhanh qua cả con phố, ta cho một nghìn người mỗi người đứng một cửa, phát chậm rãi.
Cái khó là phải tạo và tách hàng nghìn sóng cùng lúc. Đây chính là việc của Fourier. Máy phát xếp dữ liệu vào các “ô tần số” rồi làm biến đổi Fourier ngược để ra một tín hiệu duy nhất phát lên không trung. Máy thu nhận tín hiệu ấy, làm biến đổi Fourier để tách ra hàng nghìn làn và đọc từng làn. Với 4G LTE ở băng thông 20 MHz, có 1.200 sóng mang con cách nhau 15 kHz, dùng phép FFT kích thước 2.048 điểm [8], và mỗi giây điện thoại làm phép ấy hàng chục nghìn lần. Không có thuật toán FFT nhanh, chiếc điện thoại trong túi bạn không thể bắt sóng 4G.
Máy MRI: chụp bằng tần số
Máy chụp cộng hưởng từ (MRI) trong bệnh viện không chụp ảnh theo cách máy ảnh làm. Nó đặt cơ thể trong từ trường rất mạnh, kích thích các hạt nhân hydro trong nước và mỡ, rồi nghe tín hiệu radio chúng phát ra. Bằng cách thay đổi từ trường theo vị trí, máy làm cho mỗi chỗ trong cơ thể “hát” ở một tần số hơi khác.
Thứ máy thu được vì vậy không phải bức ảnh mà là phía tần số của bức ảnh, các kỹ sư gọi là “không gian k”. Một phép biến đổi Fourier ngược hai chiều (hoặc ba chiều) biến dữ liệu ấy thành hình ảnh lát cắt não hay đầu gối mà bác sĩ đọc. Richard Ernst nhận giải Nobel Hóa học năm 1991 chính vì phát triển kỹ thuật cộng hưởng từ hạt nhân dùng biến đổi Fourier, nền tảng cho cách máy MRI ngày nay thu tín hiệu [9].
Trợ lý giọng nói và AI “nghe”
Khi bạn nói với trợ lý ảo hay dùng tính năng chuyển giọng nói thành chữ, mô hình AI thường không nhận thẳng đường sóng âm thanh. Nó nhận một phổ đồ, giống của Shazam. Ví dụ, mô hình nhận dạng giọng nói Whisper của OpenAI cắt âm thanh thành các khung 25 mili giây, cứ 10 mili giây trượt một lần, và đưa vào mô hình 80 dải tần số mỗi khung [10]. Với AI, giọng nói của bạn là một “bức ảnh” tần số, và nhiều kỹ thuật dùng cho ảnh được đem sang dùng lại.
Những ứng dụng nhỏ hơn thì nhiều không kể hết: thanh chỉnh âm bass, treble trên điện thoại; bộ lọc tiếng ồn trong cuộc gọi; máy đo địa chấn phân biệt động đất với vụ nổ; máy hiện sóng của kỹ sư điện; phép nhân hai số có hàng triệu chữ số. Cái cuối cùng sẽ quay lại ở phần thuật toán.
Máy tính tính biến đổi Fourier thế nào?
Tới đây, ta đã thấy biến đổi Fourier làm gì. Phần còn lại trả lời câu hỏi của người lập trình: tính nó bằng cách nào, và tốn bao nhiêu công?
Bước 1: biến âm thanh thành dãy số
Máy tính không lưu được một đường liên tục. Nó lấy mẫu: đo tín hiệu đều đặn, ví dụ 44.100 lần mỗi giây với âm thanh CD, được một dãy con số . Giống như quay phim một vận động viên đang chạy: phim chỉ là một chuỗi ảnh tĩnh, nhưng đủ dày thì ta vẫn thấy chuyển động.
Dày bao nhiêu là đủ? Định lý lấy mẫu Nyquist–Shannon nói rằng phải lấy mẫu nhanh hơn hai lần tần số cao nhất có trong tín hiệu. Tai người nghe tới khoảng 20.000 Hz, nên CD chọn 44.100 mẫu mỗi giây, nhỉnh hơn gấp đôi. Lấy mẫu thưa hơn, tần số cao sẽ “giả dạng” thành tần số thấp. Bạn đã thấy hiện tượng này trong phim: bánh xe ô tô đang lao nhanh mà trông như quay chậm, thậm chí quay ngược, vì máy quay chụp không đủ nhanh.
Bước 2: thử từng sóng mẫu
Biến đổi Fourier rời rạc (DFT) hỏi một câu cho từng tần số: tín hiệu này “giống” sóng có tần số tới mức nào? Cách đo độ giống rất đơn giản: nhân từng mẫu của tín hiệu với từng mẫu của sóng thử, rồi cộng lại. Nếu tín hiệu có chứa sóng ấy, các tích cùng dấu dồn lại thành một số lớn. Nếu không, các tích dương âm triệt tiêu nhau và tổng gần bằng 0.
Hãy nghĩ tới việc đẩy xích đu cho trẻ con. Đẩy đúng nhịp xích đu, mỗi cú đẩy cộng dồn và xích đu bay cao. Đẩy lệch nhịp, cú này triệt tiêu cú kia và xích đu đứng yên. DFT “đẩy” tín hiệu bằng từng nhịp và xem nhịp nào làm nó “bay cao”.
Viết thành công thức:
Thừa số trông đáng sợ, nhưng chỉ là một điểm chạy vòng tròn: khi tăng, nó quay đều quanh đường tròn đơn vị, vòng sau bước, như kim giây quay vòng trong một phút. Dùng điểm quay tròn thay cho một sóng sin đơn lẻ giúp đo được cả độ to lẫn độ lệch pha (sóng bắt đầu sớm hay muộn) trong một con số phức . Độ lớn cho ta chiều cao của vạch trong Hình 1.
Cái giá là: với mỗi trong tần số, ta cộng tích. Tổng cộng khoảng phép nhân. Một giây âm thanh CD có 44.100 mẫu, tức gần 2 tỷ phép nhân cho một lần biến đổi. Một tín hiệu một triệu mẫu cần khoảng một nghìn tỷ phép nhân. Năm 1960, đó là con số bất khả thi. Ngay cả hôm nay, chiếc điện thoại cần làm hàng chục nghìn phép biến đổi mỗi giây cho 4G cũng không gánh nổi .
FFT: chia để trị
Thuật toán FFT phổ biến nhất, thuật toán Cooley–Tukey, dựa trên một quan sát: chia đôi dãy số theo vị trí chẵn và lẻ.
Tách mẫu thành hai nhóm: các mẫu ở vị trí chẵn và các mẫu ở vị trí lẻ . Mỗi nhóm có mẫu. Gọi là DFT của nhóm chẵn và là DFT của nhóm lẻ. Biến đổi một chút công thức DFT (chỉ cần tính chất ), ta được:
Hai dòng này là cả bí mật. Mỗi cặp , được dùng hai lần: một lần cho , một lần cho , chỉ khác một dấu cộng hay trừ. Giống như nấu một nồi nước dùng rồi chia ra cho hai món, phở bò và phở gà, thay vì nấu hai nồi riêng. Các kỹ sư gọi cặp phép tính chéo này là “cánh bướm” (butterfly), vì vẽ ra trông như đôi cánh.
Rồi ta làm tiếp với chính và : mỗi nhóm lại chia đôi thành hai nhóm , và cứ thế cho tới khi mỗi nhóm chỉ còn một mẫu. DFT của một mẫu là chính nó, không cần tính. Đây là kiểu chia để trị mà bạn đã gặp ở tìm kiếm nhị phân và trong lời giải đệ quy của Tháp Hà Nội: chia bài toán thành bài toán con cùng dạng nhưng nhỏ hơn, rồi ghép lời giải lại.
Mỗi tầng chia đôi tốn khoảng phép tính để ghép cánh bướm. Số tầng là số lần chia đôi cho tới khi còn 1, tức . Với một triệu, chỉ cần khoảng 20 tầng, vì , giống như gấp đôi một tờ giấy 20 lần là ra một triệu lớp. Tổng công sức là khoảng thay vì .
| Số mẫu | DFT thẳng () | FFT () | Nhanh hơn |
|---|---|---|---|
| 1.024 | 1,05 triệu | 10.240 | 102 lần |
| 65.536 | 4,3 tỷ | 1,05 triệu | 4.096 lần |
| 1.048.576 | 1,1 nghìn tỷ | 21 triệu | 52.429 lần |
Nếu mỗi phép tính mất một phần tỷ giây, dòng cuối nghĩa là khoảng 18 phút so với 0,02 giây. Khác biệt ấy quyết định công nghệ nào tồn tại được. Một chiếc máy MRI cần chờ hàng giờ để dựng mỗi lát cắt, hay một chiếc điện thoại tốn 18 phút cho mỗi phần nghìn giây sóng 4G, đều không ai dùng được.
Mẹo chia đôi cần là lũy thừa của 2 (1.024, 2.048, 4.096…). Đó là lý do các con số này xuất hiện khắp nơi trong kỹ thuật viễn thông. Những biến thể khác của FFT xử lý được mọi , nhưng ý tưởng gốc vẫn là chia nhỏ rồi dùng lại.
Ý tưởng “dùng lại” còn đi xa hơn xử lý tín hiệu. Nhân hai số rất lớn, mỗi số hàng triệu chữ số, có thể đưa về bài toán nhân hai đa thức, mà nhân đa thức thì nhanh nhất là sang phía tần số bằng FFT, nhân từng cặp, rồi quay về. Các thư viện tính số tới hàng nghìn tỷ chữ số đều dựa vào mẹo này.
Gauss có trước 160 năm, rồi chiến tranh lạnh tìm lại
Lịch sử của FFT có một khúc quanh đáng nhớ. Khoảng năm 1805, Carl Friedrich Gauss, người vài năm trước vừa tìm lại tiểu hành tinh Ceres, cần nội suy quỹ đạo của hai tiểu hành tinh khác là Pallas và Juno từ các số đo rời rạc. Để tính nhanh bằng tay, ông nghĩ ra đúng mẹo chia nhỏ dãy số mà ta vừa thấy, kể cả cách dùng nó đệ quy [12]. Nhưng ông không công bố. Bản thảo viết bằng tiếng Latin, chỉ được in sau khi ông qua đời, trong tuyển tập năm 1866, và gần như không ai để ý [13]. Điều thú vị là Gauss làm việc này trước cả khi Fourier trình bày bản thảo về nhiệt năm 1807.
Một trăm sáu mươi năm sau, đầu những năm 1960, Mỹ và Liên Xô đàm phán cấm thử vũ khí hạt nhân. Muốn ký được hiệp ước, Mỹ cần cách kiểm tra Liên Xô có giữ lời hay không mà không cần vào lãnh thổ của họ. Cách khả thi nhất là đặt máy đo địa chấn ở các nước xung quanh và phân tích rung động mặt đất: một vụ nổ ngầm có “chữ ký tần số” khác một trận động đất. Nhưng với hàng chục trạm đo và dữ liệu dài nhiều giờ, phép DFT quá chậm.
Theo các ghi chép về lịch sử thuật toán, John Tukey, nhà thống kê ở Đại học Princeton, nảy ra ý tưởng trong một cuộc họp của Ủy ban Cố vấn Khoa học của Tổng thống Kennedy bàn về chính bài toán này [13]. Richard Garwin, nhà vật lý của IBM cũng có mặt, thấy ngay tiềm năng và nối Tukey với James Cooley, một nhà toán học ở phòng nghiên cứu IBM. Garwin không nói với Cooley mục đích thật. Cooley được bảo rằng cần thuật toán để tìm chu kỳ trong một tinh thể helium-3.
Năm 1965, Cooley và Tukey công bố bài báo năm trang “Một thuật toán tính chuỗi Fourier phức bằng máy” [11]. Đúng lúc ấy, các bộ chuyển đổi tín hiệu tương tự sang số bắt đầu rẻ và nhanh, và FFT lan đi cực nhanh. Năm 1994, nhà toán học Gilbert Strang ở MIT gọi FFT là “thuật toán số quan trọng nhất trong đời chúng ta” [15]. Năm 2000, tạp chí Computing in Science & Engineering xếp nó vào danh sách mười thuật toán có ảnh hưởng lớn nhất thế kỷ 20 [14]. Phải vài năm sau bài báo năm 1965, người ta mới nhận ra Gauss đã có ý tưởng này từ đầu thế kỷ 19.
Tự tay tách một hợp âm
Đoạn code dưới đây tạo ra đúng Hình 1. Nó dựng một giây hợp âm Đô trưởng từ ba sóng sin (tần số làm tròn tới hertz), cộng thêm tiếng ồn ngẫu nhiên với seed cố định 1768, năm Fourier ra đời, rồi dùng FFT để đọc lại ba nốt. Phần cuối so tốc độ giữa DFT tính thẳng theo định nghĩa (nhân một ma trận ) và FFT của numpy trên 2.048 mẫu. Chỉ cần numpy và matplotlib.
import time
import matplotlib.pyplot as pltimport numpy as np
plt.rcParams.update({"figure.facecolor": "#16181c", "axes.facecolor": "#16181c", "text.color": "#d4d7dc", "axes.edgecolor": "#2a2e35", "axes.labelcolor": "#878d97", "xtick.color": "#878d97", "ytick.color": "#878d97", "font.size": 12})
# 1. Tạo một giây hợp âm Đô trưởng: ba nốt Đô, Mi, Sol chơi cùng lúc, cộng thêm chút tiếng ồnfs = 8_000 # tần số lấy mẫu: 8.000 mẫu mỗi giâyt = np.arange(fs) / fs # 1 giâyNOT = {"Đô": (262, 1.0), "Mi": (330, 0.7), "Sol": (392, 0.5)} # tần số (Hz, làm tròn), độ torng = np.random.default_rng(1768) # seed cố định: năm Fourier ra đờix = sum(a * np.sin(2 * np.pi * f * t) for f, a in NOT.values()) + 0.3 * rng.standard_normal(fs)
# 2. Biến đổi Fourier bằng FFT: từ 8.000 con số theo thời gian ra 4.001 "liều lượng" theo tần sốX = np.fft.rfft(x)tan_so = np.fft.rfftfreq(len(x), 1 / fs) # mỗi ô cách nhau 1 Hzbien_do = 2 * np.abs(X) / len(x) # quy về đúng độ to của từng sóngfor ten, (f, a) in NOT.items(): k = np.argmin(np.abs(tan_so - f)) print(f"{ten:>3}: đặt vào {a:.2f}, FFT đọc ra {bien_do[k]:.2f} ở {tan_so[k]:.0f} Hz")
# 3. So tốc độ: DFT tính thẳng theo định nghĩa (N² phép nhân) và FFT (N log N)N = 2_048n = np.arange(N)W = np.exp(-2j * np.pi * np.outer(n, n) / N) # ma trận N × N các "sóng mẫu"bat_dau = time.perf_counter(); X_cham = W @ x[:N]; t_cham = time.perf_counter() - bat_daubat_dau = time.perf_counter(); X_nhanh = np.fft.fft(x[:N]); t_nhanh = time.perf_counter() - bat_dauprint(f"N = {N}: hai cách cho cùng kết quả: {np.allclose(X_cham, X_nhanh)}")print(f"DFT thẳng: {t_cham * 1e3:.1f} ms · FFT: {t_nhanh * 1e3:.3f} ms")
# 4. Vẽ: trên là thứ micro ghi được, dưới là thứ Fourier đọc raMAU = {"Đô": "#e0b44c", "Mi": "#5fa8d3", "Sol": "#7fd1a8"}fig, (a1, a2) = plt.subplots(2, 1, figsize=(12, 7.2), gridspec_kw={"height_ratios": [1, 1.15]})ms = t * 1000a1.plot(ms, x, color="#d4d7dc", lw=1.4)a1.set(xlim=(0, 30), xlabel="thời gian (mili giây)", ylabel="áp suất không khí", title="Micro ghi được: một đường ngoằn ngoèo (30 ms đầu)")a2.plot(tan_so, bien_do, color="#878d97", lw=1)for ten, (f, a) in NOT.items(): k = np.argmin(np.abs(tan_so - f)) a2.vlines(tan_so[k], 0, bien_do[k], color=MAU[ten], lw=3) a2.text(tan_so[k], bien_do[k] + 0.05, f"{ten}\n{f:.0f} Hz", color=MAU[ten], ha="center", va="bottom")a2.set(xlim=(0, 800), ylim=(0, 1.35), xlabel="tần số (Hz)", ylabel="độ to", title="Fourier đọc ra: ba nốt, mỗi nốt một vạch, tiếng ồn nằm rải rác ở đáy")for a in (a1, a2): a.grid(color="#2a2e35", lw=0.6) a.set_axisbelow(True)fig.tight_layout()fig.savefig("hop-am-fourier.png", dpi=150)Kết quả in ra:
Đô: đặt vào 1.00, FFT đọc ra 1.01 ở 262 Hz Mi: đặt vào 0.70, FFT đọc ra 0.70 ở 330 HzSol: đặt vào 0.50, FFT đọc ra 0.50 ở 392 HzN = 2048: hai cách cho cùng kết quả: TrueDFT thẳng: 7.8 ms · FFT: 0.105 msDù mỗi mẫu bị nhiễu tới khoảng 0,3 đơn vị, FFT vẫn đọc lại độ to của từng nốt gần như chính xác, vì tiếng ồn ngẫu nhiên bị rải đều ra 4.001 ô tần số, còn mỗi nốt dồn hết vào một ô. Đây cũng là lý do Shazam vẫn nghe ra bài hát giữa quán ồn. Thời gian đo trên máy của tác giả; máy bạn sẽ ra số khác, nhưng FFT vẫn nhanh hơn vài chục tới vài trăm lần ở , và khoảng cách càng lớn khi tăng. Bạn có thể thử đổi tần số trong NOT thành một nốt lệch như 261,63 Hz để thấy vạch bị “loang” sang hai ô bên cạnh: một giây tín hiệu chỉ phân biệt được các tần số cách nhau 1 Hz.
Từ thanh sắt nóng tới chiếc điện thoại
Năm 1807, Fourier chỉ muốn biết một thanh sắt nguội đi như thế nào. Để trả lời, ông đưa ra một khẳng định mà những người giỏi nhất thời ấy cho là thiếu chặt chẽ: mọi hình dạng đều là tổng của những sóng đơn giản. Năm 1805, Gauss đã tìm ra cách tính nhanh nó nhưng cất trong ngăn kéo. Năm 1965, nỗi lo về những vụ nổ hạt nhân dưới lòng đất khiến hai nhà khoa học tìm lại cách tính ấy.
Hôm nay, mỗi lần bạn nghe một bài hát, gửi một tấm ảnh, bắt sóng 4G hay chụp MRI, ý tưởng của thầy giáo mồ côi ở Auxerre lại chạy hàng nghìn lần trong vài giây. Lần tới khi Shazam đọc tên bài hát chỉ sau ba giây, bạn biết trong ba giây ấy chiếc điện thoại đã nếm “bát nước dùng” âm thanh và đọc ra công thức của nó.
Nếu thích kiểu bài “một ý tưởng thuật toán đứng sau thứ bạn dùng hằng ngày”, bạn có thể đọc tiếp về Bloom filter hay tìm kiếm bằng hình ảnh.
Vẽ minh họa hình học miễn phí cho học sinh và giáo viên: EyeViz.
Tài liệu tham khảo
- [1]J. J. O'Connor và E. F. Robertson. Joseph Fourier, biography. MacTutor History of Mathematics, Đại học St Andrews.
- [2]Joseph Fourier. Théorie analytique de la chaleur. Firmin Didot, Paris, 1822.
- [3]Joseph Fourier. Remarques générales sur les températures du globe terrestre et des espaces planétaires. Annales de Chimie et de Physique, 27, 136–167, 1824.
- [4]Avery Li-Chun Wang. An Industrial-Strength Audio Search Algorithm. Proceedings of ISMIR 2003, 2003.
- [5]ISO/IEC 11172-3: Coding of moving pictures and associated audio, Part 3: Audio (MPEG-1 Audio, gồm Layer III/MP3). ISO/IEC, 1993.
- [6]ITU-T T.81: Digital compression and coding of continuous-tone still images (JPEG). ITU-T, 1992.
- [7]N. Ahmed, T. Natarajan và K. R. Rao. Discrete Cosine Transform. IEEE Transactions on Computers, C-23(1), 90–93, 1974.
- [8]3GPP TS 36.211: Evolved Universal Terrestrial Radio Access (E-UTRA); Physical channels and modulation. 3GPP.
- [9]The Nobel Prize in Chemistry 1991: Richard R. Ernst. NobelPrize.org.
- [10]A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey và I. Sutskever. Robust Speech Recognition via Large-Scale Weak Supervision (Whisper). arXiv:2212.04356, 2022.
- [11]J. W. Cooley và J. W. Tukey. An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19(90), 297–301, 1965.
- [12]M. T. Heideman, D. H. Johnson và C. S. Burrus. Gauss and the History of the Fast Fourier Transform. IEEE ASSP Magazine, 1(4), 14–21, 1984.
- [13]Cooley–Tukey FFT algorithm. Wikipedia.
- [14]J. Dongarra và F. Sullivan. Guest Editors’ Introduction: The Top 10 Algorithms. Computing in Science & Engineering, 2(1), 22–23, 2000.
- [15]Gilbert Strang. Wavelets. American Scientist, 82(3), 250–255, 1994.


