Codigos Lineales

CODIGOS LINEALES

Definición


Un código lineal de longitud n sobre un campo finito Fq es simplemente un subespacio del vector espacial Fqn.




Como los códigos lineales son vectores espaciales, su estructura algebraica a menudo lo hace mas facil de describir y usar que códigos no lineales. Vamos a enfocar nuestra atención a los códigos lineales sobre campos finitos.

Vector espacial sobre campos finitos


Sea Fq un campo finito de orden q. Un conjunto no-vacio V, juntos con algunos (vectores) de suma y multiplicación escalar por elementos de Fq , es un vector espacial (o espacio lineal) sobre Fq si satisface todas de las siguientes condiciones.  Para todo u, v, w Є V y para todo λ , µ Є Fq:










u+vЄV (u + v) + w = u + (v + w) Existe un elemento 0 Є V con la propiedad 0 + v = v = v + 0 para todo v Є V Para cada u Є V existe un elemento de V llamado – u, tal que u + (– u) = 0 = (– u) + u u+v=v+u λvЄV λ (u + v) = λu + λv, (λ λ + µ)u = λu + µu (λµ λµ)u µu) λµ = λ(µ Si 1 es la identidad multiplicativa de Fq , entonces 1u = u




Sea Fqn el conjunto de todos los vectores de longitud n con entradas en Fq : Fqn = {(v1, v2, …., vn): vi Є Fq }

Definimos la adición vectorial para Fqn : v = (v1, v2, …., vn) Є Fqn y w = (w1, w2, …., wn) Є Fqn Entonces v + w = (v1 + w1, v2 + w2, …., vn + wn) Є Fqn

Definimos la multiplicación escalar para Fqn : v = (v1, v2, …., vn) Є Fqn y λ Є Fq

Entonces λv = (λv1, λv2, …., λvn) Є Fqn Sea 0 utilizado para denotar el vector cero (0, 0, …, 0) Є Fqn




Un subconjunto C no-vacío de un vector espacial V es un subespacio de V si el mismo es un vector espacial con las mismas adición vectorial y multiplicación escalar que V.  Un subconjunto C no vacío de un vector espacial V sobre Fq es un subespacio si y solo si se cumple la siguiente condición: Si x, y Є C y λ, µ Є Fq, entonces λx + µy Є C







Sea V un vector espacial sobre Fq. Una combinación lineal de v1, v2, …., vr Є V es un vector de la forma λ1v1, λ2v2, …., λrvr , donde λ1, λ2, …., λr Є Fq,son escalares. Sea V un vector espacial sobre Fq. Un conjunto de vectores {v1, v2, …., vr } en V es linealmente independiente si λ1v1 + λ2v2 +….+ λrvr = 0 = λ1 = λ2 = ….= λr = 0 El conjunto es linealmente dependiente si no es linealmente independiente p.e. existen λ1, λ2, …., λr Є Fq, no todos cero pero algunos si, de modo que λ1v1 + λ2v2 +….+ λrvr = 0




Sea V un vector espacial sobre Fq y sea S = {v1, v2, …., vk} un subconjunto no-vacio de V. El (linear) span de S se define como <S> = {λ1v1+….+ λkvk : λi Є Fq} Si S = 0, definimos <S> = 0. Es muy fácil comprobar que <S> es un subespacio de V, llamado el subespacio generado (o spanned) por S. Dado un subespacio C de V, un subconjunto S de C es llamado un conjunto generador (o conjunto spanning) de C si C = <S>. 




Si S ya es un subespacio de V, entonces <S> = S.

Sea V un vector espacial sobre Fq . Un subconjunto no-vacío B = {v1, v2, …., vk} de V es llamado la base para V si V = y B es linealmente independiente. 



Si B = {v1, v2, …., vk} es una base para V, entonces cualquier vector v Є V puede ser expresado como una única combinacion lineal de vectores. Un vector espacial V sobre un campo finito Fq puede tener muchas bases, pero todas esas bases tendrán el mismo número de elementos. Este número es llamado la dimensión de V sobre Fq, denotado por dim(V)




Sea v = (v1, v2, …., vn), w = (w1, w2, …., wn) Є Fqn.  El producto escalar (o producto punto) de v y w se define como v.w = v1 w1+ v2 w2+ ….+ vn wn) Є Fqn
Los dos vectores v y w se dicen que son ortogonales si v.w = 0.
Sea S un subconjunto no-vacío de Fqn. El complemento ortogonal S┴ de S se define como S┴ = {v Є Fqn: v.s = 0 para todo s Є S} Si S = 0, entonces definimos S┴ = Fqn

Códigos lineales


Un código lineal C de longitud n sobre Fq es un subespacio de Fqn. p.e. (q=2) C = {000, 001,010,011} (q=3) C = {0000, 1100, 2200, 0001, 0002, 1102, 2201, 2202} (q=2) C = {000, 001, 010, 011, 100, 101, 110, 111}




Un código lineal C de longitud n y dimensión k sobre es llamado código q-ario (n,k) o, si q esta sobreentendido del contexto, un código (n,k). También es un código lineal (n,qk). Si la distancia d de C es conocida, es también referido como un código lineal (n,k,d).

Distancia Mínima de un Código








El peso Hamming ( o simplemente peso ) de v, que se denota como w(v), se define como el número de componentes distintas de cero de v. Por ejemplo, el peso de v = ( 1 0 0 1 0 1 1 ) es 4. La distancia Hamming ( o simplemente distancia ) entre v y w, que se denota como d(v,w), se define como el número de dígitos en el mismo sitio que tienen diferentes. Por ejemplo, la distancia Hamming entre v = ( 1 0 0 1 0 1 1 ) y w = ( 0 1 0 0 0 1 1 ) es 3; tienen diferentes las posiciones cero, uno y tres. De todo esto se deduce que la distancia Hamming entre dos ntuplas, v y w, es igual a el peso Hamming de la suma de v y w, esto es: d(v,w) = w( v + w ) Por ejemplo, la distancia Hamming entre v = ( 1 0 0 0 1 0 1 1 ) y w = ( 1 1 1 0 0 1 0 ) es 4 y el peso de v + w = ( 0 1 1 1 0 0 1 ) es también 4.




Dado un código bloque C, se puede calcular la distancia Hamming entre cualquiera dos palabras código distintas. La distancia mínima de C ( dmin) se define como: dmin = min { d(v,w) : v,w pertenecen a C, v distinto de w }.




Sea C un código lineal, la suma de dos vectores es también un vector código. Por lo tanto, la distancia Hamming entre dos vectores código en C es igual al peso Hamming de un tercer vector código en C. De esto obtenemos que: dmin = min { d(v,w) : v,w pertenecen a C, v distinto de w }= = min { w(x) : x pertenece a C, x distinto de 0 } = wmin.




wmin es el peso mínimo del código lineal C.

Introducción a los Códigos Bloque Lineales








Asumimos que la salida de una fuente de información es una secuencia de dígitos binarios "0" o "1". En la codificación de bloque, esta secuencia de información binaria es segmentada en bloques de mensaje de una longitud fija; cada bloque de mensaje, llamado u, consiste de k dígitos de información. Hay un total de 2k mensajes distintos. El codificador, de acuerdo con ciertas reglas, transforma cada mensaje entrante u, en una n-tupla binaria, v, con n > k. Esta n-tupla binaria v es lo que llamamos palabra código ( o vector código ) del mensaje u. Por lo tanto, para los 2k posibles mensajes, hay 2k palabras código. A este conjunto de 2k palabras código, se le llama Código bloque. Para que un código bloque sea útil, las 2k palabras código deben ser distintas. En consecuencia, tiene que haber una correspondencia uno a uno entre un mensaje u y su palabra código v.




Para un código con 2k palabras código de longitud n, a menos que tenga una estructura especial, el aparato de codificación será prohibitivamente complejo si k y n son grandes, ya que tiene que almacenar las 2k palabras código de longitud n en un diccionario. Por lo tanto, debemos restringir nuestra atención a códigos de bloque que pueden ser mecanizados de una manera práctica. Una estructura que se desea que tenga un código bloque, es la linealidad . Con esta estructura, la complejidad de la codificación se reduce enormemente, como veremos más adelante.

Código bloque lineal





A un código bloque de longitud n y 2k palabras código se le llama código lineal (n,k) si y sólo si sus 2k palabras código forman un subespacio kdimensional del espacio vectorial de las n-tuplas sobre el campo GF(2). De hecho, un código binario es lineal si y sólo si la suma de módulo 2 de dos palabras código es también una palabra código. El bloque código dado en la siguiente tabla es un código lineal (7,4). Se puede comprobar fácilmente que la suma de dos palabras código en este código es también otra palabra código.

Ejemplo de código lineal (7,4) Mensajes

Palabras código

( 0 0 0 0)

(0000000)

( 1 0 0 0)

(1101000)

( 0 1 0 0)

(0110100)

( 1 1 0 0)

(1011100)

( 0 0 1 0)

(1110010)

( 0 1 1 0)

(0011010)

( 1 1 1 0)

(1000110)

( 0 0 0 1)

(0101110)

( 1 0 0 1)

(1010001)

( 0 1 0 1)

(0111001)

( 1 1 0 1)

(1100101)

( 0 0 1 1)

(0100011)

( 1 0 1 1)

(1001011)

( 0 1 1 1)

(0010111)

( 1 1 1 1)

(1111111)







Dado que un código lineal (n,k) C es un subespacio kdimensional del espacio de vectores Vn de las n-tuplas binarias, es posible encontrar k palabras código linealmente independientes, g0, g1,..., gk-1 en C, de tal forma que cada palabra código v en C es una combinación lineal de esas k palabras código: v = u0 g0 + u1g1 + ... + uk-1gk-1 donde ui= 0 ó 1 para i mayor igual que cero y menor que k. Ahora vamos a colocar estas k palabras código linealmente independientes como las filas de una matriz k x n:




donde g = (gi0 , gi1 , ..., gi,n-1). Si u = (u0 , u1 , ..., uk-1) es el mensaje que va a ser codificado. La palabra código correspondiente puede ser dada de la siguiente manera: v=uG= u0 g0 + u1 g1 + ... + uk-1 gk-1

Evidentemente la filas de G generan el código lineal (n,k) C. Por esta razón a la matriz G se la llama matriz generadora de C. Nótese que cualquier conjunto de k palabras código linealmente independientes pueden ser usadas para formar una matriz generadora del código. Por lo tanto, un código lineal (n,k) esta completamente definido por las k filas de la matriz generadora G. Como consecuencia de esto, el codificador solo tiene que almacenar las k filas de G y formar una combinación lineal de estas k filas basada en el mensaje de entrada u.

Ejemplo:


El código lineal (7,4) dado en la tabla anterior tiene la siguiente matriz como matriz generadora:

Sea u = (1 1 0 1) el mensaje que hay que codificar, su palabra código correspondiente será : v = 1 g0 + 1 g1 + 0 g2 + 1 g3 = ( 1 1 0 1 0 0 0) + (0 1 1 0 1 0 0) + (1 0 1 0 0 0 1) = (0 0 0 1 1 0 1)

Forma sistemática





Una propiedad deseable en un código lineal es una estructura sistemática de las palabras código como la mostrada en la siguiente figura, donde una palabra código se divide en dos partes: la parte del mensaje y la parte de redundancia. La parte del mensaje consiste de k bits de información inalterada ( o mensaje) y la parte de redundancia consiste de de n - k bits de comprobación de paridad, los cuales son una suma lineal de los bits de información. A un código lineal de bloque con esta estructura se le llama código lineal sistemático de bloque . El código (7,4) dado en anteriormente es un código sistemático, los cuatro bits que están más a la derecha de cada palabra código son idénticos a los bits correspondientes de información. Forma sistemática de una palabra código:










Un código lineal (n,k) sistemático queda completamente definido por una matriz G k x n de la siguiente forma:

donde pij = 0 ó 1. Con Ik denotamos a la matriz identidad de dimensión k. Con lo que G = [P Ik]. u = ( u0, u1,...,uk-1) es el mensaje que hay que codificar. Por lo tanto, la palabra código correspondiente es: v = ( v0 , v1 , v2 , ... , vn-1) = ( u0 , u1 , ... , uk-1) G De donde obtenemos las componentes de v: vn-k+i = ui con 0 <= i < k vj = u0p0j + u1p1j + ... + uk-1vk-1,j con 0<= j < n - k. Esto nos muestra que los k primeros dígitos por la derecha de una palabra código v son idénticos a los dígitos de información u0, u1,..., uk-1 que hay que codificar, y que los n - k dígitos de redundancia que están a la derecha, son sumas lineales de los de información.

Ejemplo:


La matriz G dada está en forma sistemática. Si u = ( u0, u1, u2, u3) es el mensaje que hay que codificar, y v = ( v0, v1, v2, v3, v4, v5, v6 ) es la correspondiente palabra código. Entonces:




Por lo tanto la palabra código correspondiente a ( 1 0 1 1 ) es ( 1 0 0 1 011)




Hay otra matriz útil asociada con cada código lineal de bloque. Para cada matriz G de dimensiones k x n con k filas linealmente independientes, existe una matriz H de dimensiones ( n - k ) x n con n - k filas linealmente independientes de tal manera que cada vector en el espacio de las filas de G es ortogonal a las filas de H y cada vector que es ortogonal a las filas de H esta en el espacio de las filas de G . Como consecuencia de esto, podemos describir el código lineal (n,k) generado por G de esta forma alternativa: 

Una n-tupla v es una palabra código en el código generado por G si y sólo si v HT = 0. Esta matriz H es la matriz de comprobación de paridad del código. Las 2n-k combinaciones lineales de las filas de la matriz H forman un código lineal Cd ( n, n - k ). Este código es el espacio nulo del código lineal C (n,k) generado por la matriz G (esto es, por cualquier v perteneciente a C y cualquier w perteneciente a Cd, v w = 0 ). Cd es el código dual de C. Por lo tanto, una matriz de comprobación de paridad de un código lineal C es la matriz generadora de su código dual.

Si la matriz generadora de un código lineal (n,k) está en la forma sistemática, la matriz de comprobación de paridad tiene la siguiente forma:

H = [ In-k PT ] =

Donde PT es la traspuesta de la matriz P. Sea hj la j-ésima fila de H. Podemos comprobar que el producto de la i-ésima fila del G dada por (3.4) y de la j-ésima fila de H dada por (3.7) es gi hj = pij + pij = 0 con 0<= i < k y 0<= j < n - k. Esto implica que G HT = 0 . Además, las n - k filas de H son linealmente independientes. Por lo tanto, la matriz H es una matriz de comprobación de paridad del código lineal generado por la matriz G.

Síndrome y Detección de Errores


Consideramos un código lineal (n,k) con su matriz generadora G y su matriz de comprobación de paridad H. Sea v una palabra código que se transmite en un canal ruidoso, y r es el vector recibido a la salida del canal. Debido a que el canal es ruidoso, r puede ser distinto de v.




El vector suma de r y v es e; e es una n-tupla tal que ei=1 si ri es distinto de vi y ei=0 si ri=vi. A esta n-tupla se le llama vector de error. Los 1's que aparecen en e son errores de transmisión producidos porque el canal es ruidoso. El receptor recibe r que es la suma de la palabra código transmitida y el vector de error. Cuando recibe r, el decodificador debe determinar si contiene errores de transmisión. Si se detectan errores, el decodificador intentará corregirlos o pedirá una retransmisión.










Cuando se recibe r, el decodificador calcula la siguiente (n-k)tupla: s = r HT = ( s0, s1,..., sn-k-1 ), esta n-tupla es el síndrome de r. s = 0 si y sólo si r es una palabra código ( el receptor acepta r como la palabra código transmitida), y s es distinto de 0 si y sólo si r no es una palabra código ( el receptor detecta la presencia de un error ). Pero, es posible que los errores no sean detectables (i.e., r contiene errores pero s = 0 ). Esto sucede cuando el vector de error es idéntico a una palabra código no nula. En este caso, r es la suma de dos palabras código y por lo tanto el síndrome es igual a cero. Estos errores son errores indetectables. Como hay 2k - 1 palabras código no nulas, hay 2k - 1 errores indetectables.

Ejemplo


Vamos a calcular el sídrome del código cuya matriz de comprobación de paridad es la siguiente:




Si r = ( r0, r1, r2, r3, r4, r5, r6 ) es el vector recibido, el síndrome se calcula de la siguiente manera:




Con lo cual los dígitos que componen el síndrome son: s0 = r0 + r3 + r5 + r6 s1 = r1 + r3 + r5 + r6 s2 = r2 + r4 + r5 + r6







Como se ha visto, el síndrome depende solo del vector de error, y no de la palabra código transmitida: s = r HT = ( v + e ) HT = v HT + e HT Como v HT = 0. Obtenemos la siguiente expresión: s = e HT Una vez que se encuentra el error, se considera que el vector r + e es la palabra código transmitida. Desgraciadamente, determinar cual es el verdadero vector de error no es una cuestión sencilla. Esto es debido a que las n - k ecuaciones lineales no tienen una solución única, sino que tienen 2k soluciones. En otras palabras, hay 2k patrones de error que dan el mismo síndrome, y el verdadero error que se ha producido es únicamente uno de ellos. Para minimizar la probabilidad de error, se elige como vector de error al patrón de error más probable. Si el canal es BSC, el vector de error más probable es el que tiene el menor número de ceros.

Propiedades de detección y corrección de errores de un código bloque






Propiedades detectoras: Cuando se transmite un vector código v por un canal ruidoso, un vector de error con l errores provoca que el vector recibido r sea diferente del vector v en l posiciones [ i.e., d(v,r) = l ]. Si la distancia mínima del código C es dmin, cada pareja de dos vectores de C tienen al menos dmin posiciones distintas. Por lo tanto, cualquier vector de error con dmin - 1 o menos errores da un vector r que no es una palabra código de C. Cuando el receptor detecta que el vector recibido no es una palabra código de C, el error ha sido detectado. Por lo tanto, un código bloque con distancia mínima dmin es capaz de detectar todos los patrones de error de dmin - 1 o menos errores. Un código bloque detecta todos los patrones de error de dmin - 1 o menos errores, pero también detecta una gran fracción de los patrones de error con dmin o más errores. En realidad, un código lineal (n,k) es capaz de detectar 2n - 2k patrones de error de longitud n.







De entre los 2n - 1 patrones de error distintos de cero, hay 2k - 1 patrones de error que son idénticos a a las 2k - 1 palabras código. Si sucede cualquiera de esos 2k - 1 patrones de error, la palabras código transmitida, v se transforma en otra palabras código, w. Por lo tanto, se recibe w y su síndrome es cero. En este caso, el decodificador acepta w como la palabra transmitida y realiza una decodificación incorrecta. De todo esto concluimos que hay 2k - 1 patrones de error que son indetectables Hay 2n - 2k patrones de error detectables. Para n suficientemente grande, 2k - 1 es en general mucho mas pequeño que 2n. Por lo tanto, sólo una pequeña fracción de errores pasa por el decodificador sin ser detectados.











Propiedades correctoras: Si un código bloque C con distancia mínima dmin se usa para corregir errores aleatorios, es conveniente saber cuantos errores es capaz de corregir dicho código. La distancia mínima es par o impar. Por lo tanto, podemos elegir un entero t tal que: 2t + 1 <= dmin <= 2t + 2 Ahora vamos a probar que el código C es capaz de corregir todos los patrones de error de t o menos errores. Sean v y r el vector transmitido y recibido respectivamente. Sea w cualquier otro vector código de C. La distancia Hamming entre v, r y w satisface la desigualdad triangular:

Supongamos que un patrón de error de t' errores sucede durante la transmisión de v. Entonces, el vector recibido tiene t' posiciones distintas de v y d(v,r) = t'. Puesto que v y w son vectores código de C, tenemos que:











1. 2.


Obtenemos la siguiente desigualdad: d(w,r) => 2t + 1 - t' Si t'<= t, entonces: d(w,r) > t La desigualdad de arriba dice que si un patrón de t o menos errores tiene lugar, el vector recibido r está más cerca del vector transmitido v que a cualquier otro vector w en C. Basandose en el esquema de decodificación de máxima similitud, r es decodificado en v, que es el vector que se transmitió. Se ha realizado una decodificación correcta y por lo tanto una correccion de errores. Por otra parte, el código no es capaz de corregir todos los patrones de error de l errores con l > t, porque por lo menos hay un caso en el cual un patrón de error de l errores da lugar en recepción un vector r que está más cerca de un vector código incorrecto que al vector transmitido. Veamos esto con dos vectores código v y w: d(v,w) = dmin. Sean e1 y e2 dos patrones de error que satisfacen las siguientes condiciones: e1 + e2 = v + w. e1 y e2 no tienen componentes distintas de cero en las mismas posiciones. Obviamente, tenemos que: w(e1) + w(e2) = w(v + w) = d(v,w) = dmin.















Ahora suponemos que v se transmite y es corrompida por e1. El vector recibido es: r = v + e1. La distancia Hamming entre v y r es: d(v,r) = w(v + r) = w(e1). La distancia Hamming entre w y r es: d(w,r) = w(w + r) = w(w + v + e1) = w(e2). Ahora suponemos que el patrón de error e1 contiene más de t errores [i.e., w(e1) > t ]. Puesto que 2t + 1 <= dmin <= 2t + 2, obtenemos que: w(e2) <= t + 1. Combinando las tres últimas expresiones y usando el hecho de que w(e1) < t, obtenemos la siguiente desigualdad: d(v,r) => d(w,r). Esta desigualdad dice que existe un patrón de error de l ( l > t ) errores que da lugar a un vector recibido que que está más cerca de un vector incorrecto que del vector transmitido. Basandose en el esquema de decodificación de máxima similitud se puede producir una decodificación incorrecta. Para resumir, un código bloque con distancia mínima dmin garantiza que corrige todos los patrones de error de t = [( dmin - 1) /2] o menos errores Un código bloque con capacidad de corregir de t errores aleatorios generalmente es capaz de corregir bastantes patrones de error de t + 1 errores o más. Un código lineal (n,k) con capacidad de corregir t errores, es capaz de corregir un total de 2n - 2k patrones de error.