基2-FFT簡記

快速傅里葉變換（Fast Fourier Transform牲芋，F(xiàn)FT）是一種可在 $O(nlogn)$ 時(shí)間內(nèi)完成的離散傅里葉變換（Discrete Fourier transform撩笆，DFT）算法。

復(fù)數(shù)單位根 $w^k_n$

橫軸為實(shí)軸缸浦，縱軸為虛軸的復(fù)平面上夕冲， $e^{i\theta }=cos\theta +i\cdot sin\theta$

(將復(fù)平面單位圓均分成n份，以單位圓與實(shí)軸正半軸的交點(diǎn)一個(gè)等分點(diǎn)裂逐，以原點(diǎn)為起點(diǎn)歹鱼，n個(gè)等分點(diǎn)為終點(diǎn)，做n個(gè)單位向量卜高，其中幅角為正且最小的向量被稱為n次單位向量弥姻，記為 $w^1_n$ )

易知 $w^n_n=w_n^0=1$

所以， $w^k_n= e^{k\cdot \frac{2\pi}{n} i }$

（復(fù)平面中復(fù)數(shù)加法滿足平行四邊形法則掺涛，乘法滿足幅角相加庭敦，模長相乘）根據(jù)這性質(zhì)易幾何證明以下兩性質(zhì)

復(fù)數(shù)單位根性質(zhì)：

1、折半引理： $w^{2k}_{2n}=w^k_n$ ? $\Rightarrow$ ? $w^{mk}_{mn}=w^k_n$

2薪缆、消去引理： $w_n^{k+\frac{n}{2} }=-w^k_n$

離散傅里葉變換的復(fù)雜度為 $O(n^2)$

快速傅里葉變換的復(fù)雜度為 $O(NlogN)$

$N$ 點(diǎn)FFT階段數(shù)為 $logN$ 而每一階段的復(fù)雜度為 $N$ 秧廉，故復(fù)雜度為 $O(NlogN)$

以8點(diǎn)FFT為例，綠色的列表示一個(gè)階段拣帽，每個(gè)空心圈表示一次乘加疼电，一列共N個(gè)

先看離散傅里葉變換（DFT）表達(dá)式? ( $x_n$ 時(shí)域， $x_k$ 頻域)：? ? ? ? ?

$x_k = \sum_{n=0}^{N-1}x_n\cdot e^{-i \frac{2\pi kn}{N} }$ ,? k=0,1,...N-1

$e^{-i \frac{2\pi kn}{N} } = w^{nk}_N$

通過上述DFT的表達(dá)式减拭，其可以用復(fù)數(shù)單位根表示成：

$x_k=\sum_{n=0}^{N-1}x_n\cdot w_N^{nk}$ ? ? ? ? ? ? ? ? , $k=0,1,2,...,N-1$

? ? ? $=\sum_{n \in? even} x_n w_N^{nk}+\sum_{n \in odd} x_n w_N^{nk}$

? ? ? $=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_N^{2rk}+\sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_N^{(2r+1)k}$

? ? ? ? $=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_N^{2rk}+w_N^{k} \sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_N^{2rk}$

? ? ? ? $=\sum_{r=0}^{\frac{N}{2} -1} x_{2r} w_{\frac{N}{2}} ^{rk}+w_N^{k} \sum_{r=0}^{\frac{N}{2} -1} x_{2r+1} w_{\frac{N}{2} }^{rk}$

? ? ? ? $=G_k +w^k_NH_k$

在這邊我們要注意的是蔽豺，我們所替換的G[k]與H[k]具有周期性：

此性質(zhì)根據(jù)單位根的幾何意義得證

上述的推導(dǎo)可以劃成下面的圖，以8點(diǎn)DFT為例(N=8峡谊，左邊一列為時(shí)域茫虽，右邊一列為頻域）：

劃紅框處所示的 $\frac{N}{2}$ 點(diǎn)DFT架構(gòu)如下圖所示：

劃紅框處所示的 $\frac{N}{4}$ 點(diǎn)DFT架構(gòu)如下圖所示：

綜上刊苍，下圖是一個(gè)8點(diǎn)DIT FFT的完整架構(gòu)圖：

圖中應(yīng)用性質(zhì)，例如左邊的

庫利和圖基的FFT算法的最基本運(yùn)算為蝶形運(yùn)算濒析，每個(gè)蝶形運(yùn)算包括兩個(gè)輸入點(diǎn)正什，因而也稱為基-2算法。?

參考：庫利－圖基快速傅里葉變換算法

FFT還能用來加速多項(xiàng)式乘法号杏。樸素計(jì)算兩個(gè)N-1次（N項(xiàng)）多項(xiàng)式復(fù)雜度為 $O(N^2)$

多項(xiàng)式系數(shù)表達(dá)法

多項(xiàng)式的點(diǎn)值表達(dá)法

設(shè) $F(x) = f(x)\ast g(x)$

點(diǎn)值表達(dá)法的多項(xiàng)式乘積十分方便婴氮，復(fù)雜度為

這里有個(gè)點(diǎn)就是點(diǎn)值表示法的乘積，按理說兩個(gè)n次的多項(xiàng)式乘積的最高次為2n盾致，而點(diǎn)值表示法就像是解方程主经，2n次方程式需要2n個(gè)點(diǎn)值點(diǎn)才能唯一確定，所以我理解的是需要兩次上圖的點(diǎn)值表示法乘積才能確定結(jié)果庭惜。

而是用DFT和IDFT可以分別轉(zhuǎn)換系數(shù)表達(dá)法到點(diǎn)值表達(dá)法和點(diǎn)值表達(dá)法到系數(shù)表達(dá)法罩驻，F(xiàn)FT可以加速這兩個(gè)轉(zhuǎn)換過程。

大概過程是护赊，先將兩個(gè)系數(shù)表示法的多項(xiàng)式分別轉(zhuǎn)化為點(diǎn)值表達(dá)式惠遏，再進(jìn)行點(diǎn)值表達(dá)法的多項(xiàng)式乘積運(yùn)算，再將結(jié)果轉(zhuǎn)換回系數(shù)表達(dá)法骏啰。

需要注意的是节吮，在求兩個(gè)次數(shù)分別為 $n_1-1$ 和 $n_2-1$ 的多項(xiàng)式的乘積時(shí)，需要分別求出在至少 $n_1+n_2-1$ 個(gè)點(diǎn)處的值判耕，這樣才能保證相乘后唯一確定一個(gè) $n_1+n_2-2$ 次多項(xiàng)式透绩。

假設(shè) $C(x) = A(x)\ast B(x)$ ,A（x）、B(x)的點(diǎn)值表達(dá)式均有N個(gè)點(diǎn)壁熄，而他們的乘積C（x）因?yàn)榇螖?shù)為 $2N$ 所以需要2N個(gè)點(diǎn)值點(diǎn)帚豪，那么怎么出現(xiàn)2N個(gè)點(diǎn)呢，多選一些點(diǎn)即可请毛。所以在計(jì)算N次多項(xiàng)式的點(diǎn)值表達(dá)法時(shí)要取2N個(gè)點(diǎn)值點(diǎn)志鞍，我的理解是這2N個(gè)點(diǎn)在復(fù)平面上直接取 $w_{2N}^k$ 瞭亮，分成兩組N個(gè)點(diǎn)（保證了兩組中每個(gè)點(diǎn)均不同）方仿，對(duì)于一個(gè)系數(shù)表達(dá)式進(jìn)行兩次N點(diǎn)FFT，最終一個(gè)N次系數(shù)表達(dá)式得到2N個(gè)點(diǎn)值點(diǎn)统翩。這一步通過4次FFT完成了兩個(gè)待乘系數(shù)表達(dá)式到點(diǎn)值表達(dá)式的轉(zhuǎn)換仙蚜。然后進(jìn)行后續(xù)計(jì)算。

至于為什么將2N個(gè)點(diǎn)要分成兩組N計(jì)算厂汗，是因?yàn)橄禂?shù)表達(dá)式有N個(gè)點(diǎn)委粉，所以通過FFT一次只能計(jì)算N個(gè)點(diǎn)值點(diǎn)，需要算兩次完成一個(gè)表達(dá)式的轉(zhuǎn)換娶桦，因?yàn)樾枰愕氖莾蓚€(gè)N-1階表達(dá)式的乘積贾节，需要轉(zhuǎn)換兩個(gè)式子汁汗，所以這一步共需4次FFT。而后面的點(diǎn)值表示法再轉(zhuǎn)回稀疏表示法可以直接一次2N點(diǎn)FFT搞定栗涂。個(gè)人理解知牌，有待考證

關(guān)于FFT加速多項(xiàng)式乘法具體見下文：

快速傅里葉變換FFT

FFT(快速傅里葉變換)0基礎(chǔ)詳解