¶ NthOne — nth set-bit selector
¶ Introduction
NthOne locates the nth set bit in an input vector and outputs a match flag, the bit index and a one-hot mask. Its features include:
- A tree structure to shorten combinational logic paths.
- Configurable input vector width and set-bit rank.
- Generated plain Verilog RTL without vendor IP or device primitives.
¶ Function
Scan the input vector from bit 0 toward the MSB and select zero-based set-bit rank n. n=0 selects the first one; n=1 selects the second. If fewer than n+1 bits are set, io_found, io_idx and io_onehot are all zero. Always inspect io_found: io_idx=0 alone cannot distinguish no match from a valid match at bit 0.
To search from MSB to LSB, reverse the input bit order before feeding it to the module, then reverse
io_onehotto map it back to the original vector. On a match, the original bit index isinputWidth - 1 - io_idx; on a miss, keep the index output at zero.
¶ Waveform example
This example fixes inputWidth=8 and n=2, selecting the third set bit from LSB to MSB. Input and one-hot values are hexadecimal; indices are decimal.
{
"signal": [
{
"name": "io_input[7:0]",
"wave": "========",
"data": [
"0x00",
"0x01",
"0x05",
"0x15",
"0xB4",
"0x07",
"0xFF",
"0x00"
]
},
{
"name": "io_found",
"wave": "0..1...0"
},
{
"name": "io_idx[2:0]",
"wave": "=..===.=",
"data": [
"0",
"4",
"5",
"2",
"0"
]
},
{
"name": "io_onehot[7:0]",
"wave": "=..===.=",
"data": [
"0x00",
"0x10",
"0x20",
"0x04",
"0x00"
]
}
],
"head": {
"text": "inputWidth=8, n=2 (LSB first)",
"tock": 0
},
"foot": {
"text": "Samples 0-7 = t0-t7; stable values, no clock or physical delay"
},
"config": {
"hscale": 3
}
}
| Settled sample | io_input | io_found | io_idx | io_onehot | Explanation |
|---|---|---|---|---|---|
| t0 | 0x00 | 0 | 0 | 0x00 | No set bits |
| t1 | 0x01 | 0 | 0 | 0x00 | Only one set bit; fewer than three |
| t2 | 0x05 | 0 | 0 | 0x00 | Only two set bits; fewer than three |
| t3 | 0x15 | 1 | 4 | 0x10 | Set positions 0, 2, 4; the third is bit 4 |
| t4 | 0xB4 | 1 | 5 | 0x20 | Set positions 2, 4, 5, 7; the third is bit 5 |
| t5 | 0x07 | 1 | 2 | 0x04 | Set positions 0, 1, 2; the third is bit 2 |
| t6 | 0xFF | 1 | 2 | 0x04 | All bits set; the third is bit 2 |
| t7 | 0x00 | 0 | 0 | 0x00 | Clearing the input clears the outputs |
This module consists of combinational logic with no clock, reset or internal registers. t0–t7 indicate ordered samples taken after each input change has settled. Horizontal spacing specifies neither clock periods nor physical propagation delay, and does not imply registered outputs. Obtain actual delay from timing analysis for the target device.
¶ Parameters and constraints
The labels below match the parameters on the generation page. Both parameters are integers.
| Page label | Parameter | Default | Allowed range | Description |
|---|---|---|---|---|
| Input vector width | inputWidth |
8 | 3–32 bits inclusive | Width of the input vector and onehot output |
| Set-bit rank (zero-based) | n |
0 | 0 ≤ n < ceil(inputWidth/2), up to 15 |
Select the (n+1)th set bit from LSB to MSB; fixed at generation time |
ceil rounds upward. For example, legal n values are 0–1 for inputWidth=3, 0–3 for width 8, 0–4 for width 9, and 0–15 for width 32. Equality with the upper bound is invalid: (8,4), (9,5) and (32,16) are rejected.
Both are elaboration parameters; n is not a runtime input port. Changing only n changes the generated logic without changing port widths. These constraints belong to this publication adapter; they do not imply identical limits in the underlying library module.
¶ Ports
The names below are the actual generated RTL top-level ports. There are no clock or reset ports.
| RTL port | Direction | Width | Meaning |
|---|---|---|---|
| io_input | input | inputWidth | Input bit vector, bit 0 first priority |
| io_found | output | 1 | At least n+1 input bits are set |
| io_onehot | output | inputWidth | One at the selected position; zero on a miss |
| io_idx | output | ceil(log2(inputWidth)) | Binary index of the selected bit; zero on a miss |
Within this version's legal width range, the index is at least 2 bits wide. It is 2 bits for inputWidth=3, 3 bits for width 8, and 5 bits for width 32.
¶ PPA
The supplied data records the following environment for comparing resource usage and estimated frequency across two configuration sets:
- Vivado 2020.2, SW Build 3064766.
- Device:
xc7k325tffg900-1; clock constraint: 5.000 ns (200 MHz); OOC clock reference location:BUFGCTRL_X0Y0. - Estimated Fmax is calculated as
1000 / (5.000 - setup_WNS_ns)in MHz. It is an estimate for this test environment, not a frequency guarantee across devices or configurations.
The two configuration sets are:
- Fix
inputWidth=16and evaluate resource usage and estimated frequency forn=0–7. - Fix
n=2and compare the underlying module atinputWidth=4, 8, 16, 32, 64.
In the second set, (inputWidth=4,n=2) violates the new rank constraint, and width 64 exceeds the 32-bit ceiling. Both points are retained for comparison of the underlying module; the supported points in that set are (8,2), (16,2) and (32,2).
Orange dashed lines show synthesis results; blue solid lines show place-and-route (PR) results. At 16 bits, neither LUT usage nor estimated frequency varies strictly monotonically with n. For width 64 and n=2, PR setup WNS is -0.296 ns, failing the 200 MHz setup constraint. The other configurations in the supplied data meet that setup constraint.
The inputWidth axis uses equal spacing in log2; the n axis is linear.
¶ Usage permission
All code generated and delivered by this IP, including top-level RTL and inline submodule RTL, is licensed under MIT, permitting use, modification, distribution and commercial use. Copyright remains with the original rights holders. Copies or substantial portions of the code must retain the copyright notice and MIT permission notice. The code is provided as is, without warranty. See the delivered LICENSE.NthOne.txt for the full terms and NOTICE.NthOne.txt for the delivery notice.