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

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

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

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

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

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

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

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

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

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