/******************************************************************************
 FILE
 	dft.c - This is the C source code for the implmentation of the 
 	Discrete Fourier Transform (DFT) algorithm.
 ******************************************************************************
 
 DESCRIPTION

 	This function computes the DFT of a N length complex-valued sequence.
	Note, N cannot exceed 1024 without modification to this code.
	 
	The N point DFT of a finite-duration sequence x(n) of length L<-N is 
	defined as

		       N-1
		X(k) = SUM x(n) * exp(-j2pikn/N)    k = 0,1,2, ..., N-1
	       	       n=0

	It is always helpful to express the above equation in its real and 
	imaginary terms	for implemetation.

	exp(-j2*pi*n*k/N) = cos(2*pi*n*k/N) - jsin(2*pi*n*k/N) -> several 
	identities used here
          
				e(jb) = cos(b) + j sin(b)
				e(-jb) = cos(-b) + j sin(-b)
				cos(-b) = cos(b) and sin(-b) = -sin(b)
        			e(-jb) = cos(b) - j sin(b)

       	       N-1
	X(k) = SUM {[xr(n) + j xi(n)][cos(2*pi*n*k/N) - jsin(2*pi*n*k/N)]}
               n=0
							k=0,1,2, ... ,N-1

                                   OR

        	N-1    
	Xr(k) = SUM {[xr(n) * cos(2*pi*n*k/N)] + [xi(n) * sin(2*pi*n*k/N)]}  
        	n=0
							k=0,1,2, ... ,N-1
        	N-1    
	Xi(k) = SUM {[xi(n) * cos(2*pi*n*k/N)] - [xr(n) * sin(2*pi*n*k/N)]}  
        	n=0

******************************************************************************/


#include <math.h>
#include "params.h"


void dft(int N, COMPLEX *X)
{

	int n, k;
    	double arg;
	int Xr[1024];
	int Xi[1024];
	short Wr, Wi;
    

	for(k=0; k<N; k++)
	{
		Xr[k] = 0;
		Xi[k] = 0;
		for(n=0; n<N; n++)
		{
			arg =(2*PI*k*n)/N;
			Wr = (short)((double)32767.0 * cos(arg));
			Wi = (short)((double)32767.0 * sin(arg)); 
			Xr[k] = Xr[k] + X[n].real * Wr + X[n].imag * Wi;
			Xi[k] = Xi[k] + X[n].imag * Wr - X[n].real * Wi;
		}
	 }

	 for (k=0;k<N;k++)
	 {
		X[k].real = (short)(Xr[k]>>15);
		X[k].imag = (short)(Xi[k]>>15);
	 }

 }