FFT實際上讓你看到了什麼

問題

在鋼琴上演奏和弦——比如C和E一起演奏. 你的耳朵聽到一個聲音 但這聲音是超過兩個頻率的:261.6Hz和329.6Hz. 不同的毛細胞在不同的頻率下回應, 向你的大腦發出不同的訊息.

快速傅里叶變形也有同樣的功能 但有數字而不是毛細胞 給它一個信號( 隨時間推移的振幅樣本序列) , 它會傳回一個頻率和強度的清單 。 答案是:** 有多少頻率

到底發生了什麼

逐年抽查的訊號是數字列表: 每個樣點的振幅 。 一秒鐘的錄音是44100赫茲的數字 這些數字描述的是時域中的訊號——振幅是時空的函数.

FFT 將它轉換為**頻率域 ** —— 振幅為頻率的函数 。 相同的信息,不同的代表。 就像在笛卡爾和極地座標之間切換: 沒有建立或毀滅, 只有重新表示.

數學核心: 每一個周期性信號都可以被寫成不同頻率的正弦和余弦波的总和 。 這是Fourier的定理(1807年). FFT 計算總和的系数.

為什麼"快"

用天真的方法來計算 Fourier 變化需要 N2樣本的操作 1 024個樣本,大概有100萬次 Cooley-Tukey算法(1965年)將它降為N&log2(N)——同一個輸入的操作約10,000次. 一100x加速。 對一百萬個樣本來說 速度是5萬x.

技術:把 N 點轉換成 2 N/2 點轉換,循環轉換. 這要求 N 是 2 的權力( 或者您用 0 的 垫 ) 。 每分一半的問題。 「蝴蝶」行動將兩半结合起来:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

W是複雜的指数( 複雜的平面中的旋轉) 。 同兩個子結果給你兩個輸出點。 這就是為什麼算法是"快速的"——它重复了每次計算的兩次.

PinePaper的實施是一本教科书Cooley-Tukey radex-2 DIT(按時宣佈)。 40行 JavaScript. 我們從零開始寫,而不是匯入圖書館, 因為我們希望學生能夠讀取來源.

那些巴的意思

當你看到一個光谱分析器 —— 跳到音樂的酒吧 —— 每一個酒吧代表一個頻率桶。 高度是目前信號中频率的大小( 強度) .

• 一個純正弦波.
• • 平方波** 在基本和奇特的口琴(第3、第5、第7、第7、第1、第1、第1、第1、第1、第1、第2、第2、第3、第3、第5、第5、第7、第7、第1、第1、第1、第1、第1、第1、第1、第1、第2、第3、第3、第5、第5、第5、第7、第7、第1、第1、第1、第1、第1、第1、第1、第1、第3、第2、第3、第3、第5、第5、第5、第7、第7、第1、第1、第1、第1、第1、第1、第1、第1、第1、第1、第1、第1、第1、第1、第2、第2、第2、第2、第2、第2、第2、第2、第3、第3、第3、第3、第2、第3、第3、第 所以正方形波會發出「buzzy」的聲音.
• 白色的噪音 到處都有高度大致相等的酒吧 每一個頻率都有相同的可能性.
• 發出一個基本的(你聽到的)發音 加上成形物.

視窗: 為什麼邊緣重要

有擒. FFT假設信號會永遠重複 但我們的樣本是有限的 開始和停止 如果信號在兩端沒有零點 突然的截斷會產生人工的高頻含量 這叫做光谱泄漏.

固定 : 乘以** 窗口函數 ** , 它能平滑地在邊緣拍攝到零 。 共同視窗 :

• ** Hann**(餘弦鐘):一般目的好,失去一些頻率分辨率
• ** Hamming **:與Hann相似,但邊緣未達零度
• ** Blackman **:主葉更窄, 更好的侧球壓抑, 失去更頻率的分辨率

選項總是取舍於頻率解析度(如何精确辨別頻率)和光谱漏漏(有多少能量流到鄰居的垃圾桶中)。 沒有完美的窗戶 這是不确定性原理的后果.

FFT住的地方

您與 FFT 的結果經常交換:

• ** MP3 和 AAC 壓縮** : 將音效轉換成頻率域, 丟棄聽力阈值以下的頻率, 壓縮剩下的。 轉換是失去音效壓縮的全部基础.
• ** JPEG 壓縮 **: 2D 版本( DCT) 將 8x8 像素區塊轉換成頻率域, 将高頻元件量化 。 所以JPEG的藝術品才會出現在街頭上.
• ** WiFi 和 5G **: OFDM 編碼在很多頻率子卡路里分割資料。 FFT 在時域傳輸與頻域數據符號之間轉換 .
• MRI成像:磁共振掃瞄器的原始信號在頻率空間。 反向 FFT 重建空間影像 。 從字面上看,你見過的每一次核磁共振都是反向的Fourier轉變.
• ** Shazam **: 計算光谱( FFT 過滑動視窗) 、 提取峰值、 符合數據庫的樣式 。 FFT是認出每首歌的第一步.

一個60歲的算法,在你口袋里, 每天跑數十億次.

工具:

試試看

開啟 PinePaper, 選擇 Spectrum 分析器產生器 。 生成方波. 看看那些酒吧,你會看到 奇怪的口琴掉到1/n。 切換成锯牙, 切換到噪音——平整光谱,每一個頻率都一樣可能.

改變視窗功能 。 看著漢恩如何以更大的峰值來平滑光谱 切換到 Blackman ─ 更窄的山峰但下方的邊緣 .

你不是在看FFT 你在測量信號 觀察變化所揭示的 即知解之异.

參考

• Brigham, E.O.(1988年)。 * 《快速變形》及其應用程序*。 普倫蒂斯·霍爾.
• Cooley, J.W. & Tukey, J.W. (1965年)。 Fourier系列机器計算法 *算法 *,19(90),297-301.
• Fourier, J. (1822年). * 沙勒河分析* 巴黎:菲爾明·迪多特.
• Harris, F.J. (1978). 使用視窗與Discrete Fourier 變化的調谐分析 。 * IEEE的收益*,66(1),51-83.
• Oppenheim, A.V. & Schafer, R.W.(2009年)。 * 第3版。 普倫蒂斯·霍爾.
• Shannon, C.E.(1949年)。 在噪音的存在中的交流。 * IRE的收益*,37(1),10-21.
• Smith, S.W.(1997年)。 * 科學家和工程師數位信號處理指南*。 加州技術出版社.
• Wang, A.,等人(2003年)。 工業- Strength 音效搜尋算法 。 * 2003年ISMIR收益。 (Shazam的音效指紋算法)
• Wallace, G.K.(1991年)。 JPEG Still Pictures 壓縮標準 。 * ACM通信*,34(4),30-44.

---

*PinePaper的FFT是Cooley-Tukey radex-2的實施,配有漢恩,漢明,和布莱克曼的視窗,加上低通和高通滤波器. 在 [pinepaper. studio/editor] (/editor) 自由試試。 *