FFT信号流图：

程序实现是这样：

程序流程如下图：

首先进行位逆转，其实很简单，就是把二进制的位逆转过来：

Matlab的位逆转程序：

function a=bitreverse(Nbit, num)

%Nbit = 4;

%num = 8;

a = 0;

b = bitshift(1,Nbit-1);

for i = 1:Nbit;

if((bitand(num,1)) == 1)

a = bitor(a,b);

end

num = bitshift(num,-1);

b = bitshift(b,-1);

end;

说明：Nbit是逆转位是几位，num是逆转的数即变量。

三个循环，第一个循环是进行N阶的FFT运算

第二个循环其实就是，每一阶FFT的时候，有多少组DFT对象，拿8点来说，第一阶的时候，有4组DFT对象，到了第二阶，就有2组，到了第三，就是最后一阶，只有一组。

第三个循环，其实是在每一组DFT里边，执行多少次蝶形运算！8点DIT FFT来说，第一阶每组有一个蝶形，第二阶每组有2个，第三阶每组有4个蝶形。所以很容易得到三者的关系

i , j, k

三者，反别表示三层循环，然后得出循环次数的关系

stages = log2(PointNum)

i

从 0到stages – 1 ！

j

从 0 到其实就是