快速傅里叶变换

✍ dations ◷ 2024-12-23 09:22:37 #数字信号处理,变换编码,傅里叶变换,计算机科学中未解决的问题

快速傅里叶变换（英语：Fast Fourier Transform, FFT），是快速计算序列的离散傅里叶变换（DFT）或其逆变换的方法。傅里叶分析将信号从原始域（通常是时间或空间）转换到频域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏（大多为零）因子之积来快速计算此类变换。因此，它能够将计算DFT的复杂度从只用DFT定义计算需要的 $O(n^{2})$ ₀, ...., _-1 为复数。DFT由下式定义

直接按这个定义求值需要 O(2) 次运算：共有个输出，每个输出需要项求和。直接使用DFT运算需使用N个复数乘法(4N 个实数乘法)与N-1个复数加法(2N-2个实数加法)，因此，计算使用DFT所有N点的值需要2复数乘法与2-N 个复数加法。FFT则是能够在 O( log ) 次操作计算出相同结果的任何方法。更准确的说，所有已知的FFT算法都需要 O( log ) 次运算（技术上O只标记上界），虽然还没有已知的证据证明更低的复杂度是不可能的。（Johnson and Frigo, 2007）

要说明FFT节省时间的方式，就得考虑复数相乘和相加的次数。直接计算DFT的值涉及到 2 次复数相乘和 (−1) 次复数相加（可以通过削去琐碎运算（如乘以1）来节省 O() 次运算）。众所周知的基2库利-图基算法，为2的幂，可以只用 (/2)log₂() 次复数乘法（再次忽略乘以1的简化）和 log₂() 次加法就可以得到相同结果。在实际中，现代计算机通常的实际性能通常不受算术运算的速度和对复杂主体的分析主导（参见Frigo & Johnson, 2005），但是从 O(2) 到 O( log ) 的总体改进仍然能够体现出来。

假设一个M*N型矩阵S可分解成列向量以及行向量相乘：

$\mathbf {S} ={\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{m}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}$ 之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法（此算法在历史上数次以各种形式被再次提出）。

库利-图基算法最有名的应用，是将序列长为的DFT分割为两个长为的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey都指出的那样，Cooley-Tukey算法也可以用于序列长度为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显式的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。

下面，我们用N次单位根 $W_{N}$ 层计算，每层计算n个点的变换，故算法的时间复杂度为 $\mathrm {O} (n\log n)$ $\mathrm {O} (n\log n)$ 。

在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度 $N=N_{1}N_{2}$ $N=N_{1}N_{2}$ 且 $N_{1}$ $N_{1}$ 与 $N_{2}$ $N_{2}$ 互质的序列，可以采用基于中国剩余定理的互素因子算法将N长序列的DFT分解为两个子序列的DFT。与Cooley-Tukey算法不同的是，互素因子算法不需要旋转因子。

Rader-Brenner算法是类似于Cooley-Tukey算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radix variant of Cooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性。

Bruun以及QFT算法是不断的把DFT分成许多较小的DFT运算。（Rader-Brenner以及QFT算法是为了2的指数所设计的算法，但依然可以适用在可分解的整数上。Bruun算法则可以运用在可被分成偶数个运算的数字）。尤其是Bruun算法，把FFT看成是 $z^{N}-1$ $z^{N}-1$ ，并把它分解成 $z^{M-1}$ $z^{M-1}$ 与 $z^{2M}+az^{M}+1$ $z^{2M}+az^{M}+1$ 的形式。

另一个从多项式观点的快速傅立叶变换法是Winograd算法。此算法把 $z^{N}-1$ $z^{N}-1$ 分解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。这样只需要很少的乘法量（如果有需要的话），所以winograd是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd算法让DFT可以用 $2^{k}$ $2^{k}$ 点的DFT来简化，但减少乘法量的同时，也增加了非常多的加法量。Winograd也可以利用剩余值定理来简化DFT。

Rader算法提出了利用点数为N（N为素数）的DFT进行长度为N-1的回旋折积来表示原本的DFT，如此就可利用折积用一对基本的FFT来计算DFT。另一个prime-size的FFT算法为chirp-Z算法。此法也是将DFT用折积来表示，此法与Rader算法相比，能运用在更一般的转换上，其转换的基础为Z转换（Rabiner et al., 1969）。

在许多的运用当中，要进行DFT的资料是纯实数，如此一来经过DFT的结果会满足对称性：

而有一些算法是专门为这种情形设计的（e.g. Sorensen, 1987）。另一些则是利用旧有的算法（e.g. Cooley-Tukey），删去一些不必要的演算步骤，如此省下了记忆体的使用，也省下了时间。另一方面，也可以把一个偶数长度且纯实数的DFT，用长度为原本一半的复数型态DFT来表示（实数项为原本纯实数资料的偶数项，虚数项则为奇数项）。

在Matlab上用一次N点FFT计算两个N点实数信号x,y的FFT:

function  = Real2FFT( x,y )% N-point FFT is used for 2 real signals both with length NN = length(x);z = x+y*i ;Z = fft(z);X = 0.5*(Z+conj(Z(1+mod(0:-1:1-N,N))));Y = 0.5*(Z-conj(Z(1+mod(0:-1:1-N,N))))/i;end

一度人们认为，用离散哈特利转换（Discrete Hartley Transform）来处理纯实数的DFT会更有效率，但接着人们发现，对于同样点数的纯实数DFT，经过设计的FFT，可以比DHT省下更多的运算。Bruun算法是第一个试着从减少实数输入的DFT运算量的算法，但此法并没有成为人们普遍使用的方法。

对于实数输入，且输入为偶对称或奇对称的情形，可以更进一步的省下时间以及记忆体，此时DFT可以用离散余弦转换或离散正弦转换来代替（Discrete cosine/sine transforms）。由于DCT/DST也可以设计出FFT的算法，故在此种情形下，此方法取代了对DFT设计的FFT算法。

DFT可以应用在频谱分析以及做折积的运算，而在此处，不同应用可以用不同的算法来取代，列表如下：

用来做频谱分析的情况下，DFT可用下列的算法代替：

用来做折积的情况下，DFT可用下列的算法代替：

长久以来，人们对于求出快速傅里叶变换的复杂度下限以及需要多少的运算量感到很有兴趣，而实际上也还有许多问题需要解决。即使是用较简单的情形，即 $2^{k}$ $2^{k}$ 点的DFT，也还没能够严谨的证明出FFT至少需要 $\Omega (N\log N)$ $\Omega (N\log N)$ （不比 $N\log N$ $N\log N$ 小）的运算量，目前也没有发现复杂度更低的算法。通常量学运算量的多寡会是运算效率好坏最主要的因素，但在现实中，有许多因素也会有很大的影响，如缓冲存储器以及CPU均有很大的影响。

在1978年，Winograd率先导出一个较严谨的FFT所需乘法量的下限： $\Theta (N)$ $\Theta (N)$ 。当 $N=2^{k}$ $N=2^{k}$ 时，DFT只需要 $4N-2\log _{2}^{2}N-2\log _{2}N-4$ $4N-2\log _{2}^{2}N-2\log _{2}N-4$ 次无理实数的乘法即可以计算出来。更详尽，且也能趋近此下限的算法也一一被提出（Heideman & Burrus, 1986; Duhamel, 1990）。很可惜的是，这些算法，都需要很大量的加法计算，目前的硬件无法克服这个问题。

对于所需加法量的数目，虽然我们可以在某些受限制的假设下，推得其下限，但目前并没有一个精确的下限被推导出来。1973年，Morgenstern在乘法常量趋近巨大的情形下（对大部分的FFT算法为真，但不是全部）推导出加法量的下限： $\Omega \left(N\log N\right)$ $\Omega \left(N\log N\right)$ 。Pan（1986）在假设FFT算法的不同步的情形有其极限下证明出加法量的下限 $\Omega (NlogN)$ $\Omega (NlogN)$ ，但一般来说，此假设相当的不明确。长度为 $N=2^{k}$ $N=2^{k}$ 的情形下，在某些假设下，Papadimitriou（1979）提出使用Cooley-Tukey算法所需的复数加法量 $N\log _{2}N$ $N\log _{2}N$ 是最少的。到目前为止，在长度为 $N=2^{k}$ $N=2^{k}$ 情况，还没有任何FFT的算法可以让复数的加法量比 $N\log _{2}N$ $N\log _{2}N$ 还少。

还有一个问题是如何把乘法量与加法量的总和最小化，有时候称作"演算复杂度"（在这里考虑的是实际的运算量，而不是渐近复杂度）。同样的，没有一个严谨下限被证明出来。从1968年开始， $N=2^{k}$ $N=2^{k}$ 点DFT而言，split-radix FFT算法需要最少的运算量，在 $N>1$ $N>1$ 的情形下，其需要 $4N\log _{2}N-6N+8$ $4N\log _{2}N-6N+8$ 个乘法运算以及加法运算。最近有人导出更低的运算量： ${\frac {34}{9}}N\log _{2}N$ ${\frac {34}{9}}N\log _{2}N$ 。（Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007）

大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数数据输入的情况，因其为最简单的情形。但是，复数数据输入的FFT算法，与实数数据输入的FFT算法，离散余弦变换（DCT），离散哈特列变换（DHT），以及其他的算法，均有很大的关连性。故任何一个算法，在复杂度上有任何的改善的话，其他的算法复杂度也会马上获得改善（Duhamel & Vetterli, 1990）。

当输入信号长度为N时:

N = 1~60

N < 1000

N > 1000

快速傅里叶变换

相关