man wnfft (Fonctions bibliothèques) - discrete Fourier transform package
NAME
wn_fft_vect, wn_inverse_fft_vect, wn_sft_vect, wn_inverse_sft_vect - discrete Fourier transform package
SYNOPSIS
#include <wn/wnfft.h> wn_fft_vect(vector, len_i) wn_cplx vector[]; int len_i; wn_inverse_fft_vect(vector, len_i) wn_cplx vector[]; int len_i; wn_sft_vect(vector, len_i) wn_cplx vector[]; int len_i; wn_inverse_sft_vect(vector, len_i) wn_cplx vector[]; int len_i;
DESCRIPTION
This package implements the discrete Fourier transform and its inverse. vector is the data to be transformed; len_i is its length. The resulting transformed data is also placed in vector.
wn_fft_vect and wn_sft_vect implement the following DFT:
out[f] = (len_i^(-1/2))*sum_over(0<=t<len_i){in[t]*exp(-j*2*PI*f*t/len_i)}
wn_inverse_fft_vect and wn_inverse_sft_vect implement the following inverse DFT:
out[t] = (len_i^(-1/2))*sum_over(0<=f<len_i){in[f]*exp(j*2*PI*f*t/len_i)}
where j == (-1)^(1/2).
"sft" stands for "slow Fourier transform" while "fft" stands for "fast Fourier transform". The fft routines are much faster, but they require that len_i be a power of 2. The sft routines are much slower, but place no restriction on len_i.
Applying fft and then inverse_fft to a vector yields the original vector.
RESOURCES
wn_fft_vect and wn_inverse_fft_vect require
WORST and AVERAGE CASE:
time = len_i*log(len_i)
stack memory = log(len_i)
dynamic memory = len_i
wn_sft_vect and wn_inverse_sft_vect require
WORST and AVERAGE CASE:
time = len_i^2
stack memory = 1
dynamic memory = len_i
BUGS
This code is new and has not been tested in large industrial applications.
SEE ALSO
acc/complex/examples.c
AUTHOR
Will Naylor