hsfft Files

HSFFT is designed specifically to handle time series data efficiently.  The software is structured very similarly to available open source softwares like FFTW and kissfft. The data structure is almost identical to Mark Borgerding's kissfft implementaion. However, this implementation is lightweight compared to FFTW and should give better performance for non-power of two implementations compared to kissfft in a single core setting. The project is a work in progress and the To-Do list is considerably long, including an implementation with multicore/multithread support, real FFT support, multi-stride and multi-dimensional FFTs.

Algorithm - HSFFT computes Out of Place FFT using a recursive FFT routine which is "semi-optimized" for radix 2,3,4,5,7,8. As of now , general radices upto length 53 are supported using a generic module and a routine directly based on Paul N. Swarztrauber's Bluestein algorithm is utilized for other general lengths. 

Usage -

1. Regular Complex FFT ( Complex Data I/O)


fft_object obj = fft_init(N,1); // Initialize FFT object obj . N - FFT Length. 1 - Forward FFT and -1 for Inverse FFT

// FFT Object obj , thus created, can be used as many time as you wish.

fft_data* inp = (fft_data*) malloc (sizeof(fft_data) * N); // Allocate Input Data
fft_data* oup = (fft_data*) malloc (sizeof(fft_data) * N); // Allocate Output Data

/*  Data Access */

//Input can be entered as following
for (i = 0; i < 16; i++) {
  inp[i].re = i;
  inp[i].im = i;
}

fft_exec(obj,inp,oup); // Compute FFT

// Output is complex. Real oup[i].re and imaginary oup[i].im can be accessed for the ith location. 

//Deallocate Data and Object Obj when the computation is finished

 free(inp);
 free(oup);
 free_fft(obj);

 2. Real FFT/IFFT ( r2c Real Input, Complex Output and c2r - Complex Input and Real Output)

 Requirements - real.h,real.c,hsfft.h,hsfft.c

 Important Note- This works only with even length data. For odd length real data use the complex FFT by
 setting all imaginary inputs to zero. Otherwise it works similar to the complex FFT. 

 fft_real_object obj = fft_real_init(N,1); // Initialize FFT object obj . N - FFT Length. 1 - r2c and -1 for c2r

 // FFT Object obj , thus created, can be used as many time as you wish.

double* inp = (double*) malloc (sizeof(double) * N); // Allocate Input Data
fft_data* oup = (fft_data*) malloc (sizeof(fft_data) * N); // Allocate Output Data

fft_r2c_exec(obj,inp,oup); //Execute Real To Complex Transform

Complex To Real Transform

fft_real_object iobj = fft_real_init(N,-1);

fft_c2r_exec(obj,inp,oup);

Object memory can be deallocated by

free_real_fft(obj);

 3. Convolution

  Requirements - conv.h,conv.c,real.h,real.c,hsfft.h,hsfft.c.

 Two methods are available - An unoptimized direct convolution and a FFT based convolution

 Allocate inputs and outputs

  double* inp1 = (double*) malloc (sizeof(double) * N);
  double* inp2 = (double*) malloc (sizeof(double) * L);
  double* oup = (double*) malloc (sizeof(double) * M); // M = N + L - 1

 a.) Direct FFT is straghtforward

 conv_direct(inp1,N,inp2,L,oup); // N - Length of Input 1 while L is the length of Input 2

 b.) FFT based Convolution

 conv_object obj = conv_init(N,L); // Initialize Convolution object obj . N - Length of Input 1 while L is the length of Input 2

 conv_fft(obj,inp1,inp2,oup); //Execute Convolution

 Deallocate Memory

  free(inp1);
  free(inp2);
  free(oup);
  free_conv(obj);

 Important Note - Inputs are added sequentially. Length N should correspond to inp1 and length L should correspond to 
 inp2.


 Contact - rafat.hsn@gmail.com for any bug reporting, error corrections and recommendations.