第讲数据校验和防碰撞

1、第5讲 数据(shj)校验和防碰撞算法共七十五页在RFID系统中，数据传输的完整性存在两个方面的问题：1、外界的各种干扰可能使数据传输产生错误；2、多个应答器同时占用信道(xn do)使发送数据产生碰撞。运用数据检验（差错检测）和防碰撞算法可分别解决这两个问题。数据传输的完整性存在(cnzi)哪些问题？共七十五页数 据 校 验共七十五页差错的分类随机错误：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此(bc)无关。 突发错误：由突发干扰引起，当前面出现错误时，后面往往也会出现错误，它们之间有相关性。 混合错误 突发错误(cuw)长度b=5 4共七十五页差错的控制(kngzh

2、)方式前向纠错接收端通过纠错解码自动纠正传输中出现的差错，所以该方法不需要重传。这种方法需要采用具有很强纠错能力(nngl)的编码技术 。检错重发中，在发送端加入少量的监督码元，在接收端根据编码规则对收到的信号进行检查，当发现有错码是，即向发送端发出询问信号，要求重发。发送端收到询问信号后，立即重发，直到信息正确接收为止。混合纠错是ARQ和FEC的结合，设计思想是对出现的错误尽量纠正，纠正不了则需要通过重发来消除差错。共七十五页检纠错码 信息(xnx)码元与监督码元 信息(xnx)码元 k 监督码元r 6共七十五页检纠错码的分类(fn li) 7共七十五页（1）奇偶校验奇偶校验码是一种最简单而

3、有效的数据校验方法。实现方法: 在每个被传送码的左边或右边(yu bian)加上1位奇偶校验位0或1, 若采用奇校验位, 只需把每个编码中1的个数凑成奇数; 若采用偶校验位, 只要把每个编码中1的个数凑成偶数。检验原理: 这种编码能发现1个或奇数个错, 但因码距较小, 不能实现错误定位。对奇偶校验码的评价:它能发现一位或奇数个位出错，但无错误定位和纠错能力。尽管奇偶校验码的检错能力较低，但对出错概率统计, 其中7080是1位错误, 另因奇偶校验码实现简单, 故它还是一种应用最广泛的校验方法。实际应用中, 多采用奇校验, 因奇校验中不存在全“0”代码, 在某些场合下更便于判别。 00001000

4、100010000111010000101101101011101000010011101011011011001110101110011111RFID系统(xtng)中的差错校验共七十五页奇偶校验(xio yn)的校验(xio yn)方程设7位信息码组为C7C6C5C4C3C2C1, 校验码为C0 ,则对偶校验, 当满足C7C6C5C4C3C2C1C00 （1） 时, 为合法(hf)码; 对奇校验, 当满足C7C6C5C4C3C2C1C0 1 （2） 时, 为合法码。这里的表示模2相加。对于偶校验, 合法码字应满足 n CiC00 （3） i-1对于奇校验, 合法码字应满足 n CiC01

5、（4） i-1注意:公式(1)(2)为奇偶校验位的生成方程;公式(3)(4)为校验方程。共七十五页（2）循环(xnhun)冗余校验码(Cyclic Redundancy Check ,CRC) CRC码是一种(y zhn)检错、纠错能力很强的数据校验码, 主要用于网络、同步通信及磁表面存储器等应用场合。1循环冗余校验码的编码方法循环冗余校验码由两部分组成, 左边为信息位, 右边为校验位。若信息位为N位, 校验位为K位, 则该校验码被称为(NK, N)码。编码步骤如下：(1)将待编码的N位有效信息位表示为一个n1阶的多项式M(X)。(2)将M(X)左移K位, 得到M(X).Xk（K由预选的K1位

6、的生成多项式G(X)决定）。(3)用一个预选好的K1位的G(X)对M(X).Xk作模2除法。(4)把左移K位后的的有效信息位与余数作模2加法, 形成长度为NK的CRC码。 M(X).XkR(X) Q(X).G(X) 信息位校验位N位K位循环冗余校验码的格式M(X)Xk G(X)Q(X)R(X)G(X)共七十五页举例(j l)例:选择生成多项式为G(X)X4X1(10011),请把8位有效信息11110111编码成CRC码。 解：步骤(bzhu)1：M(X) X7X6+ X5X4 + X2X1 +1 11110111 步骤2: M(X). X4 111101110000 ( 即左移4位） 步骤3

7、：模2除，M(X)X4G(X) 111101110000 1001111100101111110011，即R(X)1111步骤4：模2加，得到循环冗余码为M(X)X4R(X) 111101110000 1111 111101111111 共七十五页纠错(ji cu)原理 由于M(X).XkQ(X). G(X)R(X)，根据模2加的规则M(X). Xk R(X)Q(X).G(X)R(X)R(X)Q(X).G(X)上式表明, 合法的CRC码应当能被生成多项式整除。若CRC码不能被生成多项式整除，说明(shumng)出现了信息的传送差错。 共七十五页4672616E7A4672616E7AE580E

8、5800发送数据接收数据CRCCRC校验(xio yn)共七十五页生成(shn chn)多项式的选择生成多项式被用来生成CRC码, 但并非任何一个K1位的多项式都能作为生成多项式用, 它应满足下列要求：（1）任何一位出错都应使余数不为0。（2）不同位出错应使余数不同。（3）对余数继续作模2除法，应使余数循环(xnhun)。生成多项式的选择主要靠经验，但已有3种多项式成为标准而被广泛运用, 它们都具有极高的检错率, 分别是:CRC-12X12X11X3X2X1CRC-16X16X15X21CRC-CCITTX16X12X51CRC-32= X32X26X23+ X22X16X12+ X11X10

9、X8+ X7X5X4 +X2X1注：在RFID标准ISO/IEC14443中，采用的是CRC-CCITT的生成多项式；但应注意的是，该标准中的TYPE A计算时循环移寄存器的初始值为6363H；TYPE B循环位移寄存器的初始值为FFFFH。共七十五页 多项式除法(chf)，可用除法(chf)电路来实现。除法(chf)电路的主体由一组移位寄存器和模2加法器(异或单元)组成。以CRC-ITU为例，它由16级移位寄存器和3个加法器组成，见下图(编码/解码共用)。编码、解码前将各寄存器初始化为1，信息位随着时钟移入。当信息位全部输入后，从寄存器组输出CRC结果。补充(bchng)1：共七十五页补充(

10、bchng)2：16位CRC适用于校验4000字节长的数据(shj)块的完整性，超过此长度，性能下降。RFID中传输的数据块都比4000字节短，故也可用12位或8位的CRC。共七十五页防 碰 撞共七十五页不需拆箱即可同时(tngsh)读取多笔资料橘色参考书一本蓝色字典一本灰色小说一本共七十五页一、产生碰撞(pn zhun)的原因 在RFID系统应用中，因为(yn wi)多个读写器或多个标签，造成的读写器之间或标签之间的相互干扰，统称为碰撞。1什么是碰撞1、标签碰撞2、读写器碰撞2碰撞的类型共七十五页电子标签1电子标签2电子标签4电子标签3电子标签5共七十五页电子标签1电子标签2电子标签4电子标

11、签3电子标签5共七十五页R1RrRrReader2Reader1读写器-读写器频率(pnl)干扰 R1为Reader1的干扰(gnro)范围 Rr为Reader1和Reader2的读取范围 从标签T反射到读写器Reader2的信号很容易被从Reader1发出的信号干扰。Tag读写器碰撞共七十五页Tag3Tag2Tag1Reader1Reader2多读写器一标签(bioqin)干扰 标签1接收(jishu)到的信息为两个读写器发射信号的矢量和,是一个未知信号。共七十五页共七十五页 如何解决碰撞(pn zhun)的问题呢？共七十五页无线通信(tng xn)技术中，通信(tng xn)碰撞的四种解决

12、防碰撞方法：空分多址(SDMA)频分多址(FDMA)码分多址(CDMA)时分多址(TDMA)二、防碰撞机制(jzh)的实现共七十五页1、空分多址SDMA法空间(kngjin)分割多重存取ReaderTagTagTag 分离的空间范围内重新使用(shyng)确定的资源（通信容量）1、自适应SDMA，电子控制定向天线，天线的方向直接对准某个标签2、减少单个读写器的作用范围共七十五页读写器Tag1Tag3Tag5Tag4Tag2阅读器广播(gungb)命令阅读器读写区域(qy)f1f2f3f4f52、频分多址FDMA法RFID系统把不同载波频率的传输通道分别提供给电子标签用户共七十五页 不同用户传输

13、信息所用的信号不是靠频率不同或时隙不同来区分，而是用各自不同的编码序列来区分，或者说，靠信号的不同波形来区分。如果从频域或时域来观察，多个CDMA信号是互相(h xing)重叠的。CDMA是利用不同的码序列分割成不同信道的多址技术 。 CDMA的频带利用率低，信道容量较小，地址码选择较难、接收时地址码捕获时间较长，其通信频带和技术复杂性在RFID系统中难以应用。3、码分多址(CDMA) 共七十五页4、时间(shjin)分割TDMAabcabcReaderTag1Tag2Tag3aabbcc TDMA是把整个可供使用的信道容量按时间分配给多个(du )同户的技术。共七十五页标签控制（驱动法） 以

14、电子标签为主控器，读写器对数据传输没有控制。该方法 控制很慢不灵活。阅读器控制（询问驱动法） 所有标签同时由阅读器进行控制和检测，通过一定算法，在所有标签中选择(xunz)其中一个标签，然后进行相互通信（如鉴别、读出或写入数据）。为了选择(xunz)另一个标签，应该解除原来的通信关系，因为在某一时间内只能建立起唯一的通信关系，即单个标签占用信道通信，可以按时间顺序快速地操作众多标签。所以阅读器控制的方法也称作定时双工传输法。共七十五页三、防碰撞(pn zhun)算法时分(shfn)多路（TDMA）ALOHA算法二进制树型搜索算法共七十五页1、ALOHA防碰撞算法 Aloha协议或称Aloha技

15、术、Aloha网，是世界上最早的无线电计算机通信网。Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统。 该系统所采用的技术是地面无线电广播技术，采用的协议就是有名的ALOHA协议，叫做纯ALOHA(Pure ALOHA)。以后，在此基础上，又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络。 各种( zhn)ALOHA算法：纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法。共七十五页 ALOHA算法(s

16、un f)的模型图共七十五页纯ALOHA算法 思想：只要用户有数据要发送，就尽管让他们发送 纯ALOHA算法的标签读取过程： （1）各个标签随机的在某时间点上发送信息。 （2）阅读器检测收到的信息，判断是成功接收或者碰撞。 （3）若判断发生碰撞，则标签随机等待一段时间再重新发送信息。 纯ALOHA存在的问题： （1）错误判决。即对同一个标签，如果连续多次发生碰撞，则将导致阅读器出现错误判断，认为标签不在阅读器作用范围内。 （2）数据帧的发送过程中发生碰撞的概率很大。过多的碰撞导致吞吐量下降系统性能降低(jingd)。 解决方向： 减小碰撞发生次数缩短重发延时 存在(cnzi)的问题？共七十五页

17、吞吐率S-代表有效(yuxio)传输的实际总数据率，即在观察时间T0内标签成功通信的平均次数输入负载G-发送的总数据率，即观察时间T0内标签的平均到达次数S=G*Pe 其中Pe是到达的标签能成功完成通信的概率性能(xngnng)分析由概率论知识：Pe=e-2G所以：纯ALOHA算法的吞吐率为：S=G*e-2G共七十五页 当输入负载G=0.5时，系统的吞吐率达到最大值0.184。由于纯ALOHA算法中存在(cnzi)碰撞概率较大，在实际中，该算法仅适于只读型的标签，即阅读器只负责接收标签发射的信号，标签只负责向阅读器发射信号的情况。共七十五页时隙ALOHA算法 在ALOHA算法的基础上把时间分成

18、多个离散时隙(slot)，并且每个时隙长度要大于标签回复的数据长度，标签只能在每个时隙内发送数据。每个时隙存在： a 空闲(kngxin)时隙：此时隙内没有标签发送 b 成功识别时隙：仅一个标签发送且被正确识别 c 碰撞时隙：多个标签发送，产生碰撞 共七十五页时隙ALOHA算法的吞吐率为：S=G*e-G当输入负载G=1时，系统的吞吐量达到最大值0.368，避免了纯ALOHA算法中的部分碰撞，提高了信道的利用率。需要(xyo)一个同步时钟以使阅读器阅读区域内的所有标签的时隙同步。时隙(sh x)ALOHA算法示意图共七十五页Frame Slotted Aloha(FSA) 将N个时隙组成一帧，一

19、帧中包含的时隙数固定，标签(bioqin)随机选择N个时隙中的一个与阅读器通信，一旦碰撞则等待下一帧，重新选择时隙重发信息。优点：简化了时隙Aloha的随机退避机制。缺点：当标签数远大于N时，出现“饿死现象”； 当标签数远小于N时，较多时隙空闲，产生浪费。 固定帧时隙Aloha运用(ynyng)于RFID系统示意图 帧时隙ALOHA算法共七十五页动态(dngti)帧时隙ALOHA算法（DFSA） 共七十五页动态帧时隙(sh x)Aloha运用于RFID系统示意图当系统待识别标签数较多时，动态增加帧长，可以降低时隙碰撞率，提高系统性能；当系统待识别标签数较少时，动态减少帧长，可以降低空闲(kng

20、xin)时隙比率，提高时隙利用率，提高系统性能；共七十五页2、二进制树型搜索算法 冲突(chngt)节点非冲突(chngt)节点011011100101树分叉算法基本思想是：将处于碰撞的标签分成左右两个子集0和1，先查询子集0，若没有碰撞，则正确识别标签，若仍有碰撞则分裂，把1子集分成00和01两个子集，直到识别子集1中所有标签。共七十五页101100001110?射频卡1射频卡2读写器译码 在二进制搜索算法的实现中，起决定作用的是读写器所使用的信号编码必须能够确定碰撞(pn zhun)的准确比特位置。曼彻斯特码(Mancherster)可在多卡同时响应时，译出错误码字，可以按位识别出碰撞。这

21、样可以根据碰撞的位置，按一定法则重新搜索射频卡。共七十五页范例(fnl)A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111送REQUEST（11111111）命令，要求区域内所有标签应答，根据(gnj)曼彻斯特编码，解码数据为101?1?1,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得下次的REQUEST(10101111)?R表示阅读器共七十五页Improved Anti-collision Algorithm搜寻(suxn)过程第一次搜寻第二次搜寻第三次搜寻第四次搜寻第五次搜寻发送序号接收序号TagATa

22、gBTagCTagD1010011110110101101011111011110111111111101?1?11010111110100111101011111010?1111010011110100111识别(shbi)TagA10110101101011111011110111111111101?1?11010111110101111识别TagB共七十五页Improved Anti-collision Algorithm搜寻(suxn)过程第六次搜寻第七次搜寻第八次搜寻第九次搜寻第十次搜寻发送序号接收序号TagATagBTagC TagD101101011011110111111111

23、1011?10110110101101101011011110110111101识别(shbi)TagC识别TagD共七十五页 射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们(t men)的序列号到读写器的接收模块。 读写器对比(dub)射频卡响应的序列号的相同位数上的数。出现不一致的现象即有的序列号该位为0，而有的序列号该位为1 把有不一致位的数从最高位到低位依次置O再输出系列号，即依次排除序列号大的数，至读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。选出序列号最小的数后，对该标签进行数据交换，然后使该卡进入“无声”状态。YN

24、二进制搜索算法的工作流程是：共七十五页共七十五页TYPE A （位检测(jin c)防碰撞协议）帧有3种类型：短帧、标准帧和面向比特的防碰撞帧。 四、 ISO/IEC 14443标准(biozhn)中的防碰撞协议 短帧标准帧50共七十五页面向(min xin)比特防碰撞帧加校验位不加校验位不加校验位共七十五页命令集 REQA/WUPA命令(mng lng)PCD给PICC发送查询信息。这两个命令为短帧。REQA编码为26H（高半字节取3位），WUPA编码为52H （高半字节取3位）， ATQA应答 PCD发出REQA命令后，处于休闲状态的PICC都应同步地以ATQA应答PCD，PCD检查是否有

25、碰撞备用(biyng)经营者编码UID大小00：UID级长为101：UID级长为210：UID级长为3比特帧防碰撞方式，仅有1位设置成1共七十五页UID结构(jigu)定义注：UID可以是一个固定的唯一(wi y)序列号，也可以使由PICC动态产生的随机数。CT：级联标志，编码为88H共七十五页命令集 ANTICOLLISION和SELECT命令(mng lng) 组成域SELNVBUID CLnBCC说明1字节1字节04字节1字节共七十五页命令集 ANTICOLLISION和SELECT命令(mng lng) 组成域SELNVBUID CLnBCC说明1字节1字节04字节1字节PCD发送(f

26、 sn)的字节数命令的非完整字节最后一位的位数共七十五页命令集 ANTICOLLISION和SELECT命令(mng lng) 组成域SELNVBUID CLnBCC说明1字节1字节04字节1字节BCC：是UID CLn的校验位，是UID CLn的4个字节(z ji)的异或。共七十五页命令集 ANTICOLLISION和SELECT命令(mng lng) 组成域SELNVBUID CLnBCC说明1字节1字节04字节1字节若NVB=70H，即指示其后有40个有效位，则应添加(tin ji)CRC-A（2字节），此时为SELECT命令。若NVB指示其后少于40个有效位，则为ANTICOLLISI

27、ON命令。共七十五页命令集 SAK应答 PCD发送(f sn)SELECT命令后，与40位UID匹配的PICC以SAK作为应答。UID不完整，还有未被确认(qurn)部分UID完整，PICC遵守ISO-14443-4标准的传输协议共七十五页命令集 HALT命令(mng lng)共七十五页PICC的状态Power-off（断电）状态 没有足够的载波能量，PICC没有工作，也不能发送反射(fnsh)波。 Idle（休闲）状态 PICC已经上电，能够解调信号，并能够识别有效的REQA和WAKE-UP命令。 Ready（就绪）状态 实现位帧的防碰撞算法或其它可行的防碰撞算法。 Active（激活）状态

28、 PCD通过防碰撞已经选出了单一的卡。Halt（停止）状态 60共七十五页防碰撞(pn zhun)流程 61共七十五页练习(linx)：P126 4.6共七十五页TYPE B的防碰撞(pn zhun)协议（时隙ALOHA算法）REQB/WUPB命令 前缀(qinzhu)APf=05H应用簇标识符，代表由PCD指定的应用类型（见表4.8）=0为REQB命令=1为WUPB命令当AFI匹配且N=1时，PICC应答REQB/WUPB命令当AFI匹配但N1时，PICC要选择随机时间片（在1N之间），若N=1立即应答；若N1等待SLOT-MARKER命令来匹配时间片。63共七十五页TYPE B的防碰撞协议

29、SLOT-MARKER命令 若多个(du )PICC在同一时间进行应答发生碰撞时，PCD应发出时间片SLOT-MARKER命令 。PCD给出命令为第nnnn个时间片，当PICC产生(chnshng)的随机时间片等于nnnn时才应答。64共七十五页TYPE B的防碰撞(pn zhun)协议ATQB应答 用于防碰撞期间区分PICC，它由PICC动态(dngti)产生的数或各种固定的数，仅在Idle状态改变其值协议信息：比特率、最大帧长、协议类型等AFI（1个字节）CRC-B（2个字节）应用数量（1个字节）：指示在PICC中有关应用的出现情况。PICC对REQB/WUPB命令和SLOT-MARKER

30、命令的应答都是ATQB65共七十五页TYPE B的防碰撞(pn zhun)协议ATTRIB命令 PICC在ATQB应答(yngd)中PUPI值PCD接收到正确的ATQB应答后发出ATTRIB命令。PICC发送副载波之前的最小延迟时间、PICC向PCD通信时是否需要SOF（帧开始）或EOF（帧结束）、最大帧长度、比特率等信息注：通过ATTRIB命令，PCD可以实现对某个PICC的选择，使其进入active状态。高层信息，长度可为0字节，选用时用于传送高层信息。66共七十五页TYPE B的防碰撞协议对ATTRIB命令(mng lng)的应答 对高层(o cn)命令的响应，长度可为0字节最大缓冲器容

31、量索引。PICC通过该编码告知PCD，PICC能够接收的链接链的最大值。返回CID值，若PICC不支持CID，则其编码为0000共七十五页TYPE B的防碰撞协议HLTB命令及应答 HLTB命令用于将PICC置于Halt状态，此时PICC除了(ch le)接受WUPB命令外，其它命令对它没有影响。68共七十五页TYPE B型PICC状态(zhungti)转换图共七十五页TYPE B防碰撞过程(guchng)示例 共七十五页习题：1、RFID中差错检测主要采用 和 。2、RFID系统中有两种类型的通信碰撞存在，一种是 ，另一种是 。 3、为了防止碰撞的发生，射频识别系统中需要设计相应的防碰撞技术，在通信中这种技术也称为多址