Parallel Prefix Leading-One Detector
Medium · Combinational · SystemVerilog
Design a combinational module that simultaneously finds the three highest-priority set bits in a 16-bit request vector and reports them via a grant vector, a count of valid grants, and three binary position outputs.
{in} is a 16-bit request vector where bit 15 carries the highest priority and bit 0 carries the lowest. Scan {in} and identify up to three bits that are set, in priority order from highest to lowest.
{grant} is a 16-bit output with at most 3 bits set. Bit $i$ of {grant} is $1$ if and only if bit $i$ of {in} is among the top-3 highest-priority set bits.
{n_grants} reports the number of valid grants: - {n_grants} $= 0$ when {in} $= 0$ (no bits set). - {n_grants} $= 1$ when exactly 1 bit of {in} is set. - {n_grants} $= 2$ when exactly 2 bits of {in} are set. - {n_grants} $= 3$ when 3 or more bits of {in} are set.
{pos0}, {pos1}, and {pos2} are the binary positions ($0$ = LSB, $15$ = MSB) of the granted bits sorted by priority: - {pos0} is the position of the highest-priority grant (valid when {n_grants} $\geq 1$). - {pos1} is the position of the second-highest-priority grant (valid when {n_grants} $\geq 2$). - {pos2} is the position of the third-highest-priority grant (valid when {n_grants} $= 3$).
When {n_grants} $= 0$: {grant} must be $0$; {pos0}, {pos1}, {pos2} may be any value (don't care). When {n_grants} $= 1$: {grant} has exactly 1 bit set (the highest-priority set bit); {pos1} and {pos2} are don't care. When {n_grants} $= 2$: {grant} has exactly 2 bits set; {pos2} is don't care. When {n_grants} $= 3$: {grant} has exactly 3 bits set; all position outputs are valid.