Module fft

scirs2_linalg

Module fft 

Source
Expand description

Fast Fourier Transform (FFT) and spectral methods for signal processing

This module implements cutting-edge FFT algorithms and spectral analysis techniques that provide efficient frequency domain computations for signal processing, image analysis, quantum physics, and machine learning applications:

  • Core FFT algorithms: Cooley-Tukey radix-2, mixed-radix, and prime-factor
  • Real-valued FFT optimizations: RFFT for real-world signal processing
  • Multidimensional FFT: 2D/3D FFT for image and volume processing
  • Windowing functions: Hann, Hamming, Blackman, Kaiser for spectral analysis
  • Discrete transforms: DCT, DST for compression and scientific computing
  • Convolution algorithms: FFT-based fast convolution for signal processing
  • Spectral analysis: Power spectral density and frequency analysis

§Key Advantages

  • Optimal complexity: O(n log n) instead of O(n²) for DFT
  • Memory efficiency: In-place algorithms with minimal overhead
  • Numerical accuracy: Bit-reversal and stable twiddle factor computation
  • Real-world optimized: RFFT leverages Hermitian symmetry for 2x speedup
  • Comprehensive toolbox: Complete spectral analysis ecosystem

§Mathematical Foundation

The Discrete Fourier Transform (DFT) of a sequence x[n] is defined as:

X[k] = Σ(n=0 to N-1) x[n] * exp(-j * 2π * k * n / N)

The FFT achieves O(n log n) complexity through divide-and-conquer recursion.

§References

  • Cooley, J. W., & Tukey, J. W. (1965). “An algorithm for the machine calculation of complex Fourier series”
  • Frigo, M., & Johnson, S. G. (2005). “The design and implementation of FFTW3”
  • Oppenheim, A. V., & Schafer, R. W. (2009). “Discrete-Time Signal Processing”

Structs§

FFTPlan
FFT planning and execution context

Enums§

FFTAlgorithm
FFT algorithm type selection
WindowFunction
Window function types for spectral analysis

Functions§

apply_window
Apply window function to signal for spectral analysis
bluestein_fft
Bluestein’s algorithm for arbitrary-size FFT
dct_1d
Discrete Cosine Transform (DCT) Type-II
dst_1d
Discrete Sine Transform (DST) Type-I
fast_walsh_transform
Fast Walsh Transform (FWT) for Boolean functions
fft_1d
Compute 1D FFT using the Cooley-Tukey radix-2 algorithm
fft_1d_with_plan
Compute 1D FFT with a precomputed plan
fft_2d
2D FFT for image processing and 2D signal analysis
fft_3d
3D FFT for volume processing and 3D signal analysis
fft_convolve
Fast convolution using FFT
fft_frequencies
Generate frequency bins for FFT output
hadamard_transform
Fast Hadamard Transform (FHT) using recursive algorithm
idct_1d
Inverse Discrete Cosine Transform (IDCT)
irfft_1d
Inverse real-valued FFT (IRFFT)
periodogram_psd
Power Spectral Density (PSD) estimation using periodogram method
rfft_1d
Real-valued FFT (RFFT) exploiting Hermitian symmetry
walsh_hadamard_transform
Walsh-Hadamard Transform (WHT) using natural ordering
welch_psd
Welch’s method for PSD estimation with overlap

Type Aliases§

Complex32
Complex64
Complex number type for FFT computations