南阳理工学院本科生毕业设计（论文）学院（系）：计算机与信息工程学院专业：通信工程学生：乔军惠指导教师：路新华完成日期 2012 年 4 月南阳理工学院本科毕业设计（论文）RFID二进制树防碰撞算法设计学院（系）：计算机与信息工程学院专业：通信工程学生姓名：乔军惠学号：104060820064指导教师（职称）：路新华（讲师）评阅教师：完成日期：2012年4月南阳理工学院Nanyang Institute of TechnologyRFID二进制树防碰撞算法设计【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。
随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。
在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。
在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID 系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。
【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列AbstractRFID is anewly developedtechnologywhich communicates through the—contact RF signal，so asto achieve objective automatic identification．Along with the development of RFID technology，how to realize Data Exchange accurately amongMultiple Targets at the same time becomes the key problem of RFID technology．RFID anti-collision algorithm is the solution to the above mentioned problems．In all the algorithms，binary algorithm is most widely used as an international standard fbr its exactness ofidentincation．International standards have put forward manyregulations on binary algorithm．It not onlypromotes the development of anti．coUision algorithm，but also b“ngs the conflict to a unilFied solution．Traditionalideas in general are handled byMCU．Along with the development ofRFID technology，an imponant direction in the f．uture is the field programmable gates arrayFPGA．As kindof integrated circuitsthatcanbe programmed in the field，FPGA is fast and programmable．All these adVantagesopenup anewef active way ofRFIDanti．collisionarithmetic．In viewof the above problems，this paperprobes into the RFID systembinary prevent collisionf．rom the perspectives ofboth theory and practice．It canbediVided into three aspects：6rstly，theoretical researchon binary algorithm．It sums up all thebinary algorithms in being and gather to three categorys suchas Basic algorithm，Dynamic algorithm and Backoff algorithm．MoreoVer，it Expounds the idea of the various algorithms and evalues their perf6rmance；secondary，it introduces an improved version of algorithm onthe basis of specinc standard．This algorithm has f．ast recognition，high efnciency and greatly improved the identification results．Key Words：RFID；Anticollision；Read／Write DeVices；Transponders；FPGA目录1 引言 (6)1．1RFID技术简介 (6)1．2RFID系统 (6)1．2．1 RFID系统组成 (6)1．2．2 RFID系统分类 (7)1．2．3 RFID系统工作原理 (8)1．3RFID技术现状及其发展 (8)1．3．1RFID技术应用 (8)1．3．2 RFID标准统一化 (9)1．3．3 RFID防碰撞算法 (9)1．4课题提出的背景及其意义 (9)1．5本文的主要工作 (10)2 现有RFID二进制树防碰撞算法 (11)2．1RFID防碰撞算法概述 (11)2．2RFID二进制树防碰撞算法概述 (11)2．2．1基本概念 (11)2．2．2性能指标 (12)2．2．3算法分类 (13)2．3基本二进制树防碰撞算法 (14)2．3．1算法思路 (14)2．3．2实例演示 (15)2．3．3性能评价 (17)2．4动态二进制树防碰撞算法 (19)2．4．1算法思路 (19)2．4．2实例演示 (21)2．4．3性能评价 (22)2．5退避式二进制树防碰撞算法 (22)2．5．1算法思路 (22)2．5．2实例演示 (24)2．5．3性能评价 (25)2．6本章小结 (25)3 改进型二进制树防碰撞算法 (25)3．1涉及二进制树算法的国际标准 (25)3．1．1 IS0 15693 (25)3．1．2 IS014443 (26)3．2IS014443标准二进制树防碰撞算法 (27)3．2．1基本概念 (27)3．2．2算法思路 (28)3．3改进型二进制树防碰撞算法 (32)3．3．1改进方向 (32)3．3．2基本概念 (32)3．3．4实例演示 (37)3．4本章小结 (39)4 FPGA实现改进型二进制树防碰撞算法 (40)4．1FPGA技术 (40)4．1．1 FPGA简介 (40)4．1．2 FPGA设计流程 (40)4．1．3 FPGA设计工具 (42)4．1．4 FPGA设计语言 (45)4．1．5 TestBench验证平台 (45)4．2RFID系统中的防碰撞模块 (46)4．3FPGA实现算法流程 (46)4．4曼彻斯特解码模块 (47)4．5命令处理模块 (50)4．5．1请求命令处理 (50)4．5．2防碰撞命令处理 (51)4．5．3选择命令处理 (53)4．5．4去选择命令处理 (53)4．6命令选择模块 (53)4．7数据存储模块 (55)4．8密勒编码模块 (56)4．9模块连接 (57)4．10本章小结 (58)结论 (58)致谢 (62)1 引言1．1 RFID技术简介自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为Automatic Equipment Identif ication，简称AEI，它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理【ll】。
目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领域的应用更具体的名称为射频识别，英文名为Radio Frequency Identification，简写为RFIDI21。
RFID技术通过射频方式进行非接触的双向通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与微波理论的发展，自从上世纪九十年代以来，RFID技术快速发展，得到了广泛的应用，进入新世纪后，各个国家，组织还有企业都加大了对RFID技术的投入，生产了大批相应的产品，在多个领域有了成功的应用案例。
RFID被誉为二十一世纪的十大战略性产业之一，可以预想，未来RFID技术的发展空间是无限广阔的。
1．2 RFID系统1．2．1 RFID系统组成根据实际应用环境，RFID系统结构有多种不同分法，一般来说，一个典型RFID系统包括三个部分：前端信息载体，数据交换环节，后端应用环境【3】。
在具体应用中，前端信息载体有多个名称，如标签(Tag)，智能标签(Smart Labels)，射频卡(RF Card)等，本文建议采用应答器(Transponder)这种更具普遍意义的说法。
在RFID系统中，应答器放置在待识别的物体上，它内部存储的信息表征着该物品的独一性。
通常来说，应答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存储器可将应答器分为EEPROM，FROM(铁电存储器)，SRAM(静态随机存储器)，根据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源供给方式分为无源，半无源，有源。