Tag Archives: 離散傅立葉轉換

快速傅立葉轉換

本文的閱讀等級:中級 給定一序列 ,離散傅立葉轉換的計算公式為 (見“離散傅立葉轉換”) 。 令 。離散傅立葉轉換可表示成矩陣形式 ,如下: , 其中 階 稱為傅立葉矩陣。若採用一般矩陣乘法運算,離散傅立葉轉換的計算複雜度為 。公元1965年,美國學者庫利 (James Cooley) 與圖基 (John Tukey) 提出了一個複雜度為 的演算法,稱為快速傅立葉轉換 (fast Fourier transform,簡稱 FFT),後來人們發現原來高斯 (Carl Friedrich Gauss) 早在1805年就已經提出同樣的演算法。本文採用別於傳統訊號處理的推導方法[1],我們先檢視傅立葉矩陣 擁有的特殊性質,然後運用分塊矩陣技巧推導 Cooley-Tukey 演算法。除了本文介紹的 Cooley-Tukey 演算法,還有其他多種形式的快速傅立葉轉換演算法,請讀者參閱維基百科[2]。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , | 6 Comments

摺積與離散傅立葉轉換

本文的閱讀等級:中級 在電機工程領域中,特別是訊號處理、電路和控制系統,線性非時變系統 (linear time-invariant system,簡稱 LTI 系統) 是一種廣泛使用的系統模型。LTI 系統按照所處理的訊號分為兩大類:連續時間系統和離散時間系統。本文從線性代數觀點介紹離散時間 LTI 系統的基本運算:摺積 (卷積,convolution),並說明如何利用離散傅立葉轉換計算摺積。   考慮兩個 次實多項式 乘積 為一 次多項式,稱為柯西乘積 (Cauchy product): , 第 次項由 構造而成,其係數為 。 上式中,,若 。將多項式 和 的係數合併成 維係數向量 這裡 和 的元指標從0開始算起,以下所有向量遵守同樣規則。同樣地,乘積 的係數 亦可合併為係數向量,如下: , 稱為 和 的摺積。我們加入最末0元的用意在使 成為 … Continue reading

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , , , , | 12 Comments

離散傅立葉轉換

本文的閱讀等級:中級 考慮定義於區間 的 -週期函數 的指數傅立葉級數 (見“傅立葉級數 (下)”): , 其中複傅立葉係數為 。 若 滿足 Dirichlet 條件 (見“傅立葉級數 (上)”),可以證明 ,在此情況下,往後我們不再區分函數 與其傅立葉級數 ,而一律以 表示。本文將解除 是週期函數的限制,以下僅假設 是有界的。當 ,傅立葉級數可推廣為傅立葉轉換 (Fourier transform)。還有,若 不再是連續函數而是一有限數列,傅立葉級數又可延伸為離散傅立葉轉換 (discrete Fourier transform,簡稱 DFT)。本文將介紹這兩種轉換的推導過程,並解說離散傅立葉轉換的線性代數性質。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , | 1 Comment