statistics - nito - switch ensemble stars
¿Cuál es la probabilidad de que X*consecutivos*bits en una matriz de N bits se establezca en 1? (5)
Intento codificar un filtro simple y suficientemente preciso para validar una pieza de hardware en una simulación de RTL. Estamos simulando la aleatoriedad inherente en los flip-flops de un chip, inicializando aleatoriamente todos los flip-flops en el diseño a 0 o 1. Esto corresponde a los flip-flops del chip obteniendo algún valor aleatorio durante el encendido. También aleatorizamos los fracasos en el árbol de reinicio (donde el árbol de reinicio no tiene bucles de retroalimentación), lo que significa que puede obtener fallas falsas en las líneas de restablecimiento.
p.ej
||| VVV Nth reset-tree flop +----+ +----+ +----+ / / +----+ reset_in | | 0 | | 1 | | 0 / / | | reset_out -------->D Q>----->D Q>----->D Q>---- / ... / -->D Q>---- | | | | | | / / | | | | | | | | / / | | +^---+ +^---+ +^---+ / / +^---+ | | | / / | clk ------+------------+------------+---------/ / ---+
Verás un 0-> 1-> 0 que parece un reinicio, pero es realmente un problema.
Quiero construir un filtro que busque un cierto número de valores 1 consecutivos para determinar si el reinicio que acabo de ver fue el reinicio proveniente del controlador de restablecimiento o un restablecimiento espurio.
Sé que esto son estadísticas y tal vez están relacionadas con la distribución de Poisson, pero ¿cómo determino la probabilidad de que X bits consecutivos en un conjunto de N bits sean 1?
PD Sí. Soy consciente de la simulación RTL de 4 valores. También lo estamos haciendo, pero algunas construcciones de Verilog no tienen suficiente pesimismo al propagar X''s y Z''s.
EDITAR: Lo siguiente no responde la pregunta, lo siento ... Comentario clarificó que el problema real es sobre la probabilidad de x 1 consecutivos de n bits, no solo lo simple que asumí. Eché un vistazo rápido a esto: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html, que puede ser lo que estás buscando, parece tratar con ejercicio la probabilidad de una corrida de costas toin fuera de una población mayor de coses toin, por lo que suena similar. Pero es tarde y estoy cansado, así que no he decodificado las matemáticas :)
OBSOLETO: Parece que básicamente se trata de una probabilidad binominal: consulte http://en.wikipedia.org/wiki/Binomial_probability .
Debo admitir que hace 20 años que no hago los cálculos, algo oxidados ...
Básicamente, binominal le permite "sumar" la probabilidad de que un evento ocurra varias veces, donde solo hay dos posibles resultados cada vez. El orden es importante en su caso, por lo que debe ser tan simple como multiplicar las probabilidades;
Por 1 bit es 50%
Para 2 bits es 50% ^ 2 = 25%
Para 3 bits es 50% ^ 3 = 12.5%
Míralo de otra manera;
1 bit solo tiene 2 combinaciones posibles, una de las cuales es 1s = 50%
2 bits tienen 4 combinaciones posibles (10, 01, 11, 00), solo uno de los cuales es todo 1, entonces 25%
3 bits tienen 2 ^ 3 = 8 combinaciones posibles, de las cuales solo una es 1, entonces 1/8 = 12.5%
Entonces ... la probabilidad de n bits es 1 = 1 / (2 ^ n).
OK, esto es lo que encontré:
P = 1 - Q (X)
dónde
Q (X) = [1 - 1/2 (Z)] / [(X + 1 - XZ) x 1/2 x Z ^ (X + 1)]
dónde
Z = 1 + (1/2) (1/2) ^ X + (X + 1) [(1/2) (1/2) ^ X] ^ 2 + ...
El enlace con algunas de las matemáticas está aquí:
Si desea una prueba rápida para ver si una secuencia de bits es aleatoria en función de la racha más larga de 1, puede usar el hecho de que la racha más larga esperada de 1 en N bits es Θ (log (N)).
Además, la probabilidad de que la racha más larga exceda r * log₂ (N) bits es como máximo 1 / N ^ (r-1), y de manera similar la probabilidad de que la racha más larga sea menor que log₂ (N) / r bits es como máximo 1 / N ^ (r-1).
Estos resultados se derivan en la sección sobre "Rayas" en el capítulo sobre "Contar y Probabilidad" en Introducción a Algoritmos
Mi enfoque para esto sería definir una FSA que acepte patrones de bits del tipo correcto, y luego simular el patrón para cada número de bits. es decir
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],
puedes hacer un programa recursivo (python):
prob (x, n) da el resultado deseado
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