Xác suất mà các bit X * liên tiếp * trong một mảng N bit được đặt là 1 là bao nhiêu?

Question

Tôi đang cố gắng mã hóa một bộ lọc đơn giản, đủ chính xác để xác thực một phần cứng trong mô phỏng RTL. Chúng tôi đang mô phỏng tính ngẫu nhiên vốn có trong các flip-flops của chip, bằng cách khởi tạo ngẫu nhiên tất cả các flip-flops trong thiết kế là 0 hoặc 1. Điều này tương ứng với các flip-flops của chip nhận được một số giá trị ngẫu nhiên trong khi khởi động. Chúng tôi cũng chọn ngẫu nhiên các thất bại trong cây đặt lại (nơi cây đặt lại không có vòng phản hồi), điều đó có nghĩa là bạn có thể gặp trục trặc sai trên các đường đặt lại của mình.

ví dụ:

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

Bạn sẽ thấy 0-> 1-> 0 trông giống như đặt lại nhưng thực sự là trục trặc.

Tôi muốn tạo bộ lọc tìm kiếm một số lượng nhất định liên tiếp 1 giá trị để xác định xem việc đặt lại tôi vừa xem là cài đặt lại từ bộ điều khiển đặt lại hoặc đặt lại giả.

Tôi biết đây là số liệu thống kê và có thể liên quan đến phân phối Poisson, nhưng làm cách nào để xác định xác suất mà bất kỳ bit X liên tiếp nào trong một bộ N bit là 1?

P.S. Vâng. Tôi biết về mô phỏng RTL 4-val. Chúng tôi đang làm điều đó cũng có, nhưng một số cấu trúc Verilog không có đủ bi quan khi tuyên truyền của X và Z.

Answer 1

Nếu bạn muốn có một thử nghiệm nhanh chóng để xem nếu một chuỗi các bit là ngẫu nhiên dựa trên chuỗi dài nhất của 1, bạn có thể sử dụng thực tế là chuỗi dài nhất mong đợi của 1 trong N bit là Θ (log (N)).

Hơn nữa, xác suất có chuỗi dài nhất vượt quá r * log₂ (N) bit tối đa là 1/N^(r-1), và tương tự xác suất mà vệt dài nhất nhỏ hơn log₂ (N)/r bit tối đa là 1/N^(r-1).

Các kết quả này được rút ra trong phần trên "Vệt" trong chương về "Đếm và xác suất" trong Introduction to Algorithms

Answer 2

OK, đây là những gì tôi thấy:

P = 1 - Q (X)

nơi

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

nơi

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

Các liên kết với một số các toán là ở đây:

Math Forum

Answer 3

EDIT: dưới đây không trả lời câu hỏi, xin lỗi ... Bình luận làm rõ rằng vấn đề thực sự là về khả năng x 1s liên tiếp trong số n bit, không chỉ là điều đơn giản mà tôi đã giả định. Đã xem nhanh điều này: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html có thể là những gì bạn đang tìm kiếm - có vẻ như để đối phó với việc làm việc ra xác suất của một hoạt động của toin cosses ra khỏi một dân số lớn hơn của toin cosses, do đó, âm thanh tương tự. Nhưng cuối của nó và tôi mệt mỏi vì vậy tôi đã không giải mã toán học :)

OBSOLETE: Có vẻ như bạn đang cơ bản đối phó với xác suất nhị thức - xem http://en.wikipedia.org/wiki/Binomial_probability.

Tôi phải thừa nhận tôi đã không thực hiện các tính toán trong khoảng 20 năm, vì vậy hơi gỉ ...

Về cơ bản, binominal cho phép bạn "gắn với nhau" xác suất của một sự kiện xảy ra nhiều lần, nơi chỉ có hai kết quả có thể mỗi lần. Thứ tự quan trọng trong trường hợp của bạn vì vậy nó phải đơn giản như nhân các xác suất;
Đối với 1 cắn nó là 50%
Đối với 2 bit nó là 50%^2 = 25%
Đối với 3 bit nó là 50%^3 = 12,5%

Hãy nhìn vào nó một cách khác;
1 bit chỉ có 2 tổ hợp có thể, một trong số đó là tất cả 1s = 50%
2 bit có 4 tổ hợp có thể (10, 01, 11, 00), chỉ một trong số đó là tất cả 1s - vì vậy 25%
3 bit có 2^3 = 8 kết hợp có thể, chỉ một trong số đó là tất cả 1s, vì vậy 1/8 = 12.5% ​​

Vì vậy ... xác suất bit n tất cả là 1 = 1/(2^n).

Answer 4

bạn có thể làm một chương trình đệ quy (python):

prob (x, n) cho kết quả mong muốn của bạ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

cách tiếp cận của tôi để này sẽ được xác định một FSA chấp nhận mẫu bit của đúng loại, và sau đó mô phỏng mẫu cho mỗi số bit. tức là

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],