畢業(yè)設(shè)計(jì)（論文）跳躍式二進(jìn)制樹形系統(tǒng)反碰撞算法研究

1、121 國外相關(guān)研究狀況 rfid迅速發(fā)展的推動因素主要有兩個。第一是rfid芯片的生產(chǎn)開始形成規(guī)模，產(chǎn)品成本大幅下降。在不久的將來一個包括rfid芯片的電子標(biāo)簽極端最低成本可以達(dá)到12美分，甚至更低。第二，大宗零售業(yè)開始接受和應(yīng)用rfid技術(shù)，rfid正不斷贏得眾多大型用戶的注意。目前國際市場的需求主要來自于零售商。rfid的迅速發(fā)展，使得其標(biāo)準(zhǔn)的制定也日臻完善。目前國際上比較完善的rfid標(biāo)準(zhǔn)有三個：iso、歐美的epc global以及日本的ubiquitous id center。而這三個組織對rfid技術(shù)應(yīng)用規(guī)范都有各自的目標(biāo)與發(fā)展規(guī)劃。iso 14443和iso 15693標(biāo)準(zhǔn)在1

2、995年開始操作，其完成則是在2000年之后，二者皆以13.56mhz交變信號為載波頻率。iso 15693讀寫距離較遠(yuǎn)，而iso 14443讀寫距離稍近，但應(yīng)用較廣泛。美國運(yùn)通卡（american express）、萬事達(dá)卡（master card）和維薩卡（visa）公司在無線交易時均已采用了iso 14443標(biāo)準(zhǔn)。反碰撞算法技術(shù)是rfid的核心技術(shù)之一，這也是和接觸式ic卡的主要區(qū)別。基于標(biāo)準(zhǔn)中對防碰撞算法的規(guī)定，目前存在的防碰撞算法大致可分為三種：空分多路法（sdma），是在分離的空間范圍內(nèi)進(jìn)行多目標(biāo)識別的技術(shù)；頻分多路法（fdma），是把多個不同載波頻率作為多個傳輸通路供多個標(biāo)簽使用

3、的技術(shù)；時分多路法（tdma），把整個可供使用的通路容量按時間分片分配給多個用戶。iso 14443和iso 15693標(biāo)準(zhǔn)對防碰撞機(jī)制做出了規(guī)定。iso 15693采用輪尋機(jī)制、分時查詢的方式完成防沖撞機(jī)制。隨后推出的iso 14443標(biāo)準(zhǔn)解決了iso 15693標(biāo)準(zhǔn)的數(shù)據(jù)傳輸速度慢，無法處理大量加密數(shù)據(jù)的缺點(diǎn)，并在 iso 14443-3分別規(guī)定了type a和type b的防沖撞機(jī)制。二者防沖撞機(jī)制的原理不同，前者是基于位碰撞檢測協(xié)議，而type b利用通信系列命令序列完成防沖撞。其中a型卡的反碰撞機(jī)理如下：當(dāng)一個a型卡到達(dá)了讀寫器的作用范圍內(nèi)，并且有足夠的供應(yīng)電能，卡就開始執(zhí)行一些預(yù)置

4、的程序后，智能卡進(jìn)入閑置狀態(tài)。處于“閑置狀態(tài)”的智能卡不能對讀寫器傳輸給其它智能卡的數(shù)據(jù)起響應(yīng)。智能卡在“閑置狀態(tài)”接收到有效的reqa命令，則回送對請求的應(yīng)答字atqa。當(dāng)智能卡對reqa命令作了應(yīng)答后，智能卡處于ready狀態(tài)。讀寫器識別出：在作用范圍內(nèi)至少有一張智能卡存在。通過發(fā)送select命令啟動“二進(jìn)制檢索樹”防碰撞算法，選出一張智能卡，對其進(jìn)行操作。動態(tài)aloha算法是一種輪尋機(jī)制的算法。根據(jù)碰撞問題本身的數(shù)學(xué)特性而采用的一種rfid的防碰撞算法。它既沒有檢測機(jī)制也沒有恢復(fù)機(jī)制，只是通過某種數(shù)據(jù)編碼檢測沖突的存在，動態(tài)地調(diào)整個讀寫器的報警時間（讀取時間），從而達(dá)到將數(shù)據(jù)幀接收錯誤

5、率降低到所要求的程度，并同時對標(biāo)簽的數(shù)據(jù)吞吐率沒有損失。使用這種方法，應(yīng)答器和讀寫器都只要分別有傳輸和接收裝置就可以了，可大大降低成本。這種方法適用于只讀標(biāo)簽中，這類應(yīng)答器通常只有一些數(shù)據(jù)（序列號）傳輸給讀寫器，并且是周期地循環(huán)地將這些數(shù)據(jù)發(fā)給讀寫器的，它適用的場合有：超市對貨物的管理、圖書館對圖書的管理、動物園對動物的監(jiān)控等數(shù)據(jù)交換量不大、帶寬要求比較低的場合。現(xiàn)在已有的反碰撞算法有隨機(jī)問詢的aloha算法、分隙aloha算法，信息的最佳利用率分別為l84、368，但隨著標(biāo)簽數(shù)量的擴(kuò)大，性能將急劇惡化。122 我國相關(guān)的研究狀況2004年1月我國宣布成立跨部門小組研發(fā)rfid技術(shù)，以便在這項(xiàng)

6、新興技術(shù)上取得領(lǐng)先優(yōu)勢。在我國常用的rfid國際標(biāo)準(zhǔn)主要有用于動物識別的iso 11784和iso 11785，用于非接觸智能卡的iso 10536（close coupled cards）、iso 15693（vicinity cards）和iso 14443（pronimity cards），用于集裝箱識別的iso 10374等。1996年佛山市政府安裝了rfid系統(tǒng)用于自動收取路橋費(fèi)，明顯地提高車輛通過率，緩解公路瓶頸。車輛可以在250公里的時速下用少于0.5毫秒的時間被識別，并且正確率達(dá)99.95%。上海也安裝了基于rfid技術(shù)的自動收繳養(yǎng)路費(fèi)系統(tǒng)。廣州也已經(jīng)在開放的高速公路上用rfi

7、d系統(tǒng)對高速行駛的車輛進(jìn)行自動收費(fèi)。從2005年我國開始更新使用非接觸式的ic卡公民身份證，這將為我國rfid產(chǎn)業(yè)帶來一個巨大的潛在市場，積極地推動我國相關(guān)技術(shù)的發(fā)展。第二代電子身份證采用的標(biāo)準(zhǔn)是iso 14443 type b協(xié)議。iso 14443定義了type a、type b兩種類型協(xié)議，通信速率為106kbit/s，它們的不同主要在于載波的調(diào)制深度及位的編碼方式。type a采用開關(guān)鍵控（on-off keying）的曼徹斯特編碼，type b采用nrz-l的bpsk編碼。type b與type a相比，具有傳輸能量不中斷、速率更高、抗干擾能力列強(qiáng)的優(yōu)點(diǎn)。防沖撞機(jī)制使得同時處于讀寫區(qū)

8、內(nèi)的多張卡的正確操作成為可能，大大提高了操作速度。作為rfid系統(tǒng)關(guān)鍵的反碰撞算法，我國也已經(jīng)有很多學(xué)者進(jìn)行了相關(guān)的研究。發(fā)表了很多有關(guān)反碰撞算法的學(xué)術(shù)論文，對一些系統(tǒng)反碰撞算法作了原理闡述并完成了算法的實(shí)現(xiàn)。例如aloha隨機(jī)推遲系統(tǒng)反碰撞算法、符合iso 14443 type a標(biāo)準(zhǔn)的二進(jìn)制樹形搜索算法等。13 論文研究內(nèi)容及結(jié)構(gòu)安排本論文著重研究了rfid系統(tǒng)的反碰撞算法，介紹一種快速高效的rfid系統(tǒng)反碰撞算法跳躍式二進(jìn)制樹形算法，并利用verilog hdl語言對算法進(jìn)行了設(shè)計(jì)同時利用fpga器件進(jìn)行了計(jì)算機(jī)仿真。在第一章中，主要介紹了課題的研究背景和研究意義，并介紹了國內(nèi)外相關(guān)的研

9、究現(xiàn)狀。作為基礎(chǔ)知識準(zhǔn)備，本文在第二章首先介紹了一些相關(guān)的基礎(chǔ)知識，其中包括：rfid系統(tǒng)的結(jié)構(gòu)與工作原理，跳躍式二進(jìn)制樹形反碰撞算法原理闡述，以及fpga的相關(guān)基礎(chǔ)知識等。同時在第二章中詳細(xì)介紹了rfid系統(tǒng)反碰撞算法的實(shí)現(xiàn)，包括：rfid系統(tǒng)反碰撞算法總體設(shè)計(jì)方案；rfid標(biāo)簽verilog hdl模型的建立；rfid讀寫器manchester解碼及碰撞位判斷模型的建立；樹形節(jié)點(diǎn)信息處理與lifo棧模型；反碰撞算法狀態(tài)機(jī)的實(shí)現(xiàn)。在第三章中對反碰撞算法進(jìn)行了系統(tǒng)的仿真并對仿真結(jié)果進(jìn)行了詳細(xì)分析，同時給出該算法的主要性能指標(biāo)。在仿真的過程中采用先分立后綜合的方式，先對各個分立的模塊進(jìn)行仿真，最

10、后將各個模塊組合起來進(jìn)行綜合仿真，然后根據(jù)得到的仿真數(shù)據(jù)直觀地反映算法的各項(xiàng)性能參數(shù)。具體內(nèi)容包括：標(biāo)簽的仿真結(jié)果及其分析；讀寫器manchester解碼及碰撞位判斷的仿真結(jié)果及分析；用于存儲樹形節(jié)點(diǎn)信息的lifo棧仿真結(jié)果及分析；rfid系統(tǒng)反碰撞算法的綜合仿真結(jié)果；rfid系統(tǒng)反碰撞算法的性能分析。 最后在第四章對本文進(jìn)行了總結(jié)。2 rfid系統(tǒng)防碰撞算法設(shè)計(jì)21 rfid系統(tǒng)與反碰撞算法211 rfid的系統(tǒng)結(jié)構(gòu)與工作原理無線射頻識別系統(tǒng)rfid（radio frequency identification system），一般由rfid標(biāo)簽、rfid讀寫器以及計(jì)算機(jī)系統(tǒng)組成，如圖1所示

11、。系統(tǒng)基本工作原理如下：rfid標(biāo)簽進(jìn)入磁場，接收rfid讀寫器發(fā)出的射頻信號，憑借感應(yīng)電流所獲得的能量發(fā)送出存儲在芯片中的產(chǎn)品信息（無源標(biāo)簽）或者主動發(fā)送某一頻率的信號（有源標(biāo)簽），rfid讀寫器讀取信息后，解碼，送至計(jì)算機(jī)系統(tǒng)對有關(guān)數(shù)據(jù)進(jìn)行處理。圖1 rfid的基本結(jié)構(gòu)組成下面對rfid的系統(tǒng)結(jié)構(gòu)以及工作原理做較詳細(xì)的說明。1、rfid系統(tǒng)基本結(jié)構(gòu)（1）rfid標(biāo)簽rfid標(biāo)簽由耦合元件及芯片組成，每個標(biāo)簽具有惟一的電子編碼，附著在物體目標(biāo)對象上。電子標(biāo)簽像紙一樣薄, 柔韌可彎曲并可編程，射頻標(biāo)簽內(nèi)編寫的程序可按特殊的應(yīng)用進(jìn)行隨時讀取和改寫。射頻標(biāo)簽也可編入相應(yīng)人員的一些數(shù)據(jù)信息，這些人員

12、的數(shù)據(jù)信息可依據(jù)需要進(jìn)行分類管理，并可隨不同的需要制作新卡，射頻標(biāo)簽中的內(nèi)容被改寫的同時也可以被永久鎖死保護(hù)起來。通常標(biāo)簽芯片體積很小，厚度一般不超過0.35mm，可以印制在紙張、塑料、木材、玻璃、紡織品等包裝材料上，也可以直接制作在商品標(biāo)簽上，通過自動貼標(biāo)簽機(jī)進(jìn)行自動貼標(biāo)。 從能量方面來看，標(biāo)簽可以分為兩種：無源標(biāo)簽和有源標(biāo)簽。無源標(biāo)簽自身不帶有電源，當(dāng)讀取裝置對標(biāo)簽進(jìn)行讀取時，所發(fā)射出的無線電接觸到rfid標(biāo)簽的天線后產(chǎn)生電量。它的重量輕、體積小，壽命可以很長，但是發(fā)射距離受限。有源標(biāo)簽使用卡內(nèi)的電池能量，識別的距離長，但是它的價格較高且壽命短。 從功能方面來看，可將rfid標(biāo)簽分為四種：

13、只讀標(biāo)簽、可重寫標(biāo)簽、帶微處理器標(biāo)簽和配有傳感器的標(biāo)簽。只讀型標(biāo)簽的結(jié)構(gòu)功能最簡單，包含的信息較少并且不能被更改；可重寫型標(biāo)簽集成了容量為幾十字節(jié)到幾萬個字節(jié)的閃存，標(biāo)簽內(nèi)的信息能被更改或重寫，只讀型和可重寫型標(biāo)簽都主要應(yīng)用于物流系統(tǒng)以及生產(chǎn)過程管理系統(tǒng)和行李控制系統(tǒng)中；帶微處理器標(biāo)簽依靠內(nèi)置式只讀存儲器中儲存的操作系統(tǒng)和程序來工作，出于安全的目的，許多標(biāo)簽都同時具備加密電路，現(xiàn)在這類標(biāo)簽主要應(yīng)用于非接觸型ic卡上，既用于電子結(jié)算、出入管理，也可用作會員卡；有些rfid標(biāo)簽集成了傳感器，包括溫度傳感器或壓力傳感器等，目前這類標(biāo)簽主要用于動物個體識別和輪胎管理上。按調(diào)制方式來分，電子標(biāo)簽還可分為

14、主動式標(biāo)簽和被動式標(biāo)簽。主動式標(biāo)簽用自身的射頻能量主動地發(fā)送數(shù)據(jù)給讀寫器，主要用于有障礙物的應(yīng)用中；被動式標(biāo)簽使用調(diào)制散射方式發(fā)射數(shù)據(jù)，它必須利用讀寫器的載波來調(diào)制自己的信號，在門禁或交通的應(yīng)用中較適宜。（2）rfid讀寫器讀寫器是負(fù)責(zé)讀取或?qū)懭霕?biāo)簽信息的設(shè)備，讀寫器可以是單獨(dú)的整體，也可以作為部件的形式嵌入到其他系統(tǒng)中去。它可以單獨(dú)具有讀寫、顯示、數(shù)據(jù)處理等功能，也可與計(jì)算機(jī)或其他系統(tǒng)進(jìn)行聯(lián)合，完成對射頻標(biāo)簽的操作。讀寫器由兩個基本的功能塊組成：控制系統(tǒng)和由發(fā)送器及接收器組成的高頻接口。讀寫器高頻接口的功能包括：產(chǎn)生高頻的發(fā)射功率，為啟動電子標(biāo)簽提供能量；對發(fā)射信號進(jìn)行調(diào)制將數(shù)據(jù)傳送給電子標(biāo)

15、簽；接收并解調(diào)來自電子標(biāo)簽的高頻信號。讀寫器控制單元的功能包括：與應(yīng)用軟件進(jìn)行通信，并執(zhí)行應(yīng)用系統(tǒng)軟件發(fā)來的命令；控制與電子標(biāo)簽的通信過程；信號的編碼與解碼。在一些復(fù)雜的系統(tǒng)中，控制單元還要執(zhí)行反碰撞算法，同時對電子標(biāo)簽與讀寫器之間要傳送的數(shù)據(jù)進(jìn)行加密和解密，并且進(jìn)行電子標(biāo)簽和讀寫器之間的身份驗(yàn)證。讀寫器可將主機(jī)的讀寫命令傳到電子標(biāo)簽，再把從主機(jī)發(fā)往電子標(biāo)簽的數(shù)據(jù)加密，將電子標(biāo)簽返回的數(shù)據(jù)解密后送到主機(jī)。讀寫器將要發(fā)送的信號，經(jīng)編碼后加載在特定頻率的載波信號上經(jīng)天線向外發(fā)送，進(jìn)入讀寫器工作區(qū)域的電子標(biāo)簽接收此脈沖信號，然后標(biāo)簽內(nèi)芯片中的有關(guān)電路對此信號進(jìn)行調(diào)制、解碼、解密，然后對命令請求、密碼

16、、權(quán)限等進(jìn)行判斷。若為讀取命令，控制邏輯電路則從存儲器中讀取有關(guān)信息，經(jīng)加密、編碼后經(jīng)標(biāo)簽內(nèi)的天線發(fā)送給讀寫器，讀寫器對接收到的信號進(jìn)行解調(diào)、解碼、解密后送至計(jì)算機(jī)處理;若是修改信息的寫入命令，有關(guān)控制邏輯引起的內(nèi)部電荷泵提升工作電壓，對標(biāo)簽中的內(nèi)容進(jìn)行改寫。（3）計(jì)算機(jī)信息系統(tǒng)計(jì)算機(jī)信息系統(tǒng)主要完成數(shù)據(jù)信息的存儲及管理、對卡進(jìn)行讀寫控制，數(shù)據(jù)管理系統(tǒng)可以是市面上現(xiàn)有的各種大小不一的數(shù)據(jù)庫或供應(yīng)鏈系統(tǒng)，用戶還能夠買到面向特定行業(yè)的高度專業(yè)化的庫存數(shù)據(jù)庫，或者把rfid系統(tǒng)當(dāng)成整個企業(yè)erp的一部分。如果應(yīng)用情況比較特殊，甚至可以自己動手編寫數(shù)據(jù)庫應(yīng)用軟件，采用pc機(jī)或者是終端機(jī)來完成。2、rf

17、id系統(tǒng)工作原理絕大多數(shù)射頻識別系統(tǒng)是按電感耦合的原理工作的，讀寫器在數(shù)據(jù)管理系統(tǒng)的控制下發(fā)送出一定頻率的射頻信號，當(dāng)電子標(biāo)簽進(jìn)入磁場時產(chǎn)生感應(yīng)電流從而獲得能量，發(fā)送出自身編碼等信息，該信息被讀寫器讀取并解碼后送至管理系統(tǒng)（一般是電腦主機(jī)）進(jìn)行有關(guān)處理，這一信息的收集處理過程是以無線方式進(jìn)行的。212 跳躍式二進(jìn)制樹形反碰撞算法原理在射頻識別系統(tǒng)中，不能排除在讀寫器范圍內(nèi)存在多個電子標(biāo)簽的情況，于是系統(tǒng)中存在兩種通信形式：從讀寫器到電子標(biāo)簽的數(shù)據(jù)傳輸，即讀寫器發(fā)送的數(shù)據(jù)流被覆蓋范圍內(nèi)的多個標(biāo)簽所接收，這種通信形式也被稱為無線電廣播；在讀寫器的作用范圍內(nèi)有多個標(biāo)簽同時應(yīng)答，這種形式被稱為多路存取

18、。在后一種通信形式中，標(biāo)簽數(shù)據(jù)的混疊問題就是我們所說的碰撞問題。為了防止由于多個電子標(biāo)簽的數(shù)據(jù)在讀寫器的接收機(jī)中相互碰撞而不能準(zhǔn)確讀出，必須采用反碰撞算法來加以克服。本文中設(shè)計(jì)的跳躍式二進(jìn)制樹形算法屬于時分多路的復(fù)用方式。文中闡述算法原理及算法設(shè)計(jì)仿真的過程中標(biāo)簽均以簡化的8位epc碼標(biāo)簽為例。下面闡述跳躍式二進(jìn)制樹形算法的工作原理。1、算法建立的幾點(diǎn)基礎(chǔ)約定（1）跳躍式二進(jìn)制樹形反碰撞算法的關(guān)鍵是確定數(shù)據(jù)發(fā)生碰撞的具體位置。為了解決這一問題，標(biāo)簽數(shù)據(jù)采用曼徹斯特編碼的副載波調(diào)制。該編碼的特點(diǎn)是，在位持續(xù)時間內(nèi)位值由電平的改變來表示。在半個比特周期時的負(fù)邊沿表示二進(jìn)制1，這時前半個比特周期含有

19、副載波信號；在半個比特周期中的正邊沿表示二進(jìn)制0，這時后半個比特周期含有副載波信號。當(dāng)兩個以上卡片將數(shù)據(jù)返回給終端時，由于返回的數(shù)據(jù)包含卡片的唯一epc碼，所以一定會在同時返回的某一位上有不同的位值，這樣就將正負(fù)邊沿抵消了，在整個比特周期中，終端得到的是不間斷的副載波信號，這樣的波形信號終端將不能識別為0或1，終端認(rèn)為在該數(shù)據(jù)位上發(fā)生了碰撞。如圖2所示。圖2 用曼徹斯特編碼的標(biāo)簽返回?cái)?shù)據(jù)能夠被識別出碰撞位 其他的編碼方式如crc檢驗(yàn)碼、奇偶校驗(yàn)碼等也能夠確定標(biāo)簽是否發(fā)生碰撞。但是這些編碼方式只能檢驗(yàn)是否發(fā)生了沖突，并不能準(zhǔn)確地檢測出碰撞發(fā)生在哪一位。則識讀時只能采用輪詢的方式進(jìn)行，大大降低了識

20、別的效率。（2）為了便于算法執(zhí)行的描述，定義兩個命令call（epc，m）及sleep（epc，m）。其中call（epc，m）命令的含義為：讀寫器向覆蓋范圍內(nèi)的標(biāo)簽發(fā)送召喚指令，如果標(biāo)簽epc碼與call命令中epc參數(shù)的前m位相等，那么滿足這個條件的epc標(biāo)簽作出應(yīng)答，向讀寫器發(fā)送epc碼，不滿足條件的epc標(biāo)簽則處于空閑狀態(tài)不作應(yīng)答。這樣做可以有效的縮小預(yù)選范圍。特別地，在第一次call命令中epc00000000，m0，作用范圍內(nèi)的所有標(biāo)簽都做出應(yīng)答。sleep(epc，m)的含義與call命令類似，如果標(biāo)簽epc碼與sleep命令中epc參數(shù)的前m位相等，那么滿足這個條件的epc標(biāo)簽

21、進(jìn)入睡眠狀態(tài)，再次收到call指令時不作應(yīng)答。欲重新激活睡眠標(biāo)簽必須使得標(biāo)簽脫離讀寫器的作用范圍才可奏效。2、算法原理下面以一個實(shí)例來直觀的描述該算法的原理。設(shè)在某時刻有四個標(biāo)簽同時進(jìn)入讀寫器的作用范圍內(nèi)，它們的epc碼分別為epc110100011，epc210011011，epc300010001，epc411101100。如圖3所示，其call命令的執(zhí)行過程如下：（1）發(fā)送call（00000000,0）命令，epc1,epc2,epc3,epc4均做出應(yīng)答?；殳B的數(shù)據(jù)返回給讀寫器，由于此時各個位均有沖突，所以讀寫器識別為?。接下來算法將call命令中的epc的最高沖突位置為0，epc0

22、?，然后根據(jù)epc參數(shù)求出m，此時m1。同時算法將接收到的epc最高沖突位置為1，并保存在用于存儲樹形節(jié)點(diǎn)信息的lifo（last in first out）棧中。（2）發(fā)送call（0?,1）命令，此時只有epc3滿足call命令的應(yīng)答條件，作出應(yīng)答。讀寫器收到的信息僅由epc3發(fā)出，不存在碰撞問題。讀寫器將epc3的epc碼00010001存入ram中等候處理。然后發(fā)送sleep（00010001,8）命令，強(qiáng)制epc3進(jìn)入睡眠狀態(tài)。最后算法讀出lifo棧中的節(jié)點(diǎn)信息，epc1?，求出m1。為下一次call命令做準(zhǔn)備。（3）發(fā)送call（1?,1）命令，此時epc1,epc2,epc4滿足

23、條件做出應(yīng)答。讀寫器識別為1?，讀寫器接下來重復(fù)類似（1）中的操作，形成下一次call命令的參數(shù)epc10?，m=2.并將節(jié)點(diǎn)信息11?存入lifo棧中。（4）發(fā)送call（10?,2）命令，此時epc1,epc2滿足條件做出應(yīng)答。讀寫器識別為10?011，讀寫器將最高沖突位置0，形成下次call命令參數(shù)epc100?011，m3。將最高沖突位置1，作為節(jié)點(diǎn)信息保存在lifo棧中。開 始節(jié)點(diǎn)1epc3（00010001）節(jié)點(diǎn)2節(jié)點(diǎn)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 跳躍式二進(jìn)制樹形反碰撞算法示意圖（5）發(fā)送call（100?011,3）命令，此時只有epc2滿足call命令的條件做出應(yīng)答，讀寫器識別位10011011，不存在碰撞問題。讀寫器將epc2的epc碼10011011存入ram中等候處理。然后發(fā)送sleep（10011011,8）命令，強(qiáng)制epc3進(jìn)入睡眠狀態(tài)。最后算法讀出lifo棧中的節(jié)點(diǎn)信息，epc101?011，求出m3。為下一次call命令做準(zhǔn)備。（6）

25、發(fā)送call（101?011,3）命令，此時只有epc1滿足call命令的條件做出應(yīng)答，讀寫器識別位10100011，不存在碰撞問題。讀寫器將epc1的epc碼10100011存入ram中等候處理。然后發(fā)送sleep（10100011,8）命令，強(qiáng)制epc1進(jìn)入睡眠狀態(tài)。最后算法讀出lifo棧中的節(jié)點(diǎn)信息，epc11?，求出m2。為下一次call命令做準(zhǔn)備。（7）發(fā)送call（11?,2）命令，此時只有epc4滿足call命令的條件做出應(yīng)答，讀寫器識別位11101100，不存在碰撞問題。讀寫器將epc4的epc碼11101100存入ram中等候處理。然后發(fā)送sleep（11101100,8）命

26、令，強(qiáng)制epc4進(jìn)入睡眠狀態(tài)。此時lifo棧為空，說明算法已經(jīng)遍歷了二進(jìn)制樹的每一個節(jié)點(diǎn)。至此整個反碰撞算法執(zhí)行完畢，epc1、epc2、epc3、epc4的epc碼已經(jīng)被識別出來，并保存起來以便于讀寫器進(jìn)行下一步操作。從以上的過程中可以看出，call命令的epc參數(shù)由碰撞位的判斷得出，而call命令中的m參數(shù)又由相應(yīng)的epc參數(shù)求得的，這樣就使得算法在執(zhí)行過程中跳過了空閑的節(jié)點(diǎn)，提高了算法的執(zhí)行效率。又因?yàn)樗惴梢孕蜗蟮赜枚M(jìn)制樹來描述，故稱為“跳躍式二進(jìn)制樹形反碰撞算法”。3、效率分析對于形如圖3所示的一個具有n個葉的二進(jìn)制樹，它的分支節(jié)點(diǎn)數(shù)目則為（n1），每個分支節(jié)點(diǎn)具有兩個分支，總的分

27、支數(shù)目即為（2n2），再加上主干后數(shù)目為（2n1）。對于本算法的二進(jìn)制樹主干與分支的數(shù)目總合即為讀寫器發(fā)送call命令的次數(shù)，二進(jìn)制樹葉的數(shù)目即為標(biāo)簽的數(shù)目。從而可以得出這樣的結(jié)論：分辨n個標(biāo)簽共需要（2n1）個call命令時隙。算法的效率公式為當(dāng)n逐漸增大時算法的效率趨近于50。2. 1. 3 fpga實(shí)現(xiàn)算法的優(yōu)越性進(jìn)入到20世紀(jì)90年代以后，電子設(shè)計(jì)自動化（electronics design auto- mation,eda）技術(shù)的發(fā)展和普及給數(shù)字系統(tǒng)的設(shè)計(jì)帶來了革命性的變化。在器件方面，可編程邏輯器件（programmable logic device,pld）的飛速發(fā)展。利用eda

28、工具，采用可編程邏輯器件，正在成為數(shù)字系統(tǒng)設(shè)計(jì)的主流。采用可編程邏輯器件通過對器件內(nèi)部的設(shè)計(jì)來實(shí)現(xiàn)系統(tǒng)功能，是一種基于芯片的設(shè)計(jì)方法。設(shè)計(jì)者可以根據(jù)需要來定義器件的內(nèi)部邏輯和引出端，將電路板設(shè)計(jì)的大部分工作放在芯片的設(shè)計(jì)中進(jìn)行，通過對芯片設(shè)計(jì)實(shí)現(xiàn)數(shù)字邏輯的功能。靈活的內(nèi)部功能塊組合、引出端定義等，可大大減輕電路設(shè)計(jì)和電路板設(shè)計(jì)的工作量和難度，有效地增強(qiáng)設(shè)計(jì)的靈活性，提高工作效率。同時采用可編程邏輯器件，設(shè)計(jì)人員在實(shí)驗(yàn)室可以反復(fù)編程，修改錯誤，以便盡快開發(fā)產(chǎn)品，迅速占領(lǐng)市場?；谛酒脑O(shè)計(jì)方法可以減少芯片的數(shù)量，縮小系統(tǒng)體積，降低功耗，提高系統(tǒng)性能和可靠性。相對于通用處理器而言，使用fpga實(shí)現(xiàn)

29、算法可以使得算法的執(zhí)行速度大幅度的提高。通用處理器在執(zhí)行軟件算法的過程中，各種指令的調(diào)用占據(jù)了相當(dāng)一部分時間，使得算法的執(zhí)行效率大大降低，以至于在某些特定應(yīng)用中不能滿足所需要的處理速度，況且通用處理器平臺價格高，體積較大。不具備良好的移動性，不適合作為小型終端的解決方案。在這種情況下用fpga來實(shí)現(xiàn)算法就成為了最好的解決方案之一。用fpga實(shí)現(xiàn)反碰撞算法首先要使用eda工具做出算法的設(shè)計(jì)輸入工作，設(shè)計(jì)輸入有原理圖輸入，hdl硬件描述語言輸入等方法。算法完成設(shè)計(jì)輸入后再對算法進(jìn)行一系列的仿真工作，以達(dá)到與實(shí)際實(shí)現(xiàn)時高度吻合的仿真效果。仿真設(shè)計(jì)是數(shù)字系統(tǒng)設(shè)計(jì)中關(guān)鍵的一個環(huán)節(jié)?？梢苑譃楣δ芊抡婧蜁r序

30、仿真。功能仿真（function simulation）的作用是對源代碼進(jìn)行編譯，檢測在語法上是否正確，發(fā)現(xiàn)錯誤，并且提出出錯的原因，設(shè)計(jì)者可以根據(jù)提示進(jìn)行修改。編譯通過后，仿真器再根據(jù)輸入信號產(chǎn)生輸出，進(jìn)而來判斷設(shè)計(jì)在功能上的正確性。如果不正確再返回修改，如此反復(fù)幫助糾正功能上的錯誤之處。功能仿真從理想的角度出發(fā)來驗(yàn)證功能的正確性，并不考慮網(wǎng)絡(luò)及器件的延時。時序仿真則將器件和網(wǎng)絡(luò)的延時考慮了進(jìn)去，以用來模擬物理實(shí)現(xiàn)的運(yùn)行狀況。時序仿真可以達(dá)到非常準(zhǔn)確的仿真效果。使得投片的成功率幾乎達(dá)到100% 。像altera公司的quartusii集成開發(fā)環(huán)境，xilinx公司的ise集成開發(fā)環(huán)境都提供了

31、很好的仿真工具。另外軟件還可以通過標(biāo)準(zhǔn)接口調(diào)用第三方仿真工具來進(jìn)行輔助設(shè)計(jì)，例如可以通過著名的modelsim仿真軟件來進(jìn)行仿真等。可見使用fpga實(shí)現(xiàn)反碰撞算法具有速度快，成本低，小巧靈活等優(yōu)點(diǎn)。2. 2 rfid系統(tǒng)反碰撞算法的實(shí)現(xiàn)在2.1中詳盡地闡述了跳躍式二進(jìn)制樹形反碰撞算法的工作原理。在本章接下來的幾節(jié)中將完成該算法的verilog hdl語言實(shí)現(xiàn)。現(xiàn)代的數(shù)字系統(tǒng)設(shè)計(jì)基本上采用自上而下的設(shè)計(jì)流程。首先對設(shè)計(jì)對象進(jìn)行總體描述確定設(shè)計(jì)對象的行為模型；然后將設(shè)計(jì)對象進(jìn)行細(xì)化，劃分為更為基本的功能模塊進(jìn)行分別設(shè)計(jì)驗(yàn)證；最后將各個分立的功能模塊組合起來形成整體的系統(tǒng)。在每一個功能模塊的設(shè)計(jì)中又

32、分為如下的幾個流程：（1）設(shè)計(jì)輸入：對所設(shè)計(jì)的功能模塊進(jìn)行hdl語言描述或原理圖描述；（2）設(shè)計(jì)編譯：完成設(shè)計(jì)輸入的邏輯綜合，時序分析，將設(shè)計(jì)配置到器件中；（3）功能仿真：驗(yàn)證設(shè)計(jì)在功能上的正確性，不考慮器件的延時；（4）時序仿真：結(jié)合器件的延時特性，模擬實(shí)際物理器件的運(yùn)行結(jié)果。下面就采取自上而下的設(shè)計(jì)流程來實(shí)現(xiàn)跳躍式二進(jìn)制樹形反碰撞算法的設(shè)計(jì)。2. 2. 1 rfid系統(tǒng)反碰撞算法總體設(shè)計(jì)方案由于rfid系統(tǒng)終端由讀寫器與標(biāo)簽共同組成，反碰撞算法的執(zhí)行過程需要讀寫器與標(biāo)簽之間的數(shù)次信息交互來完成。所以算法的verilog hdl設(shè)計(jì)包含標(biāo)簽與讀寫器兩個物理模塊。關(guān)系如圖4所示：epc標(biāo)簽?zāi)K

33、rfid讀寫器模塊epc數(shù)據(jù)call，sleep等控制信號圖4 標(biāo)簽與讀寫器示意圖epc標(biāo)簽?zāi)K可以抽象為一個manchester編碼器模塊，rfid讀寫器內(nèi)部包含著三個基本的功能模塊：manchester解碼器模塊、lifo模塊和控制整個算法的狀態(tài)機(jī)模塊。其最基本的模塊連接關(guān)系如圖5所示。算法的工作流程如下：（1）rfid讀寫器內(nèi)部的狀態(tài)機(jī)每隔一段時間發(fā)送一次call命令；（2）讀寫器有效范圍內(nèi)的標(biāo)簽收到call命令后判斷是否滿足call命令的條件，如果滿足條件則發(fā)送epc碼給讀寫器，如果不滿足條件則不作反應(yīng)； (3)讀寫器收到標(biāo)簽發(fā)來的數(shù)據(jù)進(jìn)行manchester解碼；如果沒有碰撞發(fā)生則存

34、儲epc碼后強(qiáng)制該標(biāo)簽進(jìn)入睡眠狀態(tài)。如果產(chǎn)生碰撞則根據(jù)解出的數(shù)據(jù)和碰撞位標(biāo)志進(jìn)行下一次call命令。如此循環(huán)執(zhí)行直到讀寫器范圍內(nèi)的所有標(biāo)簽被識別出來。其流程圖如圖6所示。mancheter編碼器mancheter解碼器算法控制狀態(tài)機(jī)lifo控制信號1控制信號2控制信號3編碼后epc數(shù)據(jù)解碼后epc數(shù)據(jù)存取節(jié)點(diǎn)信息數(shù)據(jù)反饋信號rfid讀寫器圖5 rfid反碰撞算法基本功能模塊連接方式在接下來的內(nèi)容中將分別對各個基本功能模塊做詳細(xì)的設(shè)計(jì)分析。復(fù)位是否有滿足條件的標(biāo)簽發(fā)送call命令否標(biāo)簽發(fā)送epc碼解碼器解碼是否發(fā)生碰撞保存epc碼發(fā)送sleep命令將識別出的標(biāo)簽置為睡眠狀態(tài)判斷l(xiāng)ifo是否為空讀

35、取節(jié)點(diǎn)信息是保存節(jié)點(diǎn)信息生成call命令參數(shù)是否是否開始圖6 跳躍式二進(jìn)制樹形反碰撞算法的流程圖2. 2. 2 rfid標(biāo)簽?zāi)Ｐ偷慕⑶懊嬉呀?jīng)講過rfid標(biāo)簽可以模型化為一個manchester編碼器，它的主要數(shù)據(jù)輸入包括該標(biāo)簽的epc碼，call或sleep命令標(biāo)志以及相應(yīng)的epc參數(shù)和m參數(shù)。當(dāng)接收到rfid讀寫器也就是算法控制狀態(tài)機(jī)的控制信號后作出相應(yīng)的判斷，如果滿足call命令的條件則開始對epc碼進(jìn)行manchester編碼，編碼完成后將編碼后數(shù)據(jù)發(fā)送給manchester解碼器，manchester解碼器接收到數(shù)據(jù)后開始進(jìn)行解碼工作。如果滿足sleep命令的條件，標(biāo)簽則進(jìn)入睡眠狀態(tài)

36、，對以后的call命令不作應(yīng)答。其流程圖如圖7所示。開始call=1或sleep=1將輸入數(shù)據(jù)存入寄存器中判斷是否滿足命令條件是否是判斷call是否等于1是標(biāo)簽進(jìn)入睡眠狀態(tài)開始對epc做manchester編碼向rfid讀寫器發(fā)送編碼數(shù)據(jù)否否圖7 rfid標(biāo)簽的工作流程圖在manchester編碼器模塊中，最關(guān)鍵的一點(diǎn)就是對標(biāo)簽是否滿足命令條件做出判斷。其中需要注意的是當(dāng)m0時一定滿足命令條件。當(dāng)m0時就需要比較epc碼與命令參數(shù)epc的前m位是否相等，本設(shè)計(jì)中采用的方法是將epc碼和epc參數(shù)同時右移（8m）位然后比較移位后的數(shù)據(jù)是否相等，如果相等則說明滿足命令條件，開始進(jìn)行manchest

37、er編碼，否則命令條件不滿足，標(biāo)簽不作任何動作。2. 2. 3 rfid讀寫器manchester解碼及碰撞位判斷模型manchester解碼及碰撞位的判斷是整個反碰撞算法的最關(guān)鍵部分。解碼和碰撞位判斷均由manchester解碼器模塊完成。當(dāng)讀寫器范圍內(nèi)存在多個標(biāo)簽時，多個標(biāo)簽同時向讀寫器發(fā)送信息，manchester解碼器接收到的是混疊在一起數(shù)據(jù)信號。對于沒有碰撞的位，manchester碼疊加在一起后其信號波形仍然反映明確的1或0數(shù)據(jù)，只需要按照正常的解碼方式解碼即可。然而對于發(fā)生碰撞的數(shù)位，原本攜帶數(shù)據(jù)信息的上升和下降相互抵消了，根據(jù)這一特點(diǎn)解碼器便可以準(zhǔn)確地定出碰撞位。但是我們知道f

38、pga中存儲器只有0和1兩個狀態(tài)，所以存儲解碼數(shù)據(jù)的寄存器要么是0要么是1，無法自己表示出哪一位為碰撞位。這就要求伴隨著解碼數(shù)據(jù)寄存器，要有一個碰撞位標(biāo)志寄存器來對碰撞位最出準(zhǔn)確的標(biāo)記。在本算法中標(biāo)志寄存器中的1表示數(shù)據(jù)寄存器相應(yīng)的位為沖突位，其數(shù)據(jù)為無效數(shù)據(jù)。如圖6所示解碼數(shù)據(jù)寄存器顯示的數(shù)據(jù)是10101011，標(biāo)志位寄存器為10100010，這表示解碼數(shù)據(jù)寄存器的位7、位5和位1為碰撞位，其數(shù)據(jù)是無效數(shù)據(jù)。實(shí)際的解碼結(jié)果為?0?010?1。解碼數(shù)據(jù)寄存器碰撞位標(biāo)志寄存器實(shí)際表示意義1101001000000111？0？010？1圖8 解碼數(shù)據(jù)與碰撞位的表示manchester解碼器的工作流

39、程如圖9所示。開 始接收rfid標(biāo)簽發(fā)送來的數(shù)據(jù)是否檢測到編碼的同步頭是對每位編碼的1/4，3/4處進(jìn)行采樣根據(jù)采樣數(shù)據(jù)解出數(shù)據(jù)及碰撞位標(biāo)志將解碼數(shù)據(jù)及碰撞位標(biāo)志發(fā)送給狀態(tài)機(jī)否圖9 manchester解碼器工作流程圖首先，manchester解碼器模塊中定義了一個兩位的移位寄存器，用來檢測標(biāo)簽發(fā)送的manchester碼的同步頭，以便判斷出編碼的到來。manchester編碼信號manchester解碼采樣信號一旦移位寄存器檢測到標(biāo)簽發(fā)送過來的信號的同步頭，manchester解碼器開始解碼工作，解碼的主要原理是：針對manchester編碼的特點(diǎn)，使用高頻時鐘產(chǎn)生采樣信號，圖10 使用高頻

40、時鐘產(chǎn)生的采樣信號對manchester碼的1/4,3/4處進(jìn)行采樣對manchester編碼信號位的1/4處和3/4處分別進(jìn)行采樣，如圖7所示。如果采樣的結(jié)果為（1，0）則解碼數(shù)據(jù)為1，碰撞位標(biāo)志為0；當(dāng)采樣的結(jié)果為（0，1）則解碼數(shù)據(jù)為0，碰撞位標(biāo)志為0；如果某數(shù)位有碰撞則采樣的結(jié)果為（1，1），則解碼數(shù)據(jù)記為0，碰撞位標(biāo)志為1，說明該位解碼數(shù)據(jù)為無效數(shù)據(jù)。開 始sample=（1，0）數(shù)據(jù)解碼為1，碰撞位標(biāo)志為0sample=（0，1）數(shù)據(jù)解碼為0，碰撞位標(biāo)志為0數(shù)據(jù)默認(rèn)為0，碰撞位標(biāo)志為1解碼結(jié)束是否是否圖11 manchester解碼器解碼關(guān)鍵點(diǎn)流程圖采樣信號的產(chǎn)生可以利用循環(huán)計(jì)數(shù)的

41、計(jì)數(shù)器來實(shí)現(xiàn)。該計(jì)數(shù)器在高頻時鐘的邊沿到來時自動加1，其循環(huán)周期與manchester編碼時鐘周期相等。在與manchester編碼位1/4，3/4處對應(yīng)的計(jì)數(shù)器數(shù)值時令采樣信號為高電平即可。當(dāng)解碼完成后解碼器將向控制狀態(tài)機(jī)發(fā)送一個data_ready脈沖信號，表明epc碼已經(jīng)解碼完畢，可以向狀態(tài)機(jī)傳送數(shù)據(jù)。2. 2. 4 存儲節(jié)點(diǎn)信息的lifo棧跳躍式二進(jìn)制樹形反碰撞算法之所以具有較高的效率是因?yàn)椋惴ㄔ趫?zhí)行過程中跳過了完整二進(jìn)制樹的空閑節(jié)點(diǎn)。我們知道對于二進(jìn)制樹形結(jié)構(gòu)每個分支節(jié)點(diǎn)會分出兩個分支，當(dāng)算法沿其中的一條分支進(jìn)行時就需要記錄下這個節(jié)點(diǎn)的信息，以便于在完成了這個分支的遍歷后返回該節(jié)點(diǎn)

42、，然后沿另外的一條分支向下執(zhí)行算法。idlewrite_readywritewrite_overread_readyreadread_overlifowr=1 & full=0liford=1 & empty=0lifowr=0liford=0reset圖12 lifo棧的內(nèi)部狀態(tài)機(jī)在本跳躍式二進(jìn)制樹形算法當(dāng)中，根據(jù)call命令的返回?cái)?shù)據(jù)判斷出樹的節(jié)點(diǎn)，每到達(dá)一個節(jié)點(diǎn)時就記錄下一個節(jié)點(diǎn)信息。當(dāng)算法執(zhí)行到一個葉的時候，也就是一個標(biāo)簽被識別出來的時候，算法將向上返回到最近的一個節(jié)點(diǎn)，也就是最后被記錄下來的節(jié)點(diǎn)，然后走另外的一條分支。這說明節(jié)點(diǎn)信息的存取是一個后入先出的順序，為滿足這樣的存取順序就需

43、要用一個lifo（last in first out）棧來存儲算法執(zhí)行過程中所經(jīng)過的節(jié)點(diǎn)的信息。為了協(xié)調(diào)lifo內(nèi)部的工作狀態(tài)，在lifo棧的模塊中定義了一個小型的狀態(tài)機(jī)，它具有圖12所示的幾個工作狀態(tài)。工作狀態(tài)的轉(zhuǎn)換條件與流程已經(jīng)在圖12中表示了出來， 在lifo棧讀寫數(shù)據(jù)的時候首先要建立起數(shù)據(jù)地址，然后才能讀寫數(shù)據(jù)，且為了保證讀寫的可靠性，地址與數(shù)據(jù)都要持續(xù)一定的時間。其時序關(guān)系如圖13所示。zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz1100100110100011首先建立讀寫地址然后給出讀寫數(shù)據(jù)t讀寫地址讀寫數(shù)據(jù)圖13 lifo讀寫地址與讀寫數(shù)據(jù)建立的時序關(guān)系實(shí)際上

44、lifo棧是基于ram來建立的，但是其外部的存取特性表現(xiàn)為后入先出。lifo棧的讀寫地址是由讀寫指針指向的，當(dāng)lifo進(jìn)入相應(yīng)的讀寫狀態(tài)后將讀寫指針賦值給讀寫地址，因此lifo棧模塊最關(guān)鍵的地方在于如何計(jì)算它的讀寫指針使其指向正確的存儲單元。指針計(jì)算的程序流程圖如圖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、指針計(jì)算結(jié)束否圖14 lifo站讀寫指針的計(jì)算流程圖2. 2. 5 反碰撞算法狀態(tài)機(jī)如前面所述，本文中的跳躍式二進(jìn)制樹形反碰撞算法的程序模塊包括：manchester編碼模塊、manchester解碼模塊、用于存儲節(jié)點(diǎn)信息的lifo棧模塊和算法狀態(tài)機(jī)。編碼器模塊、解碼器模塊和lifo棧模塊在算法狀態(tài)機(jī)的控制下協(xié)調(diào)工作。另外算法狀態(tài)機(jī)模塊還承擔(dān)了處理解碼數(shù)據(jù)生成call命令及sleep命令參數(shù)的任務(wù)。狀態(tài)機(jī)與各個模塊之間的關(guān)系如下：（1）狀態(tài)機(jī)與編碼模塊：狀態(tài)機(jī)通過內(nèi)部的狀態(tài)轉(zhuǎn)換向編碼模塊發(fā)送call，sleep命令信號和epc及m參數(shù)。編碼模塊接收到call，sleep命令后開始工作。（2）狀

46、態(tài)機(jī)與解碼模塊：狀態(tài)機(jī)監(jiān)測解碼模塊，當(dāng)解碼模塊解碼完成后向狀態(tài)機(jī)發(fā)送一個data_ready信號，狀態(tài)機(jī)接收到data_ready信號后，接收解碼器發(fā)來的數(shù)據(jù)。（3）狀態(tài)機(jī)與lifo模塊：當(dāng)狀態(tài)機(jī)需要寫入或讀取節(jié)點(diǎn)信息時，會發(fā)送lifowr（寫入控制信號）和liford（讀取控制信號）信號給lifo棧，lifo棧接收到控制信號后首先建立起讀寫地址，然后進(jìn)行讀寫數(shù)據(jù)的操作。狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換關(guān)系如圖15所示。狀態(tài)機(jī)各個狀態(tài)解析如下：（1）idle：空閑狀態(tài)，所有寄存器復(fù)位。（2）call：發(fā)送call（epc，m）命令，下一時鐘自動轉(zhuǎn)入waiting狀態(tài)。（3）waiting：等候解碼器的data

47、_ready信號，如果接收到data_ready信號則轉(zhuǎn)入receive狀態(tài)，否則等候時間t后返回到call狀態(tài)。（4）receive：接收來自解碼器的解碼數(shù)據(jù)和碰撞位標(biāo)志。下一時鐘自動轉(zhuǎn)入write_ready狀態(tài)。（5）write_ready：處理來自解碼器的數(shù)據(jù)。根據(jù)解碼器的解碼數(shù)據(jù)和碰撞位標(biāo)志求出m值，如果m=8，即無碰撞發(fā)生，則轉(zhuǎn)入save_ready狀態(tài)。如果m8，則計(jì)算出節(jié)點(diǎn)信息同時生成下一次call命令參數(shù)，然后轉(zhuǎn)入write狀態(tài)。（6）write：在此狀態(tài)下將節(jié)點(diǎn)信息寫入lifo棧。下一時鐘自動轉(zhuǎn)入write_over狀態(tài)。idlecallwaitingreceivewrit

48、e_readywritewrite_overread_readyreadread_oversave_readysavesave_oversleep等待時間t后data_ready=1無碰撞發(fā)生lifo不為空lifo為空圖15 狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換關(guān)系（7）write_over：下一時鐘自動轉(zhuǎn)入call狀態(tài)。（8）save_ready：準(zhǔn)備保存解出的epc碼，發(fā)送寫入信號給保存epc碼的ram。下一時鐘轉(zhuǎn)入save狀態(tài)。（9）save：保存解出的epc碼到ram中。（10）save_over：繼續(xù)給出保存數(shù)據(jù)，以保證保存epc碼的可靠性。下一時鐘轉(zhuǎn)入sleep狀態(tài)。（11）sleep：發(fā)送sleep

49、命令，令已經(jīng)被識別的標(biāo)簽進(jìn)入睡眠狀態(tài)。判斷存儲節(jié)點(diǎn)信息的lifo棧是否為空，如果lifo棧為空，下一時鐘轉(zhuǎn)入idle狀態(tài)。如果lifo棧不為空，則下一時鐘轉(zhuǎn)入read_ready狀態(tài)。（12）read_ready:發(fā)送讀取命令給lifo棧，準(zhǔn)備讀取保存在lifo棧中的節(jié)點(diǎn)信息。下一時鐘轉(zhuǎn)入read狀態(tài)。（13）read：讀取lifo棧內(nèi)保存的節(jié)點(diǎn)信息。下一時鐘轉(zhuǎn)入read_over狀態(tài)。（14）read_over：根據(jù)讀取的碰撞位標(biāo)志求出m值，與讀出的epc值一同作為下一次call命令的參數(shù)。下一時鐘轉(zhuǎn)入call狀態(tài)。以上是算法控制狀態(tài)機(jī)的具體實(shí)現(xiàn)。至此算法所需的各個功能模塊均已經(jīng)分別實(shí)現(xiàn)。2

50、. 2. 6 程序模塊的連接編寫好的各個功能模塊需要相互連接起來組成一個功能完善的反碰撞算法模塊。下面將介紹如何把編寫好的各個功能模塊連接為一個整體。verilog提供了較方便的模塊連接方式，例如欲將模塊m1的端口a與模塊m2的端口b用wire型信號signal連接起來。其形式如下：wire signal；m1 （，.a(signal),）；m2 （，.b(signal),）；以三個標(biāo)簽為例，本算法各個模塊間連接的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所示。本章中詳細(xì)闡述了跳躍式二進(jìn)制樹形反碰撞算法的具體實(shí)現(xiàn)。分別對算法的各個功能模塊進(jìn)行了詳細(xì)說明。最后將各個模塊連接起來完成了整個算法的verilog hdl語言實(shí)現(xiàn)。在下一章中首先將分別對各個模塊進(jìn)行仿真和結(jié)果分析，最后對整個算法進(jìn)行綜合仿真，通過對結(jié)果的分析得出算法的主要性能指標(biāo)。3rfid系統(tǒng)反碰撞算法的fpga仿真及分析本章將對第二章中實(shí)現(xiàn)的跳躍式二進(jìn)制樹形反碰撞算法進(jìn)行fpga器件的計(jì)算機(jī)仿真，并對仿真結(jié)果進(jìn)行

56、分析。首先分別對各個功能模塊進(jìn)行仿真和結(jié)果分析，然后進(jìn)行算法的整體仿真和結(jié)果分析，最后根據(jù)仿真得到的數(shù)據(jù)評估算法的主要性能指標(biāo)。計(jì)算機(jī)平臺：處理器：pentium m 1.5 ghz ；內(nèi)存：ddr333 512mb 。 操作系統(tǒng)：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的新一代設(shè)計(jì)開發(fā)軟件，支持apex20k，apex ii，excalibur，mercury，stratix，cyclone，cyclone ii 等新器件系列。使用quartus ii 開發(fā)軟件可以完成數(shù)字系統(tǒng)設(shè)計(jì)的全部流程，包括設(shè)計(jì)輸入、項(xiàng)目編譯、設(shè)計(jì)校驗(yàn)及器