作者j0958322080 (Tidus)
看板comm_and_RF
標題[問題] FFT補零的方法
時間Fri Jan 11 08:42:50 2019
快速傅立葉只能用於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)
1F：→ yeebon: chx64的1/2悖論真的很經典呢07/22 16:41
！！！！！！！！！！！！！！簽名檔破750000點擊率啦！！！！！！！！！！！！！！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.230.28
※ 文章網址: https://webptt.com/m.aspx?n=bbs/comm_and_RF/M.1547167375.A.6D0.html
2F：推 profyang: Matlab的fft，不補到2的次方也可以算 你114.137.114.214 01/12 12:23
3F：→ j0958322080: 公司沒有matlab，且包成dll用C較方便 27.242.7.14 01/12 18:11
4F：推 bxxl: 應該沒錯, 本來就是長這樣. 不同點數的DFT220.136.146.133 01/13 19:31
5F：→ bxxl: 算出來的結果本來就不會一樣啊.220.136.146.133 01/13 19:31
6F：→ bxxl: 你要先懂N點DFT結果的物理意義.220.136.146.133 01/13 19:33
7F：→ bxxl: N不同,你對應頻率上的格子點就偏移了220.136.146.133 01/13 19:35
8F：推 bxxl: 但偏移不代表不對,只是你要正確的解讀它220.136.146.133 01/13 19:42
9F：推 bxxl: 另外回到原題,最簡單的做法就是直接餵它1024220.136.146.133 01/13 19:47
10F：→ bxxl: 有限制說你不能一次取1024點資料嗎?220.136.146.133 01/13 19:48
11F：→ bxxl: 常見的應用中,取樣訊號是一直進來的220.136.146.133 01/13 19:49
12F：→ bxxl: 要取1000點或1024點是看你方便, 那當然選220.136.146.133 01/13 19:49
13F：→ bxxl: 計算快速的1024點啊220.136.146.133 01/13 19:49
14F：→ j0958322080: 點數我不能保證，因為是寫給客戶的 27.242.7.14 01/13 21:11
15F：→ j0958322080: 我們只能建議他量測2^N點數 27.242.7.14 01/13 21:12
16F：→ j0958322080: 這樣看起來就只能混用Radix去做了 27.242.7.14 01/13 21:14
17F：推 bxxl: matlab是call FFTW library220.136.146.133 01/13 23:42
18F：→ bxxl: 基本上也是不同點數的算法不一樣220.136.146.133 01/13 23:42
19F：→ bxxl: N能因數分解為小質數時最快220.136.146.133 01/13 23:43
20F：→ j0958322080: 原來matlab也是call FFTW的喔@@ 27.242.7.14 01/14 00:27
21F：推 cuello: 不用再受限2^n了吧，我之前都直接叫fftw 61.230.112.161 11/05 23:21
22F：→ cuello: 如果你剛好用Linux, $ apt-cache search 61.230.112.161 11/05 23:23
23F：→ cuello: fftw 61.230.112.161 11/05 23:23
24F：→ cuello: fftw 很強的， NR 並非ㄧ定可靠喔～ 61.230.112.161 11/05 23:26
25F：→ cuello: 有些問題用掉過我了我不少時間精力.... 61.230.112.161 11/05 23:29
26F：→ cuello: 得到的教訓：數值問題交給數值專家... 61.230.112.161 11/05 23:30
27F：→ cuello: 我根本就不該花時間去改碼到算對為止... 61.230.112.161 11/05 23:33
28F：→ cuello: （NB: 但我說的並不是它的 dft routines 61.230.112.161 11/05 23:35
29F：→ cuello: ） 61.230.112.161 11/05 23:35
30F：推 cuello: ＂算對＂？是，會有算對算錯的問題！ 61.230.112.161 11/05 23:40
31F：→ cuello: 隨時要有其它軟體可以對答案，我常用 ma 61.230.112.161 11/05 23:41
32F：→ cuello: tlab 61.230.112.161 11/05 23:41
33F：→ cuello: 所以，必須自己寫時，建議用可靠的程式庫 61.230.112.161 11/05 23:44
34F：→ j0958322080: 是這樣沒錯，FFTW沒開放源碼，僅DLL 39.9.30.88 11/16 18:20
35F：→ j0958322080: 我個人是習慣把源碼擷取出來包進程式 39.9.30.88 11/16 18:20
36F：推 cuello: 我自己的確也有這種頃向，ㄧ直都是 58.114.211.63 11/16 23:26
37F：→ cuello: 後來也找到了原始碼對付任何尺寸，不必方 58.114.211.63 11/16 23:30
38F：→ cuello: 形 58.114.211.63 11/16 23:30
39F：→ cuello: 現在想起來程式裡 fftw ㄧ直都非預設，是 58.114.211.63 11/16 23:33
40F：→ cuello: 選項 :) 58.114.211.63 11/16 23:33