我們要討論的第一種精簡必要乘法數量的算法就是winograd dft算法。winograd dft算法是rader算法（是將dft轉換成循環卷積）與我們在前面實現快速運行fir濾波器時使用過的winograd^[85]短卷積算法的結合。

　　因而長度被限制在質數或質數的冪范圍內。表簡要的給出了算法操作的必要數量。

　　表 帶有實輸入的winograd dft的效果表

　　下面n＝5的示例詳細地說明了構造winograd dft算法的步驟。

　　例 n＝5的winograd dft算法

　　在由^[5]給出的rader算法的一個表達式中，用x[0]代替x[0]的形式如下：

　　如果用winograd算法實現長度為4的循環卷積，只需要5次必不可少的乘法，我們會得到下面的算法：

　　對于實數或虛數輸入序列x[n]，總計算量分別只有5次或10次實數乘法。

　　用矩陣表示winograd dft算法是非常方便的：

　　其中al合并了輸入加法，bl是傅立葉系數的對角矩陣，而cl包括了輸出加法。惟一的缺點就是不能夠很容易地確定短卷積算法的精確步驟，這是因為計算的輸入、輸出加法所在的序列已經在這種矩陣表達式中消失了。

　　這一rader算法和短winograd卷積的組合，也就是winograd dft算法，本算法將在后面與索引映射一道引入winograd fft算法。這種算法是目前已知的fft算法中實數乘法次數最少的fft算法。

　　歡迎轉載，信息來源維庫電子市場網（www.dzsc.com）