Prefix Sum
Medium · Combinational · SystemVerilog · VHDL
Design a parallel prefix sum module.
A prefix sum, or scan, gives for every element of a sequence the total of the elements up to and including it. Computed element by element it is a chain of adders, each waiting on the one before; a parallel prefix network computes every total in a logarithmic number of adder levels, and the same networks are the core of fast carry-lookahead adders.
data_in and data_out each hold N unsigned W-bit elements, element k at bits [W*k +: W], so element 0 is the least-significant slice. Element k of data_out is the sum of elements 0 through k of data_in, modulo 2^W.
The module is combinational.
- Arithmetic