En la 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 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 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. decodificación de síndrome ). [ 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 destinatario de un bloque de mensajes puede 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 enviará. [2] Un código lineal de longitud n transmite bloques que contienen n símbolos. Por ejemplo, el código de Hamming [7,4,3] es un código binario linealque 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 4 = 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 dónde es el campo finito con q elementos. Tal código se llama código q -ary. 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 .
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 se diferencian. 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 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 ].
Queremos dar la base estándar porque cada coordenada representa un "bit" que se transmite a través de un "canal ruidoso" con alguna pequeña probabilidad de error de transmisión (un canal simétrico binario ). Si se usa alguna otra base, este modelo no se puede usar y la métrica de Hamming no mide el número de errores en la transmisión, como queremos.
Generador y matrices de control
Como un subespacio lineal de, todo el código C (que puede ser muy grande) puede representarse como el intervalo de un conjunto depalabras en clave (conocidas como base en álgebra lineal ). Estas palabras de código básicos a menudo se recogen en las filas de una matriz G conocida como una matriz generadora para el código C . Cuando G tiene la forma de matriz de bloques, dónde denota el matriz de identidad y P es algo matriz, entonces decimos que G está en forma estándar .
Una matriz H que representa una función linealcuyo 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,, luego 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 matriz, mientras que H es una matriz.
La linealidad garantiza que la distancia mínima de Hamming d entre una palabra de código c 0 y cualquiera de las otras palabras de código c ≠ c 0 es independiente de c 0 . Esto se deriva de la propiedad de que la diferencia c - c 0 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 0 ) = d ( c - c 0 , 0). Estas propiedades implican que
En otras palabras, para encontrar la distancia mínima entre las palabras de código de un código lineal, solo se necesitaría 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 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 .
Prueba: Porque, que es equivalente a , dónde es el columna de . Quite esos elementos con, esos con 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 dónde es el conjunto de índices de columna. . Ahora considere el vector tal que Si . Nota porque . Por lo tanto, tenemos, que es el número mínimo de columnas linealmente dependientes en . Por tanto, se prueba la propiedad reclamada.
Ejemplo: códigos de Hamming
Como la primera clase de códigos lineales desarrollados con el propósito de corregir errores, los códigos Hamming se han utilizado ampliamente en los sistemas de comunicación digital. Para cualquier entero positivo, existe un Código Hamming. Desde, este código de 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 Código Hamming.
Ejemplo: códigos Hadamard
El código Hadamard es uncódigo lineal y es capaz de corregir muchos errores. El código de Hadamard se puede construir columna por columna: el la columna son los bits de la representación binaria del entero , como se muestra en el siguiente ejemplo. El código de Hadamard tiene una distancia mínima y por lo tanto puede corregir errores.
Ejemplo: el código de bloque lineal con la siguiente matriz generadora es un Código Hadamard: .
El código Hadamard es un caso especial de código Reed-Muller . Si sacamos la primera columna (la columna todo cero) de, obtenemos código simplex , que es el código dual del 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 del vecino más cercano):
Entrada: Un vector recibido v en .
Salida: una palabra en clave en más cercano a , Si alguna.
- Empezando con , repita los dos pasos siguientes.
- Enumerar los elementos de la bola de radio (Hamming) alrededor de la palabra recibida , denotado .
- Para cada en , comprobar si en . Si es así, regresa como la solución.
- Incremento . Fallar solo cuando por lo que la enumeración está completa y no se ha encontrado ninguna solución.
Decimos que un lineal es -corregir error si hay como máximo una palabra de código en , para cada en .
Notación popular
Los códigos en general a menudo se indican con la letra C , y un código de longitud n y de rango k (es decir, que tiene k palabras de código en su base y k filas en su matriz generadora ) generalmente se conoce como un ( n , k ) código. Los códigos de bloques lineales se denotan frecuentemente como 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 tenga palabras de código M ) y un mínimo de Hamming distancia d .)
Límite de singleton
Lema ( límite Singleton ): Cada código lineal [n, k, d] C satisface.
Un código C cuyos parámetros satisfacen k + d = n + 1 se denomina distancia máxima separable o MDS . Tales códigos, cuando existen, son en cierto sentido los mejores posibles.
Si C 1 y C 2 son dos códigos de longitud n y si hay una permutación p en el grupo simétrico S n para el cual (c 1 , ..., c n ) en C 1 si y solo si (c p (1 ) , ..., c p (n) ) en C 2 , entonces decimos que C 1 y C 2 son equivalentes de permutación . En más general, si hay un matriz monomial que envía C 1 isomórficamente a C 2, entonces decimos que C 1 y C 2 son equivalentes .
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 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 de Hamming duales . [5]
Ejemplos de
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 los binarios y ternarios versiones
- Códigos polinomiales , de los cuales los códigos BCH son un ejemplo
- Códigos Reed-Solomon
- Códigos Reed-Muller
- Códigos 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 que no son de campo, especialmente sobre anillos finitos (más notablemente sobre Z 4 ) dando 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(es decir, GF (2 2 m )) con la distancia de Hamming y(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 como imágenes de códigos lineales de anillo de . [6] [7] [8]
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
- ^ William E. Ryan y Shu Lin (2009). Códigos de canal: clásico y moderno . Prensa de la Universidad de Cambridge. pag. 4 . ISBN 978-0-521-84868-8.
- ^ 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 , el extra los bits son funciones lineales del original bits estos bits adicionales se denominan bits de verificación de paridad
- ^ 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.
- ^ Etzion, Tuvi; Raviv, Netanel (2013). "Códigos equidistantes en Grassmannian". arXiv : 1308.6231 [ math.CO ].
- ^ Bonisoli, A. (1984). "Cada código lineal equidistante es una secuencia de códigos de Hamming duales". Ars Combinatoria . 18 : 181-186.
- ^ Marcus Greferath (2009). "Una introducción a la teoría de la codificación lineal del 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.
- ^ "Enciclopedia de las matemáticas" . www.encyclopediaofmath.org .
- ^ JH van Lint (1999). Introducción a la teoría de la codificación (3ª ed.). Saltador. Capítulo 8: Códigos superiores a ℤ 4 . ISBN 978-3-540-64133-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. 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)] . En línea, tabla 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.