código corrector de errores

Question

Tengo el siguiente código de corrección de errores: $$\begin{array}{c|c} 00&00000\\ 01&01101\\ 10&10110\\ 11&11011 \end{array}$$

Yo debía mostrar, que cada error en 2 posiciones no pueden ser (único) corregido.

Así, el código 00111 se puede correlacionar con 01 o con 10.

La prueba evidente, es comprobar cualquier posible error, pero supongo que tiene que haber algo más bonito.

Yo sé, que cada $a\in \{0,1\}^5$ tiene un hamming distancia $<=1$ a una de las palabras de código, excepto 10001 y 01010. Puedo utilizar alguna de este hecho?

---

EDIT: Hoy nuestro tutor nos mostró un muy breve y sencilla solución.

Si usted mira la matriz de la libre de errores códigos, $$\begin{array}{ccccc} 0&0&0&0&0\\ 0&1&1&0&1\\ 1&0&1&1&0\\ 1&1&0&1&1 \end{array}$$ usted puede notar que hay exactamente dos 1s y dos ceros (0) en cada columna. Si tomamos uno de los 4 códigos y agregue un error, el hamming distancia a dos de los otros árbol de códigos de disminuir al 1, y el hamming distancia a la tercera palabra se aumentará en 1. Si repetimos este procedimiento, lo mismo va a suceder. Porque sólo hay otros tres del código de palabras, el hamming distancia a uno de los tres será disminuir por 2 (principio del palomar). El max. hamming distancia beweet dos del código, de las palabras es $\le 4$, de modo que existe un código de palabras con hamming distancia $\le 4-2 = 2$.

Answer 1

En $\{0,1\}^5$, $4$ código de palabras sin error. Cada error-libre de palabra de código es adyacente a $5$ código de palabras con exactamente un error. Mediante la observación de la $\binom{4}{2}=6$ pares de error de código libre de palabras, no hay código de palabra con un error es adyacente a dos de error de código libre de palabras, ya que los pares de diferencias de la libre de errores de código las palabras tienen al menos tres 1. En este punto nos han contado que el error de código libre de palabras y el error-1 palabras de código de cuenta para $24$ códigos, dejando $8$ código de palabras que tengan un error de $\ge2$.

Si pudiéramos identificar a estos $8$ palabras de código y demostrar que cada uno se distancia de 2 de dos de error de código libre de palabras, creo que hemos establecido lo que usted está tratando de establecer. Los comentarios se han identificado dos de los infractores del código de palabras; se puede encontrar cuatro más?

De nuevo a través de la observación, 00000 y 11011 son 4 unidades de distancia. Así que hay $\binom{4}{2}$ palabras de código que están a medio camino entre ellos: 11000, 10010, 10001, 01010, 01001, y 00011. Mediante la observación de la comparación con los otros dos libres de errores código de palabras, algunas de estas son, de hecho, error-2 código de palabras: 11000, 10001, 01010, y 00011. Sólo tenemos cuatro error $\ge2$ código wordsleft a encontrar y verificar que no pueden ser corregidos de forma única. Ahora mira de nuevo por un par de error de código libre wordsthat se distancia de 4 de cada uno de los otros...

01101 y 10110 son cuatro unidades de diferencia. A mitad de camino entre ellos están 10101, 11111, 11100, 00111, 00100, y 01110. De estos, la comparación con el error de código libre wordsconfirms que 10101, 11100, 00111, y 01110 son, de hecho, error-2.

En resumen, se han identificado todos los errores 2 código wordsas mentir a mitad de camino entre dos de error de código libre de palabras, 2 unidades de distancia de ellos haciendo todos estos 8 código wordsnot únicas correcciones:

11000, 10001, 01010, y 00011 son entre 00000 y 11011,

10101, 11100, 00111, y 01110 son entre 01101 y 10110.

(También hemos descartado palabras de código de error mayor que 2.)