N 비트 배열에서 X *연속* 비트가 1로 설정될 확률은 얼마입니까?
https://stackoverflow.com/questions/530356
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
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를 전파할 때 비관론이 충분하지 않습니다.
해결책
가장 긴 1의 연속을 기반으로 비트 시퀀스가 무작위인지 확인하기 위한 빠른 테스트를 원하는 경우 N 비트에서 예상되는 가장 긴 1의 연속이 Θ(log(N))라는 사실을 사용할 수 있습니다.
또한, 가장 긴 연속이 r*log2(N) 비트를 초과할 확률은 최대 1/N^(r-1)이고, 마찬가지로 가장 긴 연속이 log2(N)/r 비트보다 작을 확률은 최대 1/N^(r-1)입니다. 1/N^(r-1).
이러한 결과는 "계산 및 확률" 장의 "연속" 섹션에서 파생됩니다. 알고리즘 소개
다른 팁
편집 : 아래는 질문에 대답하지 않습니다. 죄송합니다 ... 의견은 실제 문제가의 확률에 관한 것이라고 설명했습니다. 엑스 연속 1 초 N 비트, 내가 가정 한 단순한 것뿐만 아니라. 이것을 간단히 살펴 보았습니다. 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 년 동안 계산을하지 않았다는 것을 인정해야한다.
기본적으로 Binominal을 사용하면 이벤트가 여러 번 발생했을 확률을 "함께 추가"할 수 있으며, 매번 두 가지 가능한 결과 만 있습니다. 귀하의 경우에 주문이 중요하므로 확률을 곱하는 것만 큼 간단해야합니다.
1 비트 동안 50%입니다.
2 비트의 경우 50%^2 = 25%입니다.
3 비트의 경우 50%^3 = 12.5%입니다.
다른 방법으로보십시오.
1 비트에는 2 개의 가능한 조합 만 있으며 그 중 하나는 모두 1s = 50%입니다.
2 비트에는 4 개의 가능한 조합 (10, 01, 11, 00)이 있으며 그 중 하나는 모두 1S -25%입니다.
3 비트는 2^3 = 8 가능한 조합을 가지고 있으며 그 중 하나는 모두 1이므로 1/8 = 12.5%
그래서 ... n 비트의 확률은 모두 1 = 1/(2^n)입니다.
좋아, 여기 내가 찾은 내용은 다음과 같습니다.
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 + ...
일부 수학과의 링크는 다음과 같습니다.
재귀 프로그램 (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
이것에 대한 나의 접근 방식은 올바른 유형의 비트 패턴을 받아들이는 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],
