Sensores de 3 bits -- Una pregunta sobre la distancia de Hamming en las señales

Question

Me encontré con esta pregunta en el acertijo de Willy Wu sitio

Tienes dos sensores de 3 bits, A y B, que miden lo mismo, sea lo que sea: la temperatura de la habitación, los niveles de radiactividad, lo que sea. Ambos sensores están conectados a la misma CPU, que toma las lecturas de los sensores. Sabes que los sensores están diseñados para que sus lecturas puedan estar fuera de lugar como máximo un bit. Afirmamos que si B sabe que A ha enviado a la CPU una secuencia de 3 bits, entonces B sólo necesita enviar 2 bits, y la CPU será capaz de reconstruir la medición de 3 bits de B, conservando así el ancho de banda. ¿Cómo es esto?

Esto fue aparentemente una pregunta a nivel de investigación del profesor de Wu, así que dudo que esté malinterpretando una simple pregunta de encontrar una biyección de 4 elementos.

Entiendo que el primer bit no es el más significativo (eso sería trivial), son 3 bits independientes, y las mediciones de A y B difieren de la real como máximo en 1 bit en algún lugar. Así que digamos que la medida real era [111], A puede ser [101] y B puede ser [011].

Si consideramos la distancia Hamming entre A y B, la distancia máxima entre A y B es 2, la mínima es 0. (A partir de ahora me referiré a "la distancia Hamming entre A y B" como "distancia Hamming" para simplificar).

A primera vista, parece una tarea imposible representar todos los valores posibles de B dado A. Es decir, si se toma A XOR B, se obtendrán 7 posibilidades {000, 001, 010, 011, 100, 101, 110}.

Creo que de alguna manera los 3 bits que A pasa a la CPU deben contener también información sobre los 3 bits de B. Tal vez podríamos definir de forma única a B por los posibles valores de la medida real.

También he observado que cuando la distancia de Hamming es 2, hay 2 posibles medidas reales, y difieren en una distancia de Hamming de 2. Cuando la distancia de Hamming es 1, hay 2 posibles valores reales y difieren en una distancia de Hamming de 1. Cuando la distancia de Hamming es 0, hay 4 posibles valores reales y difieren en una distancia de Hamming de 1.

¿Alguna idea?

(Además, me disculpo de antemano si he pasado por alto algunas reglas o normas. Por favor, disculpadme ya que es la primera vez que posteo).

Answer 1

Suponiendo que su lectura del planteamiento del problema sea correcta:

$B$ y $A$ pueden diferir en 1 bit (o en ninguno), por lo que la diferencia (A XOR B) puede tomar cuatro valores posibles (000 001 010 100) . B sólo necesita codificar estos 4 valores, y puede hacerlo con 2 bits.

Por supuesto, esto requiere que B conozca el valor de A (no está claro que lo conozca)

---

Actualización: mejor aún (esto no requiere que B conozca a A)

Dejemos que $B=(b_1,b_2,b_3)$ Trasladar $C=(c_1,c_2)$ donde $c_1 = b_1 \oplus b_3$ , $c_2 = b_2 \oplus b_3$

En el lado del receptor, compara $c_1$ y $c_2$ con los valores análogos para A: $c'_1=a_1 \oplus a_3$ , $c'_2 =a_2\oplus a_3$ Esto es suficiente para reconstruir B

Si $c'_1 = c_1$ y $c'_2 = c_2$ entonces no se cambiaron los bits ( $A=B$ )

Si $c'_1 \ne c_1$ y $c'_2 = c_2$ entonces el bit 1 ha cambiado.

Si $c'_1 \ne c_1$ y $c'_2 = c_2$ entonces el bit 2 ha cambiado.

Si $c'_1 \ne c_1$ y $c'_2 \ne c_2$ entonces el bit 3 ha cambiado.