RFID應(yīng)用及原理 第七章 射頻數(shù)據(jù)的完整性

1、第6章 射頻數(shù)據(jù)的完整性射頻識別技術(shù)RFID Technology 6.1、基本概念 6.2、RFID系統(tǒng)的數(shù)據(jù)傳輸出錯 6.3、差錯控制方式 6.4、差錯控制編碼 6.5、漢明碼 6.6、奇偶校驗法 6.7、循環(huán)冗余校驗（CRC） 6.8、性能指標(biāo)第6章 射頻數(shù)據(jù)的完整性第6章 射頻數(shù)據(jù)的完整性6.1、基本概念 完整性是指信息未經(jīng)授權(quán)不能進(jìn)行改變的特性，即信息在存儲或傳輸過程中保持不被偶然或蓄意地刪除、修改、偽造、亂序、重放、插入等破壞和丟失的特性。 完整性是一種面向信息的安全性，它要求保持信息的原樣，即信息的正確生成、正確存儲和傳輸。 完整性與保密性不同，保密性要求信息不被泄漏給未授權(quán)的人

2、，而完整性則要求信息不致受到各種原因的破壞。 影響信息完整性的主要因素有：設(shè)備故障、誤碼（傳輸、處理和存儲過程中產(chǎn)生的誤碼，定時的穩(wěn)定度和精度降低造成的誤碼，各種干擾源造成的誤碼）、人為攻擊、計算機(jī)病毒等。6.1、基本概念 保證信息完整性的主要方法包括以下幾種：協(xié)議：通過各種安全協(xié)議可以有效地檢測出被復(fù)制的信息、被刪除的字段、失效的字段和被修改的字段。糾錯編碼方法：由此完成檢錯和糾錯功能。最簡單和常用的糾錯編碼方法是奇偶校驗法。密碼校驗和方法：它是抗篡改和傳輸失敗的重要手段。數(shù)字簽名：保障信息的真實性。公證：請求網(wǎng)絡(luò)管理或中介機(jī)構(gòu)證明信息的真實性。第6章 射頻數(shù)據(jù)的完整性6.2、RFID系統(tǒng)的

3、數(shù)據(jù)傳輸出錯 RFID系統(tǒng)采取無接觸的方式進(jìn)行數(shù)據(jù)傳輸，因此在傳輸過程中很容易受到干擾，包括系統(tǒng)內(nèi)部的熱噪聲和系統(tǒng)外部的各種電磁干擾等，這些都會使傳輸?shù)男盘柊l(fā)生畸變，從而使傳輸數(shù)據(jù)發(fā)生不受歡迎的改變從而導(dǎo)致傳輸錯誤，如下圖所示：圖1 干擾導(dǎo)致數(shù)據(jù)傳輸發(fā)生錯誤第6章 射頻數(shù)據(jù)的完整性6.2、RFID系統(tǒng)的數(shù)據(jù)傳輸出錯 當(dāng)接收讀寫器發(fā)出的命令以及數(shù)據(jù)信息發(fā)生傳輸錯誤時，如果被電子標(biāo)簽接收到，可能會導(dǎo)致以下結(jié)果：電子標(biāo)簽錯誤的響應(yīng)讀寫器的命令；電子標(biāo)簽的工作狀態(tài)發(fā)生混亂；電子標(biāo)簽錯誤的進(jìn)入休眠狀態(tài)。 當(dāng)電子標(biāo)簽發(fā)出的數(shù)據(jù)發(fā)生傳輸錯誤時，如果被讀寫器接收到，可能導(dǎo)致以下結(jié)果：不能識別正常工作的電子標(biāo)簽

4、，誤判電子標(biāo)簽的工作狀態(tài)；將一個電子標(biāo)簽判別為另一個電子標(biāo)簽，造成識別錯誤。第6章 射頻數(shù)據(jù)的完整性6.2、RFID系統(tǒng)的數(shù)據(jù)傳輸出錯 因傳輸?shù)男盘柣兌鴮?dǎo)致的數(shù)據(jù)傳輸出錯在RFID系統(tǒng)的數(shù)據(jù)通信中是不能容忍的，解決的方法有兩種：加大讀寫器的輸出功率，從而提高信噪比，但這種方式有一定的局限性，讀寫器發(fā)出的功率有限制，如果超限，會造成電磁污染。在原始數(shù)據(jù)的后面加上一些校驗位，這些校驗位和前邊的數(shù)據(jù)之間具有某種關(guān)聯(lián)，接收端根據(jù)判斷收到的數(shù)據(jù)位和校驗位之間是否滿足這種關(guān)聯(lián)關(guān)系來判斷有沒有發(fā)生畸變，這就是差錯控制編碼。第6章 射頻數(shù)據(jù)的完整性6.3、差錯控制方式 常用的差錯控制方式主要有檢錯重發(fā)（簡稱

5、ARQ），前向糾錯（簡稱FEC），混合糾錯（簡稱HEC）。第6章 射頻數(shù)據(jù)的完整性發(fā)端糾錯碼收端前向糾錯FEC發(fā)端檢錯碼收端檢錯重發(fā)ARQ判決信號發(fā)端檢錯和糾錯碼收端混合糾錯HEC判決信號6.3、差錯控制方式（1）檢錯重發(fā)（ARQ） 檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(Automatic Repeat Request)。 由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中有無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反饋信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康摹?其特點是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴(yán)重時有效， 但實時性差，主要在計

6、算機(jī)數(shù)據(jù)通信中得到應(yīng)用。 第6章 射頻數(shù)據(jù)的完整性6.3、差錯控制方式（1）檢錯重發(fā)（ARQ） 停止等待ARQ系統(tǒng) 數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后，發(fā)送端等待接收端的確認(rèn)答復(fù)（ACK），然后再發(fā)送下一組數(shù)據(jù)。 圖中的第3組接收數(shù)據(jù)有誤，接收端發(fā)回一個否認(rèn)答復(fù)（NAK），這時發(fā)送端將會重發(fā)第3組數(shù)據(jù)。第6章 射頻數(shù)據(jù)的完整性接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組6.3、差錯控制方法（2）前向糾錯 前向糾錯方式記作FEC( Forword Error Correction )。 發(fā)端采用某種在解碼時能糾正一定程度傳輸差錯的較復(fù)

7、雜的編碼方法，使接收端在收到的信碼中不僅能發(fā)現(xiàn)錯碼，還能夠糾正錯碼。 采用前向糾錯方式時，不需要反饋信道，也不需反復(fù)重發(fā)而延誤傳輸時間，對實時傳輸有利，但是糾錯設(shè)備比較復(fù)雜。第6章 射頻數(shù)據(jù)的完整性6.3、差錯控制方式（3）混合糾錯方式（HEC） 混合糾錯方式記作HEC(Hybrid Error Correction)是FEC和ARQ方式的結(jié)合。 發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力， 但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。 這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達(dá)到較低的誤碼率，因此，

8、 近年來得到廣泛應(yīng)用。 RFID系統(tǒng)一般使用第一種或第二種差錯控制方式。第6章 射頻數(shù)據(jù)的完整性6.4、差錯控制編碼差錯控制時所使用的編碼，常稱為糾錯編碼。根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。監(jiān)督碼元：上述幾種技術(shù)中，都是在接收端識別有無錯碼。所以在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。 不同的編碼方法，有不同的檢錯或糾錯能力。 多余度：就是指增加的監(jiān)督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為1/3。 編碼效率(簡稱碼率) ：設(shè)編碼序列中信息碼元數(shù)量為k

9、，總碼元數(shù)量為n，則比值k/n 就是碼率。 冗余度：監(jiān)督碼元數(shù)(n-k) 和信息碼元數(shù) k 之比。第6章 射頻數(shù)據(jù)的完整性6.4、差錯控制編碼 糾錯編碼的基本原理舉例說明如下: 設(shè)有一種由3位二進(jìn)制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣。 例如： “000”（晴），“001”（云）， “010”（陰），“011”（雨）， “100”（雪），“101”（霜）， “110”（霧），“111”（雹）。 其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。第6章 射頻數(shù)據(jù)的完整性6.4、差錯控制編碼若在上述8種

10、碼組中只準(zhǔn)許使用4種來傳送天氣，例如：“000”晴、“011”云、“101”陰、“110”雨這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。例如，若“000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準(zhǔn)使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯碼。當(dāng)發(fā)生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組。第6章 射頻數(shù)據(jù)的完整性6.4、差錯控制編碼上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當(dāng)接收碼

11、組為禁用碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：“000”（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當(dāng)收到禁用碼組“100”時，若當(dāng)作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為“000”（晴）。因為“111”（雨）發(fā)生任何一位錯碼時都不會變成“100”這種形式。但是，這時若假定錯碼數(shù)不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。

12、第6章 射頻數(shù)據(jù)的完整性6.5、漢明碼漢明碼又叫線性分組碼，它是一種能夠自動檢測并糾正一重錯的線性糾錯碼。漢明碼一般可用(n , k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，漢明碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進(jìn)制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。第6章 射頻數(shù)據(jù)的完整性6.5、漢明碼 在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量， 簡稱碼重。例如，碼字 10110

13、，碼重w=3。 碼距：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。 例如，“000”晴，“011”云，“101”陰，“110”雨，4個碼組之間，任意兩個的距離均為2。再例如 11000 與 10011之間的距離為3。 最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距，用d表示。最小碼距是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的依據(jù)。第6章 射頻數(shù)據(jù)的完整性6.5、漢明碼 碼距的幾何意義 對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。 每個碼組的3個碼元的值(a1, a2, a3)就是此立方體各頂點的坐標(biāo)。而上述碼距概念在此圖中就對應(yīng)于各

14、頂點之間沿立方體各邊行走的幾何距離。 由此圖可以直觀看出，上例中4個許用碼組之間的距離均為2。第6章 射頻數(shù)據(jù)的完整性(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a16.5、漢明碼 漢明不等式： 設(shè)信息位的個數(shù)為k，監(jiān)督位的個數(shù)為r，碼長為n=k + r，則漢明不等式為： 由于n位碼長中有一位出錯，可能產(chǎn)生n個不正確的代碼（錯誤位也可能發(fā)生在校驗位），所以加上r位監(jiān)督位后，就需要定位n個狀態(tài)。 用 個狀態(tài)中的一個狀態(tài)指出“有無錯”，其余 個狀態(tài)便可用于錯誤的定位。第6章 射頻數(shù)據(jù)的完整性2121rrnkr 2r21r6

15、.5、漢明碼碼距與編碼糾錯能力的關(guān)系一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯和糾錯能力。為檢測e個錯碼，要求最小碼距d0e+1，現(xiàn)證明如下：設(shè)一個碼組A位于O點。若碼組A中發(fā)生一個錯碼，則我們可以認(rèn)為A的位置將移動至以O(shè)點為圓心，以1為半徑的圓上某點，但其位置不會超出此圓。 若碼組A中發(fā)生兩位錯碼，則其位置 不會超出以O(shè)點為圓心，以2為半徑 的圓。因此，只要最小碼距不小于 3，碼組A發(fā)生兩位以下錯碼時， 不可能變成另一個許用碼組， 因而能檢測錯碼的位數(shù)等于2。 第6章 射頻數(shù)據(jù)的完整性0123BA漢明距離ed06.5、漢明碼碼距與編碼糾錯能力的關(guān)系同理，若一種編碼的最小碼距為d0

16、，則將能檢測(d0 -1)個錯碼。反之，若要求檢測e個錯碼，則最小碼距d0至少應(yīng)不小于( e+1)。為了糾正t個錯碼，要求最小碼距d0 2t + 1，現(xiàn)證明如下：圖中畫出碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。第6章 射頻數(shù)據(jù)的完整性BtA漢明距離012345td06.5、漢明碼碼距與編碼糾錯能力的關(guān)系 若這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，則以各

17、碼組的位置為中心以2為半徑畫出之圓都不會互相重疊。 這樣，每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當(dāng)最小碼距d05時，能夠糾正2個錯碼，且最多能糾正2個。若錯碼達(dá)到3個，就將落入另一圓上，從而發(fā)生錯判。 故一般說來，為糾正t個錯碼，最小碼距應(yīng)不小于(2t + 1)。第6章 射頻數(shù)據(jù)的完整性6.5、漢明碼碼距與編碼糾錯能力的關(guān)系為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和B之間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e = d0 1 = 5 1 = 4 ，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時做到兩者，因為

18、當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立即進(jìn)入另一碼組的圓內(nèi)而被錯誤地“糾正”了。例如，碼組A若錯了3位，就會被誤 認(rèn)為碼組B錯了2位造成的結(jié) 果，從而被錯“糾”為B。 這就是說，檢錯和糾錯公式 不能同時成立或同時運用。 第6章 射頻數(shù)據(jù)的完整性)(10tetedBtA漢明距離012345td06.5、漢明碼碼距與編碼糾錯能力的關(guān)系所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發(fā)生e個錯誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。因此，由此圖可以直觀看出，要求最小碼距 這種糾錯和

19、檢錯結(jié)合的工作方式簡稱糾檢結(jié)合。第6章 射頻數(shù)據(jù)的完整性)(10tetedABe1tt漢明距離6.6、奇偶校驗法奇偶校驗法是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)。奇偶校驗法是一種非常常見的差錯控制方法。奇偶校驗法又分為奇校驗法和偶校驗法，兩者的原理相同。在偶校驗法中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1”的數(shù)目為偶數(shù)，即滿足下式條件：式中a0為監(jiān)督位，其他位為信息位。這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和”，若計算結(jié)果為“1”就說明存在錯碼，結(jié)果為“0”就認(rèn)為無錯碼。奇校驗法與偶校驗法相似，只不過其碼組中“1”的數(shù)目為奇數(shù)：第6章 射頻數(shù)

20、據(jù)的完整性0021aaann1021aaann6.6、奇偶校驗法 常用的奇偶檢驗法為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗。 垂直奇偶校驗是在垂直方向上以列的形式附加上校驗位。第6章 射頻數(shù)據(jù)的完整性位/數(shù)字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶校驗0110100110奇校驗10010110016.6、奇偶校驗法 用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n。 其中，k是信息元

21、的個數(shù)，n為碼長。 則垂直奇偶校驗的編碼效率R=k/(k+1)。 同理水平奇偶校驗是在水平方向上以行的形式附加上校驗位，它的編碼效率R=n/(n+1)。 水平垂直奇偶校驗是在結(jié)合垂直奇偶校驗和水平奇偶校驗的基礎(chǔ)上形成的一種校驗方法。它是在一批字符傳送之后，另外增加一個稱為“方塊校驗字符”，它的編碼方式是使所傳輸字符代碼的每個縱向列中位代碼的“1”的個數(shù)稱為奇數(shù)（或偶數(shù)）。第6章 射頻數(shù)據(jù)的完整性6.6、奇偶校驗法 水平垂直奇偶校驗法舉例如下： 該方法的編碼效率R為R=kn/(k+1)(n+1)。第6章 射頻數(shù)據(jù)的完整性6.7、循環(huán)冗余校驗（CRC）循環(huán)冗余校驗是另一種比較常見的差錯控制方法。它

22、是將整個數(shù)據(jù)塊當(dāng)成一個連續(xù)的二進(jìn)制數(shù)據(jù)M(x)用另一個多項式（生成多項式G(x)）來除，然后利用余數(shù)進(jìn)行校驗。任意一個由二進(jìn)制位串組成的代碼都可以和一個系數(shù)僅為0和1取值的多項式一一對應(yīng)。例如：代碼1010111對應(yīng)的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應(yīng)的代碼101111。實際應(yīng)用時，發(fā)送裝置計算出CRC校驗碼，并將CRC校驗碼附加在二進(jìn)制數(shù)據(jù)M(x)后面一起發(fā)送給接收裝置，接收裝置根據(jù)接收到的數(shù)據(jù)重新計算CRC校驗碼，并將計算出的CRC校驗碼與收到的校驗碼相比較，若不同，則說明出現(xiàn)錯誤，要求重發(fā)。第6章 射頻數(shù)據(jù)的完整性6.7、循環(huán)冗余校驗（CRC） 上述過程也可以表述為：發(fā)送裝置利用生成多項式G(x)來除以二進(jìn)制數(shù)據(jù)M(x)，將相除結(jié)果的余數(shù)作為CRC校驗碼附在數(shù)據(jù)塊之后發(fā)送出去； 接收時先對傳送過來的二進(jìn)制數(shù)據(jù)用同一個生成多項式G(x)去除，若能除