CRC 循环冗余码的计算
三、 循环冗余码(CRC )
1.CRC 的工作方法
在发送端产生一个循环冗余码,附加在信息位后面一起发送到接收端,接收端收到的信息按发送端形成循环冗余码同样的算法进行校验,若有错,需重发。
2. 循环冗余码的产生与码字正确性检验例子。
例1. 已知:信息码:110011 信息多项式:K(X)=X^5+X^4+X+1
生成码:11001 生成多项式:G(X)=X^4+X^3+1 (r=4)
求:循环冗余码和码字。
解:1)(X5+X4+X+1)*X4的积是 X9+X8+X5+X4 对应的码是1100110000。
或者 G(X)的模是4,所以在信息码的后面加4个0得1100110000
2) 积/G(X)(按模二算法) 。
由计算结果知冗余码是1001,码字就是1100111001。
__________1 0 0 0 0 1 ←Q(X)
G(x)→1 1 0 0 1)1 1 0 0 1 1 0 0 0 0←F(X)*Xr
1 1 0 0 1 ,
1 0 0 0 0
1 1 0 0 1
1 0 0 1←R(X)(冗余码)
例2. 已知:接收码字: 1100111001 多项式:T(X)=X^9+X^8+X^5+X^4+X^3+1
生成码: 11001 生成多项式:G(X)=X^4+X^3+1 (r=4)
求:码字的正确性。若正确,则指出冗余码和信息码。
解:1) 用接收码字除以生成码,余数为0,所以码字正确。
1 0 0 0 0 1←Q(X)
1 1 0 0 1 )1 1 0 0 1 1 1 0 0 1←F(X)*Xr+R(x)
G(x) 1 1 0 0 1 ,
1 1 0 0 1
1 1 0 0 1
0←S(X)(余数)
2) 因r=4,所以冗余码是:1001,信息码是:110011
四、 海明码
● 对于16位的数据,需要(47)个校验位才能构成海明码。
在某个海明码的排列方式D 9D 8D 7D 6D 5D 4P 4D 3D 2D 1P 3D 0P 2P 1中,其中D i (0≤i ≤9) 表
示数据位,P j (1≤j ≤4) 表示校验位,数据位D 8由 (48) 进行校验。
(47) A、3 B、4 C、5(2的k 次方>=16+k) D、6
(48) A、P 4P 2P 1 B、P 4P 3P 2 C 、P 4P 3P 1 D、P 3P 2P 1
D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1 h14 h13 h12 h11 h10 h9 h8 h7 h6 h5 h4 h3 h2 h1 D8位对应h13,然后算:8+4+1=13,所以要第四位(p3)第八位(p4)第一位(p1)来校验了。 答案就是:p4p3p1
CRC 循环冗余码的计算
三、 循环冗余码(CRC )
1.CRC 的工作方法
在发送端产生一个循环冗余码,附加在信息位后面一起发送到接收端,接收端收到的信息按发送端形成循环冗余码同样的算法进行校验,若有错,需重发。
2. 循环冗余码的产生与码字正确性检验例子。
例1. 已知:信息码:110011 信息多项式:K(X)=X^5+X^4+X+1
生成码:11001 生成多项式:G(X)=X^4+X^3+1 (r=4)
求:循环冗余码和码字。
解:1)(X5+X4+X+1)*X4的积是 X9+X8+X5+X4 对应的码是1100110000。
或者 G(X)的模是4,所以在信息码的后面加4个0得1100110000
2) 积/G(X)(按模二算法) 。
由计算结果知冗余码是1001,码字就是1100111001。
__________1 0 0 0 0 1 ←Q(X)
G(x)→1 1 0 0 1)1 1 0 0 1 1 0 0 0 0←F(X)*Xr
1 1 0 0 1 ,
1 0 0 0 0
1 1 0 0 1
1 0 0 1←R(X)(冗余码)
例2. 已知:接收码字: 1100111001 多项式:T(X)=X^9+X^8+X^5+X^4+X^3+1
生成码: 11001 生成多项式:G(X)=X^4+X^3+1 (r=4)
求:码字的正确性。若正确,则指出冗余码和信息码。
解:1) 用接收码字除以生成码,余数为0,所以码字正确。
1 0 0 0 0 1←Q(X)
1 1 0 0 1 )1 1 0 0 1 1 1 0 0 1←F(X)*Xr+R(x)
G(x) 1 1 0 0 1 ,
1 1 0 0 1
1 1 0 0 1
0←S(X)(余数)
2) 因r=4,所以冗余码是:1001,信息码是:110011
四、 海明码
● 对于16位的数据,需要(47)个校验位才能构成海明码。
在某个海明码的排列方式D 9D 8D 7D 6D 5D 4P 4D 3D 2D 1P 3D 0P 2P 1中,其中D i (0≤i ≤9) 表
示数据位,P j (1≤j ≤4) 表示校验位,数据位D 8由 (48) 进行校验。
(47) A、3 B、4 C、5(2的k 次方>=16+k) D、6
(48) A、P 4P 2P 1 B、P 4P 3P 2 C 、P 4P 3P 1 D、P 3P 2P 1
D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1 h14 h13 h12 h11 h10 h9 h8 h7 h6 h5 h4 h3 h2 h1 D8位对应h13,然后算:8+4+1=13,所以要第四位(p3)第八位(p4)第一位(p1)来校验了。 答案就是:p4p3p1