Código lineal

En teoría de la codificación , un código lineal es un código corrector de errores para el cual cualquier combinación lineal de palabras clave también es una palabra clave. Los códigos lineales se dividen tradicionalmente en códigos de bloques y códigos convolucionales , aunque los códigos turbo pueden considerarse un híbrido de estos dos tipos. ^{[ 1 ]} Los códigos lineales permiten algoritmos de codificación y decodificación más eficientes que otros códigos (cf. decodificación de síndromes ).

Los códigos lineales se utilizan en la corrección de errores hacia adelante y se aplican en métodos para transmitir símbolos (por ejemplo, bits ) en un canal de comunicaciones de manera que, si se producen errores en la comunicación, algunos errores pueden ser corregidos o detectados por el receptor de un bloque de mensaje. Las palabras clave en un código de bloque lineal son bloques de símbolos que se codifican utilizando más símbolos que el valor original que se va a enviar. ^{[ 2 ]} Un código lineal de longitud n transmite bloques que contienen n símbolos. Por ejemplo, el código Hamming [7,4,3] es un código binario lineal que representa mensajes de 4 bits utilizando palabras clave de 7 bits. Dos palabras clave distintas difieren en al menos tres bits. Como consecuencia, se pueden detectar hasta dos errores por palabra clave, mientras que se puede corregir un solo error. ^{[ 3 ]} Este código contiene 2 ⁴  =  16 palabras clave.

Un código lineal de longitud n y dimensión k es un subespacio lineal C con dimensión k del espacio vectorial.${\displaystyle \mathbb {F} _{q}^{n}}$dónde${\displaystyle \mathbb {F} _{q}}$es el campo finito con q elementos. Dicho código se llama código q -ario. Si q  =  2 o q  =  3, el código se describe como un código binario o un código ternario , respectivamente. Los vectores en C se llaman palabras clave . El tamaño de un código es el número de palabras clave y es igual a q ^k .

El peso de una palabra clave es el número de sus elementos que no son cero y la distancia entre dos palabras clave es la distancia de Hamming entre ellas, es decir, el número de elementos en los que difieren. La distancia d del código lineal es el peso mínimo de sus palabras clave no nulas, o equivalentemente, la distancia mínima entre palabras clave distintas. Un código lineal de longitud n , dimensión k y distancia d se denomina código [ n , k , d ] (o, más precisamente,${\displaystyle [n,k,d]_{q}}$código).

Queremos dar${\displaystyle \mathbb {F} _{q}^{n}}$La base estándar se utiliza porque cada coordenada representa un "bit" que se transmite a través de un "canal ruidoso" con una pequeña probabilidad de error de transmisión (un canal binario simétrico ). Si se utiliza otra base, este modelo no se puede usar y la métrica de Hamming no mide el número de errores de transmisión, como necesitamos.

Como un subespacio lineal de${\displaystyle \mathbb {F} _{q}^{n}}$, todo el código C (que puede ser muy grande) puede representarse como el espacio generado por un conjunto de${\displaystyle k}$palabras clave (conocidas como base en álgebra lineal ). Estas palabras clave base a menudo se cotejan en las filas de una matriz G conocida como matriz generadora para el código C. Cuando G tiene la forma de matriz de bloques${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$, dónde${\displaystyle I_{k}}$denota el${\displaystyle k\times k}$matriz identidad y P es alguna${\displaystyle k\times (nk)}$matriz, entonces decimos que G está en forma estándar .

Una matriz H que representa una función lineal${\displaystyle \phi$ :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{nk}} cuyo núcleo es C se denomina matriz de verificación de C (o a veces matriz de verificación de paridad). Equivalentemente, H es una matriz cuyo espacio nulo es C. Si C es un código con una matriz generadora G en forma estándar,${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$, entonces${\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{nk}]}$es una matriz de verificación para C. El código generado por H se llama código dual de C. Se puede verificar que G es un${\displaystyle k\times n}$matriz, mientras que H es una${\displaystyle (nk)\times n}$matriz.

La linealidad garantiza que la distancia de Hamming mínima d entre una palabra clave c ₀ y cualquiera de las otras palabras clave c  ≠ c ₀ es independiente de c ₀ . Esto se deduce de la propiedad de que la diferencia c − c ₀ de dos palabras clave en C también es una palabra clave (es decir, un elemento del subespacio C ), y de la propiedad de que d ( c , c ₀ ) = d ( c − c ₀ , 0 ). Estas propiedades implican que         

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}$

En otras palabras, para hallar la distancia mínima entre las palabras clave de un código lineal, basta con observar las palabras clave distintas de cero. La palabra clave distinta de cero con el menor peso tiene entonces la distancia mínima a la palabra clave cero y, por lo tanto, determina la distancia mínima del código.

La distancia d de un código lineal C también es igual al número mínimo de columnas linealmente dependientes de la matriz de verificación H.

Prueba: Porque ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}$, lo cual es equivalente a${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}$, dónde${\displaystyle {\boldsymbol {H_ {i}}}}$es el${\displaystyle i^{th}}$columna de${\displaystyle {\boldsymbol {H}}}$. Elimine esos elementos con${\displaystyle c_{i}=0}$, aquellos${\displaystyle {\boldsymbol {H_ {i}}}}$con${\displaystyle c_{i}\neq 0}$son linealmente dependientes. Por lo tanto,${\displaystyle d}$es al menos el número mínimo de columnas linealmente dependientes. Por otro lado, consideremos el conjunto mínimo de columnas linealmente dependientes.${\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}$dónde${\displaystyle S}$es el conjunto de índices de columna. ${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}$Ahora consideremos el vector${\displaystyle {\boldsymbol {c'}}}$de tal manera que${\displaystyle c_{j}'=0}$si${\displaystyle j\notin S}$. Nota${\displaystyle {\boldsymbol {c'}}\in C}$porque${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}$Por lo tanto, tenemos${\displaystyle d\leq wt({\boldsymbol {c'}})}$, que es el número mínimo de columnas linealmente dependientes en${\displaystyle {\boldsymbol {H}}}$Por lo tanto, se demuestra la propiedad reivindicada.

Como la primera clase de códigos lineales desarrollados con fines de corrección de errores, los códigos de Hamming se han utilizado ampliamente en sistemas de comunicación digital. Para cualquier entero positivo${\displaystyle r\geq 2}$, existe un${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}$Código Hamming. Desde${\displaystyle d=3}$Este código Hamming puede corregir un error de 1 bit.

Ejemplo  : El código de bloque lineal con la siguiente matriz generadora y matriz de verificación de paridad es un${\displaystyle [7,4,3]_{2}}$Código Hamming.

${\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}$${\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}$

El código Hadamard es un${\displaystyle [2^{r},r,2^{r-1}]_{2}}$código lineal y es capaz de corregir muchos errores. El código Hadamard podría construirse columna por columna  : el${\displaystyle i^{th}}$La columna son los bits de la representación binaria del entero.${\displaystyle i}$, como se muestra en el siguiente ejemplo. El código de Hadamard tiene distancia mínima${\displaystyle 2^{r-1}}$y por lo tanto puede corregir${\displaystyle 2^{r-2}-1}$errores.

Ejemplo: El código de bloque lineal con la siguiente matriz generadora es un${\displaystyle [8,3,4]_{2}}$Código Hadamard: ${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}$.

El código de Hadamard es un caso especial del código de Reed-Muller . Si tomamos la primera columna (la columna de ceros) de${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}$, obtenemos${\displaystyle [7,3,4]_{2}}$código simplex , que es el código dual del código de Hamming.

El parámetro d está estrechamente relacionado con la capacidad de corrección de errores del código. La siguiente construcción/algoritmo ilustra esto (denominado algoritmo de decodificación del vecino más cercano):

Entrada: Un vector recibido v en${\displaystyle \mathbb {F} _{q}^{n}.}$

Salida: Una palabra clave${\displaystyle w}$en${\displaystyle C}$más cercano a${\displaystyle v}$, si los hubiera.

• Comenzando con${\displaystyle t=0}$, repita los dos pasos siguientes.
• Enumerar los elementos de la bola de radio (de Hamming)${\displaystyle t}$alrededor de la palabra recibida${\displaystyle v}$, denotado${\displaystyle B_{t}(v)}$.
  • Para cada${\displaystyle w}$en${\displaystyle B_{t}(v)}$, comprobar si${\displaystyle w}$en${\displaystyle C}$Si es así, devuélvalo.${\displaystyle w}$como la solución.
• Incremento${\displaystyle t}$. Fallar solo cuando${\displaystyle t>(d-1)/2}$Por lo tanto, la enumeración ha finalizado y no se ha encontrado ninguna solución.

Decimos que una lineal${\displaystyle C}$es${\displaystyle t}$-corrección de errores si hay como máximo una palabra clave en${\displaystyle B_{t}(v)}$, para cada${\displaystyle v}$en${\displaystyle \mathbb {F} _{q}^{n}}$.

Los códigos en general se suelen denotar con la letra C , y un código de longitud n y rango k (es decir, con n palabras clave en su base y k filas en su matriz generadora ) se suele denominar código ( n , k ). Los códigos de bloque lineales se suelen denotar como códigos [ n , k , d ], donde d se refiere a la distancia de Hamming mínima entre dos palabras clave cualesquiera.   

(La notación [ n , k , d ] no debe confundirse con la notación ( n , M , d ) utilizada para denotar un código no lineal de longitud n , tamaño M (es decir, con M palabras de código) y distancia de Hamming mínima d .)    

Lema ( Límite Singleton ): Todo código lineal [ n , k , d ] C satisface${\displaystyle k+d\leq n+1}$.

Un código C cuyos parámetros satisfacen k  + d  = n + 1 se denomina código separable de máxima distancia o MDS . Dichos códigos, cuando existen, son en cierto sentido los mejores posibles.   

Si C ₁ y C ₂ son dos códigos de longitud n y si existe una permutación p en el grupo simétrico S _n tal que ( c ₁ ,..., c _n ) en C ₁ si y solo si ( c _{p (1)} ,..., c _{p ( n )} ) en C ₂ , entonces decimos que C ₁ y C ₂ son equivalentes en permutación . En mayor generalidad, si existe una${\displaystyle n\times n}$matriz monomial${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$que envía C ₁ isomorfamente a C ₂ entonces decimos que C ₁ y C ₂ son equivalentes .

Lema : Cualquier código lineal es equivalente por permutación a un código que está en forma estándar.

Un código se define como equidistante si y solo si existe alguna constante d tal que la distancia entre cualesquiera dos de las palabras clave distintas del código es igual a d . ^{[ 4 ]} En 1984, Arrigo Bonisoli determinó la estructura de los códigos lineales de peso uno sobre cuerpos finitos y demostró que todo código lineal equidistante es una secuencia de códigos de Hamming duales . ^{[ 5 ]}

Algunos ejemplos de códigos lineales incluyen:

También se han considerado los espacios de Hamming sobre alfabetos no corpusculares, especialmente sobre anillos finitos , en particular los anillos de Galois sobre Z ₄ . Esto da lugar a módulos en lugar de espacios vectoriales y códigos lineales de anillo (identificados con submódulos ) en lugar de códigos lineales. La métrica típica utilizada en este caso es la distancia de Lee . Existe una isometría de Gray entre${\displaystyle \mathbb {Z} _{2}^{2m}}$(es decir, GF(2 ^{2 m} )) con la distancia de Hamming y${\displaystyle \mathbb {Z} _{4}^{m}}$(también denotado como GR(4,m)) con la distancia de Lee; su principal atractivo es que establece una correspondencia entre algunos códigos "buenos" que no son lineales sobre${\displaystyle \mathbb {Z} _{2}^{2m}}$como imágenes de códigos lineales anulares de${\displaystyle \mathbb {Z} _{4}^{m}}$. ^{[ 6 ] [ 7 ] [ 8 ]}

Algunos autores también se han referido a dichos códigos sobre anillos simplemente como códigos lineales. ^{[ 9 ]}

• Métodos de decodificación

• programa generador de código q -ario
• Tablas de códigos: límites de los parámetros de varios tipos de códigos , IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)] . Tabla en línea actualizada de los códigos binarios óptimos, incluye códigos no binarios.
• Base de datos en línea de códigos Z4, base de datos actualizada de códigos Z4 óptimos.