2.4.1 FFT相关性质研究


就是将后一多项式的每一项后移P位后与前一多项式相加。如果不考虑系数,也就是将X(L-1,k)后移P位后再与X(L-1,k)自身合并。由于前面执行M-1 次移位,都是第M次位移数的2 的整数倍,换而言之,本次位移的步长最多只有前面M次位移的
,因此本次位移将会填充2s(k,M-1)个空位子,从而总项数达到2×2s(k,M-1)。又s(k,M)=s(k,M-1)×2,因此命题得证。
表2-1 N=16时FFT的多项式运算结果的前8项(https://www.daowen.com)

输入(x0,x1,…,xN-1),将下标的二进制表示倒序排列所得到的二进制数作为新的下标重新升序排列得到(x0,x1,…,xN-1),经过FFT变换后得到输出的多项式表达式:

