Home > K25104 > PDEs > inv_FFT.m

inv_FFT

PURPOSE ^

Computes the inverse discrete fourier transform of sequence x

SYNOPSIS ^

function [ y ] = inv_FFT( x )

DESCRIPTION ^

 Computes the inverse discrete fourier transform of sequence x
 Input arguments:
   x, row vector of length 2^n, where n is an integer value
   y, inverse fourier transform.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [ y ] = inv_FFT( x )
0002 % Computes the inverse discrete fourier transform of sequence x
0003 % Input arguments:
0004 %   x, row vector of length 2^n, where n is an integer value
0005 %   y, inverse fourier transform.
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;   % initialise array
0017 
0018 for k=1:l-1;
0019     p=2^(l-k+1);    % length of vectors in current row
0020     q=2^(k-1);      % number of vectors in current row
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);  % extract odd elements
0023     A(2,(p/2)*(2*n-1)+1:p*n)=A(1,p*(n-1)+2:2:p*n);  % extract even elements
0024     end
0025     A(1,:)=A(2,:);
0026 end
0027 
0028 B(1,:)=A(1,:);  % first row of B holds the ordered singletons
0029 
0030 for k=1:l;
0031     w=exp((pi*1i)/(2^(k-1)));    % save the relevant primitive root of unity
0032     p=2^(k-1);      % length of vectors in current row
0033     q=2^(l-k+1);    % number of vectors in current row
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

Generated on Mon 18-Jan-2016 10:25:49 by m2html © 2005