Verificación de errores

Julio 2017

Verificación de errores

La codificación binaria es de gran utilidad práctica en dispositivos electrónicos como ordenadores, donde la información se puede codificar basándose en la presencia o no de una señal eléctrica.

Sin embargo, esta señal eléctrica puede sufrir alteraciones (como distorsiones o ruidos), especialmente cuando se transportan datos a grandes distancias. Por este motivo, ser capaz de verificar la autenticidad de estos datos es imprescindible para ciertos propósitos (incluido el uso de información en entornos profesionales, bancarios, industriales, confidenciales o relacionados con la seguridad).

Por este motivo existen algunos mecanismos que garantizan un nivel de integridad de los datos, es decir, que el destinatario obtiene una confirmación de que los datos recibidos son, de hecho, similares a los datos transmitidos. Existen dos maneras de proteger la transferencia de datos para que no se produzcan errores:

  • instalando un medio de transmisión más seguro, es decir, una capa de protección física. Una conexión convencional tiene, por lo general, un porcentaje de error entre 10-5 y 10-7.
  • implementando mecanismos lógicos para detectar y corregir errores.

La mayoría de los sistemas de control lógico de errores se basan en la suma de información (esto se denomina "redundancia") para verificar la validez de los datos. Esta información adicional se denomina suma de comprobación.

Verificación de errores

Se han perfeccionado mejores sistemas de detección de errores mediante códigos denominados:

  • Códigos de autocorrección
  • Códigos de autoverificación

Verificación de paridad

La verificación de paridad (a veces denominada VRC o verificación de redundancia vertical) es uno de los mecanismos de verificación más simples. Consiste en agregar un bit adicional (denominado bit de paridad) a un cierto número de bits de datos denominado palabra código (generalmente 7 bits, de manera que se forme un byte cuando se combina con el bit de paridad) cuyo valor (0 o 1) es tal que el número total de bits 1 es par. Para ser más claro, 1 si el número de bits en la palabra código es impar, 0 en caso contrario.

Tomemos el siguiente ejemplo:

En este ejemplo, el número de bits de datos 1 es par, por lo tanto, el bit de paridad se determina en 0. Por el contrario, en el ejemplo que sigue, los bits de datos son impares, por lo que el bit de paridad se convierte en 1:

Supongamos que después de haber realizado la transmisión, el bit con menos peso del byte anterior (aquel que se encuentra más a la derecha) ha sido víctima de una interferencia:

El bit de paridad, en este caso, ya no corresponde al byte de paridad: se ha detectado un error.

Sin embargo, si dos bits (o un número par de bits) cambian simultáneamente mientras se está enviando la señal, no se habría detectado ningún error.

Ya que el sistema de control de paridad puede detectar un número impar de errores, puede detectar solamente el 50% de todos los errores. Este mecanismo de detección de errores también tiene la gran desventaja de ser incapaz de corregir los errores que encuentra (la única forma de arreglarlo es solicitar que el byte erróneo sea retransmitido).

Verificación de redundancia longitudinal

La verificación de la redundancia longitudinal (LRC, también denominada verificación de redundancia horizontal) no consiste en verificar la integridad de los datos mediante la representación de un carácter individual, sino en verificar la integridad del bit de paridad de un grupo de caracteres.

Digamos que "HELLO" es el mensaje que transmitiremos utilizando el estándar ASCII. Estos son los datos tal como se transmitirán con los códigos de verificación de redundancia longitudinal:

LetraCódigo ASCII
(7 bits)
Bit de paridad
(LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

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 las telecomunicaciones.

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 contiene datos redundantes con la trama, de manera que los errores no sólo se pueden detectar sino que además se pueden solucionar.

Verificación de redundancia cíclica (CRC)

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 muestra a 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 mensaje transmitido, 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 en hexadecimal). 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.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..
1100.
1001.
----.
1010
1001
----
0011

Para crear M' se debe concatenar el CRC resultante con los bits de la trama que se va a transmitir:

M' = 1011000100101010 + 0011
M' = 10110001001010100011

Por lo tanto, si el destinatario del mensaje divide M' por G, obtendrá un remanente de cero si la transmisión ocurrió sin errores.

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

Polinomios generadores

Los polinomios generadores más comunes son:

  • CRC-12: X12 + X11 + X3 + X2 + X + 1
  • CRC-16: X16 + X15 + X2 + 1
  • CRC CCITT V41: X16 + X12 + X5 + 1
    (este código se utiliza en el procedimiento HDLC)
  • CRC-32 (Ethernet): = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1
  • CRC ARPA: X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1

Consulta también


Error checking
Error checking
Die Fehlerkontrolle
Die Fehlerkontrolle
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
Il controllo degli errori
Il controllo degli errori
O controlo de erros
O controlo de erros
Última actualización: 16 de octubre de 2008 a las 15:43 por Jeff.
El documento «Verificación de errores» se encuentra disponible bajo una licencia Creative Commons. Puedes copiarlo o modificarlo libremente. No olvides citar a CCM (es.ccm.net) como tu fuente de información.