Parallel Prefix Sum (Inclusive Scan)
Medium · Combinational · SystemVerilog
Design a purely combinational module that computes the inclusive prefix sum (also called an inclusive scan) of $N$ packed $W$-bit unsigned integers.
The $N$ input elements are packed into {in} using LSB-first order: element $k$ occupies bits $[W \times k + W - 1 : W \times k]$, i.e., {in}$[W \times k + : W]$, for $k = 0, 1, \ldots, N-1$. Element 0 is in the least-significant slice and element $N-1$ is in the most-significant slice.
The $N$ output elements are packed into {out} using the same convention: {out}$[W \times k + : W]$ must equal the inclusive prefix sum at position $k$:
- {out}$[W \times 0 + : W]$ $=$ element 0 of {in} (pass-through). - {out}$[W \times k + : W]$ $=$ (element 0 + element 1 + $\cdots$ + element $k$) $\bmod 2^W$, for $k = 1, \ldots, N-1$.
All arithmetic is unsigned and $W$-bit modular: sums are truncated to $W$ bits naturally (no carry-out, no saturation). The parameters $N$ and $W$ may be any positive integers; the implementation must be fully parameterized.
**Edge cases:** - When all input elements are $0$, all output elements are $0$. - When all input elements are $2^W - 1$ (all-ones), the prefix sums wrap modulo $2^W$ at each position. - When $N = 1$, {out} $=$ {in} (single-element scan; element 0 passes through unchanged).