Какова вероятность того, что X * последовательных * битов в массиве из N битов установлено в 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 значений, чтобы определить, был ли только что сброшенный сброс, сброс, исходящий от контроллера сброса, или ложный сброс.

Я знаю, что это статистика и, возможно, она связана с распределением Пуассона, но как определить вероятность того, что любые X последовательных битов в наборе из N битов равны 1?

P.S. Да. Я в курсе 4-валовой RTL симуляции. Мы также делаем это, но некоторые конструкции Verilog не имеют достаточного пессимизма при распространении X и Z.

Answer 1

РЕДАКТИРОВАТЬ: ниже не отвечает на вопрос, извините ... Комментарий пояснил, что реальная проблема заключается в вероятности x последовательных 1 с из n бит, а не просто простая вещь, которую я предположил. Если бы вы быстро взглянули на это: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html, что может быть тем, что вы ищете - похоже, он имеет дело с вычислением вероятности пробега контуров из большой популяции контуров, поэтому звучит похоже. Но уже поздно, и я устал, поэтому я не расшифровал математику:)

ИСП: Похоже, вы в основном имеете дело с биноминальной вероятностью - см. 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).

Answer 2

Если вы хотите провести быстрый тест, чтобы определить, является ли последовательность битов случайной на основе самой длинной серии 1, вы можете использовать тот факт, что ожидаемая самая длинная серия из 1 в N битах равна Θ (log (N)).

Кроме того, вероятность того, что самая длинная полоса превышает r * log₂ (N) битов, составляет самое большее 1 / N ^ (r-1), и аналогично вероятность того, что самая длинная полоса меньше, чем log₂ (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

Мой подход к этому состоял бы в том, чтобы определить 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], 

Answer 5

вы можете сделать рекурсивную программу (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