[分析] 快速傅立葉補零的補法

[j0958322080 (Tidus)]

快速傅立葉只能用於2^N個資料點數，N為自然數，

有查到通常是會用補零的方式把資料點數補滿到2^N。

我給訊號源sin(2*pi)+sin(30*pi)+sin(100*pi)，在[0,2pi)內等分1000點，

http://i.imgur.com/hXDLxgj.jpg
我把訊號轉成頻譜強度，橘色是FFT補到2048，藍色是直接DFT，還沒除1000。

這個補零的方式應該要如何補才正確？

-----
Sent from JPTT on my LGE LG-H860.

--
！！！！！！！！！！！！！簽名檔破750000點擊率啦！！！！！！！！！！！！！！！
Fw: [問卦] 電影：決勝21點的機率問題  https://goo.gl/2BpbB7  #1MfN3FgZ (joke)
→ yeebon: chx64的1/2悖論真的很經典呢
！！！！！！！！！！！！！！簽名檔破750000點擊率啦！！！！！！！！！！！！！！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.170.225
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1547003763.A.1D4.html
→ Desperato   : ...難道不是因為兩組資料點不一樣嗎(?
那要如何補到 2^N,？
推 sunev       : FFT只要不是質數都可以拆解，不一定要2^N
→ j0958322080 : 因為不知道會有幾個資料點，所以補到2^N比較好
推 wohtp       : …為什麼補零以後會一樣？
→ wohtp       : FFT應該有假設資料是periodic 吧？補了零波形都整個
→ wohtp       : 不一樣啦。
→ j0958322080 : 所以我是問要怎麼補
推 Desperato   : https://goo.gl/9Nymc9
→ Desperato   : 這篇有說明加0會發生什麼事情
→ j0958322080 : 那篇0補在後面可是他的頻譜只是變平滑而已
→ Desperato   : 雖然是平滑 畢竟變了
→ Desperato   : 它有說補零的話 0的部分至少要超過一半
→ j0958322080 : 不過如四樓所說，補零整個波形就改變了，為何出來的
→ j0958322080 : 頻譜僅是變的平滑而已？我其實認為應該是完全不同
推 shuncheng   : 無限長的訊息看成 [signal 0 0 0 0 0 0..0 0 0]
→ shuncheng   : 而我們對x1 FFT 與 [x1 0 0 0 .. 0 0] FFT是一樣的
→ shuncheng   : x1 , [x1 0], [x1 0 0] .... 都是一樣
→ shuncheng   : 了解DTFT跟取樣之後 應該會比較清楚
→ shuncheng   : 我才一年沒碰 都忘光了 有錯請指正XD 感恩
推 shuncheng   : http://t.cn/EGDSp2y 中間一段:DTFT與DFT頻率解析度
→ recorriendo : 時域的長度對應到頻域的解析度(反之亦然)這是最基本
→ recorriendo : 變平滑純粹就因為頻域的解析度變高 看上去就平滑了
→ recorriendo : 實際頻譜相同頻率點上的值沒有改變
→ recorriendo : 這裡的數學是DFT  FFT只是算DFT的一個算法而已
→ recorriendo : 你拿一個補零成兩倍長的例子代入DFT就會知道沒變
→ recorriendo : 現在你的例子不是補到整數備嘗 所以頻遇取樣的地方
→ recorriendo : 沒有對到的地方 當然就不會發現一樣的值
→ recorriendo : 還有用現成軟體套件不用自己補零因為軟體都已優化了
→ j0958322080 : 感謝樓上，因為我是要 C 實現，一開始發現為什麼網
→ j0958322080 : 路上找的code都有限定2^N可是numpy跟matlab都不用
推 sunev       : 如果補零到整數倍，那分解回來一樣是在原長度做FT
→ j0958322080 : 我剛剛試了一下出來的結果還是不一樣，不知道哪錯了
→ j0958322080 : http://i.imgur.com/ArhHQrU.jpg
→ j0958322080 : http://i.imgur.com/KYyLYH4.jpg
→ j0958322080 : FFT 先與 自己寫的 DFT 和 numpy FFT 對過沒錯
→ j0958322080 : 如果是五個量測點，我 FFT 補到 16 個去做仍不一樣
→ j0958322080 : http://i.imgur.com/hXDLxgj.jpg
我把訊號轉成頻譜強度，原訊號是
sin(2*pi)+sin(30*pi)+sin(100*pi)，在[0,2pi)內等分1000點，
橘色是FFT補到2048，藍色是直接DFT，還沒除1000。
→ PPguest     : 5個和補到16個不一樣應是r大講的頻譜取樣地方沒對到
→ PPguest     : 看matlab fft的說明文件,裡面FFTW的連結可能有幫助
→ PPguest     : 0,1/5,...,4/5和0,1/16,...,15/16除了0其他都沒對到
※ 編輯: j0958322080 (110.26.230.28), 01/10/2019 23:05:21
※ 編輯: j0958322080 (110.26.230.28), 01/10/2019 23:08:21