Comprobar la redundancia cíclica

Abrir script en vivo

Este ejemplo muestra cómo llevar a cabo la comprobación de la redundancia cíclica (CRC) en los bits de un número. La CRC se emplea para detectar errores en la transmisión de datos en sistemas digitales. Cuando se envía una parte de un conjunto de datos, se adjunta a dicha parte un breve valor de comprobación. El valor de comprobación se obtiene mediante la división de polinomios con los bits de los datos. Cuando se reciben los datos, se repite la división de polinomios y el resultado se compara con el valor de comprobación. Si los resultados difieren, los datos se corrompieron durante la transmisión.

Calcular el valor de comprobación a mano

Comience con un número binario de 16 bits, que es el mensaje que se debe transmitir:

1101100111011010

Para obtener el valor de comprobación, divida este número por el polinomio $x^{3} + x^{2} + x + 1$ . Puede representar este polinomio con sus coeficientes: 1111.

La división se realiza en pasos y, después de cada paso, el divisor del polinomio se alinea con el 1 más a la izquierda del número. Debido a que el resultado de la división por el cuarto término del polinomio tiene tres bits (en general, la división por un polinomio de longitud $n + 1$ da lugar a un valor de comprobación de longitud $n$ ), anexe el número con 000 para calcular el resto. En cada paso, el resultado emplea el XOR bit por bit de los cuatro bits sobre los que se opera y el resto de bits permanecen sin cambios.

La primera división es

1101100111011010 000
1111
----------------
0010100111011010 000

Cada división sucesiva opera sobre el resultado del paso anterior, de modo que la segunda división es

0010100111011010 000
  1111
----------------
0001010111011010 000

La división se completa cuando en el dividendo solo hay ceros. La división completa, incluidos los dos pasos anteriores, es

1101100111011010 000
1111
0010100111011010 000
  1111
0001010111011010 000
   1111
0000101111011010 000
    1111
0000010011011010 000
     1111
0000001101011010 000
      1111
0000000010011010 000
        1111
0000000001101010 000
         1111
0000000000010010 000
           1111
0000000000001100 000
            1111
0000000000000011 000
              11 11
0000000000000000 110

Los bits restantes, 110, son el valor de comprobación de este mensaje.

Calcular el valor de comprobación de forma programática

En MATLAB®, puede llevar a cabo esta misma operación para obtener el valor de comprobación con operaciones bit por bit. Primero, defina las variables del divisor del polinomio y el mensaje. Utilice números enteros de 32 bits sin signo, de modo que haya disponibles bits adicionales para el resto.

message = 0b1101100111011010u32;
messageLength = 16;
divisor = 0b1111u32;
divisorDegree = 3;

Después, inicie el divisor del polinomio. Utilice dec2bin para mostrar los bits del resultado.

divisor = bitshift(divisor,messageLength-divisorDegree-1);
dec2bin(divisor)

ans = 
'1111000000000000'

Ahora, desplace el divisor y el mensaje para que tengan el número correcto de bits (16 bits para el mensaje y 3 bits para el resto).

divisor = bitshift(divisor,divisorDegree);
remainder = bitshift(message,divisorDegree);
dec2bin(divisor)

ans = 
'1111000000000000000'

dec2bin(remainder)

ans = 
'1101100111011010000'

Realice los pasos de división de la CRC utilizando un bucle for. El bucle for siempre avanza un único bit por cada paso, así que incluya una comprobación para ver si el dígito actual es un 1. Si el dígito actual es un 1, se realiza el paso de división; de lo contrario, el bucle avanza un bit y continúa.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end

Desplace los bits del resto a la derecha para obtener el valor de comprobación de la operación.

CRC_check_value = bitshift(remainder,-messageLength);
dec2bin(CRC_check_value)

ans = 
'110'

Comprobar la integridad del mensaje

Puede utilizar el valor de comprobación para comprobar la integridad de un mensaje repitiendo la misma operación de división. Sin embargo, en lugar de utilizar un resto de 000 para comenzar, utilice el valor de comprobación 110. Si el mensaje no tiene errores, el resultado de la división será cero.

Restablezca la variable de resto y añada el valor de comprobación de la CRC a los bits del resto utilizando un OR bit por bit. Introduzca un error en el mensaje invirtiendo uno de los valores de bit con bitset.

remainder = bitshift(message,divisorDegree);
remainder = bitor(remainder,CRC_check_value);
remainder = bitset(remainder,6);
dec2bin(remainder)

ans = 
'1101100111011110110'

Lleve a cabo la operación de división de la CRC y, después, compruebe si el resultado es cero.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end
if remainder == 0
    disp('Message is error free.')
else
    disp('Message contains errors.')
end

Message contains errors.

Referencias

[1] Sklar, Bernard. Digital Communications: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.

[2] Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.

Consulte también

bitshift | bitxor