cordic_fft / cordic_ifft

Radix-2 DIT FFT and IFFT for N=8. Twiddle factors computed in hardware via cordic_core rotation mode.

Implementation

FFT

Algorithm: In-place Radix-2 DIT. One butterfly per clock, sequential stages.

Twiddle generation: N/2 cordic_core instances launched in parallel on start. Each computes W_N^k = cos(2πk/N) − j·sin(2πk/N) by rotating x_init=K_SCALE, y_init=0, z=−2πk/N. All twiddles are ready before the first butterfly stage.

CORDIC rotation converges only for |z| < π/2. Angles outside this range are folded at elaboration time via localparam: if angle < −π/2, use angle + π and negate both outputs since cos(a+π) = −cos(a), sin(a+π) = −sin(a).

Fixed-point chain:

• Data: Q1.30 (WIDTH=32, ANGLE_FRAC_BITS=30)
• Twiddle: x_out >> 16 = Q1.14 (x_out = cos × 2^30 → shift gives cos × 2^14)
• Butterfly multiply: Q1.30 × Q1.14 >> 14 = Q1.30
• Guard: >> 1 per stage against overflow
• Output scale: X[k] = DFT(x) / N

FSM:

1. S_WTTW — wait for all N/2 twiddle cores
2. S_BITREV — bit-reversal, one conditional swap per clock
3. S_BF — butterfly, iterates stage 0..N_LOG2−1, bfcnt 0..N/2−1
4. S_DONE — pulse valid, drop busy

Latency (N=8, ITER=16): 19 cycles (twiddle) + 8 (bit-reversal) + 12 (3 stages × 4 butterflies) = ~39 cycles.

IFFT

Wrapper around cordic_fft using the identity:

IFFT(X) = conj( FFT( conj(X) ) ) / N

cordic_fft already divides by N. Conjugation is two wire negations — din_im negated on input, dout_im negated on output. No extra logic. Output scale: x[n] = IDFT(X) / N.

Interface

Both modules share the same interface:

cordic_fft #(.N_LOG2(3), .WIDTH(`CORDIC_WIDTH), .ITER(`CORDIC_ITER)) u (
    .clk, .rst_n,
    .load_en, .din_re, .din_im, .din_idx,  // load before start
    .start,
    .busy, .valid,
    .rd_idx, .dout_re, .dout_im            // combinatorial readback
);

Load N samples via load_en/din_re/din_im/din_idx, pulse start, wait for valid, read via rd_idx.

Directed Tests

FFT — sim/fft_tb.v

Real-valued inputs. Reference = exact DFT / N.

IFFT — sim/ifft_tb.v

Reference = exact IDFT / N.

Round-trip error (tests 4–5) is lower than single-pass — quantization errors partially cancel through conjugation symmetry.

Verification — FFT

Stress Tests

Impulse and all-zeros are exact (zero error) as expected — no butterfly arithmetic is exercised for trivial spectra.

Monte-Carlo Results (200 tests, 1600 samples)

Max error         : 0.000083
Mean error        : 0.000021
RMS error         : 0.000024
SNR  mean/min/max : 78.79 / 74.27 / 84.46 dB
SFDR (random)     : 1.11 dBc mean
SFDR (pure-tone)  : 87.08 dBc avg across bins
Phase err mean/max: 0.0082 / 0.7267 deg

SNR ~79 dB is consistent with the theoretical limit for a 30-bit fractional CORDIC implementation. The SFDR of 87 dBc under pure-tone excitation is measured using the correct conjugate-pair metric for a real-input FFT — the symmetric bins (k, N-k) are treated as the fundamental, not as spurs. Phase error mean of 0.008° is negligible.

Per-Bin Mean Error

Even-indexed bins carry slightly higher error than odd-indexed bins — a known butterfly symmetry pattern in Cooley-Tukey at small N. The variation is minor (~30%) and within expected fixed-point rounding behaviour.

Error Distribution

Errors are tightly concentrated near zero with a long tail — typical of fixed-point CORDIC quantisation noise. The distribution is consistent across all 200 trials.

SNR Distribution

SNR ranges from 74 to 85 dB across random inputs, with mean ~79 dB. Variation is driven by input-dependent signal power, not by implementation instability.

SFDR

Left panel shows SFDR distribution for random multi-tone inputs — low values here are expected as random inputs excite all bins simultaneously and there is no dominant fundamental. Right panel shows the meaningful measurement: SFDR for a single cosine tone at each bin, ~87 dBc uniformly, demonstrating clean twiddle computation with minimal spurious content.

Per-Bin Error

Phase Error Distribution

Phase error mean of 0.008° across all active bins. Occasional outliers up to ~1° occur when the reference bin has small magnitude (denominator near zero in angle computation) — not representative of typical operation.

Error vs Input Amplitude

Error is largely independent of input amplitude, confirming that the fixed-point noise floor is dominated by twiddle quantisation rather than input-level scaling.

Stress Test Max Errors

CORDIC Iteration Sweep

SNR converges monotonically with iteration count. At 4 iterations the design is already usable at ~23 dB; 12 iterations gives ~67 dB; 16 iterations reaches the fixed-point noise floor at ~79 dB. Further iterations yield no improvement as angle quantisation (30-bit) becomes the limiting factor.

Verification — IFFT

Stress Tests

DC-only and all-zeros inputs are exact. The IFFT is implemented as a thin conjugation wrapper over the FFT core, so its error floor matches the FFT directly.

Monte-Carlo Results (200 tests, 1600 samples)

Max error         : 0.000104
Mean error        : 0.000031
RMS error         : 0.000035
SNR  mean/min/max : 78.40 / 75.43 / 82.61 dB
Phase err mean/max: 0.0059 / 0.1514 deg

IFFT SNR (~78 dB) matches the FFT closely — expected since the IFFT adds no arithmetic beyond two wire negations. The slightly higher mean error vs FFT (~31e-06 vs ~21e-06) is due to the IFFT accepting complex spectrum inputs, which exercise more of the butterfly datapath.

Roundtrip Test (FFT → IFFT, 50 trials)

Roundtrip max error  : 0.000025
Roundtrip mean error : 0.000007
Roundtrip SNR mean   : 78.26 dB
Roundtrip SNR min    : 75.54 dB

Real inputs are passed through hardware FFT, then the spectrum is fed directly into hardware IFFT. The recovered signal achieves 78 dB SNR end-to-end. Roundtrip error (7e-06 mean) is lower than single-pass IFFT error (31e-06 mean) — CORDIC angle quantisation errors partially cancel through the conjugation symmetry of the roundtrip.

Per-Bin Mean Error

Same even/odd alternating pattern as the FFT, consistent with shared butterfly structure.

Error Distribution

SNR Distribution

Roundtrip Error and SNR

Left panel shows roundtrip absolute error distribution — tightly concentrated below 2e-05. Right panel shows roundtrip SNR, mean 78 dB, confirming that FFT + IFFT in series introduces no significant error accumulation beyond the single-pass floor.

Per-Bin Error

Phase Error Distribution

IFFT phase error (mean 0.006°, max 0.15°) is tighter than FFT (max 0.73°). The conjugate-symmetry path through the IFFT wrapper suppresses phase error buildup.

Error vs Input Amplitude

Stress Test Max Errors

CORDIC Iteration Sweep

IFFT convergence curve is nearly identical to the FFT — as expected for a wrapper implementation sharing the same CORDIC core.

Summary