Search code examples
statisticshardwareverification

What's the probability that X *consecutive* bits in an array of N bits is set to 1?

I'm trying to code a simple, sufficiently accurate filter for validating a piece of hardware in an RTL simulation. We're simulating the randomness inherent in a chip's flip-flops, by randomly initializing all the flip-flops in the design to either 0 or 1. This corresponds to the chip's flip-flops getting some random value during power-up. We're also randomizing the flops in the reset tree ( where reset tree has no feedback loops ), which means that you can get false glitching on your reset lines.

e.g. 

                              |||
                              VVV                          Nth reset-tree flop
          +----+       +----+       +----+        /     /    +----+ 
reset_in  |    |  0    |    |  1    |    | 0     /     /     |    | reset_out
 -------->D    Q>----->D    Q>----->D    Q>---- / ... /   -->D    Q>----
          |    |       |    |       |    |      \     \      |    |
          |    |       |    |       |    |       \     \     |    |
          +^---+       +^---+       +^---+       /     /     +^---+
           |            |            |          /     /       |
clk  ------+------------+------------+---------/     /     ---+

You'll see a 0->1->0 which looks like a reset, but is really a glitch.

I want to build a filter that looks for a certain number of consecutive 1 values to determine whether the reset I just saw was the reset coming from the reset controller or a spurious reset.

I know this is statistics and maybe related to the Poisson distribution, but how do I determine the probability that any X consecutive bits in a set of N bits are 1?

P.S. Yes. I am aware of 4-val RTL simulation. We're doing that also, but some Verilog constructs don't have sufficient pessimism when propagating X's and Z's.

Solution

  • If you want a quick test to see if a sequence of bits is random based on the longest streak of 1's, you can use the fact that the expected longest streak of 1's in N bits is Θ(log(N)).

    Furthermore, the probability that the longest streak exceeds r*log₂(N) bits is at most 1/N^(r-1), and similarly the probability that the longest streak is less than log₂(N)/r bits is at most 1/N^(r-1).

    These results are derived in the section on "Streaks" in the chapter on "Counting and Probability" in Introduction to Algorithms