name: "4-Point Complex FFT"
category: "DSP & Numerical Algorithms"
complexity: "Medium"
description: |
  Implement a clocked hardware module that computes a 4-point complex discrete
  Fourier transform (DFT) on one input frame at a time.

  Each frame consists of four complex input samples presented over four
  consecutive clock cycles while `in_valid` is high. The first valid sample of a
  frame is `x0`, followed by `x1`, `x2`, and `x3`. Each sample uses signed
  12-bit two's-complement real and imaginary components.

  For each frame, compute the complex outputs `X0` through `X3` according to:

    X[k] = sum for n=0..3 of x[n] * W4^(k*n)

  where `W4 = exp(-j*2*pi/4)`.

  The equivalent output relations are:

    X0 = x0 + x1 + x2 + x3
    X1 = x0 - j*x1 - x2 + j*x3
    X2 = x0 - x1 + x2 - x3
    X3 = x0 + j*x1 - x2 - j*x3

  The transform must be exact for the given integer input values. Do not apply
  scaling, normalization, saturation, or rounding. The output bins must be
  produced in order `X0`, `X1`, `X2`, `X3`.

  TIMING AND CONTROL:
  - `rst` is synchronous and active-high.
  - After the fourth input sample of a frame is accepted, the module must assert
    `out_valid` on the next four clock cycles.
  - For example, if the 4th input sample is accepted on cycle N, then the first
    valid output on cycle N+1 must already be `X0` (not an uninitialized value
    and not `X1`).
  - While `out_valid` is high, `out_real` and `out_imag` must present `X0`,
    `X1`, `X2`, and `X3` on successive cycles.
  - The evaluator will not begin a new input frame until the previous output
    sequence has completed.

interface:
  module_name: "fft4_frame"
  clocked: true
  ports:
    - name: "clk"
      type: "input"
      width: "1"
      description: "Clock signal"
    - name: "rst"
      type: "input"
      width: "1"
      description: "Synchronous reset, active high"
    - name: "in_valid"
      type: "input"
      width: "1"
      description: "High when in_real and in_imag contain a valid input sample"
    - name: "in_real"
      type: "input"
      width: "12"
      description: "Real component of the input sample, signed two's-complement"
    - name: "in_imag"
      type: "input"
      width: "12"
      description: "Imaginary component of the input sample, signed two's-complement"
    - name: "out_valid"
      type: "output"
      width: "1"
      description: "High when out_real and out_imag contain a valid FFT output bin"
    - name: "out_real"
      type: "output"
      width: "14"
      description: "Real component of the output bin, signed two's-complement"
    - name: "out_imag"
      type: "output"
      width: "14"
      description: "Imaginary component of the output bin, signed two's-complement"

target_platform:
  device_family: "AMD Xilinx Zynq-7000"

tasks:
  - name: "Area-Efficient 4-Point FFT"
    constraints:
      max_lut: 160
      max_ff: 96
      max_bram: 0
      max_dsp: 0
      min_frequency: 150
    objective:
      goal: "minimise"
      target: "LUT"
