Pasar un mensaje binario a un amigo donde uno de los componentes está siempre "encendido"

Question

Supongamos que quiero comunicar a un amigo un número entero entre 1 y 1000. Para pasar este mensaje utilizo un $k$ -vector cuyas entradas pueden establecerse en $0$ o $1$ . Así, por ejemplo, si $k=3$ una forma natural de expresar el número $7$ es $\langle 1,1,0\rangle$ donde esto corresponde a la representación binaria $2^2+2^1+2^0$ para $7$ .

Sin embargo, ¡hay una arruga! Antes de que mi amigo pueda ver mi vector, debe pasarlo por una función $f_i$ que es la identidad en todos los componentes que no son iguales a $i$ y que establece el $i$ -a componente a $1$ . Por ejemplo, $f_1(\langle 1,1,0\rangle) = \langle 1,1,0\rangle$ pero $f_3(\langle 1,1,0\rangle) = \langle 1,1,1\rangle$ .

Es fundamental que el valor de $i$ es desconocido tanto para mí como para mi amigo. El desafío es:

¿Cuál es el menor $k$ para que mi amigo pueda entender siempre mi número?

Mi proceso de pensamiento:

Está claro que si no hubiera ningún error $k=10$ sería suficiente. Si simplemente quisiera que mi amigo supiera si el mensaje fue cambiado $k=11$ sería suficiente, ya que estaría de acuerdo en representar todos los números utilizando un $1$ -representación uniforme (es decir, una $k$ -binario con un número par de $1$ s) y si mi amigo recibiera un número impar conocería a uno de los $1$ s se habrían modificado.

Por supuesto que debe ser capaz de recuperar un mensaje confuso. Por lo tanto, todos los $1$ -incluso vectores que podrían haber "degenerado" plausiblemente en un $1$ -El vector impar debe considerarse equivalente. Por lo tanto, creo que se puede reducir el problema a problemas más pequeños. Sea $A^k_j$ sea el conjunto de todos los $k$ -vectores con exactamente $j$ los. Para todos incluso $j<k$ ¿Cuál es el mayor subconjunto $S_j^k\subset A_j^k$ de manera que no haya dos elementos de $S_j^k$ puede degenerar en el mismo vector en $A_{j+1}^k$ . Si resolvemos esto, entonces podemos sumar estas cardinalidades máximas sobre todos los pares $j$ y obtener el resultado.

Sin embargo, ¡no está claro cómo terminar! Soy consciente de que esto parece vagamente relacionado con los códigos de corrección de errores y la distancia de Hamming - creo que el problema reducido puede reducirse plausiblemente a una pregunta sobre subconjuntos del grupo de permutación. Pero no consigo entenderlo...

Editar : Claramente puedes dejar $k=22$ y sólo repite su mensaje dos veces, restringiendo el mensaje a ser 1-par. Este es un límite superior muy burdo. Estoy seguro de que se puede hacer mucho mejor que esto...

Actualización: Actualmente se puede llegar a un precio tan bajo como $k=15$

Puedo hacer $k=15$ como sigue: Sea $\mathbf{v}$ sea su original $k$ -vectorial. Primero se codifica el mensaje como un $1$ -incluso el mensaje con la primera $11$ dígitos. Si el mensaje no está corrompido, tu amigo lo sabrá y habrás terminado. Si está corrompido, el resto de $4$ dígale a su amigo el valor de $\sum_{i=1}^{11} v_i \cdot i \ (\text{mod} 10),$ a partir de la cual se puede inferir qué dígito fue volteado.

Answer 1

Permítanme usar, como siempre, $k$ para los "bits de datos" y $n$ para el total de bits enviados, con $n-k$ siendo la redundancia.

$n=14$ bits debería ser suficiente

Toma $k=10$ , $n-k=4$ . Construir una comprobación de paridad Hamming con $n-k=4$ filas, colocando el $2^4$ columnas distintas, excepto la columna nula y alguna columna extra (elegí la columna todos-uno) :

$$H=\begin{pmatrix} 1&0&0&0&1&1&1&0&0&0&1&1&1&0\\ 0&1&0&0&1&0&0&1&1&0&1&1&0&1\\ 0&0&1&0&0&1&0&1&0&1&1&0&1&1\\ 0&0&0&1&0&0&1&0&1&1&0&1&1&1 \end{pmatrix}=( I_4 \mid P) $$

La matriz generadora correspondiente es

$$ G= (P^t \, | \, I_{10})$$

Este código lineal (un código Hamming abreviado) tiene una distancia $d=3$ (porque hay que elegir al menos tres columnas de $H$ para obtener un conjunto linealmente dependiente), por lo que se puede corregir un único error. (No sólo $0\to 1$ pero también $1 \to 0$ )

Y puedes trasmitir $2^k=1024$ valores (más de $1000$ ).

Como esta codificación corrige más errores de los necesarios (tenemos una especie de canal Z, en lugar de un canal BSC), queda por ver si $n$ puede reducirse aún más.

---

Actualización. $n=13$ no es suficiente. Existe cierta literatura sobre este escenario, un código (no necesariamente lineal) para un canal Z, con capacidad de corrección de un solo error. Se han encontrado varios límites y métodos de construcción. Un estudio de 1983 (actualizado en 1995) puede encontrarse en el informe Códigos de corrección de errores para el canal asimétrico (Torleiv Kløve) . Una tabla en la página 38, muestra que, para nuestro escenario, $n=14$ es suficiente para enviar al menos $M=1096$ mensajes (una ligera mejora respecto a mi simple código Hamming acortado), un límite superior es $M\le 1500$ . Para $n=13$ un límite superior es $M\le 786$ (por lo que no podemos enviar 1000 mensajes), y la mejor construcción encontrada da sólo $M=586$ . Un documento más reciente (2009) en ruso, aquí .

Answer 2

[De acuerdo, modifico mi respuesta tan subóptima (que di después de leer mal la pregunta y utilizar k=30 de forma trivial)].

Esta es mi nueva solución con k=14 (que en mis comentarios demostré que no se puede mejorar) [veo que leonbloy ya publicó una solución con k=14 usando el código Hamming, la mía va más en la dirección que intentó anteriormente el OP].

Dejemos que $\{v_i\}_{i=1}^{10}$ los 10 componentes (0's y 1's) de su vector binario. Sea $x$ sea $$ x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10} $$ (nótese que he omitido los coeficientes que son potencias exactas de 2). A continuación, calcule $y = x \pmod{16}$ Exprésalo como un número binario de 4 bits y añádelo a tu cadena. Obtienes una cadena binaria de 14 bits y se la envías a tu amigo. Tu amigo calcula $x \pmod{16}$ y lo compara con $y$ de la cuerda que recibe. Si la diferencia no es una potencia de 2, le indica qué coeficiente falta en la fórmula utilizada para calcular su $x$ y qué bit ha sido alterado en su vector original. Si es una potencia de 2, entonces la parte alterada es $y$ y su vector original no ha sido modificado.

¿Funcionaría?

Answer 3

Puede que no sea lo mejor posible, pero creo que funciona.

[ Añadido : Después de publicar mi respuesta, vi que el OP encontró una estrategia similar, pero mejor, para enviar el mensaje usando un bit menos].

Codificar el número $N$ como $10$ - base de bits. $2$ valor $b_1b_2\dots b_{10}$ y, a continuación, enviar un $16$ -bit que comprende su número seguido de la representación binaria de $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$ (que está entre $0$ y $55$ , por lo que requiere $6$ bits). Comparta la fórmula de $f$ con tu amigo.

Su amigo descifra el primer $10$ bits del mensaje como $x$ y el último $6$ bits como $F$ . Si $F=f(x)$ , entonces su mensaje era $x$ . Si $F<f(x)$ , entonces a $0$ un poco de $x$ se ha ajustado a $1$ durante la transmisión. El valor de $f(x)-F$ te dice qué parte era, y $N=x-2^{10-f(x)+F}$ . Si $F>f(x)$ , a $0$ un poco de $f(N)$ se fijó durante la transmisión, y $N=x$ .