Código lineal

En teoría de codificación, un código lineal es un código de corrección 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 bloque y códigos convolucionales, aunque los códigos turbo pueden verse como un híbrido de estos dos tipos. Los códigos lineales permiten algoritmos de codificación y decodificación más eficientes que otros códigos (cf. síndrome de decodificación).

Los códigos lineales se utilizan en la corrección de errores directos y se aplican en métodos para transmitir símbolos (por ejemplo, bits) en un canal de comunicaciones de modo que, si se producen errores en la comunicación, el destinatario de una comunicación pueda corregir o detectar algunos errores. bloque de mensajes. Las palabras de código 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. 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 de código de 7 bits. Dos palabras de código distintas se diferencian en al menos tres bits. Como consecuencia, se pueden detectar hasta dos errores por palabra de código, mientras que se puede corregir un solo error. Este código contiene 2⁴=16 palabras en código.

Definición y parámetros

A 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}$ Donde ${\displaystyle \mathbb {F} _{q}$ es el campo finito con q elementos. Tal código se llama un q- código diario. 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 codewords. El tamaño de un código es el número de palabras clave e iguales q^k.

El peso de una palabra clave es el número de sus elementos que no son cero y el distancia entre dos palabras clave es la distancia Hamming entre ellos, 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 codewords no cero, o equivalentemente, la distancia mínima entre las distintas palabras clave. Un código lineal de longitud n, dimensión k, y distancia d se llama un [n,k,dCódigo (o, más precisamente, ${\displaystyle [n,k,d]$ código).

Queremos dar ${\displaystyle \mathbb {F} _{q} {n}$ la base estándar porque cada coordenadas 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 simétrico binario). Si se utiliza alguna otra base, este modelo no se puede utilizar y la métrica Hamming no mide el número de errores en la transmisión, como queremos.

Generador y matrices de verificación

Como subespacio lineal ${\displaystyle \mathbb {F} _{q} {n}$, todo el código C (que puede ser muy grande) puede ser representado como el lapso de un conjunto de ${\displaystyle k}$ codewords (conocido como base en álgebra lineal). Estas palabras clave de base a menudo se collan en las filas de una matriz G conocida como matriz para el código C. Cuando G tiene la matriz de bloques ${\displaystyle {\boldsymbol {G}=[I_{k}$, donde ${\displaystyle I_{k}$ denota los ${\displaystyle k\times k}$ matriz de identidad y P ${\displaystyle k\times (n-k)}$ matriz, entonces decimos que G está en formulario estándar.

Una matriz H representando una función lineal ${\displaystyle \phi:\mathbb {F} _{q}\n}\to \mathbb {F} _{n-k}}$ cuyo núcleo C se llama matriz de verificación de C (o a veces una 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}$Entonces ${\displaystyle {\boldsymbol {H}=[-P^{T} stillI_{n-k}}$ es una matriz de verificación para C. El código generado por H se llama Código dual de C. Puede verificarse que G es un ${\displaystyle k\times n}$ matriz, mientras que H es un ${\displaystyle (n-k)\times n}$ matriz.

La linealidad garantiza que la distancia mínima de Hamming 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 también es 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

${\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 encontrar la distancia mínima entre las palabras de código de un código lineal, sólo sería necesario mirar las palabras de código distintas de cero. La palabra de código distinta de cero con el peso más pequeño tiene entonces la distancia mínima a la palabra de código cero y, por 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}\cdot {\boldsymbol {C} {\fn} {\fnMicrosoft} {0}}$, que equivale a ${\displaystyle \sum ################################################################################################################################################################################################################################################################ {H_{i}}={\boldsymbol {0}}$, donde ${\displaystyle {\boldsymbol {H_{i}}}$ es ${\displaystyle i^{th}}$ columna of ${\displaystyle {\bun}}$. Quitar esos artículos con ${\displaystyle C_{i}=0}$, esos ${\displaystyle {\boldsymbol {H_{i}}}$ con ${\displaystyle c_{i}\neq 0}$ dependen linealmente. Por lo tanto, ${\displaystyle d}$ es al menos el número mínimo de columnas dependientes linealmente. Por otra parte, considere el conjunto mínimo de columnas dependientes linealmente ${\displaystyle ##### ########################################################################################################################################################################################################################################################### {H_{j}} S\}$ Donde ${\displaystyle S.$ es el índice de columna. ${\displaystyle \sum _{i=1} {\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 considera el vector ${\displaystyle {\boldsymbol {c}}$ tales que ${\displaystyle c_{j}=0}$ si ${\displaystyle j\notin S}$. Nota ${\displaystyle {\boldsymbol {c}\in C}$ porque ${\displaystyle {\boldsymbol}\cdot {\boldsymbol {C} {\fnK} {\fnMicrosoft Sans Serif} {0}}$. Por lo tanto, tenemos ${\displaystyle d\leq wt}}$, que es el número mínimo de columnas dependientes linealmente en ${\displaystyle {\bun}}$. The claimed property is therefore proven.

Ejemplo: códigos Hamming

Como la primera clase de códigos lineales desarrollados con propósito de corrección de errores, los códigos Hamming han sido ampliamente utilizados 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 de adelgazamiento. Desde ${\displaystyle d=3}$, este código Hamming puede corregir un error de 1 bit.

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

${\displaystyle {\boldsymbol {G}={\begin{pmatrix}1\ 0\ 0\ 1\ 0\ 0\0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 1\ 0\ 0\ 1\0\0}}}}}$ ${\displaystyle {\boldsymbol {H}={\begin{pmatrix}1\ 1\ 1\ 0\ 0\1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\0\ 1\ 1\ 1\ 0\ 0\0\ 1\end{\i}}} {\cH}}}}}}} {\cH}}}}= {\\\\\\\\\cH}}\\\\\\\\\\\\\\\cH}\\\\\\\c}\c}\c}\cH}\c}\c\c\\\c\c\\\\c\c\c\\\\\\c\c\\\\\c\c\c\c\\\\c\c\c\c\c\\\\\\\\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\c\$

Ejemplo: códigos Hadamard

El código de 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 se puede construir columna por columna: el ${\displaystyle i^{th}}$ columna es los bits de la representación binaria del entero ${\displaystyle i}$, como se muestra en el siguiente ejemplo. Código Hadamard tiene una distancia mínima ${\displaystyle 2^{r-1}$ y por lo tanto puede corregir ${\displaystyle 2^{r-2}-1}$ errores.

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

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

Algoritmo del vecino más cercano

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 (llamado algoritmo de decodificación vecino más cercano):

Entrada: A vector recibido V ${\displaystyle \mathbb {F} _{q} {n}$.

Producto: Una palabra clave ${\displaystyle w}$ dentro ${\displaystyle C}$ más cercana ${\displaystyle v}$, si hay.

• Empezando con ${\displaystyle t=0}$, repetir los siguientes dos pasos.
• Enumerar los elementos de la bola de (Hamming) radio ${\displaystyle t}$ alrededor de la palabra recibida ${\displaystyle v}$, denotado ${\displaystyle B_{t}(v)}$.
  • Para cada uno ${\displaystyle w}$ dentro ${\displaystyle B_{t}(v)}$, comprobar si ${\displaystyle w}$ dentro ${\displaystyle C}$. Si es así, regresa. ${\displaystyle w}$ como la solución.
• Incremento ${\displaystyle t}$. Fail sólo cuando ${\displaystyle t título(d-1)/2}$ por lo que la enumeración es completa y no se ha encontrado ninguna solución.

Decimos que un lineal ${\displaystyle C}$ es ${\displaystyle t}$- corrección de terror si hay en la mayoría de una palabra clave ${\displaystyle B_{t}(v)}$, para cada ${\displaystyle v}$ dentro ${\displaystyle \mathbb {F} _{q} {n}$.

Notación popular

Los códigos en general son a menudo denotados por la carta C, y un código de longitud n y de rango k (es decir, tener n palabras clave en su base y k filas en sus matriz) se conoce generalmente como un (n, k) código. Los códigos de bloqueo lineales se denotan con frecuencia como [n, k, d] códigos, donde d se refiere a la distancia mínima Hamming del código entre cualquier dos palabras clave.

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

Enlace singleton

Lemma (Singleton bound): Cada linear [n,k,d] código C satisfies ${\displaystyle k+d\leq n+1}$.

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

Si C₁ y C₂ son dos códigos de longitud n y si hay una p permutación en el grupo simétrico S_n (c)₁,..._n) en C₁ si y sólo si (c_p.1),..._p(n)) en C₂Entonces decimos C₁ y C₂ son permutación equivalente. En mayor generalidad, si hay una ${\displaystyle n\times n}$ matriz monomial ${\displaystyle M\colon \mathbb {F} _{q} {n}\to \mathbb {F} _{q}^{n}$ que envía C₁ isomorfa a C₂ entonces decimos C₁ y C₂ son equivalente.

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

Teorema de Bonisoli

Se define que un código es equidistante si y sólo si existe una d constante tal que la distancia entre dos palabras de código distintas del código sea igual a d. En 1984, Arrigo Bonisoli determinó la estructura de códigos lineales de un peso sobre campos finitos y demostró que cada código lineal equidistante es una secuencia de códigos Hamming duales.

Ejemplos

Algunos ejemplos de códigos lineales incluyen:

Generalización

También se han considerado espacios de adelgazamiento sobre alfabetos no de campo, especialmente sobre anillos finitos, sobre todo anillos Galois sobre Z4. Esto da lugar a módulos en lugar de espacios vectoriales y códigos lineales (identificados con submódulos) en lugar de códigos lineales. La métrica típica usada en este caso la distancia Lee. Hay una isometría gris entre ${\displaystyle \mathbb {Z} _{2m}$ (es decir, GF(2)^2m) con la distancia Hamming y ${\displaystyle \mathbb {Z} _{4} {m}$ (también denotado como GR(4,m)) con la distancia Lee; su principal atracción es que establece una correspondencia entre algunos códigos "buenos" que no son lineales sobre ${\displaystyle \mathbb {Z} _{2m}$ como imágenes de códigos lineales de anillo de ${\displaystyle \mathbb {Z} _{4} {m}$.

Más recientemente, algunos autores también se han referido a estos códigos sobre anillos simplemente como códigos lineales.