CÓDIGOS BLOQUE

CÓDIGOS BLOQUE LINEALES

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 en 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 palabra binaria de n bits, v, con n > k. 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.

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 k-dimensional. 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 (Tabla 1) 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.

Matriz generadora: Un código lineal (n,k) esta completamente definido por las k filas de la matriz generadora G.

Ejemplo

El código lineal (7,4) dado en la tabla 1 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 = u*G = (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 la tabla 1 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:
 

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

Sea u = ( 1 0 1 1 ), el mensaje que hay que codificar, y G la matriz de abajo. Entonces podemos obtener v de la siguiente forma:
 

v = ( 1 0 0 1 0 1 1 )

Además, podemos comprobar:

v6 = u3
v5 = u2
v4 = u1
v3 = u0
v2 = u1 + u2 + u3
v1 = u0 + u1 + u2
v0 = u0 + u2 + u3

Matriz H:  Esta matriz H es la matriz de comprobación de paridad del código. 

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.

  Esto implica que G HT = 0 . 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.
 

Vector de error:

El vector suma de r y v es e. Los unos 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 (FEC) o pedirá una retransmisión (ARQ)

Síndrome:

Cuando se recibe r, el decodificador calcula lo siguiente:

s = r HT = ( s0, s1,..., sn-k-1 ) es el síndrome de r.

s = 0 si y sólo si r es una palabra código, 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. Esto sucede cuando el vector de error es idéntico a una palabra código no nula. Estos errores son errores indetectables. Como hay 2k - 1 palabras código no nulas, hay 2k - 1 errores indetectables. Una vez que se encuentra el error, se considera que el vector r + e es la palabra código transmitida.

Ejemplo

Sea C(7,4) y r =(1 0 0 1 0 0 1) el vector recibido. La matriz G es:

entonces, la matriz H es:

Por lo tanto, el síndrome es s =rHT

cuyo resultado es s =(1,1,1) = eHT. Por lo tanto, existe error. De HT obtenemos:

s0 = 1 = e0 + e3 + e5 + e6

s1 = 1 = e1 + e3 + e4 + e5

s2 = 1 = e2 + e4 + e5 + e6

Fijamos valores de e3, e4, e5 y e6 y despejamos los valores de e0, e1 y e2

. . . . . . .

. . . . . . .

. . . . . . .

El vector error más probable será el que menos errores (unos) tenga, el cual será:

e = (0 0 0 0 0 1 0). Entonces podemos hallar v = (1 0 0 1 0 1 1)

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.

  Sean v y w, 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.

  Corolario. Sea C un código lineal cuya matriz de comprobación de paridad es H . El peso mínimo ( o la mínima distancia ) de C es igual al menor número de columnas de H que suman 0.

PROPIEDADES DETECTORAS.

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 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.

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.

Probabilidad de no detectar un error

Sea C un código lineal (n,k). Sea Ai el número de vectores del código de peso i. A los números A0, A1, ..., An se les llama distribución del peso de C. Si C se usa sólo para detección de errores en un BSC (Canal Binario Simétrico), la probabilidad de que el decodificador falle al detectar errores se puede calcular como la distribución del peso de C. Vamos a denotar la probabilidad de no detectar un error como PU(E).

Donde p es la probabilidad de error de bit del canal. Además, si la distancia mínima de C es dmin, entonces desde A1 hasta Admin - 1 son cero.

Ejemplo

Vamos a considerar el código de la tabla 1. La distribución del peso de este código es: A0 = 1, A1 = A2 = 0, A3 = A4 = 7, A5 = A6 = 0, y A7 = 1. La probabilidad de que no se detecte un error es:

  PU(E) = 7p3(1 - p)4 + 7p4(1 - p)3 + p7.

  Si p = 10-2, esta probabilidad es aproximadamente 7 x 10-6. En otras palabras, si un millón de palabras se transmiten por un canal BSC con p = 10-2, por término medio siete palabras código erróneas pasaran por el decodificador sin ser detectados.

CLASES DE CODIGOS DE BLOQUE LINEALES

CODIGOS HAMMING

Un código Hamming (n, k) se caracteriza por una matriz H cuyas columnas son todas las posibles secuencias de n- k dígitos binarios excepto el vector 0. Para todo l=1, 2, 3, ... existe un código Hamming de (2^l-1, 2^l-1-l). Su distancia mínima es 3, por lo que corrige todos los errores en un bit.

Ejemplo

Sea la matriz de comprobación del código Hamming (11,15)

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 1 1 1 0 0 0 0 1 1 1 1

H= 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

En contra de los intereses en general, esta matriz no es sistemática, aunque para que lo sea sólo hay que reordenar la columnas. Por el contrario, tiene la interesante propiedad de queun vector error obtenido con esta matriz, con un solo error, genera un síndrome que determina, en binario, la posición del error en la secuencia recibida.

Los códigos Hamming son perfectos. Esto quiere decir que todas las posibles secuencias recibidas están a distancia 2 de una palabra código.

CODIGOS HAMMING EXTENDIDOS.

Estos códigos se obtienen añadiendo un símbolo adicional que computa todos los anteriores n símbolos de la palabra código. Tienen dmin = 4, por lo que detectan todos los errores dobles y a la vez corrigen todos los individuales. La decodificación se realiza así:

CODIGOS DUALES.

Dos códigos se dice que son duales cuando la matriz de comprobación de paridad H de uno es la matriz generadora del otro.

CODIGOS MAXIMAL-LENGTH.

Son los duales de los códigos HAMMING, por lo que la matriz de comprobación H de un código Hamming es la matriz generadora de uno maximal-length.

CODIGOS REED-MULLER

Son una familia de códigos que cubre un amplio rango de tasas y distancias mínimas. Para cualquier valor de m, y fijando un r < m, hay un código Reed-Muller con n=2^m,