列进行整序处理.doc

《列进行整序处理.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在FFT算法之前需要对输入的序列进行整序处理，FFT整序框图如下：其中N为序列元素的个数，I，J为元素在内存中存储单元的序号（或数组元素的下标），A（I）、A（J）为与序号I、J对应的序列的元素。例如，含有8个元素的序列按自然顺序存入存储单元时为（1）式，则整序之后，序列的8个元素在内存中存储单元的存储顺序则为（2）式：即顺序存放的序列元素x(1)和x(4)互换，x(3)和x(6)互换，x(0),x(2),x(5),x(7)不变。顺序和整序后二进制数的次序序号（n）二进制数反序二进制数反序序号（）012345670000010100111

2、0010111011100010001011000110101111104261537由上表可见，左边按顺序标号的二进制数，下面一个数总比上面一个数大1。因此，下面的一个数可以看作是上面一个数在最低位上加1并向高位（向左）进位而得到。上表右边的数是左边的数的反序数，这些反序数有这样的规律：下面一个数也是上面一个数加1而得到的，但1是加在最高位上，而且要求“加法”是从高位向低位进位，这种反向加法具体描述如下：若已知某个反序数J，要求下一个反序数，则先判断J的最高位是否为0（与N/2）相比较，因N/2总是等于1000…的），若是，则把该位变为

3、1（让J与N/2相加即可），就得到下一个反序数；若最高位是1，可将最高位变为0（与N/2相减即可），然后再判别次高位（与（N/2）/2相比较），若次高位为0，则将其该为1（与（N/2）/2）相加，其他位不变，即得到下一个反序数；若次高位为1，则还应判别下一位…，依次进行（除非已经到最后一个数，即全1，也即N-1时）。这样就可以得到相应于顺序二进制数I的反序二进制数J，I和J均可以看成数组元素的下标，接着进行判断：当I>J时进行换位，注意，在整序中x(0)及x(N-1)总是不需要调动的。当上面的流程图就是根据上诉描述得到的。