TEMA 7: DETECCION DE
ERRORES.
1.-
Paridad.
Se añade un bit a los bits de datos, llamado bit de paridad que se elige
de forma que el numero total de 1 sea par o impar.
2.- Codigos de Hamming
(R.W. Hamming).
a) Codigos de bloque: Los datos estan agrupados en bloques, y a
cada bloque se le añade un cierto numero de bits (de redundancia). Solo ciertas
combinaciones de bits son aceptables (palabra de codigo valida).
Cuando los datos llegan al receptor, hay dos posibilidades
- La palabra recibida es de codigo valida.
- La palabra recibida no es de codigo valida, hay dos
posibilidades:
- El receptor pueda recrear el codigo original (codigo
autocorrector).
- El receptor pueda pedir que se retransmita el bloque original (codigo
de autochequeo).
La eficacia de estos codigos depende de la diferencia entre una palabra
de codigo valida y otra. Cuanto mayor sea la diferencia, menor posibilidad de
que una palabra de codigo valida sea transformada en otra por una serie de
errores.
Distancia de Hamming es el
numero de bits que tienen que ser cambiados para transformar una PALABRA DE
CODIGO VALIDA en la siguiente PALABRA DE CODIGO VALIDA en secuencia.
Ej: Codigo de Gray
00000000
La distancia de Hamming es 1
00000001
Es imposible utilizar este codigo para enviar datos porque no se
distin-
00000011
guen los errores.
00000010
00000110
Distancia de Hamming
Errores detectables
Errores corregibles
1
0
0
2
1
0
3
2
1
4
3
1
5
4
2
Dentro de los
de
1.- Chequeo de paridad vertical: A los bits de datos se les añade un bit
de paridad
2.- Codigos i en n. De las 2n posibles combinaciones, solo son
validas las que tienen i bits a 1.
Ej: Codigo 4 en 8.
28 = 256 combinaciones, de las cuales solo son
validas:
00001111
00010111
00011011
(Distancia de Hamming: 2)
00011101
00011110
...
3.- Chequeo de paridad longitudinal.
Ej: PAG en ASCII
P=50, A=41, G=47
VRC (Vertical )
P=50
10100000
A=41
10000010
G=47
10001110
LRC (long.)=>
10101100 <= (Bit de paridad cruzada)
5 6
50414756
La distancia
de Hamming es 4, por lo que detecta 3 errores, pero solo puede corregir (o ver
donde esta) 1 bit erroneo.
Como detectaria los
errores:
10110000
10000010
10001110
10101100
1.- Mira el bit de paridad (esta bien).
2.- Mira las filas, y detecta que en la 1ª hay un error.
3.- Mira las columnas, y detecta que en la 4ª hay un error.
En la interseccion de fila 1 y columna 4 esta el bit erroneo (en
negrita).
3.- Codigos Ciclicos,
Polinomiales o CRC.
Se usa un polinomio generador, G(x), de grado r.
Se considera que los bits que mandamos son los coeficientes de un
polinomio. Se le añaden r bits de redundancia, de forma que el polinomio
resultante sea divisible por el generador, sin que quede resto.
El receptor, al recibir los datos, divide por el polinomio generador. Si
el resto es 0, no hay error; si no, detecta error y pide
Algoritmo:
1.- Añadir r bits 0 a la derecha.
2.- Dividir por el polinomio generador (division en *modulo 2, es decir,
en binario y sin acarreo).
3.- Añadir el resto al polinomio original.
Ej:
10011011
G(x)=x3 + 1=1001
r=3
10011011000 |1001 .
1001
10001010
* En modulo 2, si tengo los mismos bits que en el divisor
00001011
y el primer bit es un 1, puedo dividir (y no hay acarreo al
1001
restar).
001000
(*)1001
00010
Resultado: 10011011010
(Nota: el polinomio
generador de la CCITT => G(x)= x16 + x12 + x5
+ 1)
Si quiere figurar en la sección de enlaces recomendados e intercambiar enlaces con Alipso.com
Monografías
