4.4 差错控制技术

信道编码技术

DRFID

原理与应用yuanyc@njcit.cn任务要求1

会对传输数据进行奇偶校验编码2

会对传输数据进行循环冗余校验编码信道编码技术必在RFID系统中，数据传输的完整性存在两个方面的问题：※1、外界的各种干扰可能使数据传输产生错误；※2、多个标签同时占用信道使发送数据产生碰撞。※运用数据检验(差错检测)和防碰撞算法可分别解决这两个问题。※RFID系统采用无接触的方式进行数据传输，由于无线通信环境的复杂性，这一传

输过程很容易受到干扰，导致数据传输错误。51

FE

2BC6AE

66

信道

51

FE2BAE66干扰图7-12

数据传输差错示意图※为了提高系统传输的可靠性，可以采用信道编码(又称差错控制编码)

,

对

出

现

的差错进行控制，常用的方法有奇偶校验、循环冗余校验、汉明码等。差错控制编码进行差错控制的基本思想称为“冗余校验”

:(1)

编码：在原始数据(即有效数据位)的基础上增加冗余数据(即校验位)

,

按照某种规律将有效数据位和校验位一起编码，得到数据校验码；(2)

译

码：按同一约定规律对收到的数据校验码进行分析，并判断约定规律是

否被破坏。①若未被破坏，则正确，从中取出有效数据即可；②若被破坏，则有错，根据约定规律被破坏后的某些特征对出错位进行定位，

从而可自动纠正错误。分组码※通常原始数字信号是分组传输的，例如每k个二进制码元为一组(称为信息组),

经信道编码后转换为每n个码元

一组的码字(码组),这里n>k,信道编码是利用“冗余”来提高抗干扰能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。※分组码通常表示为(n,k)。※n-码组的总位数，又称为码组的长度(码长),※k

-

码组中信息码元的数目，※r-

码组中的监督码元数目，或称监督位数目。k个信息位-

→——码长n=k+rao时

间(

r个监督位—···aran-2ar-1an-1·奇偶校验编码※分为奇校验和偶校验※编码规律：■偶校验：配一个校验位，使整个校验码(包括有效数据位和校验位)中“1”的

个数为偶数；■奇校验：配一个校验位，使整个校验码(包括有效数据位和校验位)中“1”的

个数为奇数；优点：开销小，编译码简单缺

点：只能发现

一位或奇数位出错，并且不能发现哪位出错。因为机器中一位出错的概率比几位同时出错的概率要高的多，所以这种方法有较高的实用价值。校验方程设7位信息码组为C7C6C5C4C3C2C1,

校验码为CO,田表示模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进制数据块为4672616

E7A,

求校验码01000110011100100110000101101110011110104672616E7A4672616E7A41010001100111001001100001011011100111101001000001纵向冗余校验(LRC)

编码数据传输前生成LRC

数据传输后生成LRCLRC

01000001410000000000LRC图2-19

LRC

校验示例说明XORXOR必给定数据块(每行一个字节，十六进制表示):※0x32×

0x45※0x7A※要求：使用偶校验计算纵向冗余校验(LRC)

字节，结果用十六进制表示。※要求发送ASCII字符串"HELLO"

(每个字符占1字节),添加纵向偶校验LRC

字节。必给出完整的传输数据(字符ASCII值：H=0x48,E=0x45,L=0x4C,O=0x4F)。※0x32→00110010※0x45→01000101※0x7A→01111010※纵向异或：

00001101→0x0D※算LRC:※0x48④0x45=0×0D※0×0D④0x4C=0x41※0x41④0x4C=0×0D※0×0D④0x4F=0x42※0x480x450x4C0x4C0x4F

0x42。循环冗余校验码----CRC

码※循还冗余校验码(Cyclic

Redundancy

Check)是一种检错、纠错能

力很强的数据校验码，主要用于网络、同步通信等应用场合。※CRC校验原理：必先在要发送的帧后面附加一个数(这个就是用来校验的校验码，但要注意，这里

的数也是二进制序列的，下同),生成一个新帧发送给接收端。※这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的

某个特定数整除(注意，这里不是直接采用二进制除法，而是采用一种称之为“模2

除法”)。※到达接收端后，再把接收到的新帧除以(同样采用“模2除法”)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理(也就已经能

整除了),所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出

现了差错

。模2运算※CRC

码是基于模2运算来建立编译码规律的校验码※模2运算：

以按位模2相加为基础，运算时不考虑进位和借位。模2除(用模2减求余数)上商原则：部分余数的首位为1,商取1;部分余数的首位为0,商取0。当部分余数位数小于除数位数时，该余数为最后余数。例

如

：

商余数【说明】“模2除法”与“算术除法”类似，但它既不

向上位借位，也不比较除数和被除数的相同位数

值的大小，只要以相同位数进行相除即可。。模2加减(异或)0±0=00±1=11±0=1

1±1=0。模2乘(用模2加求和)例如

：练一练※计算1011×101※计算101001000÷1101110101←Q

(商)P(除数)→

1101101001000←2M

(被除数)11011110110101

110000111

0°11010110000011001101001←R

(余数),作为FCS

校验规则：让校验码能被某一约定代码除尽。●若能除尽，表明代码无错；●若除不尽，余数将指明出错位置。实现原理：在k位信息位之后拼接r位校验位。●

问题1:

如何从k位信息位简便地得到r位校验位?信息位

校验位●

问题2:

如何从k+r位信息码判断是否有错?1

2

K

K+1

图7-13

CRC编码.

*K+r编码方法※在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。※任意一个由二进制位串组成的代码都可以和一个系数仅为‘O'和‘1'取值的多项

式

—

—

对应。※例如：代码1010111对应的多项式为※1*x⁶+0*x⁵+1*x⁴+0*x³+1*x²+1*x¹+1*x⁰,※即：x⁶+x⁴+x²+×+1必多项式为x⁵+x³+x²+X+1,对应的代码101111。※C(x):

表示发送的原始数据的多项式。例如

C(x)=x⁵+x³+x²+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=6※R:CRC

码的长度。

CRC

校验码位数=生成多项式位数-1。※在

K位信息码后再拼接

R位的校验码，整个编码长度为

N位。因此，

这种编码也叫(N,K)

码。※对于一个给定的(N,K)

码，可以证明存在一个最高次幂为

N-K=R

的多项式G(x)。※根据G(x)

可以生成

K

位信息的校验码，而G(x)

叫做这个CRC

码的生

成多项式。N=K+RK位信息码R位校验码设

：

被

除

数C(x):k

位

待

编

信

息除

数G(x):

r+

1位?

(生成多项式)余数R(x):r

位校验位商Q(x)(1)CRC

码的编码方法a.将待编码的k位有效信息位组写成表达式：C(x)=Ck-₁xk-1+Ck-2xk-²+.....-C₁X+C。(C₁=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)除尽。2026/1/5编码方法11101i原始数据C(x)

110101

左移

R

位补0111010110101111110110101101100110101110010编码举例※假设需要发送的信息C(x)为1010001101,产生多项式G(x)

对应的代码为110101,求CRC编码。※R=5。※C(x)左

移

5

位

后

补

0

,※然后对移位后的数做模2除法

运

算

，※得余数R(x)对应的代码：01110。1101010Lb11.

←CRC

码R(x)10

←

商

CRC不用←

被除数110100011011101011

0

1

0

1

0

100000G(x)除数110101编码举例举例例：选择生成多项式为G(X)=X⁴+X+1(10011),请把8位有效信息11110111编码成CRC码。编码练习例如：对C(x)=1100,用G(x)=1011,求CRC码。1.

将信息位组左移r=3位，C(x)

·Xr=M(X)

·X³=11000002.用C(x)·X除以G(x)

,

所得余数作为校验位。3.

有效的CRC码[此处为(7,4)码]为

：C(x)·Xr+R(x)

=1100000+010=1100010。编码练习※现假设选择的CRC

生成多项式为G(X)=X4+X3+1,要

求出二进制序列10110011的CRC

校验码。

1101010010110011

0000

水

面

11001

11110

11001

11111

11001

11000110010

100余数，因为不够4位，所以前面一位的0要加上添加的比特位在原数据帧后②多项式的位数位5,则在数

据帧的后面加上5-1位0,数据

帧变为101100110000,然后

使用模2除法除以除数11001,

得到余数。③将计算出来的CRC校验码

添加在原始帧的后面，真正的

数据帧为101100110100,再

把这个数据帧发送到接收端。④接收端收到数据帧后，用上

面选定的除数，用模2除法除

去，验证余数是否为0,如果

为0,则说明数据帧没有出错。编码练习※①将多项式转化为二进制序列，由G(X)=X4+X3