← All problems

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

Open this challenge in the editor →