[問題] FFT補零的方法

[j0958322080 (Tidus)]

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

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

因為套裝軟體沒辦法符合我的需求，

所以使用numerical recipe中FFT 的code，

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

http://i.imgur.com/hXDLxgj.jpg
我把訊號轉成頻譜強度，

橘色是FFT補到2048，藍色是直接DFT，都還沒除1000。

昨天問人說FFT轉出來不正確，我想可能是因為補零造成內插，

這樣FFT要如何使用於任意數的資料點數？

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

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.230.28
※ 文章網址: https://www.ptt.cc/bbs/comm_and_RF/M.1547167375.A.6D0.html
推 profyang: Matlab的fft，不補到2的次方也可以算 你
→ j0958322080: 公司沒有matlab，且包成dll用C較方便
推 bxxl: 應該沒錯, 本來就是長這樣. 不同點數的DFT
→ bxxl: 算出來的結果本來就不會一樣啊.
→ bxxl: 你要先懂N點DFT結果的物理意義.
→ bxxl: N不同,你對應頻率上的格子點就偏移了
推 bxxl: 但偏移不代表不對,只是你要正確的解讀它
推 bxxl: 另外回到原題,最簡單的做法就是直接餵它1024
→ bxxl: 有限制說你不能一次取1024點資料嗎?
→ bxxl: 常見的應用中,取樣訊號是一直進來的
→ bxxl: 要取1000點或1024點是看你方便, 那當然選
→ bxxl: 計算快速的1024點啊
→ j0958322080: 點數我不能保證，因為是寫給客戶的
→ j0958322080: 我們只能建議他量測2^N點數
→ j0958322080: 這樣看起來就只能混用Radix去做了
推 bxxl: matlab是call FFTW library
→ bxxl: 基本上也是不同點數的算法不一樣
→ bxxl: N能因數分解為小質數時最快
→ j0958322080: 原來matlab也是call FFTW的喔@@
推 cuello: 不用再受限2^n了吧，我之前都直接叫fftw
→ cuello: 如果你剛好用Linux, $ apt-cache search
→ cuello:  fftw
→ cuello: fftw 很強的， NR 並非ㄧ定可靠喔～
→ cuello: 有些問題用掉過我了我不少時間精力....
→ cuello: 得到的教訓：數值問題交給數值專家...
→ cuello: 我根本就不該花時間去改碼到算對為止...
→ cuello: （NB: 但我說的並不是它的 dft routines
→ cuello: ）
推 cuello: ＂算對＂？是，會有算對算錯的問題！
→ cuello: 隨時要有其它軟體可以對答案，我常用 ma
→ cuello: tlab
→ cuello: 所以，必須自己寫時，建議用可靠的程式庫
→ j0958322080: 是這樣沒錯，FFTW沒開放源碼，僅DLL
→ j0958322080: 我個人是習慣把源碼擷取出來包進程式
推 cuello: 我自己的確也有這種頃向，ㄧ直都是
→ cuello: 後來也找到了原始碼對付任何尺寸，不必方
→ cuello: 形
→ cuello: 現在想起來程式裡 fftw ㄧ直都非預設，是
→ cuello: 選項 :)