Remove ads

威諾格拉德快速傅立葉演算法(英語:Winograd FFT)是由美國電腦科學家Shmuel Winograd英語Shmuel Winograd在1978年提出。此演算法可以找出最少的乘法運算量。

當把DFT的公式:

用矩陣方式來表示:

如果n是質數,則可以無視第一行與第一列,把n點的DFT用n-1點的迴旋摺積來取代。

Remove ads

使用方法

使用此演算法,可分為以下幾個步驟,此處以n=5的DFT為例:


Step 1:消去第一行與第一列,式子可以改寫如下:

Step 2:找出列與行的順序:

a)找出一個原根 a,使得.

b)用p[n]表示列與行的順序:

在這例子中,N=5有兩個原根:2與3。取2作為其原根,可得其順序為:1,2,4,3。


故要將此矩陣 的第三列與第四列交換,第三行與第四行交換,把矩陣變成如下:


如此第一行與第一列都跟所求得的順序:1,2,4,3一樣,此為circular correlation的形式。

Step 3:為了要符合迴旋摺積的定義(矩陣的對角線的項數相同),故必須再將第二列與第四列交換,第二行與第四行交換,矩陣如下:

如此就可把N點DFT用N-1點的DFT來簡化,表示如下:


Remove ads

缺點

雖然此演算法有着可以大幅減少乘法量的優點,但相對於此,也有一些缺點:

  • N不同,那硬件的架構也會跟着改變。
  • Time Cycle較多(因為要做兩次N-1點的DFT)。
  • 加法量會增加很多。

其他運用

任意長度的DFT都可以用長度為點的DFT來簡化,舉例來說:

7點的DFT:先將7點DFT用Winograd簡化成6點DFT,再利用6=2x3,故6點DFT可用2點DFT與3點的DFT來表示,再把3點的DFT用Winograd簡化成2點的DFT,即可把7點的DFT用點的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.

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads