fwt.c

Walsh Hadamar Transform CDMA2

/*
Fast Walsh Transform
x - pointer to data
n = number of data points - order of FWT (should be equal to power of 2:  4,8,16,32 etc.)

only integer calculations are used, no mul/div operations used

(c)Max
*/

#include <stdlib.h>

void FWT(int *x, int n)
{
int i,b,k;
int m=1;
int p,q;
int *z;

z=malloc(n*sizeof(int));


for(i=0;i<(n-1);i+=2)
 {
 p=x[i]+x[i+1];
 q=x[i]-x[i+1];
 x[i]=p;
 x[i+1]=q;
 }


while((m<<=1)<n)
 {
 b=k=0;

 do {
    for(i=0;i<m;i+=2)
     {
     z[k]=x[b+i]+x[b+i+m];
     z[k+1]=x[b+i]-x[b+i+m];
     z[k+2]=x[b+i+1]-x[b+i+m+1];
     z[k+3]=x[b+i+1]+x[b+i+m+1];
     k+=4;
     }
    b+=2*m;
    } while(k<n);

 for(i=0;i<n;i++) x[i]=z[i];
 }

free(z);
}