Control de errores (CRC)

, Author

Nuestro vídeo

Cargar el vídeo
«Preguntas frecuentes: Control de errores (CRC)»

Control de errores

La codificación binaria es muy conveniente para su uso en dispositivos electrónicos como un ordenador, en el que la información puede ser codificada por la presencia o ausencia de una señal eléctrica.

Sin embargo, la señal eléctrica puede estar sujeta a perturbaciones (distorsión, presencia de ruido), especialmente cuando se transportan los datos a larga distancia. Así, el control de la validez de los datos
es necesario para determinadas aplicaciones (profesionales, bancarias, industriales, confidenciales, relacionadas con la seguridad, …).

Por ello, existen mecanismos que garantizan un cierto nivel de integridad de los datos, es decir, que proporcionan al receptor la seguridad de que los datos recibidos son efectivamente similares a los transmitidos. La protección contra errores puede lograrse de dos maneras:

  • o haciendo que el medio de transmisión sea fiable, es decir, recurriendo a la protección física. Un enlace convencional suele tener una tasa de error de entre 10-5 y 10-7.
  • o implementando mecanismos de detección y corrección de errores lógicos.
    • La mayoría de los sistemas de control de errores a nivel lógico se basan en añadir información (conocida como «redundancia») para verificar la validez de los datos. Esta información adicional se denomina suma de comprobación.

      Corrección de errores

      Por ello, se han desarrollado sistemas de detección de errores más sofisticados, estos códigos se denominan :

      • Códigos de autocorrección
      • Códigos de autocomprobación
      • Comprobación de paridad

        La comprobación de paridad (a veces llamada VRC, por Vertical Redundancy Check o Vertical Redundancy Checking) es uno de los sistemas de comprobación más sencillos.
        Consiste en añadir un bit extra (llamado bit de paridad) a un número de bits de datos llamado codeword
        (normalmente 7 bits, para formar un byte con el bit de paridad) cuyo valor (0 o 1) es tal que el número total de bits a 1 es par. Para ser más explícito, consiste en añadir un 1 si el número de bits de la codificación es impar, y un 0 en caso contrario.

        Tomemos el siguiente ejemplo:

        En este ejemplo, el número de bits de datos de 1 bit es par, por lo que el bit de paridad se pone a 0. En el siguiente ejemplo, sin embargo, los bits de datos son un número impar, por lo que el bit de paridad se pone a 1 :

        Ahora imaginemos que tras la transmisión el bit menos significativo (el de la derecha) del byte anterior sufre una interferencia:

        Entonces el bit de paridad ya no coincide con la paridad del byte: se detecta un error.

        Sin embargo, si dos bits (o un número par de bits) cambiaran simultáneamente durante el transporte de datos, entonces no se detectaría ningún error…

        Como el sistema de comprobación de paridad sólo detecta los errores con un número impar de bits, sólo detecta el 50% de los errores.
        Este sistema de detección de errores también tiene la gran desventaja de que no permite corregir los errores detectados (la única forma es exigir la retransmisión del byte erróneo..).

        Comprobación de paridad cruzada

        La comprobación de paridad cruzada (también conocida como Comprobación de Redundancia Longitudinal o LRC) no es una comprobación de la integridad de los datos de un carácter, sino una comprobación de la integridad de los bits de paridad de un bloque de caracteres.

        Así que «HOLA» el mensaje a transmitir, utilizando el código ASCII estándar. Aquí están los datos tal y como se transmitirán con los códigos de comprobación de paridad cruzada:

        ítuloCódigo ASCII(7 bits)Bit de paridad(LRC)

        .

        H 1001000 0
        E 1000101 1
        L 10000 1
        L 1001100 1
        0 1001111 1
        VRC 1000010 0

        Comprobación de redundancia cíclica

        Comprobación de redundancia cíclica (denominada CRC, o Comprobación de Redundancia Cíclica) es un medio potente y fácil de implementar para comprobar la integridad de los datos. Es el principal método de detección de errores utilizado en telecomunicaciones.

        Principio

        La comprobación de redundancia cíclica consiste en proteger bloques de datos, denominados tramas
        (frames en inglés). Cada trama está asociada a un bloque de datos, llamado código de comprobación
        (a veces CRC por abuso del lenguaje o FCS por Frame Check Sequence en el caso de un código de 32 bits). El código CRC contiene elementos redundantes con respecto a la trama, lo que permite detectar errores, pero también repararlos.

        Comprobación de Redundancia Cíclica (CRC)

        El principio de CRC es tratar las secuencias binarias como polinomios binarios, es decir, polinomios cuyos coeficientes coinciden con la secuencia binaria. Así, la secuencia binaria 0110101001 puede representarse
        en la siguiente forma polinómica:

        0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
        soit
        X8 + X7 + X5 + X3 + X0
        ou encore
        X8 + X7 + X5 + X3 + 1

        De este modo, el bit menos significativo de la secuencia (el de más a la derecha) representa el grado 0 del polinomio (X0 = 1), el 4º bit desde la derecha representa el grado
        3 del polinomio (X3)… Así, una secuencia de n bits constituye un polinomio de grado máximo n-1. Todas las expresiones polinómicas se tratan posteriormente con aritmética de módulo 2.

        En este mecanismo de detección de errores,
        un polinomio predefinido (llamado polinomio generador y denotado G(X)) es conocido tanto por el emisor como por el receptor. La detección de errores consiste en que el transmisor realiza un algoritmo sobre los bits de la trama para generar un CRC, y transmite estos dos elementos
        al receptor. El receptor entonces sólo tiene que realizar el mismo cálculo para verificar que el CRC es válido.

        Aplicación práctica

        Sea M el mensaje correspondiente a los bits de la trama a enviar y M(X) el polinomio asociado. Llamemos M’ al mensaje transmitido, es decir, al mensaje inicial al que se habrá concatenado el CRC de n bits. El CRC es tal que M'(X)/G(X)=0. El código CRC es, pues, igual al resto de la división polinómica de M(X) (al que previamente hemos concatenado n bits nulos correspondientes a la longitud del CRC) por G(X).

        Sigue siendo más sencillo tomar un ejemplo: tomemos el siguiente mensaje de 16 bits M: 1011 0001 0010 1010 (denotado B1 en hexadecimal). Tomemos
        G(X) = X3 + 1 (representado en binario como 1001).
        Como G(X) es de grado 3, se trata de añadir 4 bits nulos a M:

        El CRC es igual al resto de la división de M 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..
        ----..


        ----.
        1010
        1001
        ----
        0011

        Para crear M’ basta con concatenar el CRC así obtenido a los bits de la trama a transmitir:

        M' = 1011000100101010 + 0011
        M' = 10110001001010100011

        Así, si el receptor del mensaje realiza la división de M’ por G, obtendrá un resto de cero si la transmisión se completó 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 utilizados 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 particular 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 +

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *