《rfid原理及應(yīng)用》第4章數(shù)據(jù)校驗和防碰撞算法

1、合肥工業(yè)大學(xué) 計算機與信息學(xué)院,RFID技術(shù)基礎(chǔ),2,4 數(shù)據(jù)校驗和防碰撞算法,在RFID系統(tǒng)中，數(shù)據(jù)傳輸?shù)耐暾源嬖趦蓚€方面的問題： 一是外界的各種干擾可能使數(shù)據(jù)傳輸產(chǎn)生錯誤； 二是多個應(yīng)答器同時占用信道使發(fā)送數(shù)據(jù)產(chǎn)生碰撞。 運用數(shù)據(jù)檢驗（差錯檢測）和防碰撞算法可分別解決這兩個問題。,3,4 數(shù)據(jù)校驗和防碰撞算法,差錯 隨機錯誤：由信道中的隨機噪聲干擾引起。在出現(xiàn)這種錯誤時，前后位之間的錯誤彼此無關(guān)。 突發(fā)錯誤：由突發(fā)干擾引起，當(dāng)前面出現(xiàn)錯誤時，后面往往也會出現(xiàn)錯誤，它們之間有相關(guān)性。 混合錯誤,突發(fā)錯誤長度b=5,4,4 數(shù)據(jù)校驗和防碰撞算法,差錯控制 在傳輸信息數(shù)據(jù)中增加一些冗余編碼，使

2、監(jiān)督碼元和信息碼元之間建立一種確定的關(guān)系，實現(xiàn)差錯控制編碼和差錯控制解碼功能 。 反饋重發(fā)（ARQ）、前向糾錯（FEC）和混合糾錯（HEC）,反饋重發(fā)發(fā)送端需要在得到接收端正確收到所發(fā)信息碼元（通常以幀的形式發(fā)送）的確認(rèn)信息后，才能認(rèn)為發(fā)送成功。,前向糾錯接收端通過糾錯解碼自動糾正傳輸中出現(xiàn)的差錯，所以該方法不需要重傳。這種方法需要采用具有很強糾錯能力的編碼技術(shù),混合糾錯是ARQ和FEC的結(jié)合，設(shè)計思想是對出現(xiàn)的錯誤盡量糾正，糾正不了則需要通過重發(fā)來消除差錯。,5,4 數(shù)據(jù)校驗和防碰撞算法,檢糾錯碼 信息碼元與監(jiān)督碼元,信息碼元 k 監(jiān)督碼元r,檢糾錯碼 許用碼組與禁用碼組 k = 2分組為（

3、00），（10），（10），（11），（00），。如果將這樣的信息組直接送入信道傳輸，它是沒有任何抗干擾能力的，因為任意信息組中任一元素出錯都會變成另一個信息組，例如信息組（00）某一位出錯，將會變成（10）或（01），而它們代表著不同的信息組，因此在接收端就會判斷錯誤。可見不管k的大小如何，若直接傳輸信息組是無任何抗干擾能力的。,如果在各個信息組后按一定規(guī)律人為地添上一些數(shù)字，例如上例，我們在k = 2的信息組后再添上一位數(shù)字，使每一組的長度變?yōu)?，這樣的各組序列我們稱之為碼字，碼字長度記為n，本例中n = k + 1，其中每個碼字的前兩個碼元為原來的信息組，稱為信息元，它主要用來攜帶要傳輸

4、的信息內(nèi)容，后一個新添的碼元稱為監(jiān)督元（或校驗元），其作用是利用添加規(guī)則來監(jiān)督傳輸是否出錯。如果添監(jiān)督元的規(guī)則為：新添監(jiān)督元的符號（0或1）與前兩個碼元（信息元）符號（0或1）之和為0（即模2和為0），這樣的碼字共有2k = 4個，即（000）、（011）、（101）、（110），它們組成了一個碼字集合，其中每一個碼字分別代表一個不同的信息組。而在3位二進制序列（碼組）中共有8個，除以上4個作為碼字外，還有4個未被選中，即這4個碼組不在發(fā)送之列，我們稱之為禁用碼組，而被編碼選中的n重即碼字亦稱為許用碼組。對于接收端，若接收序列不在碼字集合中，說明不是發(fā)送端所發(fā)出的碼字，從而確定傳輸有錯。因此這

5、種變換后的碼字就具有一定的抗干擾能力。,8,4 數(shù)據(jù)校驗和防碰撞算法,檢糾錯碼的分類,9,4 數(shù)據(jù)校驗和防碰撞算法,分組碼 碼組的監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，而與其他碼元組的信息碼元無關(guān) 卷積碼 碼組的監(jiān)督碼元不僅與本碼組的信息碼元相關(guān)，而且與本碼組相鄰的前m個時刻輸入的碼組的信息碼元之間也具有約束關(guān)系 性能優(yōu)于分組碼 交織碼 利用交織技術(shù)構(gòu)造出來的編碼,10,4 數(shù)據(jù)校驗和防碰撞算法,交織碼,線性分組碼 如前所述，我們將信源所給出的二元信息序列首先分成等長的各個信息組，每組信息位長度為k，記為M =（m k1，m k2，m 1，m 0） 顯然，信息組M每一位上的信息數(shù)字（稱信息元）取0

6、或l，共有2k種可能的取值。編碼器根據(jù)某些規(guī)則，將輸入的信息組編成碼長為n的二元序列，即碼字記為 C =（cn1，cn 2，cn k，cn k1，c 1，c 0） 碼字中每一位數(shù)字稱為碼元，取值為0或1。如果碼字的各監(jiān)督元與信息元關(guān)系是線性的（即用一次線性方程來描述），這樣的碼稱為線性分組碼，記為(n,k)碼。,4 數(shù)據(jù)校驗和防碰撞算法,例 (7,3)分組碼，按以下的規(guī)則（校驗方程）可得到4個校驗元c0 c1 c2 c3： c3 = c6 + c4 c2 = c6 + c5 + c4 c1 = c6 + c5 c0 = c5 + c4 式中：c6，c5和c4是三個信息元。由此可得到(7,3)分

7、組碼的八個碼字。八個信息組與八個碼字的對應(yīng)關(guān)系列于表4-1中。式中的加均為模2加。由此方程看到，信息元與校驗元滿足線性關(guān)系，因此該(7,3)碼是線性碼。,4 數(shù)據(jù)校驗和防碰撞算法,表4-1 按上式編出的(7,3)碼字與信息組的對應(yīng)關(guān)系 信 息 組 碼 字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0,4 數(shù)據(jù)校驗和防碰撞算法

8、,線性分組碼的編碼問題，就是如何從n維線性空間Vn中，挑選出一個k維子空間Vn,k，而選擇的規(guī)則完全由n - k個校驗方程決定。由于線性分組碼對模2加滿足封閉性，就為其最小距離的計算帶來方便，具體有如下定理。 定理4.1 一個(n,k)線性分組碼中非零碼字的最小重量等于C中的最小距離d 0。 證明 設(shè)有任兩個碼字C a，Cb C。根據(jù)線性分組碼性質(zhì)，有C a + C b = C c C。而C c的碼重等于C a與C b的碼距d a ; b，即 W(C c)= W(C a + C b)= d a ; b C a和C b是C中任意兩個非全零碼字，所以 Wmin(C a + C b）= Wmin(C

9、 c)= d 0 證畢。 由上例(7,3)碼的8個碼字表可見，除全零碼字外，其余7個碼字最小重量為Wmin = 4，而其中任二碼字之間的最小距離d 0也為4。,4 數(shù)據(jù)校驗和防碰撞算法,在線性分組碼中檢糾錯能力和碼的最小距離有關(guān)，即：在一個碼組內(nèi)為了檢測e個誤碼，要求最小碼距應(yīng)滿足：d e1 在一個碼組內(nèi)為了糾正t個誤碼，要求最小碼距應(yīng)滿足： d 2t1 在一個碼組內(nèi)為了糾正t個誤碼，同時能檢測e個誤碼(et)，要求最小碼距應(yīng)滿足： d et1,4 數(shù)據(jù)校驗和防碰撞算法,線性分組碼 如前所述，我們將信源所給出的二元信息序列首先分成等長的各個信息組，每組信息位長度為k，記為M =（m k1，m

10、k2，m 1，m 0） 顯然，信息組M每一位上的信息數(shù)字（稱信息元）取0或l，共有2k種可能的取值。編碼器根據(jù)某些規(guī)則，將輸入的信息組編成碼長為n的二元序列，即碼字記為 C =（cn1，cn 2，cn k，cn k1，c 1，c 0） 碼字中每一位數(shù)字稱為碼元，取值為0或1。如果碼字的各監(jiān)督元與信息元關(guān)系是線性的（即用一次線性方程來描述），這樣的碼稱為線性分組碼，記為(n,k)碼。,4 數(shù)據(jù)校驗和防碰撞算法,例 (7,3)分組碼，按以下的規(guī)則（校驗方程）可得到4個校驗元c0 c1 c2 c3： c3 = c6 + c4 c2 = c6 + c5 + c4 c1 = c6 + c5 c0 = c

11、5 + c4 式中：c6，c5和c4是三個信息元。由此可得到(7,3)分組碼的八個碼字。八個信息組與八個碼字的對應(yīng)關(guān)系列于表4-1中。式中的加均為模2加。由此方程看到，信息元與校驗元滿足線性關(guān)系，因此該(7,3)碼是線性碼。,4 數(shù)據(jù)校驗和防碰撞算法,表4-1 按上式編出的(7,3)碼字與信息組的對應(yīng)關(guān)系 信 息 組 碼 字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0

12、0 1 1 1 1 1 1 1 0 1 0 0,4 數(shù)據(jù)校驗和防碰撞算法,線性分組碼的編碼問題，就是如何從n維線性空間Vn中，挑選出一個k維子空間Vn,k，而選擇的規(guī)則完全由n - k個校驗方程決定。由于線性分組碼對模2加滿足封閉性，就為其最小距離的計算帶來方便，具體有如下定理。 定理4.1 一個(n,k)線性分組碼中非零碼字的最小重量等于C中的最小距離d 0。 證明 設(shè)有任兩個碼字C a，Cb C。根據(jù)線性分組碼性質(zhì)，有C a + C b = C c C。而C c的碼重等于C a與C b的碼距d a ; b，即 W(C c)= W(C a + C b)= d a ; b C a和C b是C中

13、任意兩個非全零碼字，所以 Wmin(C a + C b）= Wmin(C c)= d 0 證畢。 由上例(7,3)碼的8個碼字表可見，除全零碼字外，其余7個碼字最小重量為Wmin = 4，而其中任二碼字之間的最小距離d 0也為4。,4 數(shù)據(jù)校驗和防碰撞算法,在線性分組碼中檢糾錯能力和碼的最小距離有關(guān)，即：在一個碼組內(nèi)為了檢測e個誤碼，要求最小碼距應(yīng)滿足：d e1 在一個碼組內(nèi)為了糾正t個誤碼，要求最小碼距應(yīng)滿足： d 2t1 在一個碼組內(nèi)為了糾正t個誤碼，同時能檢測e個誤碼(et)，要求最小碼距應(yīng)滿足： d et1,4 數(shù)據(jù)校驗和防碰撞算法,奇偶校驗碼 奇偶校驗（或稱監(jiān)督）碼是最簡單的檢錯碼，

14、由于容易實現(xiàn)，所以應(yīng)用廣泛且久遠。它實際上是一種只有一個校驗元的(n,n-1)分組碼。 奇偶校驗碼的編碼規(guī)則是在需要傳送的信息序列后附加1位校驗碼元，使加入的這一位碼元和各位信息碼元模2和的結(jié)果為0（偶校驗）或1（奇校驗）。 如果某一比特位出錯了，比如說第一比特位從1變成0，那么1的數(shù)目就會變成1（即1的數(shù)目為奇數(shù)），于是接收機就會在比特流中檢出錯誤。另一方面，如果有兩比特出錯，比如說第五比特和第六比特位出錯（即收到的碼是10001110）。這種情況下，1的總數(shù)是4（偶數(shù)），接收機將不能檢出錯誤。 因此可以得出結(jié)論：奇偶校驗碼能檢出所有奇數(shù)個比特位的錯誤，但不能檢出任何偶數(shù)個比特位出錯的情況。

15、可見其檢錯能力是有限的，但由于該碼構(gòu)造簡單，易于實現(xiàn)，且碼率很高，因此成為一種最常用的基本檢錯碼。在信道干擾不太嚴(yán)重、碼長不太長的情況下很有用，特別是在電報、計算機內(nèi)部的數(shù)據(jù)傳送和輸入輸出設(shè)備中，經(jīng)常應(yīng)用這種碼。,22,4 數(shù)據(jù)校驗和防碰撞算法,RFID中的差錯檢測 CRC碼（循環(huán)冗余碼） 較強的檢錯能力，硬件實現(xiàn)簡單 算法步驟,23,4 數(shù)據(jù)校驗和防碰撞算法,RFID中的差錯檢測 CRC碼（循環(huán)冗余碼） 較強的檢錯能力，硬件實現(xiàn)簡單 算法步驟 將k位信息寫成k-1階多項式M(X)； 設(shè)生成多項式G(X)的階為r； 用模2除法計算XrM(X)/G(X)，獲得余數(shù)多項式R(X)； 用模2減法求得

16、傳送多項式T(X)，T(X)= XrM(X)-R(X)，則T(X)多項式系數(shù)序列的前k位為信息位，后r位為校驗位，總位數(shù)n=k+r。,24,4 數(shù)據(jù)校驗和防碰撞算法,防碰撞算法 有兩個或兩個以上的應(yīng)答器同時發(fā)送數(shù)據(jù)，那么就會出現(xiàn)通信沖突，產(chǎn)生數(shù)據(jù)相互的干擾，即碰撞。 多個應(yīng)答器處在多個閱讀器的工作范圍之內(nèi)，它們之間的數(shù)據(jù)通信也會引起數(shù)據(jù)干擾。 采取防碰撞（沖突）協(xié)議，由防碰撞算法（Anti-collision Algorithms）和有關(guān)命令來實現(xiàn)。,25,4 數(shù)據(jù)校驗和防碰撞算法,ALOHA算法 純ALOHA算法用于只讀系統(tǒng)。當(dāng)應(yīng)答器進入射頻能量場被激活以后，它就發(fā)送存儲在應(yīng)答器中的數(shù)據(jù)，且

17、這些數(shù)據(jù)在一個周期性的循環(huán)中不斷發(fā)送，直至應(yīng)答器離開射頻能量場。 時隙ALOHA算法 把時間分為離散的時間段（時隙），每段時間對應(yīng)一幀 動態(tài)時隙ALOHA算法 閱讀器在等待狀態(tài)中的循環(huán)時隙段內(nèi)發(fā)送請求命令，該命令使工作應(yīng)答器同步，然后提供1或2個時隙給工作應(yīng)答器使用，工作應(yīng)答器將選擇自己的傳送時隙，如果在這1或2個時隙內(nèi)有較多應(yīng)答器發(fā)生了數(shù)據(jù)碰撞，閱讀器就用下一個請求命令增加可使用的時隙數(shù)（如4，8，），直至不出現(xiàn)碰撞為止。,信道吞吐率,S=Ge-2G,信道吞吐率,S=Ge-G,26,4 數(shù)據(jù)校驗和防碰撞算法,二進制樹型搜索算法,27,4 數(shù)據(jù)校驗和防碰撞算法,ISO/IEC 14443標(biāo)準(zhǔn)中

18、的防碰撞協(xié)議 TYPE A 幀有3種類型：短幀、標(biāo)準(zhǔn)幀和面向比特的防碰撞幀。 命令集 REQA/WUPA命令 ATQA應(yīng)答 ANTICOLLISION和SELECT命令 SAK應(yīng)答 HALT命令,29,4 數(shù)據(jù)校驗和防碰撞算法,PICC的狀態(tài) Power-off（斷電）狀態(tài) Idle（休閑）狀態(tài) Ready（就緒）狀態(tài) Active（激活）狀態(tài) Halt（停止）狀態(tài),30,4 數(shù)據(jù)校驗和防碰撞算法,防碰撞流程,31,4 數(shù)據(jù)校驗和防碰撞算法,TYPE B的防碰撞協(xié)議 REQB/WUPB命令 SLOT-MARKER命令 ATQB應(yīng)答 ATTRIB命令 HLTB命令及應(yīng)答,TYPE B防碰撞過程示例,33,4 數(shù)據(jù)校驗和防碰撞算法,碰撞檢測 檢測接收到的電信號參數(shù)（如信號電壓幅度、脈沖寬度等）是否發(fā)生了非正常變化，但是對于無線電射頻環(huán)境，門限值較難設(shè)置； 通過差錯檢測方法檢查有無錯碼，雖然應(yīng)用奇偶校驗、CRC碼檢查到的傳輸錯誤不一定是數(shù)據(jù)碰撞引起，但是這種情況的出現(xiàn)也被認(rèn)為是出現(xiàn)了碰撞； 利用某些編碼的性能，檢查是否出現(xiàn)非正常碼來判斷是否產(chǎn)生數(shù)據(jù)碰撞，如曼徹斯特碼，若以2倍數(shù)據(jù)時鐘頻率的NRZ碼表示曼徹斯特碼，則出現(xiàn)11碼就說明產(chǎn)生了碰撞，并且可以知道碰撞發(fā)生在哪一位。,34,4 數(shù)據(jù)校驗和防碰撞算法