polinomios

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 (salvo el caso excepcional que estén separados exactamente (2^16)-1 bits)
• 100% de erroresde 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.
Verificación de redundancia cíclica
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 lastelecomunicaciones.
Concepto
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 de datos 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 contienedatos redundantes con la trama, de manera que los errores no sólo se pueden detectar sino que además se pueden solucionar.

El concepto de CRC consiste en tratar a las secuencias binarias como polinomios binarios, denotando polinomios cuyos coeficientes se correspondan con la secuencia binaria. Por ejemplo, la secuencia binaria 0110101001 se puede representar como un polinomio, como se muestraa continuación:
0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
siendo
X8 + X7 + X5 + X3 + X0
o
X8 + X7 + X5 + X3 + 1
De esta manera, la secuencia de bits con menos peso (aquella que se encuentra más a la derecha) representa el grado 0 del polinomio (X0 = 1), (X0 = 1), (X0 = 1), el 4º bit de la derecha representa el grado 3 del polinomio (X3), y así sucesivamente. Luego,una secuencia de n- bits forma un polinomio de grado máximo n-1. Todas las expresiones de polinomios se manipulan posteriormente utilizando un módulo 2.
En este proceso de detección de errores, un polinomio predeterminado (denominado polinomio generador y abreviado G(X)) es conocido tanto por el remitente como por el destinatario. El remitente, para comenzar el mecanismo de detección de errores,ejecuta un algoritmo en los bits de la trama, de forma que se genere un CRC, y luego transmite estos dos elementos al destinatario. El destinatario realiza el mismo cálculo a fin de verificar la validez del CRC.
Aplicaciones prácticas
Digamos que M es el mensaje que corresponde a los bits de la trama que se enviará, y que M(X) es el polinomio relacionado. Supongamos que M' es el mensajetransmitido, por ejemplo, el mensaje inicial al que se concatena un CRC de n bits. El CRC es el siguiente: M'(X)/G(X)=0. Por lo tanto, el código CRC es igual al remanente de la división polinomial de M(X) (X) (al que se le ha anexado los n bits nulos que corresponden a la longitud del CRC) entre G(X).
Por ejemplo: tomemos el mensaje M con los siguientes 16 bits: 1011 0001 0010 1010 (denominado B1 enhexadecimal). Tomemos G(X) = X3 + 1 (representado en el sistema binario por 1001). Siendo que G(X) tiene un grado 3, el resultado es añadirle a M 4 bits nulos: 10110001001010100000. El CRC es igual al remanente de M dividido por G :
10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001......
1001,.,.....
----,.,.....
10000.,........