從另一個角度理解FFT在多項式乘法中的應(yīng)用

1、-. z從另一個角度理解FFT在多項式乘法中的應(yīng)用negiizhao我一個信號處理算法，怎么用來算多項式乘法了呢？很多同學(xué)學(xué)習(xí)FFT時，看到那一堆符號一堆算式就決定Ctrl+W并去背板。這篇文章或許能幫助那些同學(xué)從另一個角度理解FFT的過程。不要被下文中的*些矩陣嚇到，有些只是為了表達原理方便，在實際中我們并不需要實現(xiàn)這些矩陣，而是實現(xiàn)它的功能如左乘這個矩陣表示什么意思，這時應(yīng)更多關(guān)注它在算法中是用來干什么的。更新后就用黑體小寫字母a表示向量了。雖說看起來可能要更清楚，但那畢竟還是更多地用于手寫。1. 關(guān)于多項式乘法我們使用系數(shù)表示一個n次多項式，即使用序列表示多項式。我們通常稱之為多項式的系

2、數(shù)表示。我們也可以選取n個不同的數(shù)代入多項式得到n個值，用n個有序數(shù)對表示這個多項式，其函數(shù)圖像經(jīng)過了這n個有序數(shù)對所表示的點?？梢宰C明這樣所表示的多項式是唯一的。我們通常稱之為多項式的點值表示。從系數(shù)表示得到點值表示的過程稱為求值，從點值表示得到系數(shù)表示的過程稱為插值。多項式和的系數(shù)表示，我們可以得到這兩個多項式的乘積的系數(shù)表示。為了得到中項的系數(shù)，考慮當j+k=i時，。所以只需對所有滿足j+k=i的j和k，求出并求和。即。我們稱向量c為a和b的離散卷積，記作c=a*b。多項式乘法實質(zhì)上就是在計算離散卷積。直接根據(jù)定義計算離散卷積所需時間為。當n較大時，計算過程將會十分緩慢費時。如果兩個多項

3、式在一樣的n個數(shù)上的點值表示，求這兩個多項式乘積的點值表示是容易的，因為。即我們可以用時間完成這一過程。然而我們通常使用系數(shù)表示法表示多項式，如何快速地完成求值和插值就顯得很重要。現(xiàn)在我們考慮如何選取。2. 單位根和DFT以下的討論均默認在復(fù)數(shù)域、i表示虛數(shù)單位、使用弧度，讀者至少應(yīng)對復(fù)數(shù)、三角函數(shù)、弧度和矩陣有最根本的了解。在引入單位根的概念之前，我們先考慮一下復(fù)數(shù)乘法的幾何意義。復(fù)數(shù)在復(fù)平面上表示的點P到原點O的距離r稱為復(fù)數(shù)的模，*軸到OP的夾角稱為輻角。我們可以把復(fù)數(shù)z表示為。對于復(fù)數(shù)，我們可以得出，證明如下?，F(xiàn)在我們引入單位根的概念。n次單位根是指滿足方程的數(shù)，因為n次方程有n個解，

4、所以n次單位根共有n個。根據(jù)復(fù)數(shù)乘法的幾何意義，不難想到n次單位根的模為1，輻角的n倍為0。則n次單位根可以表示為根據(jù)歐拉公式，n次單位根也可以表示為為了方便，我們通常會把上式的放在分子上寫成，這就是那一堆符號的來歷。為了防止一堆符號，我們記，則n次單位根可以表示為。至于這里為什么出現(xiàn)了負號，后面會提到，其實只是信號處理中的習(xí)慣罷了。下列圖是5次單位根。對于單位根，顯然有兩個性質(zhì)和2k2n=kn。如果不理解可以看下面的證明現(xiàn)在我們引入DFT的概念。我們可以用矩陣乘法表示對求值的過程。則假設(shè)，則系數(shù)向量a,b,c滿足表示對應(yīng)元素相乘。不難想到插值過程可以表示為。令，則矩陣現(xiàn)在為為了進展插值，我們

5、需要矩陣的逆元其中稱為傅里葉矩陣。為什么要用這個矩陣？因為它有一些特別的性質(zhì)，下一小節(jié)將會詳細表達?，F(xiàn)在，我們得到了系數(shù)向量a和點值向量y之間的關(guān)系,。我們把a稱為y的離散傅里葉變換(discrete Fourier transform, DFT)，y稱為a的離散傅里葉逆變換(inverse discrete Fourier transform, IDFT)。在信號處理中這兩個變換有很重要的意義。而在多項式乘法應(yīng)用中，我們可以通過計算得到c。直接計算矩陣乘法的時間復(fù)雜度仍是。接下來我們考慮如何快速地完成這一矩陣乘法。下面是一些題外話，如果承受不能可以忽略前面直接看結(jié)論或許有人也發(fā)現(xiàn)了，我似乎把

6、DFT和IDFT搞反了？事實上并不是。DFT最早的應(yīng)用信號處理，就是對時域信號進展n次采樣，用DFT轉(zhuǎn)換成頻域信號以方便過濾噪聲。則是不是其他資料寫錯了？也不是?？赐赀@一段就會知道為什么了。我們也可以不用矩陣表示DFT和IDFT，但可能理解起來有點困難，特別是后面關(guān)于如何加速這一計算過程。當然如果您比擬強就當我沒說。不過dalao對我這辣雞blog也沒什么興趣吧？可以發(fā)現(xiàn)，兩個變換過程的區(qū)別在于系數(shù)這里分別是1和和指數(shù)或弧度的符號。事實上，這僅僅是個習(xí)慣約定，實際應(yīng)用中并不都是這樣處理，而是考慮如何表達比擬方便。DFT和IDFT本質(zhì)上是沒有區(qū)別的，對兩者的要求只是系數(shù)的積為，符號不同。而在多項

7、式乘法應(yīng)用中，為了保證求值的結(jié)果是多項式的一個點值表示，求值過程中不能乘，于是插值過程必須乘。過程對于指數(shù)的符號是沒有要求的，所以說，即使把符號對調(diào)，你的多項式乘法程序也不會出錯。為了表述方便，在多項式乘法應(yīng)用中，一般稱求值過程為DFT，插值過程為IDFT。事實上還可以僅計算一次得到兩個實序列的DFT或IDFT，具體方法網(wǎng)上也有，我就不在這里廢話了。3. 加速計算DFT的過程FFT算法再次提醒，不要被下文中的*些矩陣嚇到，對于這些矩陣只需關(guān)注它在算法中是用來干什么的。信號處理領(lǐng)域的一個變革是1965年由 J. W. Cooley 和 J. W. Tukey 引入了一種十分高效的計算DFT的方法

8、。事實上，1965年 Cooley 和 Tukey 的論文是對1805年高斯提出的方法的重新發(fā)現(xiàn)。Cooley 和 Tukey 的方法稱為快速傅里葉變換(fast Fourier transform, FFT)，這是一種計算DFT的高效算法。它利用了傅里葉矩陣的特殊性質(zhì)。為了方便，我們設(shè)，即。下面以n=8為例進展說明。我們將的各列重新排列，使得它的奇數(shù)列全都在偶數(shù)列的前面。這個重新排列等價于右乘置換矩陣如果令,則對進展分塊，用單位根的性質(zhì)可得又根據(jù)單位根的另一性質(zhì)，可知矩陣的塊和塊均等于令左乘相當于把第k行乘以。塊和塊可以分別表示為和，于是現(xiàn)在可以通過分塊乘法實現(xiàn)計算DFT如果令,，則我們得到

9、?？梢钥闯鲇嬎愫喕癁閮蓚€n=4的傅里葉變換。以上過程不難推廣到n等于任意偶數(shù)的情況。對于計算多項式乘法，我們通常把高次項系數(shù)補0使。這樣求DFT的時間復(fù)雜度。這比直接計算要快多了。注意如果是進展插值，不要忘記乘以系數(shù)，即。至于如何求？前面說過，DFT和IDFT的差異僅僅在于系數(shù)和指數(shù)的符號。求IDFT只需把求DFT過程中的對角矩陣全部換成，最后不乘即可。具體來說，而。左乘相當于把第k行乘以，左乘相當于把第k行乘以?？偨Y(jié)一下FFT求的過程1. 重排。令。即下標為奇數(shù)的元素全部移動到下標為偶數(shù)的元素前面。2. 遞歸。將分成相等兩段和，求出和。3. 合并。令，?，F(xiàn)在計算多項式乘法可以用3次FFT完成，即嗯接下來應(yīng)該是如何遞歸