// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/chirpzt/chirpzt.h: ========== // chirp z-transform // ----- SRCFILE=src/chirpzt/fftarblen.cc: ----- static inline void make_fft_chirp(Complex *w, ulong n, ulong nn, int is); // For k=0..n-1: w[k] := exp( is * k*k * (i*2*PI/n)/2 ) where i = sqrt(-1) // For k=n..nn-1: w[k] = 0 void fft_arblen(Complex *x, ulong n, int is); // Arbitrary length FFT. // ----- SRCFILE=src/chirpzt/fftfract.cc: ----- static inline void make_fft_fract_chirp(Complex *w, double v, ulong n, ulong nn); // For k=0..nn-1: w[k] == exp(v*sqrt(-1)*k*k*2*pi*/n/2) void fft_fract(Complex *x, ulong n, double v); // Fractional (fast) Fourier transform. // For complex array c[0...n] // compute \sum_{x=0}^{n}{c_x*exp(is*v*2*i*\pi*x*k/n)} // (for v==1.0 this is just the usual FFT) // Use n*k == n^2/2 + k^2/2 - (k-n)^2/2 // See: Nussbaumer: "Fast Fourier Transform and Convolution Algorithms", chap.5, p.113ff // Could use n*k == - n^2/2 - k^2/2 + (k+n)^2/2 instead. // Worst case if n=2^x+1: // then nn=2*2^x // work is about 6 times of an FFT of length 2^x // and allocated workspace =2*nn static inline void make_fft_fract_chirp(double *wr, double *wi, double v, ulong n, ulong nn); // For k=0..nn-1: Complex(wr[k], wi[k]) == exp(v*sqrt(-1)*k*k*2*pi*/n/2) void fft_fract(double *x, double *y, ulong n, double v); // Fractional (fast) fourier transform. // For complex array c[0...n] // compute \sum_{x=0}^{n}{c_x*exp(is*v*2*i*\pi*x*k/n)} // (for v==1.0 this is just the usual fft) // Use n*k == n^2/2 + k^2/2 - (k-n)^2/2 // See: Nussbaumer: "Fast Fourier Transform and Convolution Algorithms", chap.5, p.113ff // Could use n*k == - n^2/2 - k^2/2 + (k+n)^2/2 instead. // Worst case if n=2^x+1: // then nn=4*2^x // work is about 12 times of an FFT of length 2^x // and allocated workspace =4*nn // ----- SRCFILE=src/chirpzt/slowfracft.cc: ----- void slow_fract_ft(double *fr, double *fi, ulong n, double v); // (slow) fractional Fourier transform. // (for v=+-1 this is the usual Fourier transform) void slow_fract_ft(Complex *f, ulong n, double v); // (slow) fractional Fourier transform. // (for v=+-1 this is the usual Fourier transform) // ----- SRCFILE=src/chirpzt/slowzt.cc: ----- void slow_zt(Complex *f, ulong n, Complex z); // (slow) z-transform. void slow_zt(double *f, ulong n, double z); // (slow) z-transform.