Home > K25104 > PDEs > rec_inv_FFT.m

rec_inv_FFT

PURPOSE ^

Computes the inverse discrete fourier transform of sequence x recursively

SYNOPSIS ^

function [ y ] = rec_inv_FFT( x )

DESCRIPTION ^

 Computes the inverse discrete fourier transform of sequence x recursively
 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 ] = rec_inv_FFT( x )
0002 % Computes the inverse discrete fourier transform of sequence x recursively
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 if a==1;
0017     y = x;
0018 else
0019     e = x(1:2:a); % extract even indices starting with 0
0020     o = x(2:2:a);  % extract odd indices starting with 0
0021     e = rec_inv_FFT(e);
0022     o = rec_inv_FFT(o);
0023     ahalf = a/2;
0024     w=exp(pi*1i/ahalf);    % relevant primitive root of unity
0025     for l=1:ahalf;
0026         y(l) = e(l) + w^(l-1) * o(l);
0027         y(l+ahalf) = e(l) - w^(l-1) * o(l);
0028     end
0029 end
0030 end

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