Codigos bloque

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, deacuerdo 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. Enconsecuencia, 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 ysó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.

Ejemplo decódigo lineal (7,4)

Mensajes
Palabras código

( 0 0 0 0)
( 0 0 0 0 0 0 0 )

( 1 0 0 0)
( 1 1 0 1 0 0 0 )

( 0 1 0 0)
( 0 1 1 0 1 0 0 )

( 1 1 0 0)
( 1 0 1 1 1 0 0 )

( 0 0 1 0)
( 1 1 1 0 0 1 0 )

( 0 1 1 0)
( 0 0 1 1 0 1 0 )

( 1 1 1 0)
( 1 0 0 0 1 1 0 )

( 0 0 0 1)
( 0 1 0 1 1 1 0 )

( 1 0 0 1)
( 1 0 1 0 0 0 1 )

( 0 1 01)
( 0 1 1 1 0 0 1 )

( 1 1 0 1)
( 1 1 0 0 1 0 1 )

( 0 0 1 1)
( 0 1 0 0 0 1 1 )

( 1 0 1 1)
( 1 0 0 1 0 1 1 )

( 0 1 1 1)
( 0 0 1 0 1 1 1 )

( 1 1 1 1)
( 1 1 1 1 1 1 1 )


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 lasiguiente 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 delmensaje 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ódigosistemá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 sonidé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 =...