Distancia mínima de un código lineal binario

Question

Necesito encontrar parámetros $n$, $k$ y $d$ de un código lineal binario de su matriz del generador.

¿Cómo puedo encontrar eficientemente el parámetro $d$?

Sé el método que computar todos los codewords y peso mínimo cero código será la distancia mínima. pero es un algoritmo de tiempo exponencial. ¿Hay ningún algoritmo eficiente para hacer lo mismo?

Answer 1

Como se ha señalado por bola de nieve, el problema es inherentemente difícil, ver también este papel.

Sin embargo, se puede hacer mucho más rápido en general que la generación de todos los codewords.

Explico la idea lineal $[n,k]$ códigos de $C$$n = 2k$. En primer lugar, construimos dos generador de matrices de $G_1 = (I\ A)$ $G_2 = (B\ I)$ $C$ donde $I$ $(k\times k)$ unidad de la matriz y $A,B$ dos $(k\times k)$ matrices. Esto sólo es posible si las posiciones $1,\ldots,k$ $k+1,\ldots n$ forman dos conjuntos de información de $C$. Si este no es el caso, tenemos que encontrar un adecuado coordinar permutación primera.

Ahora una palabra de peso $w$ tiene peso en la mayoría de las $\lfloor w/2\rfloor$, ya sea en la primera o en la segunda $n$ coordenadas. Así, podemos encontrar todos los codewords de peso $\leq w$ entre los codewords $x G_1 = (x, xA)$ $x G_2 = (Bx, x)$ donde $x$ es un vector de longitud $k$ y en Hamming de peso en la mayoría de las $\lfloor w/2\rfloor$. Así podemos encontrar la distancia mínima $d$ $C$ si hacemos esto de forma iterativa para todos los $w = 1,2,3,\ldots, d$.

De esta manera, usted tiene que generar sólo una pequeña fracción de todos los codewords para encontrar la distancia mínima, y la idea se puede generalizar a cualquier lineal de código. El primer paso, entonces, es encontrar una cobertura de coordenadas con los conjuntos de información. Sin embargo, el algoritmo está siendo exponencial, por supuesto.

La página web codetables.de es una fuente valiosa para los límites en la mejor conocidos distancias mínimas para fija $q$, $n$ y $k$.

Answer 2

Hallar la distancia mínima $d$ de un lineal de código es equivalente a encontrar su peso mínimo. De acuerdo a la inherente dificultad de ciertos problemas de codificación, dado que la verificación de la matriz, la determinación de si existe o no una palabra de algunos de peso fijo $w$ es un NP-completo problema para los binarios códigos lineales.

Como Gerry comentó, usted puede encontrar fácilmente la distancia mínima para determinados códigos. Por ejemplo:

1. Si usted tiene un código Reed-Solomon de longitud $n$ y dimensión $k$, su distancia mínima es de $n-k+1$.

2. Si usted tiene un código de Hamming, su distancia mínima es de $3$.