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 4 =16 palabras de código.
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 .
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).
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.
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 .
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.
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 deduce de la propiedad de que la diferencia c − c 0 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 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, 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.
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.
Ejemplo: el código de bloque lineal con la siguiente matriz generadora y matriz de verificación de paridad es un código Hamming.
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.
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 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.
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 de código más cercana a , si corresponde.
Decimos que un lineal tiene corrección de errores si hay como máximo una palabra de código en , para cada en .
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 .)
Lema ( enlace Singleton ): Todo código lineal [n,k,d] C satisface .
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 1 y C 2 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 1 ,...,c n ) en C 1 si y sólo si (c p(1 ) ,...,c p(n) ) en C 2 , entonces decimos que C 1 y C 2 son permutaciones equivalentes . En términos más generales, si hay una 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.
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]
Algunos ejemplos de códigos lineales incluyen:
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]
Algunos autores también se han referido a estos códigos sobre anillos simplemente como códigos lineales. [9]
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.
{{cite book}}
: CS1 maint: multiple names: authors list (link)