Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
S.Winograd, "On computing the discrete Fourier transform," Mathematics of Computation, vol.32,no.141,pp.179-199,Jan.1978.
四月 03, 2023
威諾格拉德快速傅立葉變換演算法, 威諾格拉德快速傅立葉演算法, 英語, winograd, 是由美國電腦科學家shmuel, winograd, 英语, shmuel, winograd, 在1978年提出, 此演算法可以找出最少的乘法運算量, 當把dft的公式, displaystyle, begin, matrix, frac, matrix, qquad, cdots, 用矩陣方式來表示, displaystyle, begin, bmatrix, vdots, bmatrix, begin, bmatrix. 威諾格拉德快速傅立葉演算法 英語 Winograd FFT 是由美國電腦科學家Shmuel Winograd 英语 Shmuel Winograd 在1978年提出 此演算法可以找出最少的乘法運算量 當把DFT的公式 y j k 0 n 1 x k e j 2 p n i k j 0 1 n 1 displaystyle y j sum k 0 n 1 x k e j begin matrix frac 2 pi n end matrix ik qquad j 0 1 cdots n 1 用矩陣方式來表示 y 0 y 1 y n 1 1 1 1 1 1 1 w w 2 w n 2 w n 1 1 w n 1 w 2 n 1 w n 2 n 1 w n 1 n 1 x 0 x 1 x n 1 w e j 2 p n displaystyle begin bmatrix y 0 y 1 vdots y n 1 end bmatrix begin bmatrix 1 amp 1 amp 1 amp cdots amp 1 amp 1 1 amp w amp w 2 amp cdots amp w n 2 amp w n 1 vdots amp vdots amp vdots amp cdots amp vdots amp vdots 1 amp w n 1 amp w 2 n 1 amp cdots amp w n 2 n 1 amp w n 1 n 1 end bmatrix begin bmatrix x 0 x 1 vdots x n 1 end bmatrix quad w e j begin matrix frac 2 pi n end matrix 如果n是質數 則可以無視第一行與第一列 把n點的DFT用n 1點的迴旋摺積來取代 目录 1 使用方法 2 缺點 3 其他運用 4 參考資料使用方法 编辑使用此演算法 可分為以下幾個步驟 此處以n 5的DFT為例 y 0 y 1 y 2 y 3 y 4 1 1 1 1 1 1 w w 2 w 3 w 4 1 w 2 w 4 w w 3 1 w 3 w w 4 w 2 1 w 4 w 3 w 2 w x 0 x 1 x 2 x 3 x 4 w e j 72 displaystyle begin bmatrix y 0 y 1 y 2 y 3 y 4 end bmatrix begin bmatrix 1 amp 1 amp 1 amp 1 amp 1 1 amp w amp w 2 amp w 3 amp w 4 1 amp w 2 amp w 4 amp w amp w 3 1 amp w 3 amp w amp w 4 amp w 2 1 amp w 4 amp w 3 amp w 2 amp w end bmatrix begin bmatrix x 0 x 1 x 2 x 3 x 4 end bmatrix qquad w e j angle 72 circ Step 1 消去第一行與第一列 式子可以改寫如下 y 1 x 0 y 2 x 0 y 3 x 0 y 4 x 0 w w 2 w 3 w 4 w 2 w 4 w w 3 w 3 w w 4 w 2 w 4 w 3 w 2 w x 1 x 2 x 3 x 4 w e j 72 displaystyle begin bmatrix y 1 x 0 y 2 x 0 y 3 x 0 y 4 x 0 end bmatrix begin bmatrix w amp w 2 amp w 3 amp w 4 w 2 amp w 4 amp w amp w 3 w 3 amp w amp w 4 amp w 2 w 4 amp w 3 amp w 2 amp w end bmatrix begin bmatrix x 1 x 2 x 3 x 4 end bmatrix qquad w e j angle 72 circ Step 2 找出列與行的順序 a 找出一個原根 a 使得a k mod N 1 w h e n k 1 2 N 2 a N 1 mod N 1 displaystyle a k bmod N neq 1 quad when quad k 1 2 cdots N 2 quad a N 1 bmod N 1 b 用p n 表示列與行的順序 p n a n mod N n 0 1 N 2 displaystyle p n a n bmod N quad n 0 1 cdots N 2 在這例子中 N 5有兩個原根 2與3 取2作為其原根 可得其順序為 1 2 4 3 故要將此矩陣 y 1 x 0 y 2 x 0 y 3 x 0 y 4 x 0 w w 2 w 3 w 4 w 2 w 4 w w 3 w 3 w w 4 w 2 w 4 w 3 w 2 w x 1 x 2 x 3 x 4 displaystyle begin bmatrix y 1 x 0 y 2 x 0 y 3 x 0 y 4 x 0 end bmatrix begin bmatrix w amp w 2 amp w 3 amp w 4 w 2 amp w 4 amp w amp w 3 w 3 amp w amp w 4 amp w 2 w 4 amp w 3 amp w 2 amp w end bmatrix begin bmatrix x 1 x 2 x 3 x 4 end bmatrix quad 的第三列與第四列交換 第三行與第四行交換 把矩陣變成如下 y 1 x 0 y 2 x 0 y 4 x 0 y 3 x 0 w w 2 w 4 w 3 w 2 w 4 w 3 w w 4 w 3 w w 2 w 3 w w 2 w 4 x 1 x 2 x 4 x 3 displaystyle begin bmatrix y 1 x 0 y 2 x 0 y 4 x 0 y 3 x 0 end bmatrix begin bmatrix w amp w 2 amp w 4 amp w 3 w 2 amp w 4 amp w 3 amp w w 4 amp w 3 amp w amp w 2 w 3 amp w amp w 2 amp w 4 end bmatrix begin bmatrix x 1 x 2 x 4 x 3 end bmatrix quad 如此第一行與第一列都跟所求得的順序 1 2 4 3一樣 此為circular correlation的形式 Step 3 為了要符合迴旋摺積的定義 矩陣的對角線的項數相同 故必須再將第二列與第四列交換 第二行與第四行交換 矩陣如下 y 1 x 0 y 3 x 0 y 4 x 0 y 2 x 0 w w 3 w 4 w 2 w 2 w w 3 w 4 w 4 w 2 w w 3 w 3 w 4 w 2 w x 1 x 3 x 4 x 2 displaystyle begin bmatrix y 1 x 0 y 3 x 0 y 4 x 0 y 2 x 0 end bmatrix begin bmatrix w amp w 3 amp w 4 amp w 2 w 2 amp w amp w 3 amp w 4 w 4 amp w 2 amp w amp w 3 w 3 amp w 4 amp w 2 amp w end bmatrix begin bmatrix x 1 x 3 x 4 x 2 end bmatrix quad 如此就可把N點DFT用N 1點的DFT來簡化 表示如下 y 1 x 0 y 3 x 0 y 4 x 0 y 2 x 0 I F F T F F T 4 x 1 x 3 x 4 x 2 F F T 4 w 1 w 3 w 4 w 2 displaystyle begin bmatrix y 1 x 0 y 3 x 0 y 4 x 0 y 2 x 0 end bmatrix IFFT left FFT 4 left begin bmatrix x 1 x 3 x 4 x 2 end bmatrix right FFT 4 left begin bmatrix w 1 w 3 w 4 w 2 end bmatrix right right 缺點 编辑雖然此演算法有著可以大幅減少乘法量的優點 但相對於此 也有一些缺點 N不同 那硬體的架構也會跟著改變 Time Cycle較多 因為要做兩次N 1點的DFT 加法量會增加很多 其他運用 编辑任意長度的DFT都可以用長度為2 k displaystyle 2 k 點的DFT來簡化 舉例來說 7點的DFT 先將7點DFT用Winograd簡化成6點DFT 再利用6 2x3 故6點DFT可用2點DFT與3點的DFT來表示 再把3點的DFT用Winograd簡化成2點的DFT 即可把7點的DFT用2 k displaystyle 2 k 點的DFT來簡化 參考資料 编辑Jian Jiun Ding Advanced Digital Signal Processing class note the Department of Electrical Engineering National Taiwan University NTU Taipei Taiwan 2007 S Winograd On computing the discrete Fourier transform Mathematics of Computation vol 32 no 141 pp 179 199 Jan 1978 取自 https zh wikipedia org w index php title 威諾格拉德快速傅立葉變換演算法 amp oldid 49833288, 维基百科,wiki,书籍,书籍,图书馆,