快速傅里葉變換_第1頁
快速傅里葉變換_第2頁
快速傅里葉變換_第3頁
快速傅里葉變換_第4頁
免費預覽已結束，剩余1頁可下載查看

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、作者: 日期:51快速傅里葉變換J；快速傅里葉變換在信號處理等領域有著廣泛的應用。在競賽中，TTF主要用途是求兩個多項式的乘積，即給定兩個階小于 n的多項式A(x)kn 1akXk，B(x)0k1 kbx ，需要求解02n 2kC(x)Ckxk 0A(x)B(x)。注意C(x)的階是不超過2n ,而不是n。樸素算法依次計算C(x)的各個系數Ck，復雜度為0(n2)，而通過FFT可以做到0(n log n)。在FFT中需要應用到一些復數的知識。方程xn1在復數域上一共有 n個不同的解,2 k2 k2k i / n可以表示為cos isin 或是等價的 e(knnD0.n 1)。記e2 i/n為n

2、，則這n個解也可以表示成0n 1。n被稱為單位根。從幾何的角度來看，這n個解對應到的是復平面上單位圓的n等分點。對于一個小于n階的多項式，如果給出它在n個不同位置的取值,則該多項式的系數是唯一確定的。例如若已 知一個小于3階的多項式F(x)滿足F(0)1、F(1)3、F( 1)1，則可以知道 F(x) X2 X 1。如果已知一個小于2n階多項式的系數，則可以在0(n2)的時間內求得它在任意 n個不同位置上的取值。如果已知一個小于n階的多項式在n個不同位置上的取值，則可以通過拉格朗日插值公式(0(n2)的復雜度)或是求解線性方程組 (0(n3)的復雜度)得到它的系數。若n為偶數，則2knkn/2

3、。FFT基本思路是通過計算A(x)在2n個不同位置上的取值以及B( x)同樣在這2n個位置上的取值之后，將這兩組取值按位置相乘，就得到了C(x)在這2n個位置上去取值。最后再將C(x)的系數推出來。為了控制時間復雜度,FFT將這2n個位置選取在02n ，12n 12n2n °算法有兩個難題，一個是如何在 0(nlog n)時間內求得 A(,A( 2n). A( J1)和B( 2n)，B( 2n) . B( 22n 1),還有一個是如何在 0(nl Og n)時間內根據 C( On)，C( 2n).C( 2n 1)求得多項式C(X)的系數。不失一般性，若已知任意小于n階的多項式F(X)的系數f0， f1. fn 1，其中次幕，不足用0補足。則可以通過遞歸法在O(nlog n)時間內求解它在n1位置上的取值。首先，把F(X)按照指數的奇偶性改寫成F(X) Fe(x2)xF0(x2)，其中，Fe(X)fof2X . fn2Xn/21，而 F0(X)fif3X . fn iJ21。若n為偶數，則2k k/2。因此只需求解Fe和Fo在n/2，1/2.篤1這n個位置上的取值即可。這樣問題的規模被縮小了一半，一直遞歸下去即可。1 2n 1若已知 C( °n) , C( 2n).C( 2r)，可以證明 C(X)的系數 Ck

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論