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 2ⁿ posibles combinaciones, solo son validas las que tienen i bits a 1.

                                Ej: Codigo 4 en 8.

                                               2⁸ = 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)=x³ + 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)= x¹⁶ + x¹² + x⁵ + 1)