Module fft 

Fast Fourier Transform (radix-2 Cooley-Tukey). FFT — Cooley-Tukey radix-2 FFT, inverse FFT, real FFT, PSD.

Determinism Contract

• Bit-reversal permutation is deterministic.
• Butterfly operations in fixed order.
• Zero-padding to next power of 2 is deterministic.

Functions

blackman_window

Blackman window: w[k] = 0.42 - 0.5cos(2pik/(N-1)) + 0.08cos(4pik/(N-1)). For N=1, returns [1.0].

fft

Compute the Cooley-Tukey radix-2 FFT in-place.

fft_2d

Compute the 2-D FFT by applying 1-D fft along rows then along columns.

fft_arbitrary

Compute the FFT for an arbitrary-length signal using Bluestein’s chirp-z algorithm.

hamming_window

Hamming window: w[k] = 0.54 - 0.46 * cos(2pik / (N-1)). For N=1, returns [1.0].

hann_window

Hann window: w[k] = 0.5 * (1 - cos(2pik / (N-1))). For N=1, returns [1.0].

ifft

Compute the inverse FFT by conjugating, applying fft, then conjugating and scaling by 1/N.

ifft_2d

Compute the 2-D inverse FFT by applying 1-D ifft along rows then columns.

psd

Compute the power spectral density: |FFT(x)|^2 for each frequency bin.

rfft

Compute the FFT of a real-valued signal.