信道編碼技術(shù)

DRFID

原理與應(yīng)用yuanyc@njcit.cn任務(wù)要求1

會(huì)對(duì)傳輸數(shù)據(jù)進(jìn)行奇偶校驗(yàn)編碼2

會(huì)對(duì)傳輸數(shù)據(jù)進(jìn)行循環(huán)冗余校驗(yàn)編碼信道編碼技術(shù)必在RFID系統(tǒng)中，數(shù)據(jù)傳輸?shù)耐暾源嬖趦蓚€(gè)方面的問題：※1、外界的各種干擾可能使數(shù)據(jù)傳輸產(chǎn)生錯(cuò)誤；※2、多個(gè)標(biāo)簽同時(shí)占用信道使發(fā)送數(shù)據(jù)產(chǎn)生碰撞?！\(yùn)用數(shù)據(jù)檢驗(yàn)(差錯(cuò)檢測(cè))和防碰撞算法可分別解決這兩個(gè)問題?！鵕FID系統(tǒng)采用無接觸的方式進(jìn)行數(shù)據(jù)傳輸，由于無線通信環(huán)境的復(fù)雜性，這一傳

輸過程很容易受到干擾，導(dǎo)致數(shù)據(jù)傳輸錯(cuò)誤。51

FE

2BC6AE

66

信道

51

FE2BAE66干擾圖7-12

數(shù)據(jù)傳輸差錯(cuò)示意圖※為了提高系統(tǒng)傳輸?shù)目煽啃?，可以采用信道編碼(又稱差錯(cuò)控制編碼)

,

對(duì)

出

現(xiàn)

的差錯(cuò)進(jìn)行控制，常用的方法有奇偶校驗(yàn)、循環(huán)冗余校驗(yàn)、漢明碼等。差錯(cuò)控制編碼進(jìn)行差錯(cuò)控制的基本思想稱為“冗余校驗(yàn)”

:(1)

編碼：在原始數(shù)據(jù)(即有效數(shù)據(jù)位)的基礎(chǔ)上增加冗余數(shù)據(jù)(即校驗(yàn)位)

,

按照某種規(guī)律將有效數(shù)據(jù)位和校驗(yàn)位一起編碼，得到數(shù)據(jù)校驗(yàn)碼；(2)

譯

碼：按同一約定規(guī)律對(duì)收到的數(shù)據(jù)校驗(yàn)碼進(jìn)行分析，并判斷約定規(guī)律是

否被破壞。①若未被破壞，則正確，從中取出有效數(shù)據(jù)即可；②若被破壞，則有錯(cuò)，根據(jù)約定規(guī)律被破壞后的某些特征對(duì)出錯(cuò)位進(jìn)行定位，

從而可自動(dòng)糾正錯(cuò)誤。分組碼※通常原始數(shù)字信號(hào)是分組傳輸?shù)?，例如每k個(gè)二進(jìn)制碼元為一組(稱為信息組),

經(jīng)信道編碼后轉(zhuǎn)換為每n個(gè)碼元

一組的碼字(碼組),這里n>k,信道編碼是利用“冗余”來提高抗干擾能力的，也就是以降低信息傳輸速率為代價(jià)來減少錯(cuò)誤的，或者說是用削弱有效性來增強(qiáng)可靠性的?！纸M碼通常表示為(n,k)?！鵱-碼組的總位數(shù)，又稱為碼組的長度(碼長),※k

-

碼組中信息碼元的數(shù)目，※r-

碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。k個(gè)信息位-

→——碼長n=k+rao時(shí)

間(

r個(gè)監(jiān)督位—···aran-2ar-1an-1·奇偶校驗(yàn)編碼※分為奇校驗(yàn)和偶校驗(yàn)※編碼規(guī)律：■偶校驗(yàn)：配一個(gè)校驗(yàn)位，使整個(gè)校驗(yàn)碼(包括有效數(shù)據(jù)位和校驗(yàn)位)中“1”的

個(gè)數(shù)為偶數(shù)；■奇校驗(yàn)：配一個(gè)校驗(yàn)位，使整個(gè)校驗(yàn)碼(包括有效數(shù)據(jù)位和校驗(yàn)位)中“1”的

個(gè)數(shù)為奇數(shù)；優(yōu)點(diǎn)：開銷小，編譯碼簡單缺

點(diǎn)：只能發(fā)現(xiàn)

一位或奇數(shù)位出錯(cuò)，并且不能發(fā)現(xiàn)哪位出錯(cuò)。因?yàn)闄C(jī)器中一位出錯(cuò)的概率比幾位同時(shí)出錯(cuò)的概率要高的多，所以這種方法有較高的實(shí)用價(jià)值。校驗(yàn)方程設(shè)7位信息碼組為C7C6C5C4C3C2C1,

校驗(yàn)碼為CO,田表示模2相加。對(duì)偶校驗(yàn)，當(dāng)滿足

C7田C6田C5田C4田C3田C2田C1田C0=0時(shí)，為合法碼對(duì)奇校驗(yàn)，當(dāng)滿足

C7田C6田C5田C4田C3田C2田C1田C0=1時(shí)，為合法碼有效數(shù)據(jù)偶校驗(yàn)碼奇校驗(yàn)碼1011001010110010010110010?1011001110110011110110011?奇偶校驗(yàn)編碼必對(duì)二進(jìn)制數(shù)1011001計(jì)算偶校驗(yàn)位。※數(shù)據(jù)0110100使用奇校驗(yàn)，求校驗(yàn)位的值?！羰褂闷嫘ｒ?yàn)，接收數(shù)據(jù)01001101(末位為校驗(yàn)位),是否存在傳輸錯(cuò)誤?

※接收數(shù)據(jù)10110111(末位為校驗(yàn)位),若未出錯(cuò)，判斷是奇校驗(yàn)還是偶校驗(yàn)。

必若兩位同時(shí)翻轉(zhuǎn)，奇偶校驗(yàn)?zāi)芊駲z測(cè)?為什么?※ASCII

字符'C'(二進(jìn)制01000011)使用偶校驗(yàn)，求傳輸?shù)谋忍亓?。縱向冗余校驗(yàn)(LRC)

編碼必縱向冗余校驗(yàn)是將傳輸?shù)臄?shù)據(jù)塊的所有字節(jié)按位相加(異或運(yùn)算，模

2加法),其結(jié)果作為校驗(yàn)字節(jié)附加再傳輸數(shù)據(jù)之后。接收端對(duì)整個(gè)LRC字符串作異或運(yùn)算，結(jié)果為0則說明傳輸無誤?？v向冗余校驗(yàn)也稱

為代碼和校驗(yàn)?！鵏RC主要用于快速校驗(yàn)很小的數(shù)據(jù)塊兒(如32B)

。

在射頻識(shí)別系統(tǒng)中，由于標(biāo)簽的容量一般較小，每次交換的數(shù)據(jù)量也不大，所以這種算法

還是比較適合的?！簜鬏?shù)?6進(jìn)制數(shù)據(jù)塊為4672616

E7A,

求校驗(yàn)碼01000110011100100110000101101110011110104672616E7A4672616E7A41010001100111001001100001011011100111101001000001縱向冗余校驗(yàn)(LRC)

編碼數(shù)據(jù)傳輸前生成LRC

數(shù)據(jù)傳輸后生成LRCLRC

01000001410000000000LRC圖2-19

LRC

校驗(yàn)示例說明XORXOR必給定數(shù)據(jù)塊(每行一個(gè)字節(jié)，十六進(jìn)制表示):※0x32×

0x45※0x7A※要求：使用偶校驗(yàn)計(jì)算縱向冗余校驗(yàn)(LRC)

字節(jié)，結(jié)果用十六進(jìn)制表示?！蟀l(fā)送ASCII字符串"HELLO"

(每個(gè)字符占1字節(jié)),添加縱向偶校驗(yàn)LRC

字節(jié)。必給出完整的傳輸數(shù)據(jù)(字符ASCII值：H=0x48,E=0x45,L=0x4C,O=0x4F)。※0x32→00110010※0x45→01000101※0x7A→01111010※縱向異或：

00001101→0x0D※算LRC:※0x48④0x45=0×0D※0×0D④0x4C=0x41※0x41④0x4C=0×0D※0×0D④0x4F=0x42※0x480x450x4C0x4C0x4F

0x42。循環(huán)冗余校驗(yàn)碼----CRC

碼※循還冗余校驗(yàn)碼(Cyclic

Redundancy

Check)是一種檢錯(cuò)、糾錯(cuò)能

力很強(qiáng)的數(shù)據(jù)校驗(yàn)碼，主要用于網(wǎng)絡(luò)、同步通信等應(yīng)用場(chǎng)合。※CRC校驗(yàn)原理：必先在要發(fā)送的幀后面附加一個(gè)數(shù)(這個(gè)就是用來校驗(yàn)的校驗(yàn)碼，但要注意，這里

的數(shù)也是二進(jìn)制序列的，下同),生成一個(gè)新幀發(fā)送給接收端?！@個(gè)附加的數(shù)不是隨意的，它要使所生成的新幀能與發(fā)送端和接收端共同選定的

某個(gè)特定數(shù)整除(注意，這里不是直接采用二進(jìn)制除法，而是采用一種稱之為“模2

除法”)?！竭_(dá)接收端后，再把接收到的新幀除以(同樣采用“模2除法”)這個(gè)選定的除數(shù)。因?yàn)樵诎l(fā)送端發(fā)送數(shù)據(jù)幀之前就已通過附加一個(gè)數(shù)，做了“去余”處理(也就已經(jīng)能

整除了),所以結(jié)果應(yīng)該是沒有余數(shù)。如果有余數(shù)，則表明該幀在傳輸過程中出

現(xiàn)了差錯(cuò)

。模2運(yùn)算※CRC

碼是基于模2運(yùn)算來建立編譯碼規(guī)律的校驗(yàn)碼※模2運(yùn)算：

以按位模2相加為基礎(chǔ)，運(yùn)算時(shí)不考慮進(jìn)位和借位。模2除(用模2減求余數(shù))上商原則：部分余數(shù)的首位為1,商取1;部分余數(shù)的首位為0,商取0。當(dāng)部分余數(shù)位數(shù)小于除數(shù)位數(shù)時(shí)，該余數(shù)為最后余數(shù)。例

如

：

商余數(shù)【說明】“模2除法”與“算術(shù)除法”類似，但它既不

向上位借位，也不比較除數(shù)和被除數(shù)的相同位數(shù)

值的大小，只要以相同位數(shù)進(jìn)行相除即可。。模2加減(異或)0±0=00±1=11±0=1

1±1=0。模2乘(用模2加求和)例如

：練一練※計(jì)算1011×101※計(jì)算101001000÷1101110101←Q

(商)P(除數(shù))→

1101101001000←2M

(被除數(shù))11011110110101

110000111

0°11010110000011001101001←R

(余數(shù)),作為FCS

校驗(yàn)規(guī)則：讓校驗(yàn)碼能被某一約定代碼除盡。●若能除盡，表明代碼無錯(cuò)；●若除不盡，余數(shù)將指明出錯(cuò)位置。實(shí)現(xiàn)原理：在k位信息位之后拼接r位校驗(yàn)位。●

問題1:

如何從k位信息位簡便地得到r位校驗(yàn)位?信息位

校驗(yàn)位●

問題2:

如何從k+r位信息碼判斷是否有錯(cuò)?1

2

K

K+1

圖7-13

CRC編碼.

*K+r編碼方法※在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。※任意一個(gè)由二進(jìn)制位串組成的代碼都可以和一個(gè)系數(shù)僅為‘O'和‘1'取值的多項(xiàng)

式

—

—

對(duì)應(yīng)。※例如：代碼1010111對(duì)應(yīng)的多項(xiàng)式為※1*x?+0*x?+1*x?+0*x3+1*x2+1*x1+1*x?,※即：x?+x?+x2+×+1必多項(xiàng)式為x?+x3+x2+X+1,對(duì)應(yīng)的代碼101111。※C(x):

表示發(fā)送的原始數(shù)據(jù)的多項(xiàng)式。例如

C(x)=x?+x3+x2+x+1表示發(fā)送的數(shù)據(jù)為101111?！鵊(x)

:

表示CRC

的生成多項(xiàng)式，是接收方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，由CRC

規(guī)范給定。在整個(gè)傳輸過程中，這個(gè)數(shù)始終保持不變。※R(x):

表示CRC

碼的多項(xiàng)式。R(x)=C(x)*(x<<R)%G(x)※T(x):

表示發(fā)送的原始數(shù)據(jù)加上

CRC

碼之后的多項(xiàng)式。T(x)=C(x)*(X<<R)+R(x)※K:

發(fā)送數(shù)據(jù)的長度。其等于C(x)中的最高次的冪+1。如上例子的C(x)

中，K=5+1=6※R:CRC

碼的長度。

CRC

校驗(yàn)碼位數(shù)=生成多項(xiàng)式位數(shù)-1。※在

K位信息碼后再拼接

R位的校驗(yàn)碼，整個(gè)編碼長度為

N位。因此，

這種編碼也叫(N,K)

碼。※對(duì)于一個(gè)給定的(N,K)

碼，可以證明存在一個(gè)最高次冪為

N-K=R

的多項(xiàng)式G(x)?！鶕?jù)G(x)

可以生成

K

位信息的校驗(yàn)碼，而G(x)

叫做這個(gè)CRC

碼的生

成多項(xiàng)式。N=K+RK位信息碼R位校驗(yàn)碼設(shè)

：

被

除

數(shù)C(x):k

位

待

編

信

息除

數(shù)G(x):

r+

1位?

(生成多項(xiàng)式)余數(shù)R(x):r

位校驗(yàn)位商Q(x)(1)CRC

碼的編碼方法a.將待編碼的k位有效信息位組寫成表達(dá)式：C(x)=Ck-?xk-1+Ck-2xk-2+.....-C?X+C。(C?=0

或

1

)b.將信息位組左移r位，變成多項(xiàng)式C(x)

·Xr;c.

用C(x)

·Xr除以G(x),

所得余數(shù)作為校驗(yàn)位。d.

有效的CRC碼為：C(x)·Xr+R(x)=[Q(x)·G(x)+R(x)]+R(x)=Q(x)·G(x)。所以：CRC碼能夠被G(x)除盡。2026/1/5編碼方法11101i原始數(shù)據(jù)C(x)

110101

左移

R

位補(bǔ)0111010110101111110110101101100110101110010編碼舉例※假設(shè)需要發(fā)送的信息C(x)為1010001101,產(chǎn)生多項(xiàng)式G(x)

對(duì)應(yīng)的代碼為110101,求CRC編碼。※R=5。※C(x)左

移

5

位

后

補(bǔ)

0

,※然后對(duì)移位后的數(shù)做模2除法

運(yùn)

算

，※得余數(shù)R(x)對(duì)應(yīng)的代碼：01110。1101010Lb11.

←CRC

碼R(x)10

←

商

CRC不用←

被除數(shù)110100011011101011

0

1

0

1

0

100000G(x)除數(shù)110101編碼舉例舉例例：選擇生成多項(xiàng)式為G(X)=X?+X+1(10011),請(qǐng)把8位有效信息11110111編碼成CRC碼。編碼練習(xí)例如：對(duì)C(x)=1100,用G(x)=1011,求CRC碼。1.

將信息位組左移r=3位，C(x)

·Xr=M(X)

·X3=11000002.用C(x)·X除以G(x)

,

所得余數(shù)作為校驗(yàn)位。3.

有效的CRC碼[此處為(7,4)碼]為

：C(x)·Xr+R(x)

=1100000+010=1100010。編碼練習(xí)※現(xiàn)假設(shè)選擇的CRC

生成多項(xiàng)式為G(X)=X4+X3+1,要

求出二進(jìn)制序列10110011的CRC

校驗(yàn)碼。

1101010010110011

0000

水

面

11001

11110

11001

11111

11001

11000110010

100余數(shù)，因?yàn)椴粔?位，所以前面一位的0要加上添加的比特位在原數(shù)據(jù)幀后②多項(xiàng)式的位數(shù)位5,則在數(shù)

據(jù)幀的后面加上5-1位0,數(shù)據(jù)

幀變?yōu)?01100110000,然后

使用模2除法除以除數(shù)11001,

得到余數(shù)。③將計(jì)算出來的CRC校驗(yàn)碼

添加在原始幀的后面，真正的

數(shù)據(jù)幀為101100110100,再

把這個(gè)數(shù)據(jù)幀發(fā)送到接收端。④接收端收到數(shù)據(jù)幀后，用上

面選定的除數(shù)，用模2除法除

去，驗(yàn)證余數(shù)是否為0,如果

為0,則說明數(shù)據(jù)幀沒有出錯(cuò)。編碼練習(xí)※①將多項(xiàng)式轉(zhuǎn)化為二進(jìn)制序列，由G(X)=X4+X3