Algoritmo de los Códigos de Redundancia Cíclica
Keywords: Algoritmo de los Códigos de Redundancia Cíclica, Bit, Códigos de Redundancia Cíclica, Polinomio, Estándar CCITT, División en Módulo 2, División Binaria
El algoritmo que utilizan los códigos de redundancia cíclica es el siguiente:
Se añaden r bits "0" a la derecha del mensaje (esto es, se añaden tantos ceros como grado tenga el polinomio generador).
Se divide el polinomio obtenido por el polinomio generador. La división se realiza en módulo 2, que es igual que la división binaria, con dos excepciones:
1 + 1 = 0 (no hay acarreo) 0 - 1 = 1 (no hay acarreo)
Y se añade el resto de la división al polinomio original.
La elección del polinomio generador es esencial si queremos detectar la mayoría de los errores que ocurran.
Uno de los polinomios generadores que más se suelen utilizar es el estándar CCITT:
x16 + x12 + x5 + 1.
Este polinomio permite la detección de:
- 100% de errores simples.
- 100% de errores dobles.
- 100% de errores de un número impar de bits.
- 100% de errores en ráfagas (en una serie sucesiva de bits) de 16 o menos bits.
- 99.99% de errores en ráfagas de 18 o más bits.
Cyclic Redundancy Check (english Page)