4.4 差错控制技术

信道编码技术会对传输数据进行奇偶校验编码1会对传输数据进行循环冗余校验编码2任务要求信道编码技术在RFID系统中，数据传输的完整性存在两个方面的问题：1、外界的各种干扰可能使数据传输产生错误；2、多个标签同时占用信道使发送数据产生碰撞。运用数据检验（差错检测）和防碰撞算法可分别解决这两个问题。RFID系统采用无接触的方式进行数据传输，由于无线通信环境的复杂性，这一传输过程很容易受到干扰，导致数据传输错误。为了提高系统传输的可靠性，可以采用信道编码（又称差错控制编码），对出现的差错进行控制，常用的方法有奇偶校验、循环冗余校验、汉明码等。进行差错控制的基本思想称为“冗余校验”：

（1）编码：在原始数据（即有效数据位）的基础上增加冗余数据（即校验位），按照某种规律将有效数据位和校验位一起编码，得到数据校验码；（2）译码：按同一约定规律对收到的数据校验码进行分析，并判断约定规律是否被破坏。①若未被破坏，则正确，从中取出有效数据即可；②若被破坏，则有错，根据约定规律被破坏后的某些特征对出错位进行定位，从而可自动纠正错误。差错控制编码分组码通常原始数字信号是分组传输的，例如每k个二进制码元为一组（称为信息组），经信道编码后转换为每n个码元一组的码字（码组），这里n＞k，信道编码是利用“冗余”来提高抗干扰能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。分组码通常表示为（n，k）。n－码组的总位数，又称为码组的长度（码长），k－码组中信息码元的数目，r－码组中的监督码元数目，或称监督位数目。奇偶校验编码分为奇校验和偶校验编码规律：偶校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为偶数；奇校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为奇数；优点：开销小，编译码简单缺点：只能发现一位或奇数位出错，并且不能发现哪位出错。

因为机器中一位出错的概率比几位同时出错的概率要高的多，所以这种方法有较高的实用价值。奇偶校验编码校验方程设7位信息码组为C7C6C5C4C3C2C1，校验码为C0，⊕表示模2相加。对偶校验，当满足C7⊕C6⊕C5⊕C4⊕C3⊕C2⊕C1⊕C0＝0时，为合法码对奇校验，当满足C7⊕C6⊕C5⊕C4⊕C3⊕C2⊕C1⊕C0＝1时，为合法码有效数据偶校验码奇校验码1011001010110010010110010？1011001110110011110110011？对二进制数1011001计算偶校验位。数据0110100使用奇校验，求校验位的值。若使用奇校验，接收数据01001101（末位为校验位），是否存在传输错误？接收数据10110111（末位为校验位），若未出错，判断是奇校验还是偶校验。若两位同时翻转，奇偶校验能否检测？为什么？ASCII字符'C'（二进制01000011）使用偶校验，求传输的比特流。纵向冗余校验（LRC）编码纵向冗余校验是将传输的数据块的所有字节按位相加（异或运算，模2加法），其结果作为校验字节附加再传输数据之后。接收端对整个LRC字符串作异或运算，结果为0则说明传输无误。纵向冗余校验也称为代码和校验。LRC主要用于快速校验很小的数据块儿（如32B）。在射频识别系统中，由于标签的容量一般较小，每次交换的数据量也不大，所以这种算法还是比较适合的。例：传输的16进制数据块为4672616E7A，求校验码纵向冗余校验（LRC）编码给定数据块（每行一个字节，十六进制表示）：0x320x450x7A要求：使用偶校验计算纵向冗余校验（LRC）字节，结果用十六进制表示。要求发送ASCII字符串"HELLO"（每个字符占1字节），添加纵向偶校验LRC字节。给出完整的传输数据（字符ASCII值：H=0x48,E=0x45,L=0x4C,O=0x4F）。0x32→001100100x45→010001010x7A→01111010纵向异或：00001101→0x0D算LRC：0x48⊕0x45=0x0D0x0D⊕0x4C=0x410x41⊕0x4C=0x0D0x0D⊕0x4F=0x420x480x450x4C0x4C0x4F0x42。循环冗余校验码––––CRC码循还冗余校验码（CyclicRedundancyCheck）是一种检错、纠错能力很强的数据校验码,主要用于网络、同步通信等应用场合。CRC校验原理：先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。模2运算CRC码是基于模2运算来建立编译码规律的校验码模2运算：以按位模2相加为基础，运算时不考虑进位和借位。

●模2加减（异或）

0±0＝00±1＝11±0＝11±1＝0

●模2乘（用模2加求和）

例如：1010

×101

1010

0000

＋1010

100010模2除（用模2减求余数）

上商原则：部分余数的首位为1，商取1；

部分余数的首位为0，商取0。

当部分余数位数小于除数位数时，该余数为最后余数。

例如：101

10110000

101

0100

000

100

101

01商余数【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。练一练计算1011×101计算101001000÷1101★校验规则：让校验码能被某一约定代码除尽。

●若能除尽，表明代码无错；

●若除不尽，余数将指明出错位置。

★实现原理：在k位信息位之后拼接r位校验位。

●问题1：如何从k位信息位简便地得到r位校验位？

●问题2：如何从k+r位信息码判断是否有错？编码方法在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为1*x6+0*x5+1*x4+0*x3+1*x2+1*x1+1*x0，即：x6+x4+x2+x+1多项式为x5+x3+x2+x+1，对应的代码101111。C(x)：表示发送的原始数据的多项式。例如C(x)=x5

+x3

+x2

+x+1表示发送的数据为101111。G(x)：表示CRC的生成多项式，是接收方和发送方的一个约定，也就是一个二进制数，由CRC规范给定。在整个传输过程中，这个数始终保持不变。R(x)：

表示CRC码的多项式。R(x)=C(x)*(x<<R)%G(x)T(x)：

表示发送的原始数据加上CRC码之后的多项式。

T(x)=C(x)*(x<<R)+R(x)K：发送数据的长度。其等于C(x)中的最高次的幂+1。如上例子的C(x)中，K=5+1=6R：

CRC码的长度。CRC校验码位数=生成多项式位数-1。在K位信息码后再拼接R位的校验码，整个编码长度为N位。因此，这种编码也叫(N，K)码。对于一个给定的(N，K)码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。2026/1/5设：被除数C(x)：k位待编信息除数G(x)：r+1位？（生成多项式）

余数R(x)：r位校验位商Q(x)

(1)CRC码的编码方法a.将待编码的k位有效信息位组写成表达式：

C(x)=Ck-1Xk-1+Ck-2Xk-2+……+C1X+C0(Ci=0或1)b.将信息位组左移r位，变成多项式C(x)·

Xr；c.用C(x)·

Xr除以G(x)，所得余数作为校验位。d.有效的CRC码为：

C(x)·

Xr+R(x)=[Q(x)·

G(x)+R(x)]+R(x)=Q(x)·

G(x)。所以：CRC码能够被G(x)除尽。编码方法编码举例假设需要发送的信息C(x)为1010001101，产生多项式G(x)对应的代码为110101,求CRC编码。R＝5。C(x)左移5位后补0，然后对移位后的数做模2除法运算，得余数R(x)对应的代码：01110。编码举例例如：对C(x)=1100，用G(x)=1011，求CRC码。

1.将信息位组左移r=3位,C(x)·

Xr=M(X)·

X3=11000002.用C(x)·

Xr除以G(x)，所得余数作为校验位。3.有效的CRC码[此处为(7,4)码]为：

C(x)·

Xr+R(x)=1100000+010=1100010。编码练习编码练习现假设选择的CRC生成多项式为G（X）=X4+X3+1，要求出二进制序列10110011的CRC校验码。编码练习①将多项式转化为二进制序列，由G（X）=X4+X3+1可知二进制一种有五位，第4位、第三位和第零位分别为1，则序列为11001②多项式的位数位5，则在数据帧的后面加上5-1位0，数据帧变为101100110000，然后使用模2除法除以除数11001，得到余数。③将计算出来的CRC校验码添加在原始帧的后面，真正的数据帧为101100110100，再把这个数据帧发送到接收端。④接收端收到数据帧后，用上面选定的除数，用模2除法除去，验证余数是否为0，如果为0，则说明数据帧没有出错。★译码：用收到的CRC码除以G(x)。

●若码字无误，则余数为0；

●若有某1位错，则余数不为0且不同