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

1、編輯pptRFID技術(shù)基礎(chǔ)技術(shù)基礎(chǔ)編輯ppt24 數(shù)據(jù)校驗(yàn)和防碰撞算法 在RFID系統(tǒng)中，數(shù)據(jù)傳輸?shù)耐暾源嬖趦蓚€(gè)方面的問(wèn)題：一是外界的各種干擾可能使數(shù)據(jù)傳輸產(chǎn)生錯(cuò)誤；二是多個(gè)應(yīng)答器同時(shí)占用信道使發(fā)送數(shù)據(jù)產(chǎn)生碰撞。 運(yùn)用數(shù)據(jù)檢驗(yàn)（差錯(cuò)檢測(cè)）和防碰撞算法可分別解決這兩個(gè)問(wèn)題。 編輯ppt34 數(shù)據(jù)校驗(yàn)和防碰撞算法 差錯(cuò) 隨機(jī)錯(cuò)誤：由信道中的隨機(jī)噪聲干擾引起。在出現(xiàn)這種錯(cuò)誤時(shí)，前后位之間的錯(cuò)誤彼此無(wú)關(guān)。 突發(fā)錯(cuò)誤：由突發(fā)干擾引起，當(dāng)前面出現(xiàn)錯(cuò)誤時(shí)，后面往往也會(huì)出現(xiàn)錯(cuò)誤，它們之間有相關(guān)性。 混合錯(cuò)誤 正確比特流00111000 接收比特流01100100 異或錯(cuò)誤圖樣 01011100 突發(fā)錯(cuò)誤長(zhǎng)度

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

3、錯(cuò)碼 信息碼元與監(jiān)督碼元 信息碼元 k 監(jiān)督碼元r 編輯ppt檢糾錯(cuò)碼 許用碼組與禁用碼組 k = 2分組為（00），（10），（10），（11），（00），。如果將這樣的信息組直接送入信道傳輸，它是沒(méi)有任何抗干擾能力的，因?yàn)槿我庑畔⒔M中任一元素出錯(cuò)都會(huì)變成另一個(gè)信息組，例如信息組（00）某一位出錯(cuò)，將會(huì)變成（10）或（01），而它們代表著不同的信息組，因此在接收端就會(huì)判斷錯(cuò)誤。可見(jiàn)不管k的大小如何，若直接傳輸信息組是無(wú)任何抗干擾能力的。編輯ppt如果在各個(gè)信息組后按一定規(guī)律人為地添上一些數(shù)字，例如上例，我們?cè)趉 = 2的信息組后再添上一位數(shù)字，使每一組的長(zhǎng)度變?yōu)?，這樣的各組序列我們稱(chēng)之為碼

4、字碼字，碼字長(zhǎng)度記為n，本例中n = k + 1，其中每個(gè)碼字的前兩個(gè)碼元為原來(lái)的信息組，稱(chēng)為信息元信息元，它主要用來(lái)攜帶要傳輸?shù)男畔?nèi)容，后一個(gè)新添的碼元稱(chēng)為監(jiān)督元監(jiān)督元（或校驗(yàn)元校驗(yàn)元），其作用是利用添加規(guī)則來(lái)監(jiān)督傳輸是否出錯(cuò)。如果添監(jiān)督元的規(guī)則為：新添監(jiān)督元的符號(hào)（0或1）與前兩個(gè)碼元（信息元）符號(hào)（0或1）之和為0（即模2和為0），這樣的碼字共有2k = 4個(gè)，即（000）、（011）、（101）、（110），它們組成了一個(gè)碼字集合，其中每一個(gè)碼字分別代表一個(gè)不同的信息組。而在3位二進(jìn)制序列（碼組）中共有8個(gè)，除以上4個(gè)作為碼字外，還有4個(gè)未被選中，即這4個(gè)碼組不在發(fā)送之列，我們稱(chēng)之為

5、禁用碼組禁用碼組，而被編碼選中的n重即碼字亦稱(chēng)為許用碼組許用碼組。對(duì)于接收端，若接收序列不在碼字集合中，說(shuō)明不是發(fā)送端所發(fā)出的碼字，從而確定傳輸有錯(cuò)。因此這種變換后的碼字就具有一定的抗干擾能力。編輯ppt84 數(shù)據(jù)校驗(yàn)和防碰撞算法 檢糾錯(cuò)碼的分類(lèi) 編輯ppt94 數(shù)據(jù)校驗(yàn)和防碰撞算法 分組碼 碼組的監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，而與其他碼元組的信息碼元無(wú)關(guān) 卷積碼 碼組的監(jiān)督碼元不僅與本碼組的信息碼元相關(guān)，而且與本碼組相鄰的前m個(gè)時(shí)刻輸入的碼組的信息碼元之間也具有約束關(guān)系 性能優(yōu)于分組碼 交織碼 利用交織技術(shù)構(gòu)造出來(lái)的編碼 編輯ppt104 數(shù)據(jù)校驗(yàn)和防碰撞算法 交織碼編輯ppt線(xiàn)性分組碼

6、如前所述，我們將信源所給出的二元信息序列首先分成等長(zhǎng)的各個(gè)信息組，每組信息位長(zhǎng)度為k，記為M =（m k1，m k2，m 1，m 0）顯然，信息組M每一位上的信息數(shù)字（稱(chēng)信息元）取0或l，共有2k種可能的取值。編碼器根據(jù)某些規(guī)則，將輸入的信息組編成碼長(zhǎng)為n的二元序列，即碼字記為C =（cn1，cn 2，cn k，cn k1，c 1，c 0）碼字中每一位數(shù)字稱(chēng)為碼元，取值為0或1。如果碼字的各監(jiān)督元與信息元關(guān)系是線(xiàn)性的（即用一次線(xiàn)性方程來(lái)描述），這樣的碼稱(chēng)為線(xiàn)性分組碼，記為(n,k)碼。4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt例例 (7,3)分組碼，按以下的規(guī)則（校驗(yàn)方程）可得到4個(gè)校驗(yàn)元c0 c1

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

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

9、。而C c的碼重等于C a與C b的碼距d a ; b，即W(C c)= W(C a + C b)= d a ; bC a和C b是C中任意兩個(gè)非全零碼字，所以 Wmin(C a + C b）= Wmin(C c)= d 0 證畢。由上例(7,3)碼的8個(gè)碼字表可見(jiàn)，除全零碼字外，其余7個(gè)碼字最小重量為Wmin = 4，而其中任二碼字之間的最小距離d 0也為4。4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt在線(xiàn)性分組碼中檢糾錯(cuò)能力和碼的最小距離有關(guān)，即：在一個(gè)碼組內(nèi)為了檢測(cè)e個(gè)誤碼，要求最小碼距應(yīng)滿(mǎn)足：d e1 在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，要求最小碼距應(yīng)滿(mǎn)足： d 2t1 在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼

10、，同時(shí)能檢測(cè)e個(gè)誤碼(et)，要求最小碼距應(yīng)滿(mǎn)足： d et1 4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt線(xiàn)性分組碼如前所述，我們將信源所給出的二元信息序列首先分成等長(zhǎng)的各個(gè)信息組，每組信息位長(zhǎng)度為k，記為M =（m k1，m k2，m 1，m 0）顯然，信息組M每一位上的信息數(shù)字（稱(chēng)信息元）取0或l，共有2k種可能的取值。編碼器根據(jù)某些規(guī)則，將輸入的信息組編成碼長(zhǎng)為n的二元序列，即碼字記為C =（cn1，cn 2，cn k，cn k1，c 1，c 0）碼字中每一位數(shù)字稱(chēng)為碼元，取值為0或1。如果碼字的各監(jiān)督元與信息元關(guān)系是線(xiàn)性的（即用一次線(xiàn)性方程來(lái)描述），這樣的碼稱(chēng)為線(xiàn)性分組碼，記為(n,k)碼。

11、4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt例例 (7,3)分組碼，按以下的規(guī)則（校驗(yàn)方程）可得到4個(gè)校驗(yàn)元c0 c1 c2 c3：c3 = c6 + c4c2 = c6 + c5 + c4c1 = c6 + c5c0 = c5 + c4式中：c6，c5和c4是三個(gè)信息元。由此可得到(7,3)分組碼的八個(gè)碼字。八個(gè)信息組與八個(gè)碼字的對(duì)應(yīng)關(guān)系列于表4-1中。式中的加均為模2加。由此方程看到，信息元與校驗(yàn)元滿(mǎn)足線(xiàn)性關(guān)系，因此該(7,3)碼是線(xiàn)性碼。4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt表表4-1 按上式編出的按上式編出的(7,3)碼字與信息組的對(duì)應(yīng)關(guān)系碼字與信息組的對(duì)應(yīng)關(guān)系 信 息 組 碼 字0 0 0 0

12、 0 0 0 0 0 00 0 1 0 0 1 1 1 0 10 1 0 0 1 0 0 1 1 10 1 1 0 1 1 1 0 1 01 0 0 1 0 0 1 1 1 01 0 1 1 0 1 0 0 1 11 1 0 1 1 0 1 0 0 11 1 1 1 1 1 0 1 0 04 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt線(xiàn)性分組碼的編碼問(wèn)題，就是如何從n維線(xiàn)性空間Vn中，挑選出一個(gè)k維子空間Vn,k，而選擇的規(guī)則完全由n - k個(gè)校驗(yàn)方程決定。由于線(xiàn)性分組碼對(duì)模2加滿(mǎn)足封閉性，就為其最小距離的計(jì)算帶來(lái)方便，具體有如下定理。定理定理 一個(gè)(n,k)線(xiàn)性分組碼中非零碼字的最小重量等于C中的最小

13、距離d 0。證明證明 設(shè)有任兩個(gè)碼字C a，Cb C。根據(jù)線(xiàn)性分組碼性質(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 ; bC a和C b是C中任意兩個(gè)非全零碼字，所以 Wmin(C a + C b）= Wmin(C c)= d 0 證畢。由上例(7,3)碼的8個(gè)碼字表可見(jiàn)，除全零碼字外，其余7個(gè)碼字最小重量為Wmin = 4，而其中任二碼字之間的最小距離d 0也為4。4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt在線(xiàn)性分組碼中檢糾錯(cuò)能力和碼的最小距離有關(guān)，即：在一個(gè)碼組內(nèi)為了檢測(cè)e個(gè)誤碼，要求最小碼距

14、應(yīng)滿(mǎn)足：d e1 在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，要求最小碼距應(yīng)滿(mǎn)足： d 2t1 在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，同時(shí)能檢測(cè)e個(gè)誤碼(et)，要求最小碼距應(yīng)滿(mǎn)足： d et1 4 數(shù)據(jù)校驗(yàn)和防碰撞算法 編輯ppt奇偶校驗(yàn)碼奇偶校驗(yàn)碼奇偶校驗(yàn)（或稱(chēng)監(jiān)督）碼是最簡(jiǎn)單的檢錯(cuò)碼，由于容易實(shí)現(xiàn)，所以應(yīng)用廣泛且久遠(yuǎn)。它實(shí)際上是一種只有一個(gè)校驗(yàn)元的(n,n-1)分組碼。奇偶校驗(yàn)碼的編碼規(guī)則是在需要傳送的信息序列后附加1位校驗(yàn)碼元，使加入的這一位碼元和各位信息碼元模2和的結(jié)果為0（偶校驗(yàn)）或1（奇校驗(yàn)）。如果某一比特位出錯(cuò)了，比如說(shuō)第一比特位從1變成0，那么1的數(shù)目就會(huì)變成1（即1的數(shù)目為奇數(shù)），于是接收機(jī)就會(huì)

15、在比特流中檢出錯(cuò)誤。另一方面，如果有兩比特出錯(cuò)，比如說(shuō)第五比特和第六比特位出錯(cuò)（即收到的碼是10001110）。這種情況下，1的總數(shù)是4（偶數(shù)），接收機(jī)將不能檢出錯(cuò)誤。因此可以得出結(jié)論：奇偶校驗(yàn)碼能檢出所有奇數(shù)個(gè)比特位的錯(cuò)誤，但不能檢出任何偶數(shù)個(gè)比特位出錯(cuò)的情況?？梢?jiàn)其檢錯(cuò)能力是有限的，但由于該碼構(gòu)造簡(jiǎn)單，易于實(shí)現(xiàn)，且碼率很高，因此成為一種最常用的基本檢錯(cuò)碼。在信道干擾不太嚴(yán)重、碼長(zhǎng)不太長(zhǎng)的情況下很有用，特別是在電報(bào)、計(jì)算機(jī)內(nèi)部的數(shù)據(jù)傳送和輸入輸出設(shè)備中，經(jīng)常應(yīng)用這種碼。編輯ppt224 數(shù)據(jù)校驗(yàn)和防碰撞算法 RFID中的差錯(cuò)檢測(cè) CRC碼（循環(huán)冗余碼） 較強(qiáng)的檢錯(cuò)能力，硬件實(shí)現(xiàn)簡(jiǎn)單 算法步驟

16、 編輯ppt234 數(shù)據(jù)校驗(yàn)和防碰撞算法 RFID中的差錯(cuò)檢測(cè) CRC碼（循環(huán)冗余碼） 較強(qiáng)的檢錯(cuò)能力，硬件實(shí)現(xiàn)簡(jiǎn)單 算法步驟 將k位信息寫(xiě)成k-1階多項(xiàng)式M(X)； 設(shè)生成多項(xiàng)式G(X)的階為r； 用模2除法計(jì)算XrM(X)/G(X)，獲得余數(shù)多項(xiàng)式R(X)； 用模2減法求得傳送多項(xiàng)式T(X)，T(X)= XrM(X)-R(X)，則T(X)多項(xiàng)式系數(shù)序列的前k位為信息位，后r位為校驗(yàn)位，總位數(shù)n=k+r。 編輯ppt244 數(shù)據(jù)校驗(yàn)和防碰撞算法 防碰撞算法 有兩個(gè)或兩個(gè)以上的應(yīng)答器同時(shí)發(fā)送數(shù)據(jù)，那么就會(huì)出現(xiàn)通信沖突，產(chǎn)生數(shù)據(jù)相互的干擾，即碰撞。 多個(gè)應(yīng)答器處在多個(gè)閱讀器的工作范圍之內(nèi)，它們之

17、間的數(shù)據(jù)通信也會(huì)引起數(shù)據(jù)干擾。 采取防碰撞（沖突）協(xié)議，由防碰撞算法（Anti-collision Algorithms）和有關(guān)命令來(lái)實(shí)現(xiàn)。 編輯ppt254 數(shù)據(jù)校驗(yàn)和防碰撞算法 ALOHA算法 純ALOHA算法用于只讀系統(tǒng)。當(dāng)應(yīng)答器進(jìn)入射頻能量場(chǎng)被激活以后，它就發(fā)送存儲(chǔ)在應(yīng)答器中的數(shù)據(jù)，且這些數(shù)據(jù)在一個(gè)周期性的循環(huán)中不斷發(fā)送，直至應(yīng)答器離開(kāi)射頻能量場(chǎng)。 時(shí)隙ALOHA算法 把時(shí)間分為離散的時(shí)間段（時(shí)隙），每段時(shí)間對(duì)應(yīng)一幀 動(dòng)態(tài)時(shí)隙ALOHA算法 閱讀器在等待狀態(tài)中的循環(huán)時(shí)隙段內(nèi)發(fā)送請(qǐng)求命令，該命令使工作應(yīng)答器同步，然后提供1或2個(gè)時(shí)隙給工作應(yīng)答器使用，工作應(yīng)答器將選擇自己的傳送時(shí)隙，如果在

18、這1或2個(gè)時(shí)隙內(nèi)有較多應(yīng)答器發(fā)生了數(shù)據(jù)碰撞，閱讀器就用下一個(gè)請(qǐng)求命令增加可使用的時(shí)隙數(shù)（如4，8，），直至不出現(xiàn)碰撞為止。 信道吞吐率 S=Ge-2G 信道吞吐率 S=Ge-G 編輯ppt264 數(shù)據(jù)校驗(yàn)和防碰撞算法 二進(jìn)制樹(shù)型搜索算法 編輯ppt274 數(shù)據(jù)校驗(yàn)和防碰撞算法 ISO/IEC 14443標(biāo)準(zhǔn)中的防碰撞協(xié)議 TYPE A 幀有3種類(lèi)型：短幀、標(biāo)準(zhǔn)幀和面向比特的防碰撞幀。 命令集 REQA/WUPA命令 ATQA應(yīng)答 ANTICOLLISION和SELECT命令 SAK應(yīng)答 HALT命令 編輯ppt編輯ppt294 數(shù)據(jù)校驗(yàn)和防碰撞算法 PICC的狀態(tài) Power-off（斷電）狀態(tài) Idle（休閑）狀態(tài) Ready（就緒）狀態(tài) Active（激活）狀態(tài) Halt（停止）狀態(tài) 編輯ppt304 數(shù)據(jù)校驗(yàn)和防碰撞算法 防碰撞流程 編輯ppt314 數(shù)據(jù)校驗(yàn)和防碰撞算法 TYPE B的防碰撞協(xié)議 REQB/WUPB命令 SLOT-MARKER命令 A