Redes (deteccion de errores)

Detección de errores CRC

La verificación de redundancia cíclica (abreviado, CRC ) es un método de control de integridad de datos de fácil implementación. Es el principal método de detección de errores utilizado en las telecomunicaciones.

La verificación de redundancia cíclica consiste en la protección de los datos en bloques, denominados tramas. A cada trama se le asigna un segmento dedatos denominado código de control (al que se denomina a veces FCS, secuencia de verificación de trama, en el caso de una secuencia de 32 bits, y que en ocasiones se identifica erróneamente como CRC). El código CRC contiene datos redundantes con la trama, de manera que los errores no sólo se pueden detectar sino que además se pueden solucionar.

CRC es una técnica muy usada hoy en día.
–Un códigoCRC es un código basado en un polinomio.
–Es posible representar los datos enviados utilizando una polinomio
equivalente que posee coeficientes de valor 1 ó 0.

Representación polinomial:

–Un mensaje de d bits puede ser representado por un polinomio de grado
(d-1).
–Cada bit del mensaje corresponde a un coeficiente del polinomio.
–El bit más significativo representa el término de mayororden.

Ejemplo para un mensaje de 8 bits:

–Mensaje
• d=8
• 10011010
–Polinomio correspondiente:
• (1)x7 + (0)x6 + (0)x5 + (1)x4 + (1) x3 + (0)x2 + (1)x1 + (0)x0
• Grado = (d-1)

El objetivo es enviar esta información desde el transmisor hacia el receptor
incluyen un campo adicional denominado CRC.


El transmisor y el receptor utilizan un mismo
polinomio generador conocido paralos dos.
– El polinomio generador tiene grado r y se denomina
G(x)
– El polinomio generador se utilizará como divisor del mensaje de d bits.
– Ejemplo para r=3: x3 + x2 + 1
• El polinomio generador escogido define la habilidad de
cuántos errores se pueden detectar.
• El estudio de polinomios generadores no es parte de nuestro
análisis en este curso.
• En redes Ethernet el polinomiogenerador utiliza r =32.

Cuando el transmisor envía el mensaje de d bits envía adicionalmente r bits.
• El mensaje de d+r bits se denomina
P(x)
• El objetivo es hacer que P(x) sea exactamente divisible (es decir residuo cero) por G(x)
• Funcionamiento:
–Si P(x) se transmite sobre el canal y no hay errores de transmisión el receptor
puede tomar P(x) y dividirlo por G(x) y obtendrá un residuo decero.
• Si el residuo es distinto de cero entonces el receptor sabe que ocurrió algún error de transmisión.

La matemática utilizada para dividir los polinomios es algo distinta a la regularmente utilizada:
– Los coeficientes de los cálculos son SIEMPRE 1 ó 0.
– Todas las operaciones se realizan en módulo 2.
– La suma y la resta son idénticas e equivalentes a la operación XOR
– Se denomina“polynomial arithmetic modulo 2”.

Procedimiento para crear el mensaje a transmitirse:
– 1. Multiplicar el mensaje D(x) que tiene d bits por xr. Esto es equivalente a añadir r ceros al final de D(x). Llamaremos a este mensaje de
d+r bits T(x).
– 2. Dividir T(x) para G(x) y encontrar el residuo.
– 3. Substraer el residuo de T(x).

• Ejemplo:
– D=10011010
– G(x)=x3+x2+1
– D(x)=x7+x4+x3+x
–R(x)=x2+0x+1
• Se envía al receptor:
– 10011010000
XOR
– 101
– 10011010101



• CRC utilizados comúnmente:


• Un polinomio generador permite detectar:
– Todos los errores de un solo bit, siempre y cuando G(x) tenga uno como los coeficientes de xr y x0.
– Todos los errores de dos bits siempre y cuando G(x) tenga un factor con al menos tres términos.
– Todos los errores con unnúmero impar de bits en error. Siempre y cuando G(x) contenga el factor
(x+1).
– Cualquier error de bits consecutivos de longitud menor o igual a r.
– Muchos errores de bits consecutivos de longitud o mayor o igual a r.

Este código se basa en el principio de que n bits de datos se pueden considerar como los coeficientes de un polinomio de orden n-1. Por ejemplo, los datos 1101 pueden...