Código lineal

Clase de código de corrección de errores

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 de código también es una palabra de código. Los códigos lineales se dividen tradicionalmente en códigos de bloque 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 ). ^{[ cita requerida ]}

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 modo que, si se producen errores en la comunicación, el receptor de un bloque de mensajes pueda corregir o detectar algunos errores. 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. ^[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 de código de 7 bits. Dos palabras de código distintas difieren 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. ^[3] Este código contiene 2 ⁴ = 16 palabras de código.

Definición y parámetros

Un código lineal de longitud n y dimensión k es un subespacio lineal C con dimensión k del espacio vectorial donde es el cuerpo finito con q elementos. Un código de este tipo se denomina 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 denominan 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 . ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle \mathbb {F} _{q}}$

El peso de una palabra de código es el número de sus elementos que no son cero y la distancia entre dos palabras de código 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 de código no cero o, equivalentemente, la distancia mínima entre palabras de código 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, código). ${\displaystyle [n,k,d]_{q}}$

Queremos dar la base estándar 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 utilizar y la métrica de Hamming no mide la cantidad de errores en la transmisión, como queremos. ${\displaystyle \mathbb {F} _{q}^{n}}$

Matrices generadoras y de comprobación

Como subespacio lineal de , el código C completo (que puede ser muy grande) puede representarse como el lapso de un conjunto de palabras de código (conocido como base en álgebra lineal ). Estas palabras de código 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 , donde denota la matriz identidad y P es alguna matriz, entonces decimos que G está en forma estándar . ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle k}$ ${\displaystyle {\boldsymbol {G}}=[I_{k}|P]}$ ${\displaystyle I_{k}}$ ${\displaystyle k\times k}$ ${\displaystyle k\times (n-k)}$

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

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 ₀ sea 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 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 averiguar la distancia mínima entre las palabras clave de un código lineal, bastaría con observar las palabras clave distintas de cero. La palabra clave distinta de cero con el peso más pequeño 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 , que es equivalente a , donde es la columna de . Elimina aquellos elementos con , aquellos con son linealmente dependientes. Por lo tanto, es al menos el número mínimo de columnas linealmente dependientes. Por otro lado, considera el conjunto mínimo de columnas linealmente dependientes donde es el conjunto de índices de columna. . Ahora considera el vector tal que si . Observa porque . Por lo tanto, tenemos , que es el número mínimo de columnas linealmente dependientes en . Por lo tanto, la propiedad reclamada queda probada. ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}$ ${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}$ ${\displaystyle {\boldsymbol {H_{i}}}}$ ${\displaystyle i^{th}}$ ${\displaystyle {\boldsymbol {H}}}$ ${\displaystyle c_{i}=0}$ ${\displaystyle {\boldsymbol {H_{i}}}}$ ${\displaystyle c_{i}\neq 0}$ ${\displaystyle d}$ ${\displaystyle \{{\boldsymbol {H_{j}}}|j\in S\}}$ ${\displaystyle S}$ ${\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}}}$ ${\displaystyle {\boldsymbol {c'}}}$ ${\displaystyle c_{j}'=0}$ ${\displaystyle j\notin S}$ ${\displaystyle {\boldsymbol {c'}}\in C}$ ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}$ ${\displaystyle d\leq wt({\boldsymbol {c'}})}$ ${\displaystyle {\boldsymbol {H}}}$

Ejemplo: Códigos de Hamming

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

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

${\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}}}$

Ejemplo: Códigos Hadamard

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

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

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 lo ilustra (denominado algoritmo de decodificación del vecino más próximo):

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

Salida: Una palabra de código más cercana a , si la hay. ${\displaystyle w}$ ${\displaystyle C}$ ${\displaystyle v}$

• Comenzando con , repita los dos pasos siguientes. ${\displaystyle t=0}$
• Enumere los elementos de la bola de radio (Hamming) alrededor de la palabra recibida , denotada . ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle B_{t}(v)}$
  • Para cada uno en , verifique si en . Si es así, devuélvalo como solución. ${\displaystyle w}$ ${\displaystyle B_{t}(v)}$ ${\displaystyle w}$ ${\displaystyle C}$ ${\displaystyle w}$
• Incremento . Falla solo cuando se completa la enumeración y no se encuentra ninguna solución. ${\displaystyle t}$ ${\displaystyle t>(d-1)/2}$

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

Notación popular

Los códigos en general se denotan 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 ) generalmente se denomina código ( n ,  k ). Los códigos de bloque lineales se denotan con frecuencia como códigos [ n ,  k ,  d ], donde d se refiere a la distancia mínima de Hamming del código entre dos palabras de código 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, que tiene M palabras de código) y distancia de Hamming mínima d ).

Límite singleton

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 de máxima distancia separable o MDS . Cuando existen, estos códigos 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 para la cual (c ₁ ,...,c _n ) en C ₁ si y solo si (c _p(1) ,...,c _p(n) ) en C ₂ , entonces decimos que C ₁ y C ₂ son permutaciones equivalentes . En términos más generales, si existe una matriz monomial que envía C ₁ isomorfamente a C ₂ entonces decimos que C ₁ y C ₂ son equivalentes . ${\displaystyle n\times n}$ ${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$

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

Teorema de Bonisoli

Un código se define como equidistante si y solo si existe alguna constante d tal que la distancia entre dos palabras de código distintas del código es igual a d . ^[4] En 1984, Arrigo Bonisoli determinó la estructura de los 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 . ^[5]

Ejemplos

Algunos ejemplos de códigos lineales incluyen:

• Códigos de repetición
• Códigos de paridad
• Códigos cíclicos
• Códigos de Hamming
• Código Golay , tanto la versión binaria como la ternaria
• Códigos polinomiales , de los cuales los códigos BCH son un ejemplo
• Códigos Reed-Solomon
• Códigos Reed-Muller
• Códigos de geometría algebraica
• Códigos binarios de Goppa
• Códigos de verificación de paridad de baja densidad
• Códigos de expansión
• Códigos de verificación de paridad multidimensionales
• Códigos tóricos
• Códigos turbo

Generalización

También se han considerado espacios de Hamming sobre alfabetos no de campo, especialmente sobre anillos finitos , más notablemente anillos de Galois sobre Z 4 . Esto da lugar a módulos en lugar de espacios vectoriales y códigos lineales en 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 (es decir, GF(2 ^2m )) con la distancia de Hamming y (también denotada 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 como imágenes de códigos lineales en anillo de . ^{[6] [7] [8]} ${\displaystyle \mathbb {Z} _{2}^{2m}}$ ${\displaystyle \mathbb {Z} _{4}^{m}}$ ${\displaystyle \mathbb {Z} _{2}^{2m}}$ ${\displaystyle \mathbb {Z} _{4}^{m}}$

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

Véase también

• Métodos de decodificación

Referencias

1. William E. Ryan y Shu Lin (2009). Códigos de canal: clásicos y modernos . Cambridge University Press. pág. 4. ISBN 978-0-521-84868-8.
2. MacKay, David, JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje (PDF) . Cambridge University Press . p. 9. Bibcode :2003itil.book.....M. ISBN 9780521642989En un código de bloque lineal , los bits adicionales son funciones lineales de los bits originales; estos bits adicionales se denominan bits de verificación de paridad. ${\displaystyle N-K}$ ${\displaystyle K}${{cite book}}: CS1 maint: multiple names: authors list (link)
3. Thomas M. Cover y Joy A. Thomas (1991). Elementos de la teoría de la información. John Wiley & Sons, Inc., págs. 210-211. ISBN 978-0-471-06259-2.
4. Etzión, Tuvi; Raviv, Netanel (2013). "Códigos equidistantes en el Grassmanniano". arXiv : 1308.6231 [matemáticas.CO].
5. Bonisoli, A. (1984). "Todo código lineal equidistante es una secuencia de códigos Hamming duales". Ars Combinatoria . 18 : 181–186.
6. Marcus Greferath (2009). "Introducción a la teoría de codificación lineal en anillo". En Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Bases de Gröbner, codificación y criptografía . Springer Science & Business Media. ISBN 978-3-540-93806-4.
7. "Enciclopedia de Matemáticas". www.encyclopediaofmath.org .
8. JH van Lint (1999). Introducción a la teoría de la codificación (3.ª ed.). Springer. Capítulo 8: Códigos sobre ℤ ₄ . ISBN 978-3-540-64133-9.
9. ST Dougherty; J.-L. Kim; P. Sole (2015). "Problemas abiertos en la teoría de la codificación". En Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Anillos no conmutativos y sus aplicaciones . American Mathematical Soc. pág. 80. ISBN 978-1-4704-1032-2.

Bibliografía

• JF Humphreys; MY Prest (2004). Números, grupos y códigos (2.ª ed.). Cambridge University Press. ISBN 978-0-511-19420-7.El capítulo 5 contiene una introducción más suave (que este artículo) al tema de los códigos lineales.

Enlaces externos

• Programa generador de código q-ary
• Tablas de códigos: límites de los parámetros de varios tipos de códigos, IAKS, Facultad de Informática, Universidad de Karlsruhe (TH)] . Tabla actualizada en línea de los códigos binarios óptimos, incluidos los códigos no binarios.
• Base de datos de códigos Z4 en línea, base de datos actualizada de códigos Z4 óptimos.