Codificacion para control de errores

Capítulo VII
Codificación Para Control de Errores



La codificación de bloques puede ser escalar o vectorial, trataremos la escalar pero sus principios son aplicables a la vectorial.

En un codificador de bloques escalar se agrupan K dígitos de información y se le añaden r dígitos de paridad que dependen de los anteriores de acuerdo a cierta regla de codificación. Esto se realiza enforma sucesiva.








El código se denota (n, k) y la eficiencia de codificación se define por:


Entre mayor menor es la capacidad para detectar y corregir errores.

El decodificador opera sobre la palabra recibida (n estimada, ) y determina si los bits de información y de paridad satisfacen las reglas de codificación; en caso de discrepancia detecta y corrige los errores.

Loscodificadores de bloques más usados son aquellos en que los bits de paridad de datos están dados por una suma ponderada modulo dos de los bits de datos (códigos lineales) y los bits de paridad aparecen después de los bits de datos (códigos sistemáticos).

El caso más simple de un código escalar es el que tiene un solo bit de paridad, aquí el bit puede detectar la presencia de errores nones, pero nolocalizarlos y, en consecuencia, no corregirlos. En una secuencia de k dígitos el bit de paridad completa a par el número de unos (paridad par) o a un número non (paridad impar).

Así para el código de bloque (7, 6):
k = 6

Si escogemos paridad par:
Si escogemos paridad impar:

Este esquema es sistemático y lineal, el bit adicional es la suma modulo 2 de los anteriores.En paridad par:


y el negado en paridad impar.


Principios de funcionamiento.

Consideremos bloques de entrada de k bits:



Cada bloque forma un vector o palabra:



Y a la salida se tiene la palabra:



Para un código sistemático:



Y si es lineal, los bits de paridad están dados por:





Donde: r = n – k
=1 ó 0
La elección delos determina el tipo de código.

Matricialmente:
con sumas mod 2
1 x n k x n
1 x k

a la matriz G se le llama matriz generadora del código.

G = [ Ik P] Ik = Porque los primeros k bits coinciden con los de datos.
P = Formada por el arreglo de los transpuestos.



Veamos por ejemplo, un código (7, 3) cuya matriz p es:

P es de orden 3 x 4

entonces n=7 , k =3 y existen 4 bits de paridad, su matriz generadora es:




Si


y sucesivamente:




1
000
0000000
2
001
0011111
3
010
0100110
4
011
0111001
5
100
1001100
6
101
1010011
7
110
1101010
8
111
1110101

Los bits de paridad están dados como:



Supongamos que se recibe: 0 0 0 0 1 1 0,la palabra más cercana es 3, cada vector C difiere de cualquierde cualquier otro en al menos tres posiciones, en consecuencia cualquier vector con un error es corregible puesto que la palabra recibida seguirá estando más próxima a la correcta. La diferencia entre el mínimo número de posiciones de dos vectores codificados cualesquiera, se llama distancia de Hamming. Para que sean corregibles ‘t’ errores, la distancia de hamming (d) debe de ser:



En estecaso puede corregir un solo error.

El procedimiento de corrección de errores más simple es el comparar la palabra codificada recibida, con una tabla de palabras codificadas y seleccionar la más cercana; sin embargo el número de comparaciones crece exponencialmente con k, por lo que no es apropiado para códigos grandes. Afortunadamente las relaciones algebraicas de los códigos proporcionan otrosmétodos más eficientes.

El siguiente método es aplicable a los códigos correctores de errores simples, pero su principio de aplica a otros mayores.

A la matriz:
H = [PT Ir]

r x n r x k
se le llama matriz de comprobación de paridad. Es fácil verificar que :

1 x n
n x r

Sea el vector recibido en lugar de


donde es un vector de n bits formado por unos...