毕业设计（论文）跳跃式二进制树形系统反碰撞算法研究

1、121 国外相关研究状况 rfid迅速发展的推动因素主要有两个。第一是rfid芯片的生产开始形成规模，产品成本大幅下降。在不久的将来一个包括rfid芯片的电子标签极端最低成本可以达到12美分，甚至更低。第二，大宗零售业开始接受和应用rfid技术，rfid正不断赢得众多大型用户的注意。目前国际市场的需求主要来自于零售商。rfid的迅速发展，使得其标准的制定也日臻完善。目前国际上比较完善的rfid标准有三个：iso、欧美的epc global以及日本的ubiquitous id center。而这三个组织对rfid技术应用规范都有各自的目标与发展规划。iso 14443和iso 15693标准在1

2、995年开始操作，其完成则是在2000年之后，二者皆以13.56mhz交变信号为载波频率。iso 15693读写距离较远，而iso 14443读写距离稍近，但应用较广泛。美国运通卡（american express）、万事达卡（master card）和维萨卡（visa）公司在无线交易时均已采用了iso 14443标准。反碰撞算法技术是rfid的核心技术之一，这也是和接触式ic卡的主要区别。基于标准中对防碰撞算法的规定，目前存在的防碰撞算法大致可分为三种：空分多路法（sdma），是在分离的空间范围内进行多目标识别的技术；频分多路法（fdma），是把多个不同载波频率作为多个传输通路供多个标签使用

3、的技术；时分多路法（tdma），把整个可供使用的通路容量按时间分片分配给多个用户。iso 14443和iso 15693标准对防碰撞机制做出了规定。iso 15693采用轮寻机制、分时查询的方式完成防冲撞机制。随后推出的iso 14443标准解决了iso 15693标准的数据传输速度慢，无法处理大量加密数据的缺点，并在 iso 14443-3分别规定了type a和type b的防冲撞机制。二者防冲撞机制的原理不同，前者是基于位碰撞检测协议，而type b利用通信系列命令序列完成防冲撞。其中a型卡的反碰撞机理如下：当一个a型卡到达了读写器的作用范围内，并且有足够的供应电能，卡就开始执行一些预置

4、的程序后，智能卡进入闲置状态。处于“闲置状态”的智能卡不能对读写器传输给其它智能卡的数据起响应。智能卡在“闲置状态”接收到有效的reqa命令，则回送对请求的应答字atqa。当智能卡对reqa命令作了应答后，智能卡处于ready状态。读写器识别出：在作用范围内至少有一张智能卡存在。通过发送select命令启动“二进制检索树”防碰撞算法，选出一张智能卡，对其进行操作。动态aloha算法是一种轮寻机制的算法。根据碰撞问题本身的数学特性而采用的一种rfid的防碰撞算法。它既没有检测机制也没有恢复机制，只是通过某种数据编码检测冲突的存在，动态地调整个读写器的报警时间（读取时间），从而达到将数据帧接收错误

5、率降低到所要求的程度，并同时对标签的数据吞吐率没有损失。使用这种方法，应答器和读写器都只要分别有传输和接收装置就可以了，可大大降低成本。这种方法适用于只读标签中，这类应答器通常只有一些数据（序列号）传输给读写器，并且是周期地循环地将这些数据发给读写器的，它适用的场合有：超市对货物的管理、图书馆对图书的管理、动物园对动物的监控等数据交换量不大、带宽要求比较低的场合。现在已有的反碰撞算法有随机问询的aloha算法、分隙aloha算法，信息的最佳利用率分别为l84、368，但随着标签数量的扩大，性能将急剧恶化。122 我国相关的研究状况2004年1月我国宣布成立跨部门小组研发rfid技术，以便在这项

6、新兴技术上取得领先优势。在我国常用的rfid国际标准主要有用于动物识别的iso 11784和iso 11785，用于非接触智能卡的iso 10536（close coupled cards）、iso 15693（vicinity cards）和iso 14443（pronimity cards），用于集装箱识别的iso 10374等。1996年佛山市政府安装了rfid系统用于自动收取路桥费，明显地提高车辆通过率，缓解公路瓶颈。车辆可以在250公里的时速下用少于0.5毫秒的时间被识别，并且正确率达99.95%。上海也安装了基于rfid技术的自动收缴养路费系统。广州也已经在开放的高速公路上用rfi

7、d系统对高速行驶的车辆进行自动收费。从2005年我国开始更新使用非接触式的ic卡公民身份证，这将为我国rfid产业带来一个巨大的潜在市场，积极地推动我国相关技术的发展。第二代电子身份证采用的标准是iso 14443 type b协议。iso 14443定义了type a、type b两种类型协议，通信速率为106kbit/s，它们的不同主要在于载波的调制深度及位的编码方式。type a采用开关键控（on-off keying）的曼彻斯特编码，type b采用nrz-l的bpsk编码。type b与type a相比，具有传输能量不中断、速率更高、抗干扰能力列强的优点。防冲撞机制使得同时处于读写区

8、内的多张卡的正确操作成为可能，大大提高了操作速度。作为rfid系统关键的反碰撞算法，我国也已经有很多学者进行了相关的研究。发表了很多有关反碰撞算法的学术论文，对一些系统反碰撞算法作了原理阐述并完成了算法的实现。例如aloha随机推迟系统反碰撞算法、符合iso 14443 type a标准的二进制树形搜索算法等。13 论文研究内容及结构安排本论文着重研究了rfid系统的反碰撞算法，介绍一种快速高效的rfid系统反碰撞算法跳跃式二进制树形算法，并利用verilog hdl语言对算法进行了设计同时利用fpga器件进行了计算机仿真。在第一章中，主要介绍了课题的研究背景和研究意义，并介绍了国内外相关的研

9、究现状。作为基础知识准备，本文在第二章首先介绍了一些相关的基础知识，其中包括：rfid系统的结构与工作原理，跳跃式二进制树形反碰撞算法原理阐述，以及fpga的相关基础知识等。同时在第二章中详细介绍了rfid系统反碰撞算法的实现，包括：rfid系统反碰撞算法总体设计方案；rfid标签verilog hdl模型的建立；rfid读写器manchester解码及碰撞位判断模型的建立；树形节点信息处理与lifo栈模型；反碰撞算法状态机的实现。在第三章中对反碰撞算法进行了系统的仿真并对仿真结果进行了详细分析，同时给出该算法的主要性能指标。在仿真的过程中采用先分立后综合的方式，先对各个分立的模块进行仿真，最

10、后将各个模块组合起来进行综合仿真，然后根据得到的仿真数据直观地反映算法的各项性能参数。具体内容包括：标签的仿真结果及其分析；读写器manchester解码及碰撞位判断的仿真结果及分析；用于存储树形节点信息的lifo栈仿真结果及分析；rfid系统反碰撞算法的综合仿真结果；rfid系统反碰撞算法的性能分析。 最后在第四章对本文进行了总结。2 rfid系统防碰撞算法设计21 rfid系统与反碰撞算法211 rfid的系统结构与工作原理无线射频识别系统rfid（radio frequency identification system），一般由rfid标签、rfid读写器以及计算机系统组成，如图1所示

11、。系统基本工作原理如下：rfid标签进入磁场，接收rfid读写器发出的射频信号，凭借感应电流所获得的能量发送出存储在芯片中的产品信息（无源标签）或者主动发送某一频率的信号（有源标签），rfid读写器读取信息后，解码，送至计算机系统对有关数据进行处理。图1 rfid的基本结构组成下面对rfid的系统结构以及工作原理做较详细的说明。1、rfid系统基本结构（1）rfid标签rfid标签由耦合元件及芯片组成，每个标签具有惟一的电子编码，附着在物体目标对象上。电子标签像纸一样薄, 柔韧可弯曲并可编程，射频标签内编写的程序可按特殊的应用进行随时读取和改写。射频标签也可编入相应人员的一些数据信息，这些人员

12、的数据信息可依据需要进行分类管理，并可随不同的需要制作新卡，射频标签中的内容被改写的同时也可以被永久锁死保护起来。通常标签芯片体积很小，厚度一般不超过0.35mm，可以印制在纸张、塑料、木材、玻璃、纺织品等包装材料上，也可以直接制作在商品标签上，通过自动贴标签机进行自动贴标。 从能量方面来看，标签可以分为两种：无源标签和有源标签。无源标签自身不带有电源，当读取装置对标签进行读取时，所发射出的无线电接触到rfid标签的天线后产生电量。它的重量轻、体积小，寿命可以很长，但是发射距离受限。有源标签使用卡内的电池能量，识别的距离长，但是它的价格较高且寿命短。 从功能方面来看，可将rfid标签分为四种：

13、只读标签、可重写标签、带微处理器标签和配有传感器的标签。只读型标签的结构功能最简单，包含的信息较少并且不能被更改；可重写型标签集成了容量为几十字节到几万个字节的闪存，标签内的信息能被更改或重写，只读型和可重写型标签都主要应用于物流系统以及生产过程管理系统和行李控制系统中；带微处理器标签依靠内置式只读存储器中储存的操作系统和程序来工作，出于安全的目的，许多标签都同时具备加密电路，现在这类标签主要应用于非接触型ic卡上，既用于电子结算、出入管理，也可用作会员卡；有些rfid标签集成了传感器，包括温度传感器或压力传感器等，目前这类标签主要用于动物个体识别和轮胎管理上。按调制方式来分，电子标签还可分为

14、主动式标签和被动式标签。主动式标签用自身的射频能量主动地发送数据给读写器，主要用于有障碍物的应用中；被动式标签使用调制散射方式发射数据，它必须利用读写器的载波来调制自己的信号，在门禁或交通的应用中较适宜。（2）rfid读写器读写器是负责读取或写入标签信息的设备，读写器可以是单独的整体，也可以作为部件的形式嵌入到其他系统中去。它可以单独具有读写、显示、数据处理等功能，也可与计算机或其他系统进行联合，完成对射频标签的操作。读写器由两个基本的功能块组成：控制系统和由发送器及接收器组成的高频接口。读写器高频接口的功能包括：产生高频的发射功率，为启动电子标签提供能量；对发射信号进行调制将数据传送给电子标

15、签；接收并解调来自电子标签的高频信号。读写器控制单元的功能包括：与应用软件进行通信，并执行应用系统软件发来的命令；控制与电子标签的通信过程；信号的编码与解码。在一些复杂的系统中，控制单元还要执行反碰撞算法，同时对电子标签与读写器之间要传送的数据进行加密和解密，并且进行电子标签和读写器之间的身份验证。读写器可将主机的读写命令传到电子标签，再把从主机发往电子标签的数据加密，将电子标签返回的数据解密后送到主机。读写器将要发送的信号，经编码后加载在特定频率的载波信号上经天线向外发送，进入读写器工作区域的电子标签接收此脉冲信号，然后标签内芯片中的有关电路对此信号进行调制、解码、解密，然后对命令请求、密码

16、、权限等进行判断。若为读取命令，控制逻辑电路则从存储器中读取有关信息，经加密、编码后经标签内的天线发送给读写器，读写器对接收到的信号进行解调、解码、解密后送至计算机处理;若是修改信息的写入命令，有关控制逻辑引起的内部电荷泵提升工作电压，对标签中的内容进行改写。（3）计算机信息系统计算机信息系统主要完成数据信息的存储及管理、对卡进行读写控制，数据管理系统可以是市面上现有的各种大小不一的数据库或供应链系统，用户还能够买到面向特定行业的高度专业化的库存数据库，或者把rfid系统当成整个企业erp的一部分。如果应用情况比较特殊，甚至可以自己动手编写数据库应用软件，采用pc机或者是终端机来完成。2、rf

17、id系统工作原理绝大多数射频识别系统是按电感耦合的原理工作的，读写器在数据管理系统的控制下发送出一定频率的射频信号，当电子标签进入磁场时产生感应电流从而获得能量，发送出自身编码等信息，该信息被读写器读取并解码后送至管理系统（一般是电脑主机）进行有关处理，这一信息的收集处理过程是以无线方式进行的。212 跳跃式二进制树形反碰撞算法原理在射频识别系统中，不能排除在读写器范围内存在多个电子标签的情况，于是系统中存在两种通信形式：从读写器到电子标签的数据传输，即读写器发送的数据流被覆盖范围内的多个标签所接收，这种通信形式也被称为无线电广播；在读写器的作用范围内有多个标签同时应答，这种形式被称为多路存取

18、。在后一种通信形式中，标签数据的混叠问题就是我们所说的碰撞问题。为了防止由于多个电子标签的数据在读写器的接收机中相互碰撞而不能准确读出，必须采用反碰撞算法来加以克服。本文中设计的跳跃式二进制树形算法属于时分多路的复用方式。文中阐述算法原理及算法设计仿真的过程中标签均以简化的8位epc码标签为例。下面阐述跳跃式二进制树形算法的工作原理。1、算法建立的几点基础约定（1）跳跃式二进制树形反碰撞算法的关键是确定数据发生碰撞的具体位置。为了解决这一问题，标签数据采用曼彻斯特编码的副载波调制。该编码的特点是，在位持续时间内位值由电平的改变来表示。在半个比特周期时的负边沿表示二进制1，这时前半个比特周期含有

19、副载波信号；在半个比特周期中的正边沿表示二进制0，这时后半个比特周期含有副载波信号。当两个以上卡片将数据返回给终端时，由于返回的数据包含卡片的唯一epc码，所以一定会在同时返回的某一位上有不同的位值，这样就将正负边沿抵消了，在整个比特周期中，终端得到的是不间断的副载波信号，这样的波形信号终端将不能识别为0或1，终端认为在该数据位上发生了碰撞。如图2所示。图2 用曼彻斯特编码的标签返回数据能够被识别出碰撞位 其他的编码方式如crc检验码、奇偶校验码等也能够确定标签是否发生碰撞。但是这些编码方式只能检验是否发生了冲突，并不能准确地检测出碰撞发生在哪一位。则识读时只能采用轮询的方式进行，大大降低了识

20、别的效率。（2）为了便于算法执行的描述，定义两个命令call（epc，m）及sleep（epc，m）。其中call（epc，m）命令的含义为：读写器向覆盖范围内的标签发送召唤指令，如果标签epc码与call命令中epc参数的前m位相等，那么满足这个条件的epc标签作出应答，向读写器发送epc码，不满足条件的epc标签则处于空闲状态不作应答。这样做可以有效的缩小预选范围。特别地，在第一次call命令中epc00000000，m0，作用范围内的所有标签都做出应答。sleep(epc，m)的含义与call命令类似，如果标签epc码与sleep命令中epc参数的前m位相等，那么满足这个条件的epc标签

21、进入睡眠状态，再次收到call指令时不作应答。欲重新激活睡眠标签必须使得标签脱离读写器的作用范围才可奏效。2、算法原理下面以一个实例来直观的描述该算法的原理。设在某时刻有四个标签同时进入读写器的作用范围内，它们的epc码分别为epc110100011，epc210011011，epc300010001，epc411101100。如图3所示，其call命令的执行过程如下：（1）发送call（00000000,0）命令，epc1,epc2,epc3,epc4均做出应答。混叠的数据返回给读写器，由于此时各个位均有冲突，所以读写器识别为?。接下来算法将call命令中的epc的最高冲突位置为0，epc0

22、?，然后根据epc参数求出m，此时m1。同时算法将接收到的epc最高冲突位置为1，并保存在用于存储树形节点信息的lifo（last in first out）栈中。（2）发送call（0?,1）命令，此时只有epc3满足call命令的应答条件，作出应答。读写器收到的信息仅由epc3发出，不存在碰撞问题。读写器将epc3的epc码00010001存入ram中等候处理。然后发送sleep（00010001,8）命令，强制epc3进入睡眠状态。最后算法读出lifo栈中的节点信息，epc1?，求出m1。为下一次call命令做准备。（3）发送call（1?,1）命令，此时epc1,epc2,epc4满足

23、条件做出应答。读写器识别为1?，读写器接下来重复类似（1）中的操作，形成下一次call命令的参数epc10?，m=2.并将节点信息11?存入lifo栈中。（4）发送call（10?,2）命令，此时epc1,epc2满足条件做出应答。读写器识别为10?011，读写器将最高冲突位置0，形成下次call命令参数epc100?011，m3。将最高冲突位置1，作为节点信息保存在lifo栈中。开 始节点1epc3（00010001）节点2节点3epc4（11101100）epc2(10011011)epc1(10100011)(1) call(00000000,0)(2) call(0?,1)(3) ca

24、ll(1?,1)(4) call(10?,2)(5) call(100?011,3)(6) call(101?011,3)(7) call(11?,2)(?)(1?)(10?011)图3 跳跃式二进制树形反碰撞算法示意图（5）发送call（100?011,3）命令，此时只有epc2满足call命令的条件做出应答，读写器识别位10011011，不存在碰撞问题。读写器将epc2的epc码10011011存入ram中等候处理。然后发送sleep（10011011,8）命令，强制epc3进入睡眠状态。最后算法读出lifo栈中的节点信息，epc101?011，求出m3。为下一次call命令做准备。（6）

25、发送call（101?011,3）命令，此时只有epc1满足call命令的条件做出应答，读写器识别位10100011，不存在碰撞问题。读写器将epc1的epc码10100011存入ram中等候处理。然后发送sleep（10100011,8）命令，强制epc1进入睡眠状态。最后算法读出lifo栈中的节点信息，epc11?，求出m2。为下一次call命令做准备。（7）发送call（11?,2）命令，此时只有epc4满足call命令的条件做出应答，读写器识别位11101100，不存在碰撞问题。读写器将epc4的epc码11101100存入ram中等候处理。然后发送sleep（11101100,8）命

26、令，强制epc4进入睡眠状态。此时lifo栈为空，说明算法已经遍历了二进制树的每一个节点。至此整个反碰撞算法执行完毕，epc1、epc2、epc3、epc4的epc码已经被识别出来，并保存起来以便于读写器进行下一步操作。从以上的过程中可以看出，call命令的epc参数由碰撞位的判断得出，而call命令中的m参数又由相应的epc参数求得的，这样就使得算法在执行过程中跳过了空闲的节点，提高了算法的执行效率。又因为算法可以形象地用二进制树来描述，故称为“跳跃式二进制树形反碰撞算法”。3、效率分析对于形如图3所示的一个具有n个叶的二进制树，它的分支节点数目则为（n1），每个分支节点具有两个分支，总的分

27、支数目即为（2n2），再加上主干后数目为（2n1）。对于本算法的二进制树主干与分支的数目总合即为读写器发送call命令的次数，二进制树叶的数目即为标签的数目。从而可以得出这样的结论：分辨n个标签共需要（2n1）个call命令时隙。算法的效率公式为当n逐渐增大时算法的效率趋近于50。2. 1. 3 fpga实现算法的优越性进入到20世纪90年代以后，电子设计自动化（electronics design auto- mation,eda）技术的发展和普及给数字系统的设计带来了革命性的变化。在器件方面，可编程逻辑器件（programmable logic device,pld）的飞速发展。利用eda

28、工具，采用可编程逻辑器件，正在成为数字系统设计的主流。采用可编程逻辑器件通过对器件内部的设计来实现系统功能，是一种基于芯片的设计方法。设计者可以根据需要来定义器件的内部逻辑和引出端，将电路板设计的大部分工作放在芯片的设计中进行，通过对芯片设计实现数字逻辑的功能。灵活的内部功能块组合、引出端定义等，可大大减轻电路设计和电路板设计的工作量和难度，有效地增强设计的灵活性，提高工作效率。同时采用可编程逻辑器件，设计人员在实验室可以反复编程，修改错误，以便尽快开发产品，迅速占领市场。基于芯片的设计方法可以减少芯片的数量，缩小系统体积，降低功耗，提高系统性能和可靠性。相对于通用处理器而言，使用fpga实现

29、算法可以使得算法的执行速度大幅度的提高。通用处理器在执行软件算法的过程中，各种指令的调用占据了相当一部分时间，使得算法的执行效率大大降低，以至于在某些特定应用中不能满足所需要的处理速度，况且通用处理器平台价格高，体积较大。不具备良好的移动性，不适合作为小型终端的解决方案。在这种情况下用fpga来实现算法就成为了最好的解决方案之一。用fpga实现反碰撞算法首先要使用eda工具做出算法的设计输入工作，设计输入有原理图输入，hdl硬件描述语言输入等方法。算法完成设计输入后再对算法进行一系列的仿真工作，以达到与实际实现时高度吻合的仿真效果。仿真设计是数字系统设计中关键的一个环节。可以分为功能仿真和时序

30、仿真。功能仿真（function simulation）的作用是对源代码进行编译，检测在语法上是否正确，发现错误，并且提出出错的原因，设计者可以根据提示进行修改。编译通过后，仿真器再根据输入信号产生输出，进而来判断设计在功能上的正确性。如果不正确再返回修改，如此反复帮助纠正功能上的错误之处。功能仿真从理想的角度出发来验证功能的正确性，并不考虑网络及器件的延时。时序仿真则将器件和网络的延时考虑了进去，以用来模拟物理实现的运行状况。时序仿真可以达到非常准确的仿真效果。使得投片的成功率几乎达到100% 。像altera公司的quartusii集成开发环境，xilinx公司的ise集成开发环境都提供了

31、很好的仿真工具。另外软件还可以通过标准接口调用第三方仿真工具来进行辅助设计，例如可以通过著名的modelsim仿真软件来进行仿真等。可见使用fpga实现反碰撞算法具有速度快，成本低，小巧灵活等优点。2. 2 rfid系统反碰撞算法的实现在2.1中详尽地阐述了跳跃式二进制树形反碰撞算法的工作原理。在本章接下来的几节中将完成该算法的verilog hdl语言实现。现代的数字系统设计基本上采用自上而下的设计流程。首先对设计对象进行总体描述确定设计对象的行为模型；然后将设计对象进行细化，划分为更为基本的功能模块进行分别设计验证；最后将各个分立的功能模块组合起来形成整体的系统。在每一个功能模块的设计中又

32、分为如下的几个流程：（1）设计输入：对所设计的功能模块进行hdl语言描述或原理图描述；（2）设计编译：完成设计输入的逻辑综合，时序分析，将设计配置到器件中；（3）功能仿真：验证设计在功能上的正确性，不考虑器件的延时；（4）时序仿真：结合器件的延时特性，模拟实际物理器件的运行结果。下面就采取自上而下的设计流程来实现跳跃式二进制树形反碰撞算法的设计。2. 2. 1 rfid系统反碰撞算法总体设计方案由于rfid系统终端由读写器与标签共同组成，反碰撞算法的执行过程需要读写器与标签之间的数次信息交互来完成。所以算法的verilog hdl设计包含标签与读写器两个物理模块。关系如图4所示：epc标签模块

33、rfid读写器模块epc数据call，sleep等控制信号图4 标签与读写器示意图epc标签模块可以抽象为一个manchester编码器模块，rfid读写器内部包含着三个基本的功能模块：manchester解码器模块、lifo模块和控制整个算法的状态机模块。其最基本的模块连接关系如图5所示。算法的工作流程如下：（1）rfid读写器内部的状态机每隔一段时间发送一次call命令；（2）读写器有效范围内的标签收到call命令后判断是否满足call命令的条件，如果满足条件则发送epc码给读写器，如果不满足条件则不作反应； (3)读写器收到标签发来的数据进行manchester解码；如果没有碰撞发生则存

34、储epc码后强制该标签进入睡眠状态。如果产生碰撞则根据解出的数据和碰撞位标志进行下一次call命令。如此循环执行直到读写器范围内的所有标签被识别出来。其流程图如图6所示。mancheter编码器mancheter解码器算法控制状态机lifo控制信号1控制信号2控制信号3编码后epc数据解码后epc数据存取节点信息数据反馈信号rfid读写器图5 rfid反碰撞算法基本功能模块连接方式在接下来的内容中将分别对各个基本功能模块做详细的设计分析。复位是否有满足条件的标签发送call命令否标签发送epc码解码器解码是否发生碰撞保存epc码发送sleep命令将识别出的标签置为睡眠状态判断lifo是否为空读

35、取节点信息是保存节点信息生成call命令参数是否是否开始图6 跳跃式二进制树形反碰撞算法的流程图2. 2. 2 rfid标签模型的建立前面已经讲过rfid标签可以模型化为一个manchester编码器，它的主要数据输入包括该标签的epc码，call或sleep命令标志以及相应的epc参数和m参数。当接收到rfid读写器也就是算法控制状态机的控制信号后作出相应的判断，如果满足call命令的条件则开始对epc码进行manchester编码，编码完成后将编码后数据发送给manchester解码器，manchester解码器接收到数据后开始进行解码工作。如果满足sleep命令的条件，标签则进入睡眠状态

36、，对以后的call命令不作应答。其流程图如图7所示。开始call=1或sleep=1将输入数据存入寄存器中判断是否满足命令条件是否是判断call是否等于1是标签进入睡眠状态开始对epc做manchester编码向rfid读写器发送编码数据否否图7 rfid标签的工作流程图在manchester编码器模块中，最关键的一点就是对标签是否满足命令条件做出判断。其中需要注意的是当m0时一定满足命令条件。当m0时就需要比较epc码与命令参数epc的前m位是否相等，本设计中采用的方法是将epc码和epc参数同时右移（8m）位然后比较移位后的数据是否相等，如果相等则说明满足命令条件，开始进行manchest

37、er编码，否则命令条件不满足，标签不作任何动作。2. 2. 3 rfid读写器manchester解码及碰撞位判断模型manchester解码及碰撞位的判断是整个反碰撞算法的最关键部分。解码和碰撞位判断均由manchester解码器模块完成。当读写器范围内存在多个标签时，多个标签同时向读写器发送信息，manchester解码器接收到的是混叠在一起数据信号。对于没有碰撞的位，manchester码叠加在一起后其信号波形仍然反映明确的1或0数据，只需要按照正常的解码方式解码即可。然而对于发生碰撞的数位，原本携带数据信息的上升和下降相互抵消了，根据这一特点解码器便可以准确地定出碰撞位。但是我们知道f

38、pga中存储器只有0和1两个状态，所以存储解码数据的寄存器要么是0要么是1，无法自己表示出哪一位为碰撞位。这就要求伴随着解码数据寄存器，要有一个碰撞位标志寄存器来对碰撞位最出准确的标记。在本算法中标志寄存器中的1表示数据寄存器相应的位为冲突位，其数据为无效数据。如图6所示解码数据寄存器显示的数据是10101011，标志位寄存器为10100010，这表示解码数据寄存器的位7、位5和位1为碰撞位，其数据是无效数据。实际的解码结果为?0?010?1。解码数据寄存器碰撞位标志寄存器实际表示意义1101001000000111？0？010？1图8 解码数据与碰撞位的表示manchester解码器的工作流

39、程如图9所示。开 始接收rfid标签发送来的数据是否检测到编码的同步头是对每位编码的1/4，3/4处进行采样根据采样数据解出数据及碰撞位标志将解码数据及碰撞位标志发送给状态机否图9 manchester解码器工作流程图首先，manchester解码器模块中定义了一个两位的移位寄存器，用来检测标签发送的manchester码的同步头，以便判断出编码的到来。manchester编码信号manchester解码采样信号一旦移位寄存器检测到标签发送过来的信号的同步头，manchester解码器开始解码工作，解码的主要原理是：针对manchester编码的特点，使用高频时钟产生采样信号，图10 使用高频

40、时钟产生的采样信号对manchester码的1/4,3/4处进行采样对manchester编码信号位的1/4处和3/4处分别进行采样，如图7所示。如果采样的结果为（1，0）则解码数据为1，碰撞位标志为0；当采样的结果为（0，1）则解码数据为0，碰撞位标志为0；如果某数位有碰撞则采样的结果为（1，1），则解码数据记为0，碰撞位标志为1，说明该位解码数据为无效数据。开 始sample=（1，0）数据解码为1，碰撞位标志为0sample=（0，1）数据解码为0，碰撞位标志为0数据默认为0，碰撞位标志为1解码结束是否是否图11 manchester解码器解码关键点流程图采样信号的产生可以利用循环计数的

41、计数器来实现。该计数器在高频时钟的边沿到来时自动加1，其循环周期与manchester编码时钟周期相等。在与manchester编码位1/4，3/4处对应的计数器数值时令采样信号为高电平即可。当解码完成后解码器将向控制状态机发送一个data_ready脉冲信号，表明epc码已经解码完毕，可以向状态机传送数据。2. 2. 4 存储节点信息的lifo栈跳跃式二进制树形反碰撞算法之所以具有较高的效率是因为，算法在执行过程中跳过了完整二进制树的空闲节点。我们知道对于二进制树形结构每个分支节点会分出两个分支，当算法沿其中的一条分支进行时就需要记录下这个节点的信息，以便于在完成了这个分支的遍历后返回该节点

42、，然后沿另外的一条分支向下执行算法。idlewrite_readywritewrite_overread_readyreadread_overlifowr=1 & full=0liford=1 & empty=0lifowr=0liford=0reset图12 lifo栈的内部状态机在本跳跃式二进制树形算法当中，根据call命令的返回数据判断出树的节点，每到达一个节点时就记录下一个节点信息。当算法执行到一个叶的时候，也就是一个标签被识别出来的时候，算法将向上返回到最近的一个节点，也就是最后被记录下来的节点，然后走另外的一条分支。这说明节点信息的存取是一个后入先出的顺序，为满足这样的存取顺序就需

43、要用一个lifo（last in first out）栈来存储算法执行过程中所经过的节点的信息。为了协调lifo内部的工作状态，在lifo栈的模块中定义了一个小型的状态机，它具有图12所示的几个工作状态。工作状态的转换条件与流程已经在图12中表示了出来， 在lifo栈读写数据的时候首先要建立起数据地址，然后才能读写数据，且为了保证读写的可靠性，地址与数据都要持续一定的时间。其时序关系如图13所示。zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz1100100110100011首先建立读写地址然后给出读写数据t读写地址读写数据图13 lifo读写地址与读写数据建立的时序关系实际上

44、lifo栈是基于ram来建立的，但是其外部的存取特性表现为后入先出。lifo栈的读写地址是由读写指针指向的，当lifo进入相应的读写状态后将读写指针赋值给读写地址，因此lifo栈模块最关键的地方在于如何计算它的读写指针使其指向正确的存储单元。指针计算的程序流程图如图14所示。开始state=read或state=write否是state=write？是否lifo为空？wp=1；rp=0wp=wp+1rp=rp+1是否否lifo为空？是显示lifo已空不能读取lifo为满？wp=ram_size-1rp=ram_size-2否是lifo为满？显示lifo已满不能写入是wp=wp-1rp=rp-1

45、指针计算结束否图14 lifo站读写指针的计算流程图2. 2. 5 反碰撞算法状态机如前面所述，本文中的跳跃式二进制树形反碰撞算法的程序模块包括：manchester编码模块、manchester解码模块、用于存储节点信息的lifo栈模块和算法状态机。编码器模块、解码器模块和lifo栈模块在算法状态机的控制下协调工作。另外算法状态机模块还承担了处理解码数据生成call命令及sleep命令参数的任务。状态机与各个模块之间的关系如下：（1）状态机与编码模块：状态机通过内部的状态转换向编码模块发送call，sleep命令信号和epc及m参数。编码模块接收到call，sleep命令后开始工作。（2）状

46、态机与解码模块：状态机监测解码模块，当解码模块解码完成后向状态机发送一个data_ready信号，状态机接收到data_ready信号后，接收解码器发来的数据。（3）状态机与lifo模块：当状态机需要写入或读取节点信息时，会发送lifowr（写入控制信号）和liford（读取控制信号）信号给lifo栈，lifo栈接收到控制信号后首先建立起读写地址，然后进行读写数据的操作。状态机的状态转换关系如图15所示。状态机各个状态解析如下：（1）idle：空闲状态，所有寄存器复位。（2）call：发送call（epc，m）命令，下一时钟自动转入waiting状态。（3）waiting：等候解码器的data

47、_ready信号，如果接收到data_ready信号则转入receive状态，否则等候时间t后返回到call状态。（4）receive：接收来自解码器的解码数据和碰撞位标志。下一时钟自动转入write_ready状态。（5）write_ready：处理来自解码器的数据。根据解码器的解码数据和碰撞位标志求出m值，如果m=8，即无碰撞发生，则转入save_ready状态。如果m8，则计算出节点信息同时生成下一次call命令参数，然后转入write状态。（6）write：在此状态下将节点信息写入lifo栈。下一时钟自动转入write_over状态。idlecallwaitingreceivewrit

48、e_readywritewrite_overread_readyreadread_oversave_readysavesave_oversleep等待时间t后data_ready=1无碰撞发生lifo不为空lifo为空图15 状态机的状态转换关系（7）write_over：下一时钟自动转入call状态。（8）save_ready：准备保存解出的epc码，发送写入信号给保存epc码的ram。下一时钟转入save状态。（9）save：保存解出的epc码到ram中。（10）save_over：继续给出保存数据，以保证保存epc码的可靠性。下一时钟转入sleep状态。（11）sleep：发送sleep

49、命令，令已经被识别的标签进入睡眠状态。判断存储节点信息的lifo栈是否为空，如果lifo栈为空，下一时钟转入idle状态。如果lifo栈不为空，则下一时钟转入read_ready状态。（12）read_ready:发送读取命令给lifo栈，准备读取保存在lifo栈中的节点信息。下一时钟转入read状态。（13）read：读取lifo栈内保存的节点信息。下一时钟转入read_over状态。（14）read_over：根据读取的碰撞位标志求出m值，与读出的epc值一同作为下一次call命令的参数。下一时钟转入call状态。以上是算法控制状态机的具体实现。至此算法所需的各个功能模块均已经分别实现。2

50、. 2. 6 程序模块的连接编写好的各个功能模块需要相互连接起来组成一个功能完善的反碰撞算法模块。下面将介绍如何把编写好的各个功能模块连接为一个整体。verilog提供了较方便的模块连接方式，例如欲将模块m1的端口a与模块m2的端口b用wire型信号signal连接起来。其形式如下：wire signal；m1 （，.a(signal),）；m2 （，.b(signal),）；以三个标签为例，本算法各个模块间连接的verilog hdl语言描述如下：manchester_encoder me1(.clk(clk),.rst(rst),.call(call),.sleep(sleep),.tag

51、_epc(din1),.epc(epc),.m(m),.man_code(code1);manchester_encoder me2(.clk(clk),.rst(rst),.call(call),.sleep(sleep),.tag_epc(din2),.epc(epc),.m(m),.man_code(code2);manchester_encoder me3(.clk(clk),.rst(rst),.call(call),.sleep(sleep),.tag_epc(din3),.epc(epc),.m(m),.man_code(code3);or or_gate1(superposed

52、,code1,code2,code3);manchester_decoder md1(.clk(clk),.rst(rst),.call(call),.man_code(superposed),.data_ready(data_ready),.epc_out(epc1),.flag_out(flag1);state state1(.clk(clk),.rst(rst),.data_ready(data_ready),.empty1(empty1),.empty2(empty2),.epc_ready(epc_ready),.flag_ready(flag_ready),.epcin1(epc1

53、),.flagin1(flag1),.epcin2(epc2),.flagin2(flag2),.call(call),.sleep(sleep),.lifowr1(lifowr1),.liford1(liford1),.lifowr2(lifowr2),.liford2(liford2),.lifowr3(lifowr3),.epc_buffer(epc_buffer),.flag_buffer(flag_buffer),.epc(epc),.m(m);lifo lifo1(.clk(clk),.rst(rst),.lifowr(lifowr1),.liford(liford1),.din(

54、epc_buffer),.dout(epc2),.data_ready(epc_ready),.full(full1),.empty(empty1);lifo lifo2(.clk(clk),.rst(rst),.lifowr(lifowr2),.liford(liford2),.din(flag_buffer),.dout(flag2),.data_ready(flag_ready),.full(full2),.empty(empty2);lifo lifo3(.clk(clk),.rst(rst),.lifowr(lifowr3),.liford(readepc),.din(epc),.d

55、out(dout),.data_ready(dout_ready),.full(full3),.empty(empty3);连接好后，由quartusii生成的连接图如图16所示。本章中详细阐述了跳跃式二进制树形反碰撞算法的具体实现。分别对算法的各个功能模块进行了详细说明。最后将各个模块连接起来完成了整个算法的verilog hdl语言实现。在下一章中首先将分别对各个模块进行仿真和结果分析，最后对整个算法进行综合仿真，通过对结果的分析得出算法的主要性能指标。3rfid系统反碰撞算法的fpga仿真及分析本章将对第二章中实现的跳跃式二进制树形反碰撞算法进行fpga器件的计算机仿真，并对仿真结果进行

56、分析。首先分别对各个功能模块进行仿真和结果分析，然后进行算法的整体仿真和结果分析，最后根据仿真得到的数据评估算法的主要性能指标。计算机平台：处理器：pentium m 1.5 ghz ；内存：ddr333 512mb 。 操作系统：windows xp professional service pack 2。仿真工具：quartus ii 5.1 build 216 03/06/2006 sj full version。service pack 2 。 modelsim se plus 6.1b 。3. 1 仿真工具及所用fpga器件简介quartus ii 是altera的新一代设计开发软件，支持apex20k，apex ii，excalibur，mercury，stratix，cyclone，cyclone ii 等新器件系列。使用quartus ii 开发软件可以完成数字系统设计的全部流程，包括设计输入、项目编译、设计校验及器