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

Status
Not open for further replies.

peto

Newbie level 2
Joined
May 16, 2015
Messages
2
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Visit site
Activity points
14
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.
 

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
 

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
Code:
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
 

@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.
 

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.
 

Status
Not open for further replies.
Cookies are required to use this site. You must accept them to continue using the site. Learn more…