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.
我正在尝试编写一个简单,足够精确的过滤器,用于验证RTL仿真中的硬件。我们通过将设计中的所有触发器随机初始化为0或1来模拟芯片触发器中固有的随机性。这对应于芯片的触发器在上电期间获得一些随机值。我们还将重置树中的触发器随机化(其中重置树没有反馈循环),这意味着您可以在重置线上获得错误的毛刺。
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.
你会看到一个0-> 1-> 0看起来像一个重置,但实际上是一个小故障。
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.
我想构建一个过滤器,查找一定数量的连续1值,以确定我刚刚看到的复位是复位控制器复位还是复位复位。
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?
我知道这是统计数据,可能与泊松分布有关,但我如何确定一组N位中任何X个连续位为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.
附:是。我知道4-val RTL仿真。我们也这样做,但是一些Verilog构造在传播X和Z时没有足够的悲观情绪。
5 个解决方案
#1
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)).
如果你想根据1的最长条纹进行快速测试以查看比特序列是否是随机的,你可以使用N比特中预期的最长条纹1是Θ(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).
此外,最长条纹超过r * log 2(N)位的概率最多为1 / N ^(r-1),类似地,最长条纹小于log 2(N)/ r位的概率最多1 / N ^(R-1)。
These results are derived in the section on "Streaks" in the chapter on "Counting and Probability" in Introduction to Algorithms
这些结果来自算法导论中“计数和概率”一章中的“条纹”部分。
#2
EDIT: The below doesn't answer the question, sorry... Comment clarified that the real problem is about the probability of x consecutive 1s out of n bits, not just the simple thing I assumed. Had a quick look at this: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html which may be what you are looking for - it seems to deal with working out the probability of a run of toin cosses out of a larger population of toin cosses, so sounds similar. But its late and I am tired so I haven't decoded the math :)
编辑:下面没有回答这个问题,对不起......评论澄清说真正的问题是关于n位中x连续1的概率,而不仅仅是我假设的简单事情。快速浏览一下:http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html这可能就是你想要的东西 - 似乎要解决这个问题由于角色成本较大,所以听起来很有可能。但它已经很晚了我累了所以我没有解码数学:)
OBSOLETE: It sounds like you are basically dealing with binominal probability - see http://en.wikipedia.org/wiki/Binomial_probability.
OBSOLETE:听起来你基本上处理的是二项式概率 - 请参阅http://en.wikipedia.org/wiki/Binomial_probability。
I have to admit I haven't done the calculations for about 20 years, so somewhat rusty...
我不得不承认我已经做了大约20年的计算,所以有点生锈......
Basically, binominal allows you to "add together" the probability of an event occuring multiple times, where there is only two possible outcomes each time. Order is significant in your case so it should be as simple as multiplying the probabilites;
For 1 bit it is 50%
For 2 bits it is 50%^2 = 25%
For 3 bits it is 50%^3 = 12.5%
基本上,二项式允许您将事件发生概率“加在一起”多次,每次只有两种可能的结果。在你的情况下,命令很重要,所以它应该像乘以概率一样简单; 1位为50%2位为50%^ 2 = 25%3位为50%^ 3 = 12.5%
Look at it another way;
1 bit only has 2 possible combinations, one of which is all 1s = 50%
2 bits have 4 possible combinations (10, 01, 11, 00), only one of which is all 1s - so 25%
3 bit have 2^3 = 8 possible combinations, only one of which is all 1s, so 1/8 = 12.5%
另一种方式看待它; 1位只有2种可能的组合,其中一种是1s = 50%2位有4种可能的组合(10,01,11,00),其中只有一种是全1 - 所以25%3位有2 ^ 3 = 8种可能的组合,其中只有一种是全1,所以1/8 = 12.5%
So... probability of n bits all being 1 = 1/(2^n).
所以...... n位的概率都是1 = 1 /(2 ^ n)。
#3
OK, here's what I found:
好的,这是我找到的:
P = 1 - Q(X)
P = 1 - Q(X)
where
Q(X) = [1 - 1/2(Z)]/[(X + 1 - XZ) x 1/2 x Z^(X+1)]
Q(X)= [1 - 1/2(Z)] / [(X + 1 - XZ)x 1/2 x Z ^(X + 1)]
where
Z = 1 + (1/2)(1/2)^X + (X+1)[(1/2)(1/2)^X]^2 + ...
Z = 1 +(1/2)(1/2)^ X +(X + 1)[(1/2)(1/2)^ X] ^ 2 + ......
The link with some of the math is here:
一些数学的链接在这里:
#4
you can do a recursive program (python):
你可以做一个递归程序(python):
prob (x,n) gives your desired result
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
#5
My approach to this would be to define a FSA that accepts bit patterns of the correct type, and then simulate the pattern for each number of bits. i.e.
我的方法是定义一个接受正确类型的位模式的FSA,然后模拟每个位数的模式。即
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],
#1
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)).
如果你想根据1的最长条纹进行快速测试以查看比特序列是否是随机的,你可以使用N比特中预期的最长条纹1是Θ(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).
此外,最长条纹超过r * log 2(N)位的概率最多为1 / N ^(r-1),类似地,最长条纹小于log 2(N)/ r位的概率最多1 / N ^(R-1)。
These results are derived in the section on "Streaks" in the chapter on "Counting and Probability" in Introduction to Algorithms
这些结果来自算法导论中“计数和概率”一章中的“条纹”部分。
#2
EDIT: The below doesn't answer the question, sorry... Comment clarified that the real problem is about the probability of x consecutive 1s out of n bits, not just the simple thing I assumed. Had a quick look at this: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html which may be what you are looking for - it seems to deal with working out the probability of a run of toin cosses out of a larger population of toin cosses, so sounds similar. But its late and I am tired so I haven't decoded the math :)
编辑:下面没有回答这个问题,对不起......评论澄清说真正的问题是关于n位中x连续1的概率,而不仅仅是我假设的简单事情。快速浏览一下:http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html这可能就是你想要的东西 - 似乎要解决这个问题由于角色成本较大,所以听起来很有可能。但它已经很晚了我累了所以我没有解码数学:)
OBSOLETE: It sounds like you are basically dealing with binominal probability - see http://en.wikipedia.org/wiki/Binomial_probability.
OBSOLETE:听起来你基本上处理的是二项式概率 - 请参阅http://en.wikipedia.org/wiki/Binomial_probability。
I have to admit I haven't done the calculations for about 20 years, so somewhat rusty...
我不得不承认我已经做了大约20年的计算,所以有点生锈......
Basically, binominal allows you to "add together" the probability of an event occuring multiple times, where there is only two possible outcomes each time. Order is significant in your case so it should be as simple as multiplying the probabilites;
For 1 bit it is 50%
For 2 bits it is 50%^2 = 25%
For 3 bits it is 50%^3 = 12.5%
基本上,二项式允许您将事件发生概率“加在一起”多次,每次只有两种可能的结果。在你的情况下,命令很重要,所以它应该像乘以概率一样简单; 1位为50%2位为50%^ 2 = 25%3位为50%^ 3 = 12.5%
Look at it another way;
1 bit only has 2 possible combinations, one of which is all 1s = 50%
2 bits have 4 possible combinations (10, 01, 11, 00), only one of which is all 1s - so 25%
3 bit have 2^3 = 8 possible combinations, only one of which is all 1s, so 1/8 = 12.5%
另一种方式看待它; 1位只有2种可能的组合,其中一种是1s = 50%2位有4种可能的组合(10,01,11,00),其中只有一种是全1 - 所以25%3位有2 ^ 3 = 8种可能的组合,其中只有一种是全1,所以1/8 = 12.5%
So... probability of n bits all being 1 = 1/(2^n).
所以...... n位的概率都是1 = 1 /(2 ^ n)。
#3
OK, here's what I found:
好的,这是我找到的:
P = 1 - Q(X)
P = 1 - Q(X)
where
Q(X) = [1 - 1/2(Z)]/[(X + 1 - XZ) x 1/2 x Z^(X+1)]
Q(X)= [1 - 1/2(Z)] / [(X + 1 - XZ)x 1/2 x Z ^(X + 1)]
where
Z = 1 + (1/2)(1/2)^X + (X+1)[(1/2)(1/2)^X]^2 + ...
Z = 1 +(1/2)(1/2)^ X +(X + 1)[(1/2)(1/2)^ X] ^ 2 + ......
The link with some of the math is here:
一些数学的链接在这里:
#4
you can do a recursive program (python):
你可以做一个递归程序(python):
prob (x,n) gives your desired result
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
#5
My approach to this would be to define a FSA that accepts bit patterns of the correct type, and then simulate the pattern for each number of bits. i.e.
我的方法是定义一个接受正确类型的位模式的FSA,然后模拟每个位数的模式。即
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],