2.9.1 FFT并行特性分析


ψ(L-1,k)与ψ(L-1,k+B)结构上是同构的,执行运算:(https://www.daowen.com)

即把后一多项式的每一项后移P位后与前一多项式相加。在不考虑系数的情况下,相当于将ψ(L-1,k)后移P位后再与自身合并。由于前面执行M-1次移位,都是第M次位移数的偶数倍,换而言之,本次位移的步长最多只有前面M次移位的
。根据假设,已经有了2s( k,M-1),因此本次位移将会填充2s(k,M-1)个空位,从而总项数达到2s( k,M-1)+1。又s(k,M-1)×2=s(k,M),因此命题得证。