I have some problems with a question that ask me to get the number of one's in the longest one's sequence in a 16 bit input using a 5 bit number in verilog. For example (0111011111010101 = 00101 the answer is five duo to the sequence in the middle) (1111111111111111 = 100000) I would like to know how to do it using both combinational and sequential circuits.
You can solve this question with a shift and kill method.
Let's say you have N input bits and N is 16.
Load a N bit wide shift register with your input in parallel. Add a zero bit at LSB.
0111 1010 0111 0011|0
reset your result counter to 0
Perform a 'shift' operation that expands existing zeros to the left neighbor bit.
0111 1010 0111 0011|0 0111 0000 0110 0010|0
Increment the result counter.
Check if the register is all zero.
false -> repeat step 2 and 3
true -> result counter holds your longest one sequence.
0111 1010 0111 0011|0 cnt=0 / input 0111 0000 0110 0010|0 cnt=1 0110 0000 0100 0000|0 cnt=2 0100 0000 0000 0000|0 cnt=3 0000 0000 0000 0000|0 cnt=4 / done
Minimum execution time is 1 load and 1 compare -> can be solved in 1 cycle.
Maximum execution time is 1 load and N shifts -> 17 cycles in the example.
Real execution time is 1 load and n shifts if n is the length of the longest one sequence -> 5 cycles in the example.
How to calculate the bits while shifting?
Let's name the shift register
a(0) := 0 for i in 1..N-1 a(i) := a(i) and a(i-1) next
How many hardware is used?
- N registers for a
- N LUTs for load and shift before each register
- a ld(N+1) bit counter
- a N bit zero comparator
On Xilinx hardware: Xilinx FPGAs have 6-input LUTs which can be used as 2 5-input LUTs moreover there are 2 FF per LUT. Synthesis can map a 16 bit shift register into only 2 slices and the comperator into a third slice.
As requested - a 5 bit counter
reg [4:0] counter; always @(posedge Clock) begin if(Reset) counter <= 5'b0; else if(counter_en) counter <= counter + 1; end