Challenge Overview
Our client BG100 has a vector of samples representing Complex numbers with real and imaginary parts in the range -1.0 <= x < 1.0, mapped to 16 bit integers as int(x * 2^15), so that -1.0 is mapped to -32768 and (1.0 – 1.0/32768.0) is mapped to 32767.
As part of this challenge, we need to create a set of functions, callable from a C program that performs FFT and inverse FFT of such vectors, optimized for the x86 AVX2 architecture.
Detailed requirements
The Complex numbers are defined as following:
typedef struct {
int16_t re;
int16_t im;
} Complex;
The twiddle factors needed should be initialized at run-time.
The function prototypes may look like:
void init_fft(); // Initialize FFT twiddle factors
void fft(Complex *out, Complex *in); // Perform out = FFT(in)
void init_ifft(); // Initialize inverse FFT twiddle factors
void ifft(Complex *out, Complex *in); // Perform out = inverse FFT(in)
Each function should also print the CPU time and the CPU cycles used.
NOTE: Customer expects the Library to work on a single core as a pure library. Solutions that spawn additional worker-threads, are not valid and will be rejected.
Target OS: Linux with kernel v4