6

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

例如 

                              |||
                              VVV Nth 复位树触发器
          +----+ +----+ +----+ / / +----+
重置 | | 0 | | 1 | | 0 // | | 重置输出
 -------->D Q>-->D Q>----->D Q>---- / ... / -->D Q>----
          | | | | | | \ \ | |
          | | | | | | \ \ | |
          +^---+ +^---+ +^---+ / / +^---+
           | | | // |
clk ------+------------+------------+---------/ / ---+

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

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

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

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

4

5 回答 5

3

编辑：下面没有回答这个问题，对不起......评论澄清了真正的问题是关于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/Binomial_probability。

我不得不承认我已经有大约 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)。

于 2009-02-09T22:46:14.330 回答
2

好的，这就是我发现的：

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

一些数学的链接在这里：

数学论坛

于 2009-02-09T22:35:40.173 回答
2

如果您想快速测试以查看基于 1 的最长条纹的位序列是否是随机的，您可以使用 N 位中 1 的预期最长条纹为 Θ(log(N)) 的事实。

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

这些结果是在“算法简介”中“计数和概率”一章的“条纹”部分得出的

于 2009-02-09T23:30:52.257 回答
0

你可以做一个递归程序（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
于 2009-02-09T22:53:13.033 回答
0

我的方法是定义一个接受正确类型的位模式的 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],
于 2009-02-10T00:15:15.833 回答