N 位数组中的 X *连续*位设置为 1 的概率是多少？

Question

我正在尝试编写一个简单且足够准确的滤波器，用于在 RTL 模拟中验证硬件。 我们通过将设计中的所有触发器随机初始化为 0 或 1 来模拟芯片触发器固有的随机性。这对应于芯片触发器在加电期间获得一些随机值。 我们还在重置树中随机化触发器（其中重置树没有反馈循环），这意味着您可能会在重置线路上出现错误故障。

例如

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

您会看到 0->1->0，看起来像是重置，但实际上是一个故障。

我想构建一个过滤器，查找一定数量的连续 1 值，以确定我刚刚看到的重置是来自重置控制器的重置还是虚假重置。

我知道这是统计数据，可能与泊松分布有关，但如何确定一组 N 位中的任何 X 个连续位为 1 的概率？

附言：是的。 我知道 4-val RTL 模拟。 我们也在这样做，但是一些 Verilog 构造在传播 X 和 Z 时没有足够的悲观主义。

Answer 1

编辑：下面没有回答问题，抱歉...评论澄清了真正的问题是关于 n 位中 x 连续 1 的概率，而不仅仅是我假设的简单的事情。
快速浏览一下： http:// /www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html 这可能就是您正在寻找的 - 它似乎处理计算一系列的概率toin cosses 是从更多的 toin cosses 中脱颖而出的，所以听起来很相似。 但已经晚了，我累了，所以我还没有解码数学:)

过时的：
听起来你基本上是在处理二项式概率 - 请参阅 http://en.wikipedia.org/wiki/二项式概率。

我不得不承认我已经有大约 20 年没有做过计算了，所以有点生疏了......

基本上，二项式允许你将一个事件多次发生的概率“加在一起”，每次只有两种可能的结果。
顺序对于您的情况很重要，因此它应该像乘以概率一样简单；
对于 1 位来说是 50%
对于 2 位，它是 50%^2 = 25%
对于 3 位，它是 50%^3 = 12.5%

从另一个角度来看；
1位只有2种可能的组合，其中一种是全1=50%
2 位有 4 种可能的组合（10、01、11、00），其中只有一种全为 1 - 所以 25%
3 位有 2^3 = 8 种可能的组合，其中只有一种是全 1，所以 1/8 = 12.5%

所以... n 位全为 1 的概率 = 1/(2^n)。

Answer 2

如果您想快速测试一下位序列是否基于最长的 1 连续，您可以使用 N 位中预期的最长 1 连续是 θ(log(N))。

此外，最长条纹超过 r*log2(N) 位的概率至多为 1/N^(r-1)，同样，最长条纹小于 log2(N)/r 位的概率至多为1/N^(r-1)。

这些结果源自 算法介绍

Answer 3

好的，这就是我发现的：

P = 1 - Q(X)

其中

Q(X) = [1 - 1/2(Z)]/[(X + 1 - XZ) x 1/2 x Z^(X+ 1)]

其中

Z = 1 + (1/2)(1/2)^X + (X+1)[(1/2)(1/2)^X]^2 + ...

与某些的链接数学的部分在这里：

数学论坛

Answer 4

你可以做一个递归程序（python）：

prob (x,n) 给出你想要的结果

---

import math

def prob(x,n,i=0):
    if i == x: return 1
    if (x+i) > n: return 0
    t = .5 * prob(x,n-1,i+1) + .5 * prob(x,n-1,i)
    return t

Answer 5

我的方法是定义一个接受正确类型的位模式的 FSA，然后模拟每个位数的模式。 IE

State state_map[] = {
    0 => { 0 -> 0; 1 -> 1; accepts = false },
    1 => { 0 -> 0; 1 -> 2; accepts = false },
    2 => { 0 -> 0; 1 -> 3; accepts = false },
    3 => { 0 -> 3; 1 -> 3; accepts = true }
};

state[t: 0, s: 0] = 1.0;
state[t: 0, s: 1] = 0.0;
state[t: 0, s: 2] = 0.0;
state[t: 0, s: 3] = 0.0;

for (t = 0; t < N; t++)
    for (s = 0; s<NUM_STATES; s++)
        state[t: t+1, s: state_map[s].0] += state[t, s] * .5
        state[t: t+1, s: state_map[s].1] += state[t, s] * .5

print "Probability: {0}", state[t: N, s: 3],