Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

执行循环冗余校验

此示例说明如何对数值的位执行循环冗余校验 (CRC)。CRC 用于检测数字系统中数据传输中的错误。发送数据时,会对数据附加一个短校验值。该校验值通过用数据中的位进行多项式除法获得。当接收到数据时,重复执行多项式除法,并将结果与校验值进行比较。如果结果不同,则数据在传输过程中被破坏。

手动计算校验值

从一个 16 位二进制数开始,这是要传输的报文:

1101100111011010

要获得校验值,请将该数除以多项式 x3+x2+x+1。您可以用其系数来表示此多项式:1111

除法是分步骤进行的,每步后多项式除数都与数值中最左边的 1 对齐。由于除以四项多项式的结果有三位(通常除以长度为 n+1 的多项式会产生长度为 n 的校验值),请对该数值追加 000 以计算余数。每一步,结果都对正在操作的四个位进行按位 XOR,所有其他位保持不变。

第一个除法是

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

每个后续除法运算都基于前一步的结果,因此第二个除法是

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

一旦被除数全为零,则除法完成。整个除法运算过程(包括上述两步在内)如下

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

余数位 110 是该报文的校验值。

以编程方式计算校验值

在 MATLAB® 中,您可以通过按位运算执行上述运算来获得校验值。首先,为报文和多项式除数定义变量。使用无符号 32 位整数,以便有额外的位可供余数使用。

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

接下来,初始化多项式除数。使用 dec2bin 显示结果的位。

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

现在,移动除数和报文,使它们具有正确的位数(报文为 16 位,余数为 3 位)。

divisor = bitshift(divisor,divisorDegree);
remainder = bitshift(message,divisorDegree);
dec2bin(divisor)
ans = 
'1111000000000000000'
dec2bin(remainder)
ans = 
'1101100111011010000'

使用 for 循环执行循环冗余校验的除法步骤。for 循环每步都会前进一位,因此请包含一项校验来查看当前位是否为 1。如果当前位是 1,则执行除法步骤;否则,循环前进一位并继续。

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

将余数的位向右移动,以获得运算的校验值。

CRC_check_value = bitshift(remainder,-messageLength);
dec2bin(CRC_check_value)
ans = 
'110'

检查报文完整性

您可以重复上述除法运算以使用校验值来验证报文的完整性。但是,不要使用余数 000 开始,而应使用校验值 110。如果报文没有错误,则除法的结果将为零。

重置余数变量,并使用按位 OR 将 CRC 校验值添加到余数位。使用 bitset 翻转一个位值,以在报文中引入一个错误。

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

执行 CRC 除法运算,然后检查结果是否为零。

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.

参考

[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.

另请参阅

|

相关主题