实序列离散傅里叶变换的快速算法

\newcommand{\dft}[1]{\text{DFT}\left[#1\right]}从多项式乘法到快速傅里叶变换中我们介绍了快速傅立叶变换的算法。由于在计算多项式乘法或者大整数乘法时,我们所使用的都是实数,而快速傅立叶变换并不仅适用于实序列,对于复序列也是可以计算的,这让我们考虑是否可以利用虚部来保存额外的信息而减少计算的次数。

事实上,对于实序列x(n),其DFT是共轭对称的,也就是X^*(n) = X(N - n),如果将两个实数序列x(n)y(n)合并称为新的z(n) = x(n) + i\cdot y(n),对其进行FFT,我们可以从中复原出分别对两个序列进行FFT的结果。也就是,可以通过两次FFT就进行多项式乘法的计算(原先是需要三次的)。

沿用其中的记号,先回忆一下离散傅里叶变换的公式。

考虑长度为N的序列x(n)及其N点离散傅里叶变换X(n) := \dft{x(n)}

\begin{equation} X(n) = \sum_{k=0}^{N - 1} x(k)\cdot\omega_N^{kn},~ n = 0, 1, \cdots, N - 1 \end{equation}

其中\omega_N = e^{-2\pi i/N},即N次单位根。

现在来考虑X(n)X(N - n)之间的关系,我们用X^*(n)\overline{X(n)}来表示X(n)的共轭

\begin{equation} X^*(n) = \sum_{k=0}^{N - 1} x^*(k)\cdot\omega_N^{-kn} = \sum_{k=0}^{N - 1} x^*(k)\cdot\omega_N^{k(N-n)} \end{equation}

这是因为 \overline{\omega_N^{kn}} = e^{2\pi ikn/N} = e^{-2\pi ik(N - n)/N} = \omega_N^{k(N - n)}

那么,对于实序列,x^*(n) = x(n),我们可以得到 X^*(n) = X(N - n)。也就是说,实序列的DFT是共轭对称的。

现在来考虑两个实序列x(n)y(n),其对应的DFT为X(n)Y(n),定义新的序列z(n) = x(n) + i\cdot y(n),其对应DFT为Z(n),那么

\begin{equation} Z(n) = \dft{x(n) + i\cdot y(n)} = X(n) + i\cdot Y(n) \end{equation}

注意这里X(n)Y(n)本身并不是一个实数,因此它们也不是Z(n)的实部和虚部,我们设Z(n)的实部和虚部分别为A(n)B(n)

\begin{equation} \begin{aligned} \overline{X(N - n) + i\cdot Y(N - n)} &= \overline{A(N - n) + i\cdot B(N - n)} \\ \Rightarrow X(n) - i\cdot Y(n) &= A(N - n) - i\cdot B(N - n) \end{aligned} \end{equation}

这样就可以得到

\begin{equation} \begin{aligned} 2X(n) &= [A(n) + A(N - n)] + i[B(n) - B(N - n)] \\ 2Y(n) &= [B(n) + B(N - n)] - i[A(n) - A(N - n)] \end{aligned} \end{equation}

这样,对于两个实序列的DFT可以只利用一次FFT以及一点额外的运算进行计算而不必分别计算两次FFT。

下面来考虑一个长度为 2N 的实序列 x(n)。我们将其按照下标的奇偶分解为两个长度为N的序列

\begin{equation} \begin{aligned} x_1(n) &= x(2n)\\ x_2(n) &= x(2n + 1) \end{aligned} \end{equation}

现在可以利用刚刚的方法通过一次N点的FFT来计算它们分别的DFT序列X_1(n)X_2(n),通过类似于FFT的办法将其合并

\begin{equation} \begin{aligned} X_1(n) + \omega_{2N}^n X_2(n) &= \sum_{k=0}^{N-1}x_1(k)\omega_N^{kn}+\omega_{2N}^n\sum_{k=0}^{N-1}x_2(k)\omega_N^{kn} \\ &= \sum_{k=0}^{N-1}x(2k)\omega_{2N}^{2kn}+\sum_{k=0}^{N-1}x(2k + 1)\omega_{2N}^{(2k+1)n} \\ &= X(n) \end{aligned} \end{equation}

这里只有前N项,对于其余项可以利用共轭对称这个性质直接计算。 对于大整数乘法,我们也可以利用两个实序列DFT的快速算法进行计算,这样只需要两次FFT即可,下面我提供一个多项式乘法的代码(UOJ#34),FFT的模板是很久以前写的就别看了,可以看看下面处理的部分。

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2018/01/real-dft

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “实序列离散傅里叶变换的快速算法

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.