要先对输入的序列进行位序颠倒。如果总点数为N 2的x(n)的顺序数是用M位二进制数表示，则倒序数只需将顺序数的二进制位倒置即可，按照这一规律用硬件电路和汇编语言很容易产生倒序数。但用MATLAB等高级语言实现倒序时，直接倒置二进制数位的方法不可取，还须找出产生倒序的十进制规律。将十进制顺序数用I表示，与之对应的二进制数用IB表示。十进制倒序数用J表示，与之对应的二进制数用JB表示。JB是IB的位倒置结果，十进制顺序数I增加1，相当于IB最低位加1且逢2向高位进1，即相当于JB最高位加1且逢2向低位进1。JB的变化规律反映到J的变化分二种情况：如果JB的最高位是0(J N/2)，则直接由加1(J J N/2)得到下一个倒序值；如果JB的最高位是1(J N/2)，则要先将最高位变0(J J N/2)，再在次高位加1(J J N/4)。但次高位加1时，同样要判断0、1值，如果是0 (J N/4)，则直接加1(J J N/4)，否则要先将次高位变0(J J N/4)，再判断下一位。依此类推，直到完成最高位加1，逢2向右进位的运算。利用这一算法可按顺序数I的递增顺序，依次求得与之对应的倒序数J。为了节省内存，数据倒序可原址进行，当I = J时不需要交换，当I ≠ J时需要交换数据。另外，为了避免再次调换前面已经调换过的一对数据，只对I<J的情况进行数据交换即可实现数据倒序操作。
M