第5讲数据校验和防碰撞PPT

第5讲数据校验和防碰撞算法 1 在RFID系统中 数据传输的完整性存在两个方面的问题 1 外界的各种干扰可能使数据传输产生错误 2 多个应答器同时占用信道使发送数据产生碰撞 运用数据检验 差错检测 和防碰撞算法可分别解决这两个问题 数据传输的完整性存在哪些问题 2 数据校验 3 4 差错的分类随机错误 由信道中的随机噪声干扰引起 在出现这种错误时 前后位之间的错误彼此无关 突发错误 由突发干扰引起 当前面出现错误时 后面往往也会出现错误 它们之间有相关性 混合错误 突发错误长度b 5 差错的控制方式 前向纠错接收端通过纠错解码自动纠正传输中出现的差错 所以该方法不需要重传 这种方法需要采用具有很强纠错能力的编码技术 检错重发中 在发送端加入少量的监督码元 在接收端根据编码规则对收到的信号进行检查 当发现有错码是 即向发送端发出询问信号 要求重发 发送端收到询问信号后 立即重发 直到信息正确接收为止 混合纠错是ARQ和FEC的结合 设计思想是对出现的错误尽量纠正 纠正不了则需要通过重发来消除差错 5 6 检纠错码信息码元与监督码元 信息码元k监督码元r 7 检纠错码的分类 1 奇偶校验 奇偶校验码是一种最简单而有效的数据校验方法 实现方法 在每个被传送码的左边或右边加上1位奇偶校验位0或1 若采用奇校验位 只需把每个编码中1的个数凑成奇数 若采用偶校验位 只要把每个编码中1的个数凑成偶数 检验原理 这种编码能发现1个或奇数个错 但因码距较小 不能实现错误定位 对奇偶校验码的评价 它能发现一位或奇数个位出错 但无错误定位和纠错能力 尽管奇偶校验码的检错能力较低 但对出错概率统计 其中70 80 是1位错误 另因奇偶校验码实现简单 故它还是一种应用最广泛的校验方法 实际应用中 多采用奇校验 因奇校验中不存在全 0 代码 在某些场合下更便于判别 00001000100010000111010000101101101011101000010011101011011011001110101110011111 RFID系统中的差错校验 8 奇偶校验的校验方程 设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 为校验方程 9 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 10 举例 例 选择生成多项式为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 11 纠错原理 由于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码不能被生成多项式整除 说明出现了信息的传送差错 12 发送数据 接收数据 CRC CRC校验 13 生成多项式的选择 生成多项式被用来生成CRC码 但并非任何一个K 1位的多项式都能作为生成多项式用 它应满足下列要求 1 任何一位出错都应使余数不为0 2 不同位出错应使余数不同 3 对余数继续作模2除法 应使余数循环 生成多项式的选择主要靠经验 但已有3种多项式成为标准而被广泛运用 它们都具有极高的检错率 分别是 CRC 12 X12 X11 X3 X2 X 1CRC 16 X16 X15 X2 1CRC CCITT X16 X12 X5 1CRC 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 14 多项式除法 可用除法电路来实现 除法电路的主体由一组移位寄存器和模2加法器 异或单元 组成 以CRC ITU为例 它由16级移位寄存器和3个加法器组成 见下图 编码 解码共用 编码 解码前将各寄存器初始化为 1 信息位随着时钟移入 当信息位全部输入后 从寄存器组输出CRC结果 补充1 15 补充2 16位CRC适用于校验4000字节长的数据块的完整性 超过此长度 性能下降 RFID中传输的数据块都比4000字节短 故也可用12位或8位的CRC 16 防碰撞 17 不需拆箱即可同时读取多笔资料 18 一 产生碰撞的原因 在RFID系统应用中 因为多个读写器或多个标签 造成的读写器之间或标签之间的相互干扰 统称为碰撞 1 标签碰撞2 读写器碰撞 19 电子标签1 电子标签2 电子标签4 电子标签3 电子标签5 20 电子标签1 电子标签2 电子标签4 电子标签3 电子标签5 21 R1 Rr Rr Reader2 Reader1 读写器 读写器频率干扰 R1为Reader1的干扰范围 Rr为Reader1和Reader2的读取范围 从标签T反射到读写器Reader2的信号很容易被从Reader1发出的信号干扰 Tag 读写器碰撞 22 多读写器一标签干扰 标签1接收到的信息为两个读写器发射信号的矢量和 是一个未知信号 23 24 如何解决碰撞的问题呢 25 无线通信技术中 通信碰撞的四种解决防碰撞方法 空分多址 SDMA 频分多址 FDMA 码分多址 CDMA 时分多址 TDMA 二 防碰撞机制的实现 26 1 空分多址SDMA法 空间分割多重存取 分离的空间范围内重新使用确定的资源 通信容量 1 自适应SDMA 电子控制定向天线 天线的方向直接对准某个标签 2 减少单个读写器的作用范围 27 读写器 Tag1 Tag3 Tag5 Tag4 Tag2 阅读器广播命令 阅读器读写区域 f1 f2 f3 f4 f5 2 频分多址FDMA法 RFID系统把不同载波频率的传输通道分别提供给电子标签用户 28 不同用户传输信息所用的信号不是靠频率不同或时隙不同来区分 而是用各自不同的编码序列来区分 或者说 靠信号的不同波形来区分 如果从频域或时域来观察 多个CDMA信号是互相重叠的 CDMA是利用不同的码序列分割成不同信道的多址技术 CDMA的频带利用率低 信道容量较小 地址码选择较难 接收时地址码捕获时间较长 其通信频带和技术复杂性在RFID系统中难以应用 3 码分多址 CDMA 29 4 时间分割TDMA TDMA是把整个可供使用的信道容量按时间分配给多个同户的技术 30 标签控制 驱动法 以电子标签为主控器 读写器对数据传输没有控制 该方法控制很慢不灵活 阅读器控制 询问驱动法 所有标签同时由阅读器进行控制和检测 通过一定算法 在所有标签中选择其中一个标签 然后进行相互通信 如鉴别 读出或写入数据 为了选择另一个标签 应该解除原来的通信关系 因为在某一时间内只能建立起唯一的通信关系 即单个标签占用信道通信 可以按时间顺序快速地操作众多标签 所以阅读器控制的方法也称作定时双工传输法 31 三 防碰撞算法 时分多路 TDMA ALOHA算法 二进制树型搜索算法 32 1 ALOHA防碰撞算法Aloha协议或称Aloha技术 Aloha网 是世界上最早的无线电计算机通信网 Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机 从而实现一点到多点的数据通信 第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统 该系统所采用的技术是地面无线电广播技术 采用的协议就是有名的ALOHA协议 叫做纯ALOHA PureALOHA 以后 在此基础上 又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络 各种ALOHA算法 纯ALOHA算法 时隙ALOHA算法 帧时隙ALOHA算法 动态帧时隙ALOHA算法 33 ALOHA算法的模型图 34 纯ALOHA算法思想 只要用户有数据要发送 就尽管让他们发送纯ALOHA算法的标签读取过程 1 各个标签随机的在某时间点上发送信息 2 阅读器检测收到的信息 判断是成功接收或者碰撞 3 若判断发生碰撞 则标签随机等待一段时间再重新发送信息 纯ALOHA存在的问题 1 错误判决 即对同一个标签 如果连续多次发生碰撞 则将导致阅读器出现错误判断 认为标签不在阅读器作用范围内 2 数据帧的发送过程中发生碰撞的概率很大 过多的碰撞导致吞吐量下降系统性能降低 解决方向 减小碰撞发生次数缩短重发延时 存在的问题 35 吞吐率S 代表有效传输的实际总数据率 即在观察时间T0内标签成功通信的平均次数输入负载G 发送的总数据率 即观察时间T0内标签的平均到达次数S G Pe其中Pe是到达的标签能成功完成通信的概率 性能分析 由概率论知识 Pe e 2G所以 纯ALOHA算法的吞吐率为 S G e 2G 36 当输入负载G 0 5时 系统的吞吐率达到最大值0 184 由于纯ALOHA算法中存在碰撞概率较大 在实际中 该算法仅适于只读型的标签 即阅读器只负责接收标签发射的信号 标签只负责向阅读器发射信号的情况 37 时隙ALOHA算法在ALOHA算法的基础上把时间分成多个离散时隙 slot 并且每个时隙长度要大于标签回复的数据长度 标签只能在每个时隙内发送数据 每个时隙存在 a空闲时隙 此时隙内没有标签发送b成功识别时隙 仅一个标签发送且被正确识别c碰撞时隙 多个标签发送 产生碰撞 38 时隙ALOHA算法的吞吐率为 S G e G当输入负载G 1时 系统的吞吐量达到最大值0 368 避免了纯ALOHA算法中的部分碰撞 提高了信道的利用率 需要一个同步时钟以使阅读器阅读区域内的所有标签的时隙同步 时隙ALOHA算法示意图 39 FrameSlottedAloha FSA 将N个时隙组成一帧 一帧中包含的时隙数固定 标签随机选择N个时隙中的一个与阅读器通信 一旦碰撞则等待下一帧 重新选择时隙重发信息 优点 简化了时隙Aloha的随机退避机制 缺点 当标签数远大于N时 出现 饿死现象 当标签数远小于N时 较多时隙空闲 产生浪费 固定帧时隙Aloha运用于RFID系统示意图 帧时隙ALOHA算法 40 动态帧时隙ALOHA算法 DFSA 41 动态帧时隙Aloha运用于RFID系统示意图 当系统待识别标签数较多时 动态增加帧长 可以降低时隙碰撞率 提高系统性能 当系统待识别标签数较少时 动态减少帧长 可以降低空闲时隙比率 提高时隙利用率 提高系统性能 42 2 二进制树型搜索算法 冲突节点 非冲突节点 0 1 10 11 100 101 树分叉算法 基本思想是 将处于碰撞的标签分成左右两个子集0和1 先查询子集0 若没有碰撞 则正确识别标签 若仍有碰撞则分裂 把1子集分成00和01两个子集 直到识别子集1中所有标签 43 1 0 1 1 0 0 0 0 1 1 1 0 射频卡1 射频卡2 读写器译码 在二进制搜索算法的实现中 起决定作用的是读写器所使用的信号编码必须能够确定碰撞的准确比特位置 曼彻斯特码 Mancherster 可在多卡同时响应时 译出错误码字 可以按位识别出碰撞 这样可以根据碰撞的位置 按一定法则重新搜索射频卡 44 范例 A 10100111 B 10110101 C 10101111 D 10111101 R 11111111 R 11111111 送REQUEST 11111111 命令 要求区域内所有标签应答 根据曼彻斯特编码 解码数据为101 1 1 发生碰撞 算法做下如下 将碰撞的最高置0 其它碰撞位置1 得下次的REQUEST 10101111 R表示阅读器 45 ImprovedAnti collisionAlgorithm搜寻过程 10100111 10110101 10101111 10111101 11111111 101 1 1 10101111 10100111 10101111 1010 111 10100111 10100111 识别TagA 10110101 10101111 10111101 11111111 101 1 1 10101111 10101111 识别TagB 46 ImprovedAnti collisionAlgorithm搜寻过程 10110101 10111101 11111111 1011 101 10110101 10110101 10111101 10111101 识别TagC 识别TagD 47 射频卡进入读写器的工作范围 读写器发出一个最大序列号让所有射频卡响应 同一时刻开始传输它们的序列号到读写器的接收模块 读写器对比射频卡响应的序列号的相同位数上的数 出现不一致的现象 即有的序列号该位为0 而有的序列号该位为1 把有不一致位的数从最高位到低位依次置O再输出系列号 即依次排除序列号大的数 至读写器对比射频卡响应的序列号的相同位数上的数完全一致时 说明无碰撞 选出序列号最小的数后 对该标签进行数据交换 然后使该卡进入 无声 状态 Y N 二进制搜索算法的工作流程是 48 49 50 TYPEA 位检测防碰撞协议 帧有3种类型 短帧 标准帧和面向比特的防碰撞帧 四 ISO IEC14443标准中的防碰撞协议 短帧 标准帧 面向比特防碰撞帧 加校验位 不加校验位 不加校验位 51 命令集REQA WUPA命令PCD给PICC发送查询信息 这两个命令为短帧 REQA编码为26H 高半字节取3位 WUPA编码为52H 高半字节取3位 ATQA应答PCD发出REQA命令后 处于休闲状态的PICC都应同步地以ATQA应答PCD PCD检查是否有碰撞 备用 经营者编码 UID大小00 UID级长为101 UID级长为210 UID级长为3 比特帧防碰撞方式 仅有1位设置成1 52 UID结构定义 注 UID可以是一个固定的唯一序列号 也可以使由PICC动态产生的随机数 CT 级联标志 编码为88H 53 命令集ANTICOLLISION和SELECT命令 54 命令集ANTICOLLISION和SELECT命令 PCD发送的字节数 命令的非完整字节最后一位的位数 55 命令集ANTICOLLISION和SELECT命令 BCC 是UIDCLn的校验位 是UIDCLn的4个字节的异或 56 命令集ANTICOLLISION和SELECT命令 若NVB 70H 即指示其后有40个有效位 则应添加CRC A 2字节 此时为SELECT命令 若NVB指示其后少于40个有效位 则为ANTICOLLISION命令 57 命令集SAK应答PCD发送SELECT命令后 与40位UID匹配的PICC以SAK作为应答 UID不完整 还有未被确认部分 UID完整 PICC遵守ISO 14443 4标准的传输协议 58 命令集HALT命令 59 60 PICC的状态Power off 断电 状态没有足够的载波能量 PICC没有工作 也不能发送反射波 Idle 休闲 状态PICC已经上电 能够解调信号 并能够识别有效的REQA和WAKE UP命令 Ready 就绪 状态实现位帧的防碰撞算法或其它可行的防碰撞算法 Active 激活 状态PCD通过防碰撞已经选出了单一的卡 Halt 停止 状态 61 防碰撞流程 练习 P1264 6 62 63 TYPEB的防碰撞协议 时隙ALOHA算法 REQB WUPB命令 前缀APf 05H 应用簇标识符 代表由PCD指定的应用类型 见表4 8 0为REQB命令 1为WUPB命令 当AFI匹配且N 1时 PICC应答REQB WUPB命令当AFI匹配但N 1时 PICC要选择随机时间片 在1 N之间 若N 1立即应答 若N 1等待SLOT MARKER命令来匹配时间片 64 TYPEB的防碰撞协议SLOT MARKER命令若多个PICC在同一时间进行应答发生碰撞时 PCD应发出时间片SLOT MARKER命令 PCD给出命令为第nnnn个时间片 当PICC产生的随机时间片等于nnnn时才应答 65 TYPEB的防碰撞协议ATQB应答 用于防碰撞期间区分PICC 它由PICC动态产生的数或各种固定的数 仅在Idle状态改变其值 协议信息 比特率 最大帧长 协议类型等 AFI 1个字节 CRC B 2个字节 应用数量 1个字节 指示在PICC中有关应用的出现情况 PICC对REQB WUPB命令和SLOT MARKER命令的应答都是ATQB 66 TYPEB的防碰撞协议ATTRIB命令 PICC在ATQB应答中PUPI值 PCD接收到正确的ATQB应答后发出ATTRIB命令 PICC发送副载波之前的最小延迟时间 PICC向PCD通信时是否需要SOF 帧开始 或EOF 帧结束 最大帧长度 比特率等信息 注 通过ATTRIB命令 PCD可以实现对某个PICC的选择 使其进入active状态 高层信息 长度可为0字节 选用时用于传送高层信息 TYPEB的防碰撞协议对ATTRIB命令的应答 对高层命令的响应 长度可为0字节 最大缓冲器容量索引 PICC通过该编码告知PCD PICC能够接收的链接链的最大值 返回CID值 若PICC不支持CID 则其编码