3.4.1.3 规律
设序列x（n）倒序后存放在数组A中，如果蝶形运算两个输入相距B=2^(L-1)。 采用原位运算：蝶形运算可表示为： x(K)=x(K)+x(K+B)*W^Np; x(K+B)=x(K)-x(K+B)*W^Np.其中P=J*2^（M-1）,(J=0,1,2,3……,2^(L-1)-1)
旋转因子的确定：
第L级共有2^(L-1)个旋转因子，以(N=2^3=8为例)：
Jp
L=1时，WN=W2^L J=0； JpL=2时，WN=W2^L J=0，1； JpL=3时，WN=W2^L J=0，1
，2，3；
J*2^(M L)JpWN=W2 P=J*2^(M-L)，用来确定第L级旋转因子 ^L=WN
从输入端开始，共进行M级运算，在进行第L级运算时，依次求出2^(L-1)个旋转因子，然后计算每个旋转因子所对应的2^(M-L)个蝶形元素。第L级的蝶形运算中，每个蝶形运算的两个输入相距B=2^L-1,同一旋转因子对应的蝶形运算相隔2^L个，同一旋转因子对应的蝶形运算有2^M-L个。
注：1、控制第L级顺序运算
2、控制不同种的旋转因子
3、控制同种旋转因子所对应的蝶形运算
第 12 页 共 23页