PUERTA | PUERTA-CS-2004 | Pregunta 78

Dos strings binarias de n bits, S1 y S2, se eligen aleatoriamente con probabilidad uniforme. La probabilidad de que la distancia de Hamming entre estas strings (el número de posiciones de bit donde difieren las dos strings) sea igual a d es
(A) nCd /2 ⁿ
(B) nCd / ^d
(C) d/2 ⁿ
(D) 1 /2 ^d

Respuesta: (A)
Explicación: La distancia de hamming de las strings S1 y S2 puede tener cualquier valor entre 0 y n.
La distancia de Hamming es el número de bits diferentes entre dos strings. Para una string dada y una distancia d, puede haber strings C (n, d) que tengan d como la distancia de hamming a partir de n bits, se debe elegir cualquier d.
Para cualquier string S1, hay:
C(n,0) strings con 0 distancia de hamming
C(n,1) strings con 1 distancia de hamming
C(n,2) strings con 2 distancia de hamming
.
.
Strings C(n,n) con distancia de hamming n
Strings totales = C(n,0) + C(n,1) + … + C(n,n) =
Strings con distancia de hamming d = C(n,d)
Por lo tanto probabilidad =
prueba de esta pregunta