从另一个角度理解FFT在多项式乘法中的应用

1、-. z从另一个角度理解FFT在多项式乘法中的应用negiizhao我一个信号处理算法，怎么用来算多项式乘法了呢？很多同学学习FFT时，看到那一堆符号一堆算式就决定Ctrl+W并去背板。这篇文章或许能帮助那些同学从另一个角度理解FFT的过程。不要被下文中的*些矩阵吓到，有些只是为了表达原理方便，在实际中我们并不需要实现这些矩阵，而是实现它的功能如左乘这个矩阵表示什么意思，这时应更多关注它在算法中是用来干什么的。更新后就用黑体小写字母a表示向量了。虽说看起来可能要更清楚，但那毕竟还是更多地用于手写。1. 关于多项式乘法我们使用系数表示一个n次多项式，即使用序列表示多项式。我们通常称之为多项式的系

2、数表示。我们也可以选取n个不同的数代入多项式得到n个值，用n个有序数对表示这个多项式，其函数图像经过了这n个有序数对所表示的点。可以证明这样所表示的多项式是唯一的。我们通常称之为多项式的点值表示。从系数表示得到点值表示的过程称为求值，从点值表示得到系数表示的过程称为插值。多项式和的系数表示，我们可以得到这两个多项式的乘积的系数表示。为了得到中项的系数，考虑当j+k=i时，。所以只需对所有满足j+k=i的j和k，求出并求和。即。我们称向量c为a和b的离散卷积，记作c=a*b。多项式乘法实质上就是在计算离散卷积。直接根据定义计算离散卷积所需时间为。当n较大时，计算过程将会十分缓慢费时。如果两个多项

3、式在一样的n个数上的点值表示，求这两个多项式乘积的点值表示是容易的，因为。即我们可以用时间完成这一过程。然而我们通常使用系数表示法表示多项式，如何快速地完成求值和插值就显得很重要。现在我们考虑如何选取。2. 单位根和DFT以下的讨论均默认在复数域、i表示虚数单位、使用弧度，读者至少应对复数、三角函数、弧度和矩阵有最根本的了解。在引入单位根的概念之前，我们先考虑一下复数乘法的几何意义。复数在复平面上表示的点P到原点O的距离r称为复数的模，*轴到OP的夹角称为辐角。我们可以把复数z表示为。对于复数，我们可以得出，证明如下。现在我们引入单位根的概念。n次单位根是指满足方程的数，因为n次方程有n个解，

4、所以n次单位根共有n个。根据复数乘法的几何意义，不难想到n次单位根的模为1，辐角的n倍为0。则n次单位根可以表示为根据欧拉公式，n次单位根也可以表示为为了方便，我们通常会把上式的放在分子上写成，这就是那一堆符号的来历。为了防止一堆符号，我们记，则n次单位根可以表示为。至于这里为什么出现了负号，后面会提到，其实只是信号处理中的习惯罢了。下列图是5次单位根。对于单位根，显然有两个性质和2k2n=kn。如果不理解可以看下面的证明现在我们引入DFT的概念。我们可以用矩阵乘法表示对求值的过程。则假设，则系数向量a,b,c满足表示对应元素相乘。不难想到插值过程可以表示为。令，则矩阵现在为为了进展插值，我们

5、需要矩阵的逆元其中称为傅里叶矩阵。为什么要用这个矩阵？因为它有一些特别的性质，下一小节将会详细表达。现在，我们得到了系数向量a和点值向量y之间的关系,。我们把a称为y的离散傅里叶变换(discrete Fourier transform, DFT)，y称为a的离散傅里叶逆变换(inverse discrete Fourier transform, IDFT)。在信号处理中这两个变换有很重要的意义。而在多项式乘法应用中，我们可以通过计算得到c。直接计算矩阵乘法的时间复杂度仍是。接下来我们考虑如何快速地完成这一矩阵乘法。下面是一些题外话，如果承受不能可以忽略前面直接看结论或许有人也发现了，我似乎把

6、DFT和IDFT搞反了？事实上并不是。DFT最早的应用信号处理，就是对时域信号进展n次采样，用DFT转换成频域信号以方便过滤噪声。则是不是其他资料写错了？也不是。看完这一段就会知道为什么了。我们也可以不用矩阵表示DFT和IDFT，但可能理解起来有点困难，特别是后面关于如何加速这一计算过程。当然如果您比拟强就当我没说。不过dalao对我这辣鸡blog也没什么兴趣吧？可以发现，两个变换过程的区别在于系数这里分别是1和和指数或弧度的符号。事实上，这仅仅是个习惯约定，实际应用中并不都是这样处理，而是考虑如何表达比拟方便。DFT和IDFT本质上是没有区别的，对两者的要求只是系数的积为，符号不同。而在多项

7、式乘法应用中，为了保证求值的结果是多项式的一个点值表示，求值过程中不能乘，于是插值过程必须乘。过程对于指数的符号是没有要求的，所以说，即使把符号对调，你的多项式乘法程序也不会出错。为了表述方便，在多项式乘法应用中，一般称求值过程为DFT，插值过程为IDFT。事实上还可以仅计算一次得到两个实序列的DFT或IDFT，具体方法网上也有，我就不在这里废话了。3. 加速计算DFT的过程FFT算法再次提醒，不要被下文中的*些矩阵吓到，对于这些矩阵只需关注它在算法中是用来干什么的。信号处理领域的一个变革是1965年由 J. W. Cooley 和 J. W. Tukey 引入了一种十分高效的计算DFT的方法

8、。事实上，1965年 Cooley 和 Tukey 的论文是对1805年高斯提出的方法的重新发现。Cooley 和 Tukey 的方法称为快速傅里叶变换(fast Fourier transform, FFT)，这是一种计算DFT的高效算法。它利用了傅里叶矩阵的特殊性质。为了方便，我们设，即。下面以n=8为例进展说明。我们将的各列重新排列，使得它的奇数列全都在偶数列的前面。这个重新排列等价于右乘置换矩阵如果令,则对进展分块，用单位根的性质可得又根据单位根的另一性质，可知矩阵的块和块均等于令左乘相当于把第k行乘以。块和块可以分别表示为和，于是现在可以通过分块乘法实现计算DFT如果令,，则我们得到

9、。可以看出计算简化为两个n=4的傅里叶变换。以上过程不难推广到n等于任意偶数的情况。对于计算多项式乘法，我们通常把高次项系数补0使。这样求DFT的时间复杂度。这比直接计算要快多了。注意如果是进展插值，不要忘记乘以系数，即。至于如何求？前面说过，DFT和IDFT的差异仅仅在于系数和指数的符号。求IDFT只需把求DFT过程中的对角矩阵全部换成，最后不乘即可。具体来说，而。左乘相当于把第k行乘以，左乘相当于把第k行乘以。总结一下FFT求的过程1. 重排。令。即下标为奇数的元素全部移动到下标为偶数的元素前面。2. 递归。将分成相等两段和，求出和。3. 合并。令，。现在计算多项式乘法可以用3次FFT完成，即嗯接下来应该是如何递归