海明码和循环冗余校验码

循环冗余校验编码( 循环冗余校验编码(CRC) ) Cyclic Redundancy checking (CRC)循环 循环 冗余校验，又称多项式码。 冗余校验，又称多项式码。 在循环冗余校验中，不是通过将各比特位 在循环冗余校验中， 相加来得到期望的校验， 相加来得到期望的校验，而是通过在数据 单元末尾加一串冗余比特，称作循环冗余 单元末尾加一串冗余比特，称作循环冗余 校验码或循环冗余校验余数， 校验码或循环冗余校验余数，使得整个数 据单元可以被另一个预定的二进制数所整 除。

1.CRC校验基本思想 校验基本思想 CRC校验的基本思想是： 根据欲发的k位信息生成一个 位信息生成一个r比特的序 (1) 根据欲发的 位信息生成一个 比特的序 列 ， 称 为 帧 校 验 序 列 FCS ( Frame checking Series)。 ) 求出实际发送的数据帧(k+r位 ( 2 ) 求出实际发送的数据帧 ( k+r 位 ) , 这 个帧所对应二进制序列恰好能够被某个预先 确定的数 生成多项式)整除。 确定的数(生成多项式)整除。 接收器用相同的数(生成多项式) (3)接收器用相同的数(生成多项式)去除 传来的帧。如果无余数，则认为无差错

循环冗余校验码(CRC)的基本原理

循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2的R次方，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2的R次方除以生成多项式G(x)得到的余数就是校验码。

CRC 校验码题目

一、CRC 属于检错码还是纠错码？如果某一数据通信系统采用 CRC校验方式，生成多项式G(x)为 X4 +X3+1 ，目的结点接收到二进制比特序列为 110111101（含CRC 校验码），判断传输过程中是否出现了错误？并解释原因。

答 属于检错码。

余数110

二、某一数据通信系统采用 CRC校验方式，生成多项式G(x)的二进制比特序列为 11001，目的结点接收到二进制比特序列为 110111101（含CRC 校验码），则下列说法正确的是 B 。

（A）收到的二进制比特序列除以生成多项式的余数为 10100，传输出现差错 （B）收到的二进制比特序列除以生成多项式的余数为 110，传输出现差错

（C）收到的二进制比特序列能被生成多项式整除，传输过程没有差错 （D）无法判断传输是否出现差错

三、利用标准CRC方法传输位流10011101，生成多项式为x3 +1，请给出实际被传输的位串。

假设在传输过程中左边第三位变反了，请证明这个错误可以在接收端被检测出来。

余数是100.

四、如果某一数据通信系统采用CRC校验方式，

CRC 校验码题目

一、CRC 属于检错码还是纠错码？如果某一数据通信系统采用 CRC校验方式，生成多项式G(x)为 X4 +X3+1 ，目的结点接收到二进制比特序列为 110111101（含CRC 校验码），判断传输过程中是否出现了错误？并解释原因。

答 属于检错码。

余数110

二、某一数据通信系统采用 CRC校验方式，生成多项式G(x)的二进制比特序列为 11001，目的结点接收到二进制比特序列为 110111101（含CRC 校验码），则下列说法正确的是 B 。

（A）收到的二进制比特序列除以生成多项式的余数为 10100，传输出现差错 （B）收到的二进制比特序列除以生成多项式的余数为 110，传输出现差错

（C）收到的二进制比特序列能被生成多项式整除，传输过程没有差错 （D）无法判断传输是否出现差错

三、利用标准CRC方法传输位流10011101，生成多项式为x3 +1，请给出实际被传输的位串。

假设在传输过程中左边第三位变反了，请证明这个错误可以在接收端被检测出来。

余数是100.

四、如果某一数据通信系统采用CRC校验方式，

循环冗余码（CRC）

（1）CRC的工作方法

在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，需重发。

（2）循环冗余码的产生与码字正确性检验例子

54

例1.已知：信息码：110011 信息多项式：K(X)=X+X+X+1

43

生成码：11001 生成多项式：G(X)=X+X+1(r=4) 求：循环冗余码和码字。

5449854解：① (X+X+X+1)*X的积是 X+X+X+X 对应的码是1100110000。 1 0 0 0 0 1←Q(X) r G(x)→1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0←F(X)*X 1 1 0 0 1 ， 1 0 0 0 0 1 1 0 0 1 1 0 0 1←R(X)(冗余码) 98543

例2.已知：接收码字：1100111001 多项式：T(X)=X+X+X+X+X+1

43

生成码： 11001

海明码及码距

一、码距

一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit来表示八个不同信息中。在这个系统中，两个码字之间不同的bit数从1到3不等，但最小值为1，故这个系统的码距为1。如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图2的表中所示。

信息序号 二进码字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 图 1

信息序号 二进码字

a3

海明码及码距

一、码距

一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit来表示八个不同信息中。在这个系统中，两个码字之间不同的bit数从1到3不等，但最小值为1，故这个系统的码距为1。如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图2的表中所示。

信息序号 二进码字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 图 1

信息序号 二进码字

a3

二、创新实验设计

创新实验一：（7,4）汉明码的编码与译码实现

1、实验目的

实现（7,4）汉明码的编码与译码，通过这次实验不但加深了对汉明码编码和译码原理了解，而且对线性分组码有所了解。

2、实验原理

线性分组码的构造方法比较简单、理论较为成熟，应用比较广泛。汉明码是一种能够纠正一个错码的效率比较高的线性分组码，下面以（7,4）码为例就汉明码的编码与译码分别进行介绍：

（1）编码原理

一般来说，若汉明码长为n，信息位数为k，则监督位数r=n-k。若希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r?1?n或2?1?k?r?1 (1)

设汉明码（n,k）中k=4，为了纠正一位错码，由式（1）可知，要求监督位数r≥3。若取r=3,则n=k+r=7。这样就构成了（7,4）码。用示这7个码元，用

a6a5a4a3a2a1a0r来表

s1s2s3的值表示3个监督关系式中的校正子，则

s1s2s3的值与

错误码元位置的对应关系可以规定如表1所列。

表2.1 校正子和错码位置的关系

s1s2s3 错码位置 a0a1a2a3 s1s2s3 错码位置 a4a5a6 001 101

二、创新实验设计

创新实验一：（7,4）汉明码的编码与译码实现

1、实验目的

实现（7,4）汉明码的编码与译码，通过这次实验不但加深了对汉明码编码和译码原理了解，而且对线性分组码有所了解。

2、实验原理

线性分组码的构造方法比较简单、理论较为成熟，应用比较广泛。汉明码是一种能够纠正一个错码的效率比较高的线性分组码，下面以（7,4）码为例就汉明码的编码与译码分别进行介绍：

（1）编码原理

一般来说，若汉明码长为n，信息位数为k，则监督位数r=n-k。若希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r?1?n或2?1?k?r?1 (1)

设汉明码（n,k）中k=4，为了纠正一位错码，由式（1）可知，要求监督位数r≥3。若取r=3,则n=k+r=7。这样就构成了（7,4）码。用示这7个码元，用

a6a5a4a3a2a1a0r来表

s1s2s3的值表示3个监督关系式中的校正子，则

s1s2s3的值与

错误码元位置的对应关系可以规定如表1所列。

表2.1 校正子和错码位置的关系

s1s2s3 错码位置 a0a1a2a3 s1s2s3 错码位置 a4a5a6 001 101

实验设计

实验一：（7,4）循环码的编码与译码

1．实验编码原理： 根据循环码的代数性质建立系统编码的过程，可以把消息矢量用如下多项式表示：

m(x)?mk?1xk?1?mk?2xk?2?...?m1x?m0要编码成系统循环码形式，把消息比特移入码字寄存器的最右边k位，而把监督

n?kn?kxx比特加在最左边的n-k个中，则要用乘以m(x)得到 m(x)=

mk?1xn?1?mk?2xn?2?...?m1xn?k?1?m0xn?kn?k，则p(x)+ x m(x)

xn?k m(x)= q(x) g(x)+ p(x)，其中p(x)可以表示为

n?k?1?...?p1x?p0p(x)= pn?k?1xn?1n?2n?k?1?m0xn?k+ pn?k?1xn?k?1?...?p1x?p0= mk?1x?mk?2x?...?m1xn?kpmp另U(x)= p(x)+ x m(x)，则U=（0，p1，p2，···，n?k?1，0 ，m1，···，

mk?1）。

本实验根据以上原理，用matlab实现书上例6.8系统形式的循环码，生成多项式为g(x)=

2．实验译码原理：译码的实验原理 g(x)= ，在（n，k）循环码中，

nx