复杂度

离散傅立叶变换的复杂度为O(n2){\displaystyle {\mathcal {O}}(n^{2})}（可参考大O符号）

快速傅立叶变换的复杂度为O(Nlog⁡ ⁡ -->N){\displaystyle {\mathcal {O}}(N\log N)}，分析可见下方架构图部分，级数为log⁡ ⁡ -->N{\displaystyle \log N}而每一级的复杂度为N{\displaystyle N}，故复杂度为O(Nlog⁡ ⁡ -->N){\displaystyle {\mathcal {O}}(N\log N)}

时域/频域抽取法

在FFT算法中，针对输入做不同方式的分组会造成输出顺序上的不同。如果我们使用时域抽取（Decimation-in-time），那么输入的顺序将会是位元反转排列（bit-reversed order），输出将会依序排列。但若我们采取的是频域抽取（Decimation-in-frequency），那么输出与输出顺序的情况将会完全相反，变为依序排列的输入与位元反转排列的输出。

时域抽取法

我们可以将DFT公式中的项目在时域上重新分组，这样就叫做时域抽取（Decimation-in-time），在这里e− − -->j(2π π -->nkN){\displaystyle e^{-j(2\pi {\frac {nk}{N}})}}将会被代换为旋转因子（twiddle factor）WNnk{\displaystyle W_{N}^{nk}}。

X[k]=∑ ∑ -->n=0N− − -->1x[n]e− − -->j(2π π -->nkN)k=0,1,… … -->,N− − -->1{\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]e^{-j(2\pi {\frac {nk}{N}})}\qquad k=0,1,\ldots ,N-1}

=∑ ∑ -->n evenx[n]WNnk+∑ ∑ -->n oddx[n]WNnk{\displaystyle =\sum _{n\ even}x[n]W_{N}^{nk}+\sum _{n\ odd}x[n]W_{N}^{nk}}

=∑ ∑ -->r=0(N/2)− − -->1x[2r]WN2rk+∑ ∑ -->r=0(N/2)− − -->1x[2r+1]WN(2r+1)k{\displaystyle =\sum _{r=0}^{(N/2)-1}x[2r]W_{N}^{2rk}+\sum _{r=0}^{(N/2)-1}x[2r+1]W_{N}^{(2r+1)k}}

=∑ ∑ -->r=0(N/2)− − -->1x[2r]WN2rk+WNk∑ ∑ -->r=0(N/2)− − -->1x[2r+1]WN2rk{\displaystyle =\sum _{r=0}^{(N/2)-1}x[2r]W_{N}^{2rk}+W_{N}^{k}\sum _{r=0}^{(N/2)-1}x[2r+1]W_{N}^{2rk}}

=∑ ∑ -->r=0(N/2)− − -->1x[2r]WN/2rk+WNk∑ ∑ -->r=0(N/2)− − -->1x[2r+1]WN/2rk{\displaystyle =\sum _{r=0}^{(N/2)-1}x[2r]W_{N/2}^{rk}+W_{N}^{k}\sum _{r=0}^{(N/2)-1}x[2r+1]W_{N/2}^{rk}}

=G[k]+WNkH[k]{\displaystyle =G[k]+W_{N}^{k}H[k]}

在这边我们要注意的是，我们所替换的G[k]与H[k]具有周期性：

{G[k+N2]=G[k]H[k+N2]=H[k]{\displaystyle {\begin{cases}G[k+{\frac {N}{2}}]=G[k]\\H[k+{\frac {N}{2}}]=H[k]\end{cases}}}

上述的推导可以划成下面的图：

划红框处所示的N2{\displaystyle {\frac {N}{2}}}点DFT架构如下图所示：

划红框处所示的N4{\displaystyle {\frac {N}{4}}}点DFT架构如下图所示：

下图是一个8点DIT FFT的完整架构图。

频域抽取法

我们可以将DFT公式中的项目在频域上重新分组，这样就叫做频域抽取（Decimation-in-frquency）。

首先先观察在频域上偶数项的部分：

X[2r]=∑ ∑ -->n=0N− − -->1x[n]WNn(2r) r=0,1,⋯ ⋯ -->,N2− − -->1{\displaystyle X[2r]=\sum _{n=0}^{N-1}x[n]W_{N}^{n(2r)}\ r=0,1,\cdots ,{\frac {N}{2}}-1}

=∑ ∑ -->n=0N2− − -->1x[n]WN2nr+∑ ∑ -->n=N2N− − -->1x[n]WN2nr{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2nr}+\sum _{n={\frac {N}{2}}}^{N-1}x[n]W_{N}^{2nr}}

=∑ ∑ -->n=0N2− − -->1x[n]WN2nr+∑ ∑ -->n=0N2− − -->1x[n+N2]WN2r[n+N2]{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2nr}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{2r[n+{\frac {N}{2}}]}}

∵ ∵ -->WN2r[n+N2]=WN2rnWNrN=WN2rn{\displaystyle {\color {Gray}\because W_{N}^{2r[n+{\frac {N}{2}}]}=W_{N}^{2rn}W_{N}^{rN}=W_{N}^{2rn}}}

=∑ ∑ -->n=0N2− − -->1x[n]WN2rn+∑ ∑ -->n=0N2− − -->1x[n+N2]WN2rn{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2rn}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{2rn}}

=∑ ∑ -->n=0N2− − -->1(x[n]+x[n+N2])WN2rn{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]+x[n+{\frac {N}{2}}])W_{\frac {N}{2}}^{rn}}

=∑ ∑ -->n=0N2− − -->1g[n]WN2rn{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}g[n]W_{\frac {N}{2}}^{rn}}

再观察在频域上奇数项的部分：

X[2r+1]=∑ ∑ -->n=0N− − -->1x[n]WNn(2r+1) r=0,1,⋯ ⋯ -->,N2− − -->1{\displaystyle X[2r+1]=\sum _{n=0}^{N-1}x[n]W_{N}^{n(2r+1)}\ r=0,1,\cdots ,{\frac {N}{2}}-1}

=∑ ∑ -->n=0N2− − -->1x[n]WNn(2r+1)+∑ ∑ -->n=N2N− − -->1x[n]WNn(2r+1){\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum _{n={\frac {N}{2}}}^{N-1}x[n]W_{N}^{n(2r+1)}}

=∑ ∑ -->n=0N2− − -->1x[n]WNn(2r+1)+∑ ∑ -->n=0N2− − -->1x[n+N2]WN(2r+1)[n+N2]{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{(2r+1)[n+{\frac {N}{2}}]}}

∵ ∵ -->WN(2r+1)[n+N2]=WN(2r+1)nWN(2r+1)N2=− − -->WN(2r+1)n{\displaystyle {\color {Gray}\because W_{N}^{(2r+1)[n+{\frac {N}{2}}]}=W_{N}^{(2r+1)n}W_{N}^{(2r+1){\frac {N}{2}}}=-W_{N}^{(2r+1)n}}}

=∑ ∑ -->n=0N2− − -->1x[n]WN(2r+1)n− − -->∑ ∑ -->n=0N2− − -->1x[n+N2]WN(2r+1)n{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{(2r+1)n}-\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{(2r+1)n}}

=∑ ∑ -->n=0N2− − -->1(x[n]− − -->x[n+N2])WNn(2r+1){\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]-x[n+{\frac {N}{2}}])W_{N}^{n(2r+1)}}

=∑ ∑ -->n=0N2− − -->1(x[n]− − -->x[n+N2])WNnWN2nr{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]-x[n+{\frac {N}{2}}])W_{N}^{n}W_{\frac {N}{2}}^{nr}}

=∑ ∑ -->n=0N2− − -->1(h[n]WNn)WN2rn{\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(h[n]W_{N}^{n})W_{\frac {N}{2}}^{rn}}

上述的推导可以画成下面的图：

更进一步的拆解N2{\displaystyle {\frac {N}{2}}}-point DFT的架构

下图为8点FFT下N4{\displaystyle {\frac {N}{4}}}-point DFT的架构

总结上述架构，完整的8点DIF FFT架构图为

单一基底

利用库利－图基算法进行离散傅立叶拆解时，能够依需求而以2, 4, 8…等2的幂次方为单位进行拆解，不同的拆解方法会产生不同层数快速傅里叶变换的架构，基底越大则层数越少，复数乘法器也越少，但是每级的蝴蝶形架构则会越复杂，因此常见的架构为2基底、4基底与8基底这三种设计。

2基底

2基底-快速傅立叶算法（Radix-2 FFT）是最广为人知的一种库利－图基快速傅立叶算法分支。此方法不断地将N点的FFT拆解成两个"N/2"点的FFT，利用旋转因子Wnk,WN2{\displaystyle W^{nk},W^{\frac {N}{2}}}的对称性借此来降低DFT的计算复杂度，达到加速的功效。

而其实前述有关时域抽取或是频域抽取的方法介绍，即为2基底的快速傅立叶转换法。以下展示其他种2基底快速傅立叶算法的连线方法，此种不规则的连线方法可以让输出与输入都为循序排列，但是连线的复杂度却大大的增加。

4基底

4基底快速傅立叶变换算法则是承接2基底的概念，在此里用时域抽取的技巧，将原本的DFT公式拆解为四个一组的形式：

X[k]=∑ ∑ -->n=0N− − -->1x[n]e− − -->j(2π π -->nkN)k=0,1,… … -->,N− − -->1{\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]e^{-j(2\pi {\frac {nk}{N}})}\qquad k=0,1,\ldots ,N-1}

=∑ ∑ -->n=0N4− − -->1x[4n+0]WN(4n+0)k+∑ ∑ -->n=0N4− − -->1x[4n+1]WN(4n+1)k{\displaystyle =\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+0]W_{N}^{(4n+0)k}+\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+1]W_{N}^{(4n+1)k}}

+∑ ∑ -->n=0N4− − -->1x[4n+2]WN(4n+2)k+∑ ∑ -->n=0N4− − -->1x[4n+3]WN(4n+3)k{\displaystyle +\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+2]W_{N}^{(4n+2)k}+\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+3]W_{N}^{(4n+3)k}}

=WN0∑ ∑ -->n=0N4− − -->1x[4n+0]WN4nk+WN1k∑ ∑ -->n=0N4− − -->1x[4n+1]WN4nk{\displaystyle =W_{N}^{0}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+0]W_{\frac {N}{4}}^{nk}+W_{N}^{1k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+1]W_{\frac {N}{4}}^{nk}}

+WN2k∑ ∑ -->n=0N4− − -->1x[4n+2]WN4nk+WN3k∑ ∑ -->n=0N4− − -->1x[4n+3]WN4nk{\displaystyle +W_{N}^{2k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+2]W_{\frac {N}{4}}^{nk}+W_{N}^{3k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+3]W_{\frac {N}{4}}^{nk}}

WN0F0(k)+WNkF1(k)+WN2kF2(k)+WN3kF3(k){\displaystyle W_{N}^{0}F_{0}(k)+W_{N}^{k}F_{1}(k)+W_{N}^{2k}F_{2}(k)+W_{N}^{3k}F_{3}(k)}

在这里再利用Wnk+N4=− − -->Wnk+3N4=− − -->jWnk{\displaystyle W^{nk+{\frac {N}{4}}}=-W^{nk+{\frac {3N}{4}}}=-jW^{nk}}的特性来进行与2基数FFT类似的化减方法，以降低算法复杂度。

8基底

在库利－图基算法里，使用的基底（radix）越大，复数的乘法与内存的存取就越少，所带来的好处不言而喻。但是随之而来的就是实数的乘法与实数的加法也会增加，尤其计算单元的设计也就越复杂，对于可应用FFT之点数限制也就越严格。在表中我们可以看到在不同基底下所需的计算成本。

在DFT的公式中，我们重新定义x=[x(0),x(1),…,x(N-1)], X=[X(0),X(1),…,X(N-1)]，则DFT可重写为X=FN‧x。FN是一个N×N的DFT矩阵，其元素定义为[FN]ij=WNij(i,j ∈ [0,N-1])，当N=8时，我们可以得到以下的F8矩阵并且进一步将其拆解。

在拆解成三个矩阵相乘之后，我们可以将复数运算的数量从56个降至24个复数的加法。底下是8基底的的SFG。要注意的是所有的输出与输入都是复数的形式，而输出与输入的排序也并非规律排列，此种排列方式是为了要达到接线的最佳化。

混合基底

2/8基底

在2/8基底的算法中，我们可以看到我们对于偶数项的输出会使用2基底的分解法，对于奇数项的输出采用8基底的分解法。这个做法充分利用了2基底与4基底拥有最少乘法数与加法数的特性。当使用了2基底的分解法后，偶数项的输出如下所示。

C2k=∑ ∑ -->n=0N2− − -->1(x2n+xN2+n)W2nk{\displaystyle C_{2k}=\sum _{n=0}^{{\frac {N}{2}}-1}(x_{2n}+x_{{\frac {N}{2}}+n})W^{2nk}}

奇数项的输出则交由8基底分解来处理，如下四式所述。

C8k+1=∑ ∑ -->n=0N8− − -->1{[(xn− − -->xn+N2)− − -->j(xn+N4− − -->xn+3N4)]+WN8[(xn+N8− − -->xn+5N8)− − -->j(xn+3N8− − -->xn+7N8)]}W8nkWn{\displaystyle C_{8k+1}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})-j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]+W^{\frac {N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})-j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{n}}

C8k+5=∑ ∑ -->n=0N8− − -->1{[(xn− − -->xn+N2)− − -->j(xn+N4− − -->xn+3N4)]− − -->WN8[(xn+N8− − -->xn+5N8)− − -->j(xn+3N8− − -->xn+7N8)]}W8nkW5n{\displaystyle C_{8k+5}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})-j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]-W^{\frac {N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})-j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{5n}}

C8k+3=∑ ∑ -->n=0N8− − -->1{[(xn− − -->xn+N2)+j(xn+N4− − -->xn+3N4)]+W3N8[(xn+N8− − -->xn+5N8)+j(xn+3N8− − -->xn+7N8)]}W8nkW3n{\displaystyle C_{8k+3}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})+j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]+W^{\frac {3N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})+j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{3n}}

C8k+7=∑ ∑ -->n=0N8− − -->1{[(xn− − -->xn+N2)+j(xn+N4− − -->xn+3N4)]− − -->W3N8[(xn+N8− − -->xn+5N8)+j(xn+3N8− − -->xn+7N8)]}W8nkW7n{\displaystyle C_{8k+7}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})+j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]-W^{\frac {3N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})+j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{7n}}

以上式子就是2/8基底的FFT快速算法。在架构图上可化为L型的蝴蝶运算架构，如下图所示。

而下图表示的是一个64点的FFT使用2/8基底的架构图。虽然2/8基底的算法缩减了WN8,W3N8{\displaystyle W^{\frac {N}{8}},W^{\frac {3N}{8}}}的乘法量，但是这种算法最大的缺点是跟其他固定基底或是混合基底比较起来，他的架构较为不规则。所以在硬件上比4基底或是2基底更难实现。

2/4/8基底

为了改进Radix 2/8在架构上的不规则性，我们在这里做了一些修改，如下图4.。此修改可让架构更加规则，且所使用的加法器与乘法器数量更加减少，如下表所示。

在这里我们最小的运算单元称为PE（Process Element）,PE内部包含了2/8基底、2/4基底、2基底的运算，简化过的信号处理流程与蝴蝶型架构图可见下图

2基底

基底的选择越大会造成蝴蝶形架构更加复杂，控制电路也会复杂化。因此Shousheng He和Mats Torkelson在1996提出了一个2^2基底的FFT算法，利用旋转因子的特性：WN4=− − -->j{\displaystyle W_{\frac {N}{4}}=-j}。而–j的乘法基本上只需要将被乘数的实部虚部对调，然后将虚部加上负号即可，这样的负数乘法被定义为"简单乘法"，因此可以用很简单的硬件架构来实现。利用上面的特性，2基底FFT能用串接的方式将旋转因子以4为单位对DFT公式进行拆解，将蝴蝶形架构层数降到log4N，大幅减少复数乘法器的用量，而同时却维持了2基底蝴蝶形架构的简单性，在效能上获得改进。2基底DIF FFT算法的拆解方法如下列公式所述：

N点DFT公式： X(k)=∑ ∑ -->n=0N− − -->1x(n)WNnk,0≦ ≦ -->k<N{\displaystyle X(k)=\sum _{n=0}^{N-1}x(n)W_{N}^{nk},0\leqq k

利用线性映射将n与k映射到三个维度上面

{n=Nk=N{\displaystyle {\begin{cases}n=_{N}\\k=_{N}\end{cases}}}

然后套用Common Factor Algorithm（CFA）

X(k1+2k2+4k3)=∑ ∑ -->n3=0N4− − -->1∑ ∑ -->n2=01∑ ∑ -->n1=01x(N2n1+N4n2+n3)WN(N2n1+N4n2+n3)(k1+2k2+4k3){\displaystyle X(k_{1}+2k_{2}+4k_{3})=\sum _{n_{3}=0}^{{\frac {N}{4}}-1}\sum _{n_{2}=0}^{1}\sum _{n_{1}=0}^{1}x({\frac {N}{2}}n_{1}+{\frac {N}{4}}n_{2}+n_{3})W_{N}^{({\frac {N}{2}}n_{1}+{\frac {N}{4}}n_{2}+n_{3})(k_{1}+2k_{2}+4k_{3})}}

=∑ ∑ -->n3=0N4− − -->1∑ ∑ -->n2=01{BN2k1WN(N4n2+n3)k1}WN(N4n2+n3)(2k2+4k3){\displaystyle =\sum _{n_{3}=0}^{{\frac {N}{4}}-1}\sum _{n_{2}=0}^{1}{\begin{Bmatrix}B_{\frac {N}{2}}^{k_{1}}W_{N}^{({\frac {N}{4}}n_{2}+n_{3})k_{1}}\end{Bmatrix}}W_{N}^{({\frac {N}{4}}n_{2}+n_{3})(2k_{2}+4k_{3})}}

而蝴蝶型架构会变成以下形式

BN2k1=x(N4n2+n3)+(− − -->1)k1x(N4n2+n3+N2){\displaystyle B_{\frac {N}{2}}^{k_{1}}=x({\frac {N}{4}}n_{2}+n_{3})+(-1)^{k_{1}}x({\frac {N}{4}}n_{2}+n_{3}+{\frac {N}{2}})}

利用旋转因子WN4=− − -->j{\displaystyle W_{\frac {N}{4}}=-j}的特性，可以观察出

WN(N4n2+n3)(k1+2k2+4k3)=WNNn2n3WNN4n2(k1+2k2)WNn3(k1+2k2)WN4n3k3{\displaystyle W_{N}^{({\frac {N}{4}}n_{2}+n_{3})(k_{1}+2k_{2}+4k_{3})}=W_{N}^{Nn_{2}n_{3}}W_{N}^{{\frac {N}{4}}n_{2}(k_{1}+2k_{2})}W_{N}^{n_{3}(k_{1}+2k_{2})}W_{N}^{4n_{3}k_{3}}}

=(− − -->j)n2(k1+2k2)WNn3(k1+2k2)WN4n3k3{\displaystyle =(-j)^{n_{2}(k_{1}+2k_{2})}W_{N}^{n_{3}(k_{1}+2k_{2})}W_{N}^{4n_{3}k_{3}}}

再将此公式带入原式中可以得到

X(k1+2k2+4k3)=∑ ∑ -->n3=0N4− − -->1[H(k1,k2,n3)WNn3(k1+2k2)]WN4n3k3{\displaystyle X(k_{1}+2k_{2}+4k_{3})=\sum _{n_{3}=0}^{{\frac {N}{4}}-1}[H(k_{1},k_{2},n_{3})W_{N}^{n_{3}(k_{1}+2k_{2})}]W_{N}^{4n_{3}k_{3}}}

H(k1,k2,n3)=BF2I[x(n3)+(− − -->1)k1(n3+N2)]⏞ ⏞ -->+(− − -->j)k1+2k2BF2I[x(n3+N4)+(− − -->1)k1(n3+3N4)]⏞ ⏞ -->⏟ ⏟ -->BF2II{\displaystyle H(k_{1},k_{2},n_{3})={\begin{matrix}\underbrace {{\begin{matrix}BF2I\\\overbrace {[x(n_{3})+(-1)^{k_{1}}(n_{3}+{\frac {N}{2}})]} \end{matrix}}{\begin{matrix}\\\\+(-j)^{k_{1}+2k_{2}}\end{matrix}}{\begin{matrix}BF2I\\\overbrace {[x(n_{3}+{\frac {N}{4}})+(-1)^{k_{1}}(n_{3}+{\frac {3N}{4}})]} \end{matrix}}} \\BF2II\end{matrix}}}

如上述公式所示，原本的DFT公式会被拆解成多个H(k1,k2,n3){\displaystyle H(k_{1},k_{2},n_{3})}，而H(k1,k2,n3){\displaystyle H(k_{1},k_{2},n_{3})}又可分为BF2I与BF2II两个阶层，分别会对应到之后所介绍的两种硬件架构。

一个16点的DFT公式经过一次上面所述之拆解之后可得下面的FFT架构

可以看出上图的架构保留了2基底的简单架构，然而复数乘法却降到每两级才出现一次，也就是log4N{\displaystyle log_{4}N}次。而BF2I以及BF2II所对应的硬件架构下图：

其中BF2II硬件单元中左下角的交叉电路就是用来处理-j的乘法。

一个256点的FFT架构可以由下面的硬件来实现：

其中图下方的为一7位元宽的计数器，而此架构的控制电路相当单纯，只要将计数器的各个位元分别接上BF2I与BF2II单元即可。

下表将2基底、4基底与2基底算法做一比较，可以发现2基底算法所需要的乘法气数量为2基底的一半，加法弃用量是4基底的一半，并维持一样的内存用量和控制电路的简单性。

2基底

如上所述，2算法是将旋转因子WN4=− − -->j{\displaystyle W^{\frac {N}{4}}=-j}视为一个简单乘法，进而由公式以及硬件上的化简获得硬件需求上的改进。而借由相同的概念，Shousheng He和Mats Torkelson进一步将旋转因子WN8=22(1− − -->j){\displaystyle W^{\frac {N}{8}}={\frac {\sqrt {2}}{2}}(1-j)}的乘法化简成一个简单乘法，而化简的方法将会在下面讲解。

22{\displaystyle {\frac {\sqrt {2}}{2}}}乘法化简

在2基数FFT算法中的基本概念是利用旋转因子Wnk,WN2{\displaystyle W^{nk},W^{\frac {N}{2}}}的对称性，4基数算法则是利用 Wnk+N4=− − -->Wnk+3N4=− − -->jWnk{\displaystyle W^{nk+{\frac {N}{4}}}=-W^{nk+{\frac {3N}{4}}}=-jW^{nk}} 的特性。但是我们会发现在这些旋转因子的对称特性中─

WN8=− − -->W5N8=22(1− − -->j),W3N8=− − -->W7N8=− − -->22(1+j){\displaystyle W^{\frac {N}{8}}=-W^{\frac {5N}{8}}={\frac {\sqrt {2}}{2}}(1-j),W^{\frac {3N}{8}}=-W^{\frac {7N}{8}}=-{\frac {\sqrt {2}}{2}}(1+j)}

─并没有被利用到。主要是因为22(1− − -->j){\displaystyle {\frac {\sqrt {2}}{2}}(1-j)}的乘法运算会让整个FFT变得复杂，但是如果借由近似的方法，我们便可以将此一运算化简为12个加法。

22=0.70710678=2− − -->1+2− − -->3+2− − -->4+2− − -->6+2− − -->8+2− − -->9{\displaystyle {\frac {\sqrt {2}}{2}}=0.70710678=2^{-1}+2^{-3}+2^{-4}+2^{-6}+2^{-8}+2^{-9}}

我们可以从上式注意到，22{\displaystyle {\frac {\sqrt {2}}{2}}}可以被近似为五个加法的结果，所以22(1+j){\displaystyle {\frac {\sqrt {2}}{2}}(1+j)}就可以被简化为只有六个加法，再算入实部与虚部的计算，总共只需12个加法器就可以运用到此一简化特性。

经由与2基底类似的推导，并用串接的方式将旋转因子以8为单位对DFT公式进行拆解，2基底FFT算法进一步将复数乘法器的用量缩减到log8N，并同时维持硬件架构的简单性。 　　 推导的方法与2基底相当类似。借由这样的方法，2基底能将乘法器的用量缩减到2基底的1/3，并同时维持一样的内存用量以及控制电路的简单性。

参考资料

Widhe, T., J. Melander, et al. (1997). Design of efficient radix-8 butterfly PEs for VLSI. Cirts and Systems, 1997. ISCAS "97., Proceedings of 1997 IEEE International Symposium on.

Lihong, J., G. Yonghong, et al. (1998). A new VLSI-oriented FFT algorithm and implementation. ASIC Conference 1998. Proceedings. Eleventh Annual IEEE International.

Duhamel, P. and H. Hollmann (1984). "Split-radix FFT algorithm." Electronics Letters 20(1): 14-16.

Vetterli, M. and P. Duhamel (1989). "Split-radix algorithms for length-pm DFT"s." Acoustics, Speech and Signal Processing, IEEE Transactions on 37(1): 57-64.

Richards, M. A. (1988). "On hardware implementation of the split-radix FFT." Acoustics, Speech and Signal Processing, IEEE Transactions on 36(10): 1575-1581.

Shousheng, H. and M. Torkelson (1996). A new approach to pipeline FFT processor. Parallel Processing Symposium, 1996., Proceedings of IPPS "96, The 10th International.

Shousheng, H. and M. Torkelson (1998). Designing pipeline FFT processor for OFDM (de)modulation. Signals, Systems, and Electronics, 1998. ISSSE 98. 1998 URSI International Symposium on.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。