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

[peto]

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.

 

[D.A.(Tony)Stewart]

Not sure of your details but any maximal length sequence using non-inverted feedback and initialized with 0 , the number of 1's is N-1 is always the largest number of 1's, for N shift stages and the sequence length is 2^N-1. Since all 1's is an invalid state.

Conversely with inverted feedback from XOR's , initial condition can be all 1's but not all 0's.

Do I have this backwards? I think I misunderstood your question.

- - - Updated - - -

http://en.m.wikipedia.org/wiki/Maximum_length_sequence

 

[peto]

i did solved the problem but to find the length of the longest sequence of consecutive ones in 4 bit but i found it harder for 16 bit
this is my verilog fo 4 bit

module consecutiveones4bit(
    input [3:0] A,
    output [2:0] B
    );

assign B[2]=A[3]&A[2]&A[1]&A[0];
assign B[1]=(~A[2]&A[1]&A[0])|(A[3]&A[2]&~A[1])|(~A[3]&A[2]&A[1]&A[0])|(A[2]&A[1]&~A[0]);
assign B[0]=(A[3]&A[1]&~A[0])|(~A[2]&~A[1]&A[0])|(~A[3]&A[2]&~A[1])|(~A[3]&A[2]&A[1]&A[0])|(~A[2]&A[1]&~A[0]);

endmodule

 

[vGoodtimes]

@SkinnySkyguy -- that is for LFSR's or things that generate sequences of values. The OP is wanting to find the longest run of 1's within a vector.

@peto -- I can't think of any really good pure combinatorial circuits. For sequential, you can use the (-(~x)) & (~x) to get the location of the rightmost 0. This can go to a binary encoder to generate a number. The maximum number and location can be saved as the input is shifted each cycle.

This could also be done with 16 circuits and a comparator tree. It would be a complex circuit overall. You could also just write a function for it and see what the synthesis tool comes up with. Sometimes that works better than a more complicated approach that you might construct.

you could also write a script that generates the logic for the 16 element case in the same way you wrote it for the 4b case.

 

[FvM]

Your approach looks like handwritten PALASM rather than Verilog. It's time to remember that Verilog is a high level description language that e.g. knows behavioral code. Here's a straightforward combinational solution:

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
module seqlength
(
   input [15:0] seq,
   output [4:0] ones
);
 
reg [4:0] ones;
integer i;
always @(*)
  begin
    ones = 0;
    count = 0;
    for (i = 0; i <= 15; i++)
      begin
        if (seq[i])
          begin
            count++;
            if (count > ones)
              ones = count;
          end
        else
          count = 0;   
      end
  end
endmodule

---

The result effectivity depends strongly on the intelligence of the synthesis tool. Most synthesis tools are not so good in optimizing non-arithmetical problem, but you get at least a correct reference design.