CRC (Comprobación de Redundancia Cíclica)

T= 2ⁿm + FCS

T= Trama de m+n bits

n= # de bits de paridad

p= polinomio generador

FCS= Secuencia de comprobación de la trama (Residuo de )

m= mensaje

Tamaño de n = tamaño de p-1

Verificación

- Si tiene residuo -> Trama dañada
- Si no tiene residuo -> Trama sin errores

Ejemplo:

Dado m = “1010001101” y p=110101 encontrar T.

Tamaño de n= 6-1 = 5

n= 5

T = 2ⁿm + FCS

2ⁿ = 00000

2ⁿm = 101000110100000

FCS = Residuo

Nota: En la división no se toman en cuenta los acarreos, se hace una operación x-or.

FCS tendrá la misma longitud de “n”.

T= 101000110100000 + 01110

Al sumar:

T= 101000110101110

Verificación

Ejemplo 2:

Dado m= “1110100001011000” encontrar T, n, p, FCS.

Para encontrar n y p se usa la siguiente desigualdad.

2ⁿ ≥ m + n + 1

2ⁿ ≥ 16 + n + 1

Elegimos un valor para n que cumpla la desigualdad, por ejemplo 5.

2⁵ ≥ 16 + 5 + 1

32≥ 22

Se cumple la desigualdad por lo tanto n = 5 (puede tomar valores mayores a 5 porque se sigue cumpliendo la desigualdad)

P = n + 1

= 5 + 1 = 6 bits.

P debe empezar y terminar con 1. Los bits de en medio pueden ser cualquier combinación posible:

P= 10001

10011

10101

10111

11001

11011

11101

11111

Usemos entonces la primera combinación.

P = 10001

T = 111010000101100000000 + FCS

FCS:

T= 1110100001011000000000 + 00001

T= 111010000101100000001

Ahora veamos qué pasa si se modifica uno de los bits de T y hacemos la verificación. El bit modificado se muestra en negritas.

T= 111010100101100000001

Verificación