código lineal

Clase de código de corrección de errores

En teoría de la codificación , un código lineal es un código de corrección de errores para el cual cualquier combinación lineal de palabras en clave también es una palabra en 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. ^[1] 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 ). ^{[ cita necesaria ]}

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 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 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. ^[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 campo 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 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 . ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle \mathbb {F} _{q}}$

El peso de una palabra en clave es el número de elementos distintos de cero y la distancia entre dos palabras en clave es la distancia de Hamming entre ellas, es decir, la cantidad de elementos en los que difieren. La distancia d del código lineal es el peso mínimo de sus palabras de código distintas de cero, o de manera equivalente, la distancia mínima entre distintas palabras de código. 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 simétrico binario ). Si se utiliza alguna otra base entonces este modelo no se puede utilizar y la métrica de Hamming no mide el número de errores en la transmisión, como queremos. ${\displaystyle \mathbb {F} _{q}^{n}}$

Generador y matrices de verificación.

Como subespacio lineal de , el código completo C (que puede ser muy grande) puede representarse como el lapso de un conjunto de palabras en código (conocido como base en álgebra lineal ). Estas palabras de código básicas a menudo se recopilan en las filas de una matriz G conocida como matriz generadora del 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 verificación de C (o, a veces, matriz de verificació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 verificación para C. El código generado por H se llama 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 ₀ 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 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 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 , que es equivalente a , donde está la columna de . Elimine los elementos con , los que tienen son linealmente dependientes. Por lo tanto, es al menos el número mínimo de columnas linealmente dependientes. Por otro lado, considere el conjunto mínimo de columnas linealmente dependientes donde se establece el índice de columna. . Ahora considere el vector tal que si . Tenga en cuenta porque . Por lo tanto, tenemos , que es el número mínimo de columnas linealmente dependientes en . Por tanto, queda probada la propiedad reclamada. ${\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 Hamming

Como primera clase de códigos lineales desarrollados con fines de corrección de errores, los códigos Hamming se han utilizado ampliamente en sistemas de comunicación digitales. Para cualquier número entero positivo existe un código Hamming. Desde entonces , 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 podría construirse columna por columna: la columna son los bits de la representación binaria de un número entero , como se muestra en el siguiente ejemplo. El código Hadamard tiene una distancia mínima y por 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 quitamos la primera columna (la columna de todos ceros) , 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 ilustra esto (llamado algoritmo de decodificación del vecino más cercano):

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

Salida: una palabra de código más cercana a , si corresponde. ${\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 entrada , marque si está dentro . Si es así, regrese como la solución. ${\displaystyle w}$ ${\displaystyle B_{t}(v)}$ ${\displaystyle w}$ ${\displaystyle C}$ ${\displaystyle w}$
• Incremento . Falla sólo cuando la enumeración está completa y no se ha encontrado ninguna solución. ${\displaystyle t}$ ${\displaystyle t>(d-1)/2}$

Decimos que un lineal tiene corrección de 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 a menudo se denotan 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 ( n ,  k ). código. Los códigos de bloque lineales se denominan frecuentemente códigos [ n ,  k ,  d ], donde d se refiere a la distancia Hamming mínima 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 Hamming mínimo. distancia d .)

Encuadernado singleton

Lema ( enlace 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 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 existe una permutación p en el grupo simétrico S _n para la cual (c ₁ ,...,c _n ) en C ₁ si y sólo 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 hay una matriz monomial que envía C ₁ isomórficamente 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 sólo si existe alguna constante d tal que la distancia entre dos de las distintas palabras de código del código sea igual a d . ^[4] 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 . ^[5]

Ejemplos

Algunos ejemplos de códigos lineales incluyen:

• Códigos de repetición
• Códigos de paridad
• Códigos cíclicos
• códigos hamming
• Código Golay , tanto en versión binaria como ternaria .
• Códigos polinomiales , de los cuales los códigos BCH son un ejemplo
• Códigos Reed-Salomón
• Códigos Reed-Muller
• Códigos de geometría algebraica
• Códigos binarios 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 Hamming sobre alfabetos que no son 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 denominada 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 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}}$

Más recientemente, ^{[ ¿cuándo? ]} algunos autores también se han referido a estos códigos sobre anillos simplemente como códigos lineales. ^[9]

Ver también

• Métodos de decodificación

Referencias

1. William E. Ryan y Shu Lin (2009). Códigos de canales: clásico y moderno . Prensa de la Universidad de Cambridge. pag. 4.ISBN _ 978-0-521-84868-8.
2. MacKay, David, JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje (PDF) . Prensa de la Universidad de Cambridge . pag. 9. Bibcode : 2003itil.book.....M. ISBN 9780521642989. En 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). "Cada código lineal equidistante es una secuencia de códigos Hamming duales". Ars Combinatoria . 18 : 181–186.
6. Marco Greferath (2009). "Una introducción a la teoría de la codificación lineal en anillos". En Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Bases de Gröbner, codificación y criptografía . Medios de ciencia y negocios de Springer. 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.). Saltador. Capítulo 8: Códigos superiores al ℤ ₄ . ISBN 978-3-540-64133-9.
9. ST Dougherty; J.-L. kim; P. Solé (2015). "Problemas abiertos en la teoría de la codificación". En Steven Dougherty; Alberto Facchini; André Gerard Leroy; Edmundo Puczylowski; Patricio Sole (eds.). Anillos no conmutativos y sus aplicaciones . Sociedad Matemática Estadounidense. pag. 80.ISBN _ 978-1-4704-1032-2.

Bibliografía

• JF Humphreys; MI Prest (2004). Números, Grupos y Códigos (2ª ed.). Prensa de la Universidad de Cambridge. 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, 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.
• La base de datos de códigos Z4 en línea, base de datos actualizada de códigos Z4 óptimos.