第5讲数据校验和防碰撞

第5讲数据校验和防碰撞算法在RFID系统中，数据传输的完整性存在两个方面的问题：1、外界的各种干扰可能使数据传输产生错误；2、多个应答器同时占用信道使发送数据产生碰撞。运用数据检验（差错检测）和防碰撞算法可分别解决这两个问题。数据传输的完整性存在哪些问题？数据校验4差错的分类随机错误：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此无关。突发错误：由突发干扰引起，当前面出现错误时，后面往往也会出现错误，它们之间有相关性。混合错误正确比特流00111000接收比特流01100100异或错误图样01011100突发错误长度b=5差错的控制方式前向纠错接收端通过纠错解码自动纠正传输中出现的差错，所以该方法不需要重传。这种方法需要采用具有很强纠错能力的编码技术。检错重发中，在发送端加入少量的监督码元，在接收端根据编码规则对收到的信号进行检查，当发现有错码是，即向发送端发出询问信号，要求重发。发送端收到询问信号后，立即重发，直到信息正确接收为止。混合纠错是ARQ和FEC的结合，设计思想是对出现的错误尽量纠正，纠正不了则需要通过重发来消除差错。6检纠错码信息码元与监督码元krn信息码元k监督码元r7检纠错码的分类检纠错码检纠随机错误码检纠突发错误码卷积码非线性码比特交织码非循环码分组码分组码交织码线性码字节交织码循环码海明码奇偶校验码CRCRSBCH（1）奇偶校验奇偶校验码是一种最简单而有效的数据校验方法。实现方法:在每个被传送码的左边或右边加上1位奇偶校验位0或1,若采用奇校验位,只需把每个编码中1的个数凑成奇数;若采用偶校验位,只要把每个编码中1的个数凑成偶数。检验原理:这种编码能发现1个或奇数个错,但因码距较小,不能实现错误定位。对奇偶校验码的评价:它能发现一位或奇数个位出错，但无错误定位和纠错能力。尽管奇偶校验码的检错能力较低，但对出错概率统计,其中70～80％是1位错误,另因奇偶校验码实现简单,故它还是一种应用最广泛的校验方法。实际应用中,多采用奇校验,因奇校验中不存在全“0”代码,在某些场合下更便于判别。00001000100010000111010000101101101011101000010011101011011011001110101110011111RFID系统中的差错校验奇偶校验的校验方程设7位信息码组为C7C6C5C4C3C2C1,校验码为C0,则对偶校验,当满足C7⊕C6⊕C5⊕C4⊕C3⊕C2⊕C1⊕C0＝0……（1）时,为合法码;对奇校验,当满足C7⊕C6⊕C5⊕C4⊕C3⊕C2⊕C1⊕C0＝1……（2）时,为合法码。这里的⊕表示模2相加。对于偶校验,合法码字应满足n∑Ci⊕C0＝0……（3）i-1对于奇校验,合法码字应满足n∑Ci⊕C0＝1……（4）i-1注意:公式(1)(2)为奇偶校验位的生成方程;公式(3)(4)为校验方程。（2）循环冗余校验码(CyclicRedundancyCheck,CRC)CRC码是一种检错、纠错能力很强的数据校验码,主要用于网络、同步通信及磁表面存储器等应用场合。1．循环冗余校验码的编码方法循环冗余校验码由两部分组成,左边为信息位,右边为校验位。若信息位为N位,校验位为K位,则该校验码被称为(N＋K,N)码。编码步骤如下：(1)将待编码的N位有效信息位表示为一个n－1阶的多项式M(X)。(2)将M(X)左移K位,得到M(X).Xk（K由预选的K＋1位的生成多项式G(X)决定）。(3)用一个预选好的K＋1位的G(X)对M(X).Xk作模2除法。(4)把左移K位后的的有效信息位与余数作模2加法,形成长度为N＋K的CRC码。M(X).Xk＋R(X)＝Q(X).G(X)信息位校验位N位K位循环冗余校验码的格式M(X)·XkG(X)＝Q(X)＋R(X)／G(X)举例例:选择生成多项式为G(X)＝X4＋X＋1(10011),请把8位有效信息11110111编码成CRC码。解：步骤1：M(X)＝X7＋X6+X5＋X4+X2＋X1+1＝11110111步骤2:M(X).X4＝111101110000(即左移4位）步骤3：模2除，M(X)·X4／G(X)＝111101110000／10011＝11100101＋1111／10011，即R(X)＝1111步骤4：模2加，得到循环冗余码为M(X)·X4＋R(X)＝111101110000＋1111＝111101111111纠错原理由于M(X).Xk＝Q(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码不能被生成多项式整除，说明出现了信息的传送差错。4672616E7A4672616E7AE580E5800发送数据接收数据CRCCRC校验生成多项式的选择生成多项式被用来生成CRC码,但并非任何一个K＋1位的多项式都能作为生成多项式用,它应满足下列要求：（1）任何一位出错都应使余数不为0。（2）不同位出错应使余数不同。（3）对余数继续作模2除法，应使余数循环。生成多项式的选择主要靠经验，但已有3种多项式成为标准而被广泛运用,它们都具有极高的检错率,分别是:CRC-12＝X12＋X11＋X3＋X2＋X＋1CRC-16＝X16＋X15＋X2＋1CRC-CCITT＝X16＋X12＋X5＋1CRC-32=X32＋X26＋X23+X22＋X16＋X12+X11＋X10＋X8+X7＋X5＋X4+X2＋X＋1注：在RFID标准ISO/IEC14443中，采用的是CRC-CCITT的生成多项式；但应注意的是，该标准中的TYPEA计算时循环移寄存器的初始值为6363H；TYPEB循环位移寄存器的初始值为FFFFH。多项式除法，可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器(异或单元)组成。以CRC-ITU为例，它由16级移位寄存器和3个加法器组成，见下图(编码/解码共用)。编码、解码前将各寄存器初始化为1，信息位随着时钟移入。当信息位全部输入后，从寄存器组输出CRC结果。补充1：=1DQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQDQQ=1=1inputclkresetsetQ0Q1Q2Q3Q4Q5Q6Q7Q8Q9Q10Q11Q12Q13Q14Q15补充2：16位CRC适用于校验4000字节长的数据块的完整性，超过此长度，性能下降。RFID中传输的数据块都比4000字节短，故也可用12位或8位的CRC。防碰撞不需拆箱即可同时读取多笔资料橘色参考书一本蓝色字典一本灰色小说一本一、产生碰撞的原因在RFID系统应用中，因为多个读写器或多个标签，造成的读写器之间或标签之间的相互干扰，统称为碰撞。1什么是碰撞1、标签碰撞2、读写器碰撞2碰撞的类型电子标签1电子标签2电子标签4电子标签3电子标签5电子标签1电子标签2电子标签4电子标签3电子标签5R1RrRrReader2Reader1读写器-读写器频率干扰R1为Reader1的干扰范围Rr为Reader1和Reader2的读取范围从标签T反射到读写器Reader2的信号很容易被从Reader1发出的信号干扰。Tag读写器碰撞Tag3Tag2Tag1Reader1Reader2多读写器一标签干扰标签1接收到的信息为两个读写器发射信号的矢量和,是一个未知信号。如何解决碰撞的问题呢？无线通信技术中，通信碰撞的四种解决防碰撞方法：空分多址(SDMA)频分多址(FDMA)码分多址(CDMA)时分多址(TDMA)二、防碰撞机制的实现1、空分多址SDMA法空间分割多重存取ReaderTagTagTag分离的空间范围内重新使用确定的资源（通信容量）1、自适应SDMA，电子控制定向天线，天线的方向直接对准某个标签2、减少单个读写器的作用范围读写器Tag1Tag3Tag5Tag4Tag2阅读器广播命令阅读器读写区域f1f2f3f4f52、频分多址FDMA法RFID系统把不同载波频率的传输通道分别提供给电子标签用户不同用户传输信息所用的信号不是靠频率不同或时隙不同来区分，而是用各自不同的编码序列来区分，或者说，靠信号的不同波形来区分。如果从频域或时域来观察，多个CDMA信号是互相重叠的。CDMA是利用不同的码序列分割成不同信道的多址技术。CDMA的频带利用率低，信道容量较小，地址码选择较难、接收时地址码捕获时间较长，其通信频带和技术复杂性在RFID系统中难以应用。3、码分多址(CDMA)4、时间分割TDMAa’b’c’abcReaderTag1Tag2Tag3a’ab’bc’cTDMA是把整个可供使用的信道容量按时间分配给多个同户的技术。标签控制（驱动法）以电子标签为主控器，读写器对数据传输没有控制。该方法控制很慢不灵活。阅读器控制（询问驱动法）所有标签同时由阅读器进行控制和检测，通过一定算法，在所有标签中选择其中一个标签，然后进行相互通信（如鉴别、读出或写入数据）。为了选择另一个标签，应该解除原来的通信关系，因为在某一时间内只能建立起唯一的通信关系，即单个标签占用信道通信，可以按时间顺序快速地操作众多标签。所以阅读器控制的方法也称作定时双工传输法。三、防碰撞算法时分多路（TDMA）ALOHA算法二进制树型搜索算法1、ALOHA防碰撞算法Aloha协议或称Aloha技术、Aloha网，是世界上最早的无线电计算机通信网。Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统。该系统所采用的技术是地面无线电广播技术，采用的协议就是有名的ALOHA协议，叫做纯ALOHA(PureALOHA)。以后，在此基础上，又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络。各种ALOHA算法：纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法。ALOHA算法的模型图纯ALOHA算法思想：只要用户有数据要发送，就尽管让他们发送纯ALOHA算法的标签读取过程：（1）各个标签随机的在某时间点上发送信息。（2）阅读器检测收到的信息，判断是成功接收或者碰撞。（3）若判断发生碰撞，则标签随机等待一段时间再重新发送信息。纯ALOHA存在的问题：（1）错误判决。即对同一个标签，如果连续多次发生碰撞，则将导致阅读器出现错误判断，认为标签不在阅读器作用范围内。（2）数据帧的发送过程中发生碰撞的概率很大。过多的碰撞导致吞吐量下降系统性能降低。解决方向：减小碰撞发生次数缩短重发延时存在的问题？？？•吞吐率S---代表有效传输的实际总数据率，即在观察时间T0内标签成功通信的平均次数•输入负载G---发送的总数据率，即观察时间T0内标签的平均到达次数•S=G*Pe其中Pe是到达的标签能成功完成通信的概率性能分析由概率论知识：Pe=e-2G所以：纯ALOHA算法的吞吐率为：S=G*e-2G当输入负载G=0.5时，系统的吞吐率达到最大值0.184。由于纯ALOHA算法中存在碰撞概率较大，在实际中，该算法仅适于只读型的标签，即阅读器只负责接收标签发射的信号，标签只负责向阅读器发射信号的情况。时隙ALOHA算法在ALOHA算法的基础上把时间分成多个离散时隙(slot)，并且每个时隙长度要大于标签回复的数据长度，标签只能在每个时隙内发送数据。每个时隙存在：a空闲时隙：此时隙内没有标签发送b成功识别时隙：仅一个标签发送且被正确识别c碰撞时隙：多个标签发送，产生碰撞时隙ALOHA算法的吞吐率为：S=G*e-G当输入负载G=1时，系统的吞吐量达到最大值0.368，避免了纯ALOHA算法中的部分碰撞，提高了信道的利用率。需要一个同步时钟以使阅读器阅读区域内的所有标签的时隙同步。时隙ALOHA算法示意图FrameSlo