Hay un $(6,9,3)_2$ código?

Question

¿Existe un $1$-corrección de errores de código binario con la longitud del bloque de $6$ $9$ codewords?

• El Hamming obligado dice que para cualquier código de $C$ con esos parámetros, $|C| \le \frac{2^6}{1+6} \approx 9.14$. Así, no podemos descartar la existencia de un código mediante el Hamming obligado.

• El Singleton obligado dice que para cualquier código de $C$ con esos parámetros, $|C| \le 2^{6-3+1} = 16$, por lo que no podemos descartar la existencia de un código mediante el Singleton obligado.

• También, esto puede no ser lineal en el código, ya que $\log_2 9$ no es un entero. Esto descarta la posibilidad de que se acaba de enumerar los posibles generador de matrices.

Me siento un poco tonto preguntar esto, pero la aproximación directa (suponga $000\ 000$ está en el código, a continuación, todos los demás deben tener Hamming peso $\ge 3$, ...) se convierte en inmanejable rápidamente. ¿De qué otra manera puedo hacerlo?

Answer 1

Mediante la adición de un bit de paridad / pinchar en cualquier no-constante de coordenadas (es decir, en este coordinar, ambos símbolos de $0$ $1$ aparecen en algunos la palabra), un $(6,9,3)_2$ código existe si y sólo si $(7,9,4)_2$ código existe. Para un $(7,9,4)_2$-código, el Plotkin obligado de los rendimientos de la contradicción $$4 = d \leq \frac{n\cdot \left|C\right| \cdot (q-1)}{(\left|C\right|-1)\cdot q} = \frac{7 \cdot 9\cdot 1}{8\cdot 2} \approx 3.94.$$ Así que no hay $(7,9,4)_2$ código y no $(6,9,3)_2$ código.

Una herramienta conveniente de preguntas como esta la internet tabla para las pequeñas binario bloque de códigos. De acuerdo a esto, el tamaño máximo de un código binario de longitud $7$ y la distancia $4$$8$, así que de nuevo, no es $(7,9,4)_2$ código.

De hecho, sólo hay un único isomorfismo de clase de una $(6,8,3)_2$ código, y además es lineal (si traducidas de manera tal que el cero de la palabra está en el código). El código de joriki tiene el generador de matriz $$\begin{pmatrix}1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1\end{pmatrix}.$$

Answer 2

Aquí está el código que realiza una exhaustiva búsqueda de un código y no encontrar uno. Encuentra un $(6,8,3)_2$ código de:

000000
111000
100110
011110
010101
101101
110011
001011

Answer 3

Para un binario de la palabra de longitud $6$, $4$ opciones para los últimos dos coordenadas: $00,01,10$ o $11$. Supongamos ahora que, hay un código binario con nueve codewords. Pero entonces, al menos tres de los codewords deben tener la misma de los últimos dos coordenadas por el principio del palomar. Sin embargo, tres codewords tener la misma últimos dos coordenadas no puede satisfacer el mínimo de la distancia, ya que debe satisfacer la misma distancia mínima para la longitud de la $4$. Por lo tanto, no es $(6,9,3)_2$ código.