How to get the longest one's sequence in verilog

Question

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.

• Plutonium smuggler: A typical FSM kinda problem. You can take one register array holding the no of ones so far. Whenever a 1 comes, increment a counter. If a zero comes, compare counter with register, and if it is larger than reg, overwrite it. This is one of many possible ways.
• Ramon: I am a beginner in this design language so I couldn't understand your advice. Would you please wright the code.
• Plutonium smuggler: Nope. Cant really do that. Be specific what part you dont understand.
• Ramon: Ok first of all i have to use xlinix. second i don't know how to make the module count a series of ones and then stop when a zero comes then start counting again and comparing the second result with the first one
• Plutonium smuggler: Looks like you are just getting started using verilog. I would say you get some good book like this -> amazon.com/FPGA-Prototyping-Verilog-Examples-Spartan-3/dp/… .....and spend some time learning synthesis using verilog.

Answer 1

You can solve this question with a shift and kill method.

Let's say you have N input bits and N is 16.

Step 1)
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

Step 2)
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.

Step 3)
Check if the register is all zero.
false -> repeat step 2 and 3
true -> result counter holds your longest one sequence.

Example:

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.

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

• Ramon: Didn't understand /:
• Paebbels: Can you be more precise, please. I'll try to explain these parts more in detail.
• Ramon: can u just build a 5 bits counter in verilog please
• Tut: "for i in 1..N-1" ... That's not the syntax I'm familiar with for a Verilog for statement. Is this VHDL? (I'm not too sure about the "..")
• Paebbels: That's pseudo code.