卷積定理（convolution theorem）

卷積是把一個訊號滑過另一個、在重疊處相乘、再加總的運算——模糊如何塗抹一張影像、回聲如何拖在聲音之後、濾波器如何塑形波形，靠的都是它。直接做很費力：對兩串各長 N 的清單，每個輸出點是對多達 N 個乘積求和，整體 O(N^2) 工作。卷積定理是那條美麗的捷徑，它說：困難的卷積，一旦進入頻域，就變成容易的普通乘法。

陳述很俐落：卷積的傅立葉轉換等於各傅立葉轉換的逐點乘積。用符號表示，若 x 與 h 是訊號、* 表示卷積，則 DFT(x * h) = DFT(x) . DFT(h)，其中圓點是單純的逐元素相乘。所以卷積兩個訊號的配方是三步：轉換 x、轉換 h（兩次 FFT），把兩個頻譜逐項相乘（便宜，O(N) 工作），再把乘積反轉換回來（再一次 FFT）。時域裡糾纏的滑動與求和，在頻域塌縮成單一次乘法。直觀上這說得通，因為卷積對每個頻率獨立作用——濾波器只是把每個頻率分量縮放某個量——而轉換正是揭露那些獨立分量的東西。

這個定理是計算數學中最具影響力的事實之一，因為它把 O(N^2) 運算化為 O(N log N)（成本由三次 FFT 主導）。它支撐快速數位濾波、影像處理、快速多項式與大整數乘法，以及雷達與通訊中的匹配濾波器。一個要小心的點：DFT 執行的是「循環」（週期）卷積，會把兩端環繞。要得到普通的線性卷積，你必須在轉換前把兩個訊號補零到至少「合併長度減一」，否則環繞會汙染結果。