0001 function [ y ] = inv_FFT( x )
0002
0003
0004
0005
0006
0007 [b,a]=size(x);
0008 if b~=1;
0009 error('input must be a row vector');
0010 end
0011 l=log2(a);
0012 if mod(l,1)~=0;
0013 error('input must have length 2^n for some integer n');
0014 end
0015
0016 A(1,:)=x;
0017
0018 for k=1:l-1;
0019 p=2^(l-k+1);
0020 q=2^(k-1);
0021 for n=1:q
0022 A(2,p*(n-1)+1:(p/2)*(2*n-1))=A(1,p*(n-1)+1:2:p*n);
0023 A(2,(p/2)*(2*n-1)+1:p*n)=A(1,p*(n-1)+2:2:p*n);
0024 end
0025 A(1,:)=A(2,:);
0026 end
0027
0028 B(1,:)=A(1,:);
0029
0030 for k=1:l;
0031 w=exp((pi*1i)/(2^(k-1)));
0032 p=2^(k-1);
0033 q=2^(l-k+1);
0034 for n=1:q/2
0035 left=B(1,p*(2*n-2)+1:p*(2*n-1));
0036 right=B(1,p*(2*n-1)+1:p*2*n);
0037
0038 B(1,2*p*(n-1)+1:2*p*n)=[left,left];
0039 for m=1:p;
0040 B(1,2*p*(n-1)+m)=B(1,2*p*(n-1)+m)+right(m)*w^(m-1);
0041 B(1,2*p*(n-1)+m+p)=B(1,2*p*(n-1)+m+p)+right(m)*w^(p+m-1);
0042 end
0043 end
0044 end
0045
0046 y=B(1,:);
0047
0048 end
0049