%
function c = fastCircConv( a, b ) 
% 
% Calling sequence : 
%
% v = fastCircConv( a, b ) ; 
% 
% Input : 
% --------
% a, b    vectors of the same length  
%
% Output 
% -------
% c       circulant convolution of a and b 
% 
% Algorithm escription  
% ----------------------
% Based on the discrete convolution theorem; 
% use the FFT 
% 
% in comparison to the direct method for 
% circulant convolution, see dirtCircConv.m 
% for example 
% 
% Error checking  
% ------------------ 
% The input conditions are assumed to be met  
% by external checking. 
% Internal error checking is therefore skipped 
% for efficiency when the function is used 
% repeatedly. 
% 


% -----------------------
% Xiaobai Sun 
% for cps-250 
% Duke CS 
% -----------------------


 Fa  = fft(a) ; 
 iFb = ifft(b); 
 
 c  =  fft( Fa .* iFb ); 

 return 

% Notes on the decomposition of a circulant matrix. 
% (1)  
% Let A be the circulant matrix (along diagonals). 
% Then 
%    A F = F D; 
% where F is the DFT matrix in matlab representation 
% and D is diagonal with Fa on the diagonal.  
% 
% (2) 
% This version of the convolution theorem makes 
% the two vectors seemingly asymmetric, due to 
% the DFT representation in MATLAB, which is 
% symmetric about the diagonal, not symmetric 
% in the spectral domain about the zero frequency. 
% 
% (3) 
% There is a related fast approach that is more memory 
% efficient. 
% 
