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、率降低到所要求的程度，并同時對標簽的數據吞吐率沒有損失。使用這種方法，應答器和讀寫器都只要分別有傳輸和接收裝置就可以了，可大大降低成本。這種方法適用于只讀標簽中，這類應答器通常只有一些數據（序列號）傳輸給讀寫器，并且是周期地循環地將這些數據發給讀寫器的，它適用的場合有：超市對貨物的管理、圖書館對圖書的管理、動物園對動物的監控等數據交換量不大、帶寬要求比較低的場合?，F在已有的反碰撞算法有隨機問詢的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均做出應答?；殳B的數據返回給讀寫器，由于此時各個位均有沖突，所以讀寫器識別為?。接下來算法將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、工具，采用可編程邏輯器件，正在成為數字系統設計的主流。采用可編程邏輯器件通過對器件內部的設計來實現系統功能，是一種基于芯片的設計方法。設計者可以根據需要來定義器件的內部邏輯和引出端，將電路板設計的大部分工作放在芯片的設計中進行，通過對芯片設計實現數字邏輯的功能。靈活的內部功能塊組合、引出端定義等，可大大減輕電路設計和電路板設計的工作量和難度，有效地增強設計的靈活性，提高工作效率。同時采用可編程邏輯器件，設計人員在實驗室可以反復編程，修改錯誤，以便盡快開發產品，迅速占領市場?；谛酒脑O計方法可以減少芯片的數量，縮小系統體積，降低功耗，提高系統性能和可靠性。相對于通用處理器而言，使用fpga實現

29、算法可以使得算法的執行速度大幅度的提高。通用處理器在執行軟件算法的過程中，各種指令的調用占據了相當一部分時間，使得算法的執行效率大大降低，以至于在某些特定應用中不能滿足所需要的處理速度，況且通用處理器平臺價格高，體積較大。不具備良好的移動性，不適合作為小型終端的解決方案。在這種情況下用fpga來實現算法就成為了最好的解決方案之一。用fpga實現反碰撞算法首先要使用eda工具做出算法的設計輸入工作，設計輸入有原理圖輸入，hdl硬件描述語言輸入等方法。算法完成設計輸入后再對算法進行一系列的仿真工作，以達到與實際實現時高度吻合的仿真效果。仿真設計是數字系統設計中關鍵的一個環節。可以分為功能仿真和時序

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

31、很好的仿真工具。另外軟件還可以通過標準接口調用第三方仿真工具來進行輔助設計，例如可以通過著名的modelsim仿真軟件來進行仿真等?？梢娛褂胒pga實現反碰撞算法具有速度快，成本低，小巧靈活等優點。2. 2 rfid系統反碰撞算法的實現在2.1中詳盡地闡述了跳躍式二進制樹形反碰撞算法的工作原理。在本章接下來的幾節中將完成該算法的verilog hdl語言實現?，F代的數字系統設計基本上采用自上而下的設計流程。首先對設計對象進行總體描述確定設計對象的行為模型；然后將設計對象進行細化，劃分為更為基本的功能模塊進行分別設計驗證；最后將各個分立的功能模塊組合起來形成整體的系統。在每一個功能模塊的設計中又

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 開發軟件可以完成數字系統設計的全部流程，包括設計輸入、項目編譯、設計校驗及器件編