Códigos lineales

En teoría de la codificación, un código lineal es un código de corrección de errores para los que cualquier combinación lineal de palabras de código es también una palabra de código. Los códigos lineales son tradicionalmente divididos en bloques de códigos y códigos convolucionales, aunque los códigos turbos pueden ser vistos como un híbrido de estos dos tipos. Los códigos lineales permiten algoritmos de codificación y decodificación más eficiente que otros códigos (cf. síndrome de decodificación).

Los códigos lineales se utilizan en la corrección de errores hacia adelante y se aplican en los métodos de transmisión de símbolos (por ejemplo, los 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 de código en un código de bloque lineal son bloques de símbolos que son codificados usando más símbolos que el valor original para ser enviadas. Un código lineal de longitud n transmite bloques que contienen n símbolos. Por ejemplo, la [7, 4,3] código de Hamming es un código binario lineal que representa los mensajes de 4-bits utilizando palabras de código de 7-bits. Dos palabras de código distintas difieren en por lo menos tres bits. Como consecuencia de ello, hasta dos errores por palabra de código pueden ser detectados y un solo error puede ser corregido. Este código contiene 2⁴=16 palabras de código.

Definición y parámetros

Un código lineal de longitud n y rango k es un subespacio lineal C con dimensión k del espacio vectorial $\mathbb {F} _{q}^{n}$ donde $\mathbb {F} _{q}$ es el campo finito con q elementos. Tal código se denomina un 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 de código. El tamaño de un código es el número de palabras de código y es igual a q^k.

El peso de una palabra de código es el número de sus elementos que son distintos de cero y la distancia entre dos palabras de código es la distancia de Hamming entre ellos, es decir, el número de elementos en los que difieren. La distancia d de un código lineal es el peso mínimo de sus palabras de código distintas de cero, o de forma equivalente, la distancia mínima entre palabras de código diferentes. Un código lineal de longitud n, la dimensión k, y la distancia d se denomina [n,k,d] código.

Observación: Queremos dar a $\mathbb {F} _{q}^{n}$ la base estándar habitual, ya que cada coordenada representa un "bit", que se transmite a través de un " canal con ruido ", con alguna pequeña probabilidad de transmisión de errores (un canal binario simétrico). Si se utiliza alguna otra base, este modelo no puede ser utilizada y la métrica de Hamming no mide el número de errores en la transmisión, que es lo que se quiere.

Propiedades

Como un subespacio lineal de $\mathbb {F} _{q}^{n}$ , todo el código de C (que puede ser muy grande) puede ser representado como el espacio de un conjunto minimal de palabras de código (conocida como una base en álgebra lineal). La base de estas palabras de código a menudo se ubica en las filas de una matriz G conocidas como una matriz de generación para el código C. Cuando G tiene la forma de la matriz bloque $G=(I_{k}|A)$ , donde $I_{k}$ es una matriz identidad de $k\times k$ y A es alguna matriz de $k\times (n-k)$ , entonces decimos G está en forma estándar.

Una matriz H que es representada como una función lineal $\phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}$ cuyo núcleo es C se denomina matriz de comprobación de C (o a veces una matriz de comprobación de paridad). Equivalentemente, H es una matriz cuyo espacio nulo es C. Si C es un código con una matriz de generación G en forma estándar, G = (I_k | A), entonces H = (−A^t | I_n − k) es una matriz de comprobación para C. El código generado por H es llamado código dual de C.

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

\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, con el fin de encontrar la distancia mínima entre las palabras de código de un código lineal, uno sólo necesita conocer a las palabras de código distinto de cero. La palabra de código distinto de cero con el peso más pequeño tiene entonces la distancia mínima para la palabra de código 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 comprobación H. Demostración: Dado ${\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}$ , que es equivalente a $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}$ , donde ${\boldsymbol {H_{i}}}$ es la $i^{th}$ columna ${\boldsymbol {H}}$ . Si se eliminan los elementos con $c_{i}=0$ , los ${\boldsymbol {H_{i}}}$ con $c_{i}\neq 0$ son linealmente dependientes. Por lo tanto $d$ es al menos el número mínimo de columnas linealmente dependientes. Por otra parte, considerando el conjunto mínimo de columnas linealmente dependientes $\{{\boldsymbol {H_{j}}}|j\in S\}$ donde $S$ es el conjunto de índice de columna. $\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}}$ .Consideremos ahora el vector ${\boldsymbol {c'}}$ tal que $c_{j}^{'}=0$ sí $j\notin S$ . Notar que ${\boldsymbol {c'}}\in C$ porque ${\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}$ . Por lo tanto tenemos $d\leq wt({\boldsymbol {c'}})$ , que es el número mínimo de columnas linealmente dependientes ${\boldsymbol {H}}$ . Por tanto, la propiedad queda demostrada.

Ejemplo: códigos de Hamming

Artículo principal: Código de Hamming

Como la primera clase de códigos lineales desarrollados para el propósito de corrección de errores, los códigos de Hamming han sido ampliamente utilizados en los sistemas de comunicación digitales. Para cualquier entero positivo $r\geq 2$ , existe un $[2^{r}-1,2^{r}-r-1,3]_{2}$ código de Hamming. Desde $d=3$ , el código Hamming puede corregir errores de 1-bit.

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

{\boldsymbol {G}}={\begin{pmatrix}1\ 1\ 0\ 1\ 0\ 0\ 0\\0\ 1\ 1\ 0\ 1\ 0\ 0\\1\ 1\ 1\ 0\ 0\ 1\ 0\\1\ 0\ 1\ 0\ 0\ 0\ 1\end{pmatrix}},

:

{\boldsymbol {H}}={\begin{pmatrix}1\ 0\ 0\ 1\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 1\ 1\ 0\\0\ 0\ 1\ 0\ 1\ 1\ 1\end{pmatrix}}

Ejemplo: códigos de Hadamard

Artículo principal: Código de Hadamard

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

Ejemplo: el código de bloque lineal con la siguiente matriz generadora es un $[8,3,4]_{2}$ código Hadamard: ${\boldsymbol {G}}_{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 Hadamard es un caso especial de código Reed-Muller Si tomamos la primera columna (la columna todo ceros) de ${\boldsymbol {G}}_{Had}$ , obtenemos un código simple $[7,3,4]_{2}$ , que es el código dual del código de Hamming.

Algoritmo de vecino más cercano

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

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

Salida: una palabra de código w en C cercano a v.

Enumerar los elementos de la bola (Hamming) de radio t alrededor de la palabra recibida v, denota B_t(v).
- Para cada w de B_t(v), compruebe si w esta en C. Si es así, devuelva w como la solución!
Falla cuando la enumeración se completa y no se ha encontrado solución.

Nota: El "fallo" no se devuelve a menos que t > (d − 1)/2. Decimos que un C es una corrección lineal de t-errores si hay como máximo una palabra de código de B_t(v), para cada v en $\mathbb {F} _{q}^{n}$ .

Notación Popular

Los códigos, en general, son denotados a menudo con la letra C, y un código de longitud n y de rango k (es decir, que tiene n palabras de código en su base y k filas en su matriz generadora) se conocen en general como un código (n, k). Los códigos de bloque lineales se designan con frecuencia como códigos [n, k, d], donde d se refiere a la distancia de Hamming mínima del código entre dos palabras de código.

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

Límite de Singleton

Lema (límite de Singleton): Cada código lineal C denotado [n, k, d] satisface que $k+d\leq n+1$ .

Un código C cuyos parámetros satisfacer k + d = n +1 se conoce como distancia máxima separable o MDS (por sus siglas en inglés). Estos códigos, cuando existen, son de alguna manera lo mejor posible.

Si C₁ y C₂ son dos códigos de longitud n y si hay una permutación p en el grupo simétrico S_n para los que (c₁,...,c_n) está en C₁ si y sólo si (c_p(1),...,c_p(n)) está en C₂, entonces se dice que C₁ y C₂ son una permutación equivalente. En general, si hay una matriz monomial de $n\times n$ llamada $M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$ que envía C₁ isomórficamente a C₂ entonces decimos que C₁ y C₂ son equivalentes.