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

看板Math作者 (Tidus)時間7年前 (2019/01/09 11:16), 7年前編輯推噓6(6推 0噓 34→)
留言40則, 7人參與, 7年前最新討論串1/1
快速傅立葉只能用於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)
→
07/22 16:41,
chx64的1/2悖論真的很經典呢
07/22 16:41
！！！！！！！！！！！！！！簽名檔破750000點擊率啦！！！！！！！！！！！！！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.170.225 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1547003763.A.1D4.html
→
01/09 11:24, 7年前 , 1F
...難道不是因為兩組資料點不一樣嗎(?
01/09 11:24, 1F
那要如何補到 2^N,？
推
01/09 13:44, 7年前 , 2F
FFT只要不是質數都可以拆解，不一定要2^N
01/09 13:44, 2F
→
01/09 14:03, 7年前 , 3F
因為不知道會有幾個資料點，所以補到2^N比較好
01/09 14:03, 3F
推
01/09 16:51, 7年前 , 4F
…為什麼補零以後會一樣？
01/09 16:51, 4F
→
01/09 16:53, 7年前 , 5F
FFT應該有假設資料是periodic 吧？補了零波形都整個
01/09 16:53, 5F
→
01/09 16:53, 7年前 , 6F
不一樣啦。
01/09 16:53, 6F
→
01/09 16:55, 7年前 , 7F
所以我是問要怎麼補
01/09 16:55, 7F
推
01/09 17:28, 7年前 , 8F
01/09 17:28, 8F
→
01/09 17:28, 7年前 , 9F
這篇有說明加0會發生什麼事情
01/09 17:28, 9F
→
01/09 17:49, 7年前 , 10F
那篇0補在後面可是他的頻譜只是變平滑而已
01/09 17:49, 10F
→
01/09 17:51, 7年前 , 11F
雖然是平滑 畢竟變了
01/09 17:51, 11F
→
01/09 17:52, 7年前 , 12F
它有說補零的話 0的部分至少要超過一半
01/09 17:52, 12F
→
01/09 18:09, 7年前 , 13F
不過如四樓所說，補零整個波形就改變了，為何出來的
01/09 18:09, 13F
→
01/09 18:09, 7年前 , 14F
頻譜僅是變的平滑而已？我其實認為應該是完全不同
01/09 18:09, 14F
推
01/09 21:31, 7年前 , 15F
無限長的訊息看成 [signal 0 0 0 0 0 0..0 0 0]
01/09 21:31, 15F
→
01/09 21:32, 7年前 , 16F
而我們對x1 FFT 與 [x1 0 0 0 .. 0 0] FFT是一樣的
01/09 21:32, 16F
→
01/09 21:32, 7年前 , 17F
x1 , [x1 0], [x1 0 0] .... 都是一樣
01/09 21:32, 17F
→
01/09 21:34, 7年前 , 18F
了解DTFT跟取樣之後 應該會比較清楚
01/09 21:34, 18F
→
01/09 21:35, 7年前 , 19F
我才一年沒碰 都忘光了 有錯請指正XD 感恩
01/09 21:35, 19F
推
01/09 22:09, 7年前 , 20F
http://t.cn/EGDSp2y 中間一段:DTFT與DFT頻率解析度
01/09 22:09, 20F
→
01/10 04:48, 7年前 , 21F
時域的長度對應到頻域的解析度(反之亦然)這是最基本
01/10 04:48, 21F
→
01/10 04:52, 7年前 , 22F
變平滑純粹就因為頻域的解析度變高 看上去就平滑了
01/10 04:52, 22F
→
01/10 04:54, 7年前 , 23F
實際頻譜相同頻率點上的值沒有改變
01/10 04:54, 23F
→
01/10 04:54, 7年前 , 24F
這裡的數學是DFT FFT只是算DFT的一個算法而已
01/10 04:54, 24F
→
01/10 04:55, 7年前 , 25F
你拿一個補零成兩倍長的例子代入DFT就會知道沒變
01/10 04:55, 25F
→
01/10 04:56, 7年前 , 26F
現在你的例子不是補到整數備嘗 所以頻遇取樣的地方
01/10 04:56, 26F
→
01/10 04:57, 7年前 , 27F
沒有對到的地方 當然就不會發現一樣的值
01/10 04:57, 27F
→
01/10 08:11, 7年前 , 28F
還有用現成軟體套件不用自己補零因為軟體都已優化了
01/10 08:11, 28F
→
01/10 08:42, 7年前 , 29F
感謝樓上，因為我是要 C 實現，一開始發現為什麼網
01/10 08:42, 29F
→
01/10 08:42, 7年前 , 30F
路上找的code都有限定2^N可是numpy跟matlab都不用
01/10 08:42, 30F
推
01/10 11:06, 7年前 , 31F
如果補零到整數倍，那分解回來一樣是在原長度做FT
01/10 11:06, 31F
→
01/10 11:38, 7年前 , 32F
我剛剛試了一下出來的結果還是不一樣，不知道哪錯了
01/10 11:38, 32F
→
01/10 11:38, 7年前 , 33F
01/10 11:38, 33F
→
01/10 11:39, 7年前 , 34F
01/10 11:39, 34F
→
01/10 11:40, 7年前 , 35F
FFT 先與 自己寫的 DFT 和 numpy FFT 對過沒錯
01/10 11:40, 35F
→
01/10 11:40, 7年前 , 36F
如果是五個量測點，我 FFT 補到 16 個去做仍不一樣
01/10 11:40, 36F
→
01/10 17:52, 7年前 , 37F
01/10 17:52, 37F
我把訊號轉成頻譜強度，原訊號是 sin(2*pi)+sin(30*pi)+sin(100*pi)，在[0,2pi)內等分1000點， 橘色是FFT補到2048，藍色是直接DFT，還沒除1000。
→
01/10 22:08, 7年前 , 38F
5個和補到16個不一樣應是r大講的頻譜取樣地方沒對到
01/10 22:08, 38F
→
01/10 22:11, 7年前 , 39F
看matlab fft的說明文件,裡面FFTW的連結可能有幫助
01/10 22:11, 39F
→
01/10 22:19, 7年前 , 40F
0,1/5,...,4/5和0,1/16,...,15/16除了0其他都沒對到
01/10 22:19, 40F
※ 編輯: j0958322080 (110.26.230.28), 01/10/2019 23:05:21 ※ 編輯: j0958322080 (110.26.230.28), 01/10/2019 23:08:21
‣ 更多 j0958322080 的文章
文章代碼(AID): #1SDMTp7K (Math)