Re: [問題] 還有人記得傅立葉變換嗎？

[HuangJC (吹笛牧童)]

: → recorriendo : 是誤差?還是頻域取樣的問題? #1SDMTp7K (Math)       11/15 17:33

: → recorriendo : 一樣的輸入 輸出卻不同 就是你程式設計者本身的問題  11/16 16:10

我提供了程式，以及數個執行結果，以避免溝通上的問題
我希望你也可以講得明白一點

我承認這不是誤差，但當時我還是用'誤差'一詞比較好表達
舉例來說，圓週率 PI 約是 3.14159265359
如果改用 22/7，那誤差就會比較大
但不管用多精密的電腦，只要你用 22/7，誤差永遠都會那麼大

你要說這是程式設計的問題，的確可以
你可以說：誰叫你只用 22 / 7？為什麼不從其他逼進法去精確求取
可是這就是另一個題目了

現今我們題目是： 快速傅立葉如何求取 10 hz 取樣的 1hz sin 波
你說一樣的輸入，我不懂你的意思，因為輸入明顯不一樣


: → recorriendo : 這不是什麼誤差 而是你不願去了解數學細節 曲解輸出  11/16 16:12
: → recorriendo : 的意義  更不是頻率洩漏 那完全是另一個問題 跟補不  11/16 16:13
: → recorriendo : 補零無關                                          11/16 16:13
: → recorriendo : 你可以直接補到128點,256點等等 看看得出來結果怎麼  11/16 16:17
: → recorriendo : 變化 或許有助了解其中原理                         11/16 16:18

我無法補到 128 點
因為我一取就是十點，如果是 16 點就沒問題
但"硬體設備有其天然限制"，今天我就是給你十點

十點怎麼變成更多點我也交代了，也附上了執行結果
的確有助於了解其原理
而了解後我說：這就是頻率洩露

如果不使用快速傅立葉，那我可以直接設計 10 點的輸入陣列
求取出來就是精準

這不叫程式設計的問題，傅立葉這個 DLL 是別人寫好的
問題是如何呼叫
前面的文章也是有人在問：請問零要怎麼補，怎麼會補了感覺還是不對勁

這個怎麼補零，才是呼叫端可以討論的事
而補零的方法不同，輸入就不同
所以我說我不懂你講的"一樣的輸入，輸出不同就是程式設計的問題"

你這就類似"一樣在求取 PI，但用 22/7 就是程式設計的問題"
先有方法後有程式
一但決定用 22 / 7 去找圓週率，那問題就永遠存在，'誤差'永遠在
（雖然你說這不叫誤差，但實在很難找到值形容，所以我加引號）

同樣的我要說，一但決定用補零的方法去做快速傅立葉
那問題就永遠存在

這如果不是頻率洩露，那我希望得到更詳細的講解
畢竟網頁就在那裡，我也可以自行翻譯
但是翻譯時能不能掌握精髓，或者就是翻得有誤會
這不是你說'這不叫頻率洩露'我就可以頓悟的

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.204.139.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1573897974.A.0E8.html

如果用 10hz 取樣結果，輸入給 size=128 的快速傅立葉
則頻率解析度勢必是 10/128

10/128*12 = 0.9375
10/128*13 = 1.015625

我們可以不斷提高快速傅立葉的解析度，但始終只是逼近而不是相等於 1hz
輸入波型是 1hz 的 sin 波
但傳回值始終都不會有 1hz 這一項

這問題是永遠存在的，而繪出來的波型也不會是一根細細長長，而是圓圓的
不叫頻率洩露的話，那應該有另一個更精確的名字

推 j0958322080 : 當然是你不懂FFT，FFT不是只能用2的整數數次方數
                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

這句挺關鍵的，所以你有看懂我的問題

→ j0958322080 : 當然FFT也不可能應用在任意數目上，在某些數還是DFT
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

可是又有這句...

→ j0958322080 : 看你之前的回應我不是很想回你，只是有人貼我那篇
懶得打字的話也沒關係，在純文字介面上要討論這些本來就很不容易
如果我不再回應，心中認為自己是對的，那狀況大概和你差不多
只有打出來才會被檢視，更何況被質疑時，也不知是自己錯還是質疑我們的人錯呢..

我們都只能在有打出來的這個範圍繞圈圈而已
現實的說，我搞懂的部份已經解決了我的問題
其實我不用再做回應

還是很感謝大家
※ 編輯: HuangJC (123.204.139.199 臺灣), 11/16/2019 19:35:44
推 sunev       : 你查過中文維基了嗎？快速傅立葉變換根本就不限於
→ sunev       : 2^N啊
應該說我沒把題目寫好
我只能拿到需要 2^N 的這種快速傅立葉

有其他的，但我沒拿到
而我們問題也是繞在 "只有這種工具，怎麼用它"
一個補零動作其實是有很多問題的...

> Cooley-Tukey演算法也可以用於序列長度N 為任意因數分解形式的DFT

如果說，能因式分解就能加速，那就只有質數不能做快速傅立葉
（前面推文好像有看到這句）

而 10hz 取樣，所以一秒取了 10 個值， 10 = 5 * 2
我們當然也可以加速一些

但程式複雜度呢？傅立葉分析畢竟是要被寫成副程式運用的
要說任意 size 的話，那連快速兩字都摘掉，直接用 FFT 當然可以 size = 10
但如果沒有 FFTW 這個 DLL，以我同事傳給我的副程式
它很強列的要求 2 的 N 次方
前面那篇視為困擾的也是補 0 這件事

如果你們不是程式設計師，而是數學家
可能感受沒我這麼強烈
你們想的可能是：就算 5*2，也已經用到快速傅立葉，有用到就算
但我會想的是：5*2 這種拆解，那我得去寫這樣的快速傅立葉
我手上沒有

我手上有的是什麼呢？我或許該進一步把副程式公佈，程式小而美
但那才是工程師面對的：這就是我的資源

我同事在我用 FFTW 時跟我說一句話：你要小心可攜性，除非你不想拿去別的平台用
幸運的是我在 win 下開發，所以我沒管可攜性
但我同事在專用晶片開發，廠商已經有寫好的快速傅立葉供他呼叫
如果是廠商限制只能用 2^n 這種型式，那問題還是在的
除非他有興趣自己重寫副程式

問題通常不只一個地方可以解，呼叫端解或者副程式解都可以，都是對的
但我們不是想重寫副程式那個人，我們只有接受而已
因為 speed & size 通常人家都最佳化好了
除非我們很有興趣從輪子開始打造車子...



※ 編輯: HuangJC (123.204.139.199 臺灣), 11/16/2019 23:32:41
→ HuangJC     : 不過我挺有興趣查查，晶片有名也才那些..
→ HuangJC     : 我同事好像用 arm, 而 arm 好像有 fftw 可以用