# How to get the longest one's sequence in verilog

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.

• 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. – Plutonium smuggler May 10 '15 at 1:55
• I am a beginner in this design language so I couldn't understand your advice. Would you please wright the code. – Ramon May 10 '15 at 12:22
• Nope. Cant really do that. Be specific what part you dont understand. – Plutonium smuggler May 10 '15 at 14:03
• 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 – Ramon May 10 '15 at 14:09
• 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. – Plutonium smuggler May 10 '15 at 14:14

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

• Didn't understand /: – Ramon May 12 '15 at 22:50
• Can you be more precise, please. I'll try to explain these parts more in detail. – Paebbels May 12 '15 at 23:20
• can u just build a 5 bits counter in verilog please – Ramon May 14 '15 at 14:00
• "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 "..") – Tut May 14 '15 at 15:31
• That's pseudo code. – Paebbels May 14 '15 at 15:51