二射頻數據的完整性

1、射頻數據的完整性射頻識別技術RFID Technology 1、基本概念 2、RFID系統的數據傳輸出錯 3、差錯控制方式 4、差錯控制編碼 5、漢明碼 6、奇偶校驗法 7、循環(huán)冗余校驗（CRC） 8、性能指標射頻數據的完整性射頻數據的完整性1、基本概念 完整性是指信息未經授權不能進行改變的特性，即信息在存儲或傳輸過程中保持不被偶然或蓄意地刪除、修改、偽造、亂序、重放、插入等破壞和丟失的特性。 完整性是一種面向信息的安全性，它要求保持信息的原樣，即信息的正確生成、正確存儲和傳輸。 完整性與保密性不同，保密性要求信息不被泄漏給未授權的人，而完整性則要求信息不致受到各種原因的破壞。 影響信息完整性

2、的主要因素有：設備故障、誤碼（傳輸、處理和存儲過程中產生的誤碼，定時的穩(wěn)定度和精度降低造成的誤碼，各種干擾源造成的誤碼）、人為攻擊、計算機病毒等。1、基本概念 保證信息完整性的主要方法包括以下幾種： 協議：通過各種安全協議可以有效地檢測出被復制的信息、被刪除的字段、失效的字段和被修改的字段。 糾錯編碼方法：由此完成檢錯和糾錯功能。最簡單和常用的糾錯編碼方法是奇偶校驗法。 密碼校驗和方法：它是抗篡改和傳輸失敗的重要手段。 數字簽名：保障信息的真實性。公證：請求網絡管理或中介機構證明信息的真實性。射頻數據的完整性2、RFID系統的數據傳輸出錯 RFID系統采取無接觸的方式進行數據傳輸，因此在傳輸過

3、程中很容易受到干擾，包括系統內部的熱噪聲和系統外部的各種電磁干擾等，這些都會使傳輸的信號發(fā)生畸變，從而使傳輸數據發(fā)生不受歡迎的改變從而導致傳輸錯誤，如下圖所示：圖1 干擾導致數據傳輸發(fā)生錯誤射頻數據的完整性2、RFID系統的數據傳輸出錯 當接收讀寫器發(fā)出的命令以及數據信息發(fā)生傳輸錯誤時，如果被電子標簽接收到，可能會導致以下結果： 電子標簽錯誤的響應讀寫器的命令； 電子標簽的工作狀態(tài)發(fā)生混亂； 電子標簽錯誤的進入休眠狀態(tài)。 當電子標簽發(fā)出的數據發(fā)生傳輸錯誤時，如果被讀寫器接收到，可能導致以下結果： 不能識別正常工作的電子標簽，誤判電子標簽的工作狀態(tài)； 將一個電子標簽判別為另一個電子標簽，造成識別

4、錯誤。射頻數據的完整性2、RFID系統的數據傳輸出錯 因傳輸的信號畸變而導致的數據傳輸出錯在RFID系統的數據通信中是不能容忍的，解決的方法有兩種： 加大讀寫器的輸出功率，從而提高信噪比，但這種方式有一定的局限性，讀寫器發(fā)出的功率有限制，如果超限，會造成電磁污染。在原始數據的后面加上一些校驗位，這些校驗位和前邊的數據之間具有某種關聯，接收端根據判斷收到的數據位和校驗位之間是否滿足這種關聯關系來判斷有沒有發(fā)生畸變，這就是差錯控制編碼。射頻數據的完整性3、差錯控制方式 常用的差錯控制方式主要有檢錯重發(fā)（簡稱ARQ），前向糾錯（簡稱FEC），混合糾錯（簡稱HEC）。射頻數據的完整性發(fā)端糾錯碼收端前向

5、糾錯FEC發(fā)端檢錯碼收端檢錯重發(fā)ARQ判決信號發(fā)端檢錯和糾錯碼收端混合糾錯HEC判決信號3、差錯控制方式（1）檢錯重發(fā)（ARQ） 檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(Automatic Repeat Request)。 由發(fā)端送出能夠發(fā)現錯誤的碼，由收端判決傳輸中有無錯誤產生，如果發(fā)現錯誤，則通過反饋信道把這一判決結果反饋給發(fā)端，然后，發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸的目的。 其特點是需要反饋信道，譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效， 但實時性差，主要在計算機數據通信中得到應用。 射頻數據的完整性3、差錯控制方式（1）檢錯重發(fā)（ARQ） 停止等待ARQ系統

6、數據按分組發(fā)送。每發(fā)送一組數據后，發(fā)送端等待接收端的確認答復（ACK），然后再發(fā)送下一組數據。 圖中的第3組接收數據有誤，接收端發(fā)回一個否認答復（NAK），這時發(fā)送端將會重發(fā)第3組數據。射頻數據的完整性接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組3、差錯控制方法（2）前向糾錯 前向糾錯方式記作FEC( Forward Error Correction )。 發(fā)端采用某種在解碼時能糾正一定程度傳輸差錯的較復雜的編碼方法，使接收端在收到的信碼中不僅能發(fā)現錯碼，還能夠糾正錯碼。 采用前向糾錯方式時，不需要反饋信道，也不需反復重發(fā)而延誤傳

7、輸時間，對實時傳輸有利，但是糾錯設備比較復雜。射頻數據的完整性3、差錯控制方式（3）混合糾錯方式（HEC） 混合糾錯方式記作HEC(Hybrid Error Correction)是FEC和ARQ方式的結合。 發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內，則自動糾錯，如果超過了碼的糾錯能力， 但能檢測出來，則經過反饋信道請求發(fā)端重發(fā)。 這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此， 近年來得到廣泛應用。 RFID系統一般使用第一種或第二種差錯控制方式。射頻數據的完整性4、差錯控制編碼差錯控制時所使用的編碼，常稱為糾錯編

8、碼。根據碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。監(jiān)督碼元：上述幾種技術中，都是在接收端識別有無錯碼。所以在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。 不同的編碼方法，有不同的檢錯或糾錯能力。 多余度：就是指增加的監(jiān)督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為1/3。 編碼效率(簡稱碼率) ：設編碼序列中信息碼元數量為k，總碼元數量為n，則比值k/n 就是碼率。 冗余度：監(jiān)督碼元數(n-k) 和信息碼元數 k 之比。射頻數據的完整性4、差錯控制編碼 糾錯編碼的基本原理舉

9、例說明如下: 設有一種由3位二進制數字構成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣。 例如： “000”（晴），“001”（云）， “010”（陰），“011”（雨）， “100”（雪），“101”（霜）， “110”（霧），“111”（雹）。 其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現錯誤。射頻數據的完整性4、差錯控制編碼若在上述8種碼組中只準許使用4種來傳送天氣，例如：“000”晴、“011”云、“101”陰、“110”雨這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現碼組中的一個錯碼。例如，若“

10、000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認為發(fā)現了錯碼。當發(fā)生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。但是這種碼不能發(fā)現一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產生的是許用碼組。射頻數據的完整性4、差錯控制編碼上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當接收碼組為禁用碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：“000”（晴

11、），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當收到禁用碼組“100”時，若當作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為“000”（晴）。因為“111”（雨）發(fā)生任何一位錯碼時都不會變成“100”這種形式。但是，這時若假定錯碼數不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。射頻數據的完整性5、漢明碼漢明碼又叫線性分組碼，它是一種能夠自動檢測并糾正一重錯的線性糾錯碼。漢明碼一般可用(n , k)表示。其中，k是每組二進制信息碼元的數目，n是編碼碼組的碼元總位數

12、，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數目。簡單地說，漢明碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。射頻數據的完整性18 檢糾錯碼 信息碼元與監(jiān)督碼元 信息碼元 k 監(jiān)督碼元r 5、漢明碼 在分組碼中，非零碼元的數目稱為碼字的漢明重量， 簡稱碼重。例如，碼字 10110，碼重w=3。 碼距：把兩個碼組中對應位上數字不同的位數稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。 例如，“000”晴，“011”云，“101”陰，

13、“110”雨，4個碼組之間，任意兩個的距離均為2。再例如 11000 與 10011之間的距離為3。 最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距，用d表示。最小碼距是碼的一個重要參數， 它是衡量碼檢錯、糾錯能力的依據。射頻數據的完整性5、漢明碼 碼距的幾何意義 對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。 每個碼組的3個碼元的值(a1, a2, a3)就是此立方體各頂點的坐標。而上述碼距概念在此圖中就對應于各頂點之間沿立方體各邊行走的幾何距離。 由此圖可以直觀看出，上例中4個許用碼組之間的距離均為2。射頻數據的完整性(0,0,0)(0,0,1)(1,0,1)(1,0,

14、0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a15、漢明碼 漢明不等式： 設信息位的個數為k，監(jiān)督位的個數為r，碼長為n=k + r，則漢明不等式為： 由于n位碼長中有一位出錯，可能產生n個不正確的代碼（錯誤位也可能發(fā)生在校驗位），所以加上r位監(jiān)督位后，就需要定位n個狀態(tài)。 用 個狀態(tài)中的一個狀態(tài)指出“有無錯”，其余 個狀態(tài)便可用于錯誤的定位。射頻數據的完整性2121rrnkr 2r21r5、漢明碼碼距與編碼糾錯能力的關系一種編碼的最小碼距d0的大小直接關系著這種編碼的檢錯和糾錯能力。為檢測e個錯碼，要求最小碼距d0e+1，現證明如下：設一個碼組A位于O點。若碼組A中發(fā)

15、生一個錯碼，則我們可以認為A的位置將移動至以O點為圓心，以1為半徑的圓上某點，但其位置不會超出此圓。 若碼組A中發(fā)生兩位錯碼，則其位置 不會超出以O點為圓心，以2為半徑 的圓。因此，只要最小碼距不小于 3，碼組A發(fā)生兩位以下錯碼時， 不可能變成另一個許用碼組， 因而能檢測錯碼的位數等于2。 射頻數據的完整性0123BA漢明距離ed05、漢明碼碼距與編碼糾錯能力的關系同理，若一種編碼的最小碼距為d0 ，則將能檢測(d0 -1)個錯碼。反之，若要求檢測e個錯碼，則最小碼距d0至少應不小于( e+1)。為了糾正t個錯碼，要求最小碼距d0 2t + 1，現證明如下：圖中畫出碼組A和B的距離為5。碼組A

16、或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。射頻數據的完整性BtA漢明距離012345td05、漢明碼碼距與編碼糾錯能力的關系 若這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，則以各碼組的位置為中心以2為半徑畫出之圓都不會互相重疊。 這樣，每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當最小碼距d05時，能夠糾正2個錯碼，且最多能糾正2個。若錯碼達到3個，就將落入另一圓上，從而發(fā)生錯判

17、。 故一般說來，為糾正t個錯碼，最小碼距應不小于(2t + 1)。射頻數據的完整性5、漢明碼碼距與編碼糾錯能力的關系為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和B之間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e = d0 1 = 5 1 = 4 ，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時做到兩者，因為當錯碼位數超過糾錯能力時，該碼組立即進入另一碼組的圓內而被錯誤地“糾正”了。例如，碼組A若錯了3位，就會被誤 認為碼組B錯了2位造成的結 果，從而被錯“糾”為B。 這就是說，檢錯和糾錯公式 不能同時成立或同時運用。 射頻數

18、據的完整性)(10tetedBtA漢明距離012345td05、漢明碼碼距與編碼糾錯能力的關系所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發(fā)生e個錯誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。因此，由此圖可以直觀看出，要求最小碼距 這種糾錯和檢錯結合的工作方式簡稱糾檢結合。射頻數據的完整性)(10tetedABe1tt漢明距離27 檢糾錯碼的分類 6、奇偶校驗法奇偶校驗法是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數是奇數或偶數。奇偶校驗法是一種非常常見的差錯控制

19、方法。奇偶校驗法又分為奇校驗法和偶校驗法，兩者的原理相同。在偶校驗法中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1”的數目為偶數，即滿足下式條件： 式中a0為監(jiān)督位，其他位為信息位。這種編碼能夠檢測奇數個錯碼。在接收端，按照上式求“模2和”，若計算結果為“1”就說明存在錯碼，結果為“0”就認為無錯碼。 奇校驗法與偶校驗法相似，只不過其碼組中“1”的數目為奇數：射頻數據的完整性0021aaann1021aaann6、奇偶校驗法 常用的奇偶檢驗法為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗。 垂直奇偶校驗是在垂直方向上以列的形式附加上校驗位。射頻數據的完整性位/數字0123456789C10

20、101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶校驗0110100110奇校驗10010110016、奇偶校驗法 用差錯控制編碼提高通信系統的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n。 其中，k是信息元的個數，n為碼長。 則垂直奇偶校驗的編碼效率R=k/(k+1)。 同理水平奇偶校驗是在水平方向上以行的形式附加上校驗位，它的編碼效率R=n/(n+1)。 水平垂直奇偶校驗是在結合垂直奇偶校驗和水平奇偶校驗的基礎上形成的一種校驗方法。它是在一批字

21、符傳送之后，另外增加一個稱為“方塊校驗字符”，它的編碼方式是使所傳輸字符代碼的每個縱向列中位代碼的“1”的個數稱為奇數（或偶數）。射頻數據的完整性6、奇偶校驗法 水平垂直奇偶校驗法舉例如下： 該方法的編碼效率R為R=kn/(k+1)(n+1)。射頻數據的完整性32 RFID中的差錯檢測 CRC碼（循環(huán)冗余碼） 較強的檢錯能力，硬件實現簡單 算法步驟 注：在RFID標準ISO/IEC14443中，采用的是CRC（CCITT）的生成多項式。但應注意的是，該標準中的TYPE A采用CRC-A，計算時循環(huán)移寄存器的初始值為6363H；TYPE B采用CRC-B，循環(huán)位移寄存器的初始值為FFFFH。循環(huán)

22、冗余校驗碼循環(huán)冗余校驗碼(Cyclic Redundancy Check ,CRC) CRCCRC碼是一種檢錯、糾錯能力很強的數據校驗碼碼是一種檢錯、糾錯能力很強的數據校驗碼, , 主要用于網絡、主要用于網絡、同步通信及磁表面存儲器等應用場合。同步通信及磁表面存儲器等應用場合。1 1循環(huán)冗余校驗碼的編碼方法循環(huán)冗余校驗碼的編碼方法循環(huán)冗余校驗碼由兩部分組成循環(huán)冗余校驗碼由兩部分組成, , 左邊為信息位左邊為信息位, , 右邊為校驗位。若右邊為校驗位。若信息位為信息位為k k位位, , 校驗位為校驗位為r r位位, , 則該校驗碼被稱為則該校驗碼被稱為(k (kr, k)r, k)碼。碼。編碼步

23、驟編碼步驟如下：如下：(1)(1)將待編碼的將待編碼的k k位有效信息位表示為一個位有效信息位表示為一個k k1 1階的多項式階的多項式M(X)M(X)。(2)(2)將將M(X)M(X)左移左移r r位位, , 得到得到M(X).XM(X).Xr r（r r由預選的由預選的r r1 1位的生成多項式位的生成多項式G(X)G(X)決定）。決定）。(3)(3)用一個預選好的用一個預選好的r r1 1位的位的G(X)G(X)對對M(X).XM(X).Xr r作模作模2 2除法。除法。(4)(4)把左移把左移r r位后的的有效信息位與余數作位后的的有效信息位與余數作模模2 2加法加法, , 形成長度為

24、形成長度為k kr r的的CRCCRC碼。碼。 M(X).XM(X).Xr rR(X) R(X) Q(X).G(X) Q(X).G(X) 信息位校驗位k位r位循環(huán)冗余校驗碼的格式M(X)XXr r G(X)Q(X)R(X)G(X)舉例舉例例例: :選擇生成多項式為選擇生成多項式為G(X)G(X)X X4 4X X1(10011),1(10011),請把請把8 8位有效信位有效信息息1111011111110111編碼成編碼成CRCCRC碼。碼。 解：解：步驟步驟1 1：M(X) M(X) X X7 7X X6 6+ X+ X5 5X X4 4 + X+ X2 2X X1 1 +1 +1 111

25、10111 11110111 步驟步驟2 2: M(X). X: M(X). X4 4 111101111111011100000000 ( ( 即左移即左移4 4位）位） 步驟步驟3 3：模：模2 2除，除，M(X)XM(X)X4 4G(X)G(X) 111101111111011100000000 10011100111110010111100101111111111001110011，即，即R(X)R(X)11111111步驟步驟4 4：模：模2 2加，得到循環(huán)冗余碼為加，得到循環(huán)冗余碼為M(X)XM(X)X4 4R(X) R(X) 111101111111011100000000 11

26、111111 111101111111011111111111 糾錯原理糾錯原理 由于由于M(X).XM(X).Xk kQ(X). G(X)Q(X). G(X)R(X)R(X)，根據模，根據模2 2加的規(guī)則加的規(guī)則M(X). XM(X). Xk k R(X)R(X)Q(X).G(X)Q(X).G(X)R(X)R(X)R(X)R(X)Q(X).G(X)Q(X).G(X)上式表明上式表明, , 合法的合法的CRCCRC碼應當能被生成多項式整除。碼應當能被生成多項式整除。若若CRCCRC碼不能被生成多項式整除，說明出現了信息的傳送差錯。碼不能被生成多項式整除，說明出現了信息的傳送差錯。 467261

27、6E7A4672616E7AE580E5800發(fā)送數據接收數據CRCCRC校驗生成多項式的選擇生成多項式的選擇生成多項式被用來生成生成多項式被用來生成CRCCRC碼碼, , 但并非任何一個但并非任何一個K K1 1位的多位的多項式都能作為生成多項式用項式都能作為生成多項式用, , 它它應滿足下列要求：應滿足下列要求：（1 1）任何一位出錯都應使余數不為）任何一位出錯都應使余數不為0 0。（2 2）不同位出錯應使余數不同。）不同位出錯應使余數不同。（3 3）對余數繼續(xù)作模）對余數繼續(xù)作模2 2除法，應使余數循環(huán)。除法，應使余數循環(huán)。生成多項式的選擇主要靠經驗，但已有生成多項式的選擇主要靠經驗，但

28、已有3 3種多項式種多項式成為標準成為標準而被廣泛運用而被廣泛運用, , 它們都具有極高的檢錯率它們都具有極高的檢錯率, , 分別是分別是: :CRC-12CRC-12X X1212X X1111X X3 3X X2 2X X1 1CRC-16CRC-16X X1616X X1515X X2 21 1CRC-CCITTCRC-CCITTX X1616X X1212X X5 51 1CRC-32CRC-32= X= X3232X X2626X X23+ 23+ X X2222X X1616X X1212+ + X X1111X X1010X X8+ 8+ X X7 7X X5 5X X4 4 +

29、X+X2 2X X1 1注：在RFID標準ISO/IEC14443中，采用的是CRC-CCITT的生成多項式； ISO18000-6中，采用的是CRC-16 多項式除法，可用除法電路來實現。除法電路的主體由一組移位寄存器和模2加法器(異或單元)組成。以CRC-ITU為例，它由16級移位寄存器和3個加法器組成，見下圖(編碼/解碼共用)。編碼、解碼前將各寄存器初始化為1，信息位隨著時鐘移入。當信息位全部輸入后，從寄存器組輸出CRC結果。補充：7、循環(huán)冗余校驗（CRC）循環(huán)冗余校驗是另一種比較常見的差錯控制方法。它是將整個數據塊當成一個連續(xù)的二進制數據M(x)用另一個多項式（生成多項式G(x)）來除，然后利用余數進行校驗。任意一個由二進制位串組成的代碼都可以和一個系數僅為0和1取值的多項式一一對應。例如：代碼1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+