ch常用差錯(cuò)控制編碼方法實(shí)用

會(huì)計(jì)學(xué)1ch常用差錯(cuò)控制編碼方法實(shí)用

差錯(cuò)控制的核心就是抗干擾編碼，為了提高通信系統(tǒng)的檢錯(cuò)和糾錯(cuò)能力，人們創(chuàng)造出許多差錯(cuò)控制編碼，比較常用的有奇偶校驗(yàn)編碼、循環(huán)冗余校驗(yàn)編碼、卷積碼等。

第1頁/共63頁3.3.1奇偶校驗(yàn)編碼

又稱奇偶監(jiān)督編碼，或垂直冗余校驗(yàn)（VRC，VerticalRedundancyCheck），在計(jì)算機(jī)數(shù)據(jù)傳輸中應(yīng)用廣泛。

編碼規(guī)則：發(fā)送端，將所要傳輸?shù)臄?shù)據(jù)碼元分組，在分組數(shù)據(jù)后面加一位監(jiān)督碼（校驗(yàn)位），使得該組碼連同監(jiān)督碼在內(nèi)的碼組中“1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。接收端，按照編碼規(guī)則檢查如果發(fā)現(xiàn)不符，就說明產(chǎn)生差錯(cuò)，但不能明確差錯(cuò)的具體位置即不能糾錯(cuò)。第2頁/共63頁公式表示：設(shè)碼組長度為n，表示為（an-1,an-2……,a1,c0）其中前n-1位為信息位，第n位c0為監(jiān)督位①奇校驗(yàn)：an-1⊕an-2⊕……⊕a1⊕c0=1即c0=an-1⊕an-2⊕……⊕a1⊕1②偶校驗(yàn)：an-1⊕an-2⊕……⊕a1⊕c0=0即c0=an-1⊕an-2⊕……⊕a1奇偶校驗(yàn)編碼

第3頁/共63頁特點(diǎn)：無論信息位為多少位，監(jiān)督位只有一位。只能檢測信息碼組中奇數(shù)個(gè)錯(cuò)誤，對偶數(shù)個(gè)錯(cuò)誤無能為力；信息位越長,效率越高.奇偶校驗(yàn)編碼

第4頁/共63頁實(shí)例寫出下列二進(jìn)制序列的偶校驗(yàn)碼：①1001110②0101111寫出下列二進(jìn)制序列的奇校驗(yàn)碼：①1100101②011001010011100

010111111100101101100100第5頁/共63頁3.3.2方陣校驗(yàn)碼又稱行列監(jiān)督碼，矩陣碼，縱向冗余校驗(yàn)碼（LRC，LognitudinalRedundancyCheck），它的碼元受到行和列兩個(gè)方向奇偶監(jiān)督，又稱二維奇偶校驗(yàn)碼。編碼規(guī)則：使的每個(gè)碼元受到縱向（列）和橫向兩次監(jiān)督；將欲發(fā)送的信息碼按行排成一個(gè)矩陣，矩陣中每一行為一碼組，每行的最后加上一個(gè)奇偶監(jiān)督碼元；矩陣中的每一列是由不同碼組相同位置的碼元組成，在每列最后也加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶校驗(yàn)；最后按行或列碼組的順序發(fā)送。第6頁/共63頁

X X X X X X X X

X X X X X X X X X X X X X XX X X X X X X X X X X X X X X X X X

方陣校驗(yàn)碼結(jié)構(gòu)第7頁/共63頁實(shí)例

信息碼元監(jiān)督碼元（偶）111001001101001010000111000100011100111101101111發(fā)送端在發(fā)送時(shí)則按列(或行）的順序傳輸：111010

110011

100001

010100

……001111接收端仍將碼元排成發(fā)送時(shí)方陣形式，然后按行、列進(jìn)行奇偶校驗(yàn)第8頁/共63頁特點(diǎn)：可以檢測出某行某列上的奇數(shù)個(gè)錯(cuò)誤和長度不大于行（列）數(shù)的突發(fā)錯(cuò)誤?？梢詸z測出某行或某列上偶數(shù)個(gè)錯(cuò)誤不能糾正差錯(cuò)數(shù)正好是4的倍數(shù)且位置在行列矩陣/子矩陣的4個(gè)頂點(diǎn)上的差錯(cuò)

方陣校驗(yàn)碼第9頁/共63頁失效！??！

信息碼元監(jiān)督碼元（偶）111001001101001010000111000100011100111101101111第10頁/共63頁3.3.3恒比碼(定比碼)編碼規(guī)則：恒比碼中每碼組中“1”和“0”個(gè)數(shù)保持恒定比例，接收端在檢測接收到的碼組中“1”的數(shù)目是否對就知道是否出錯(cuò)。實(shí)例：我國電傳機(jī)傳輸漢字時(shí)使用數(shù)字代表漢字，采用的所謂“保護(hù)電碼”就是一種“3：2”或“5中取3”的恒比碼。C52=10個(gè)許用碼組英文電報(bào)采用“7中取3”或“4：3”恒比碼，共有C73=35個(gè)許用碼組第11頁/共63頁3.3.4正反碼_能簡單糾錯(cuò)的編碼多用于10單位電碼的前向自動(dòng)糾錯(cuò)設(shè)備中，能糾正一位差錯(cuò)，發(fā)現(xiàn)大部分兩位錯(cuò)，差錯(cuò)編碼和差錯(cuò)控制結(jié)合起來控制。以10單位電碼為例：n=k+r且k=r=51.編碼規(guī)則：(1)當(dāng)信息碼中“1”的個(gè)數(shù)為奇數(shù)時(shí)，監(jiān)督碼與信息碼相同（正碼）1010110101(2)當(dāng)信息碼中“1”的個(gè)數(shù)為偶數(shù)時(shí)，監(jiān)督碼與信息碼相反（反碼）1010001011第12頁/共63頁2.解碼方法：(1)將接收到信息碼與監(jiān)督碼按相應(yīng)的碼位模2加（異或），得到一個(gè)新的5位碼組。(2)根據(jù)接收到的信息碼中“1”的個(gè)數(shù)：if“1”的個(gè)數(shù)為奇數(shù)，則取新5位碼組為校驗(yàn)碼組if“1”的個(gè)數(shù)為偶數(shù)，則取新5位碼組的反碼為校驗(yàn)碼組正反碼第13頁/共63頁正反碼判決表校驗(yàn)碼組的組成判決差錯(cuò)情況1全“0”無錯(cuò)24個(gè)“1”一個(gè)“0”信息碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中0所對應(yīng)的位置34個(gè)“0”一個(gè)“1”監(jiān)督碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中1所對應(yīng)的位置4其他差錯(cuò)個(gè)數(shù)>1個(gè)（3），最后可按下表，根據(jù)檢驗(yàn)碼組中“1”的個(gè)數(shù)進(jìn)行判斷及糾正可能發(fā)現(xiàn)的錯(cuò)碼第14頁/共63頁實(shí)例：已知信息碼11010使用正反碼差錯(cuò)控制方式，試問下列接收端收到的數(shù)據(jù)是否有錯(cuò)？能否糾正？①1101011010②1001011010③1101001010④1000011010第15頁/共63頁（1）編碼：11010（信息碼）11010（監(jiān)督碼）→1101011010（正反碼）（2）解碼：①接收端1101011010②接收端1001011010③接收端1101001010④接收端1000011010判斷：第16頁/共63頁11010+1101000000

結(jié)果為0，正確。第17頁/共63頁10010+1101001000由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，10111，信息碼中有一位出錯(cuò)，根據(jù)判決2，出錯(cuò)位置就是檢驗(yàn)碼組中0所對應(yīng)的位置，糾正后為11010第18頁/共63頁11010+0101010000由于接收信息碼中為奇數(shù)個(gè)1，所以檢驗(yàn)碼不變，根據(jù)判決3，監(jiān)督碼碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中1所對應(yīng)的位置，糾正后為11010第19頁/共63頁10000+0101001010檢驗(yàn)碼中1的個(gè)數(shù)>1，根據(jù)判決4，無法判斷和糾錯(cuò)第20頁/共63頁作業(yè)已知信息碼10010使用正反碼差錯(cuò)控制方式，試問下列接收端收到的數(shù)據(jù)是否有錯(cuò)？能否糾正？①1101001101②1001010010③1001001101④1001001001第21頁/共63頁11010+0110110111由于接收信息碼中為奇數(shù)個(gè)1，所以檢驗(yàn)碼不變，根據(jù)判決2，信息碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中0所對應(yīng)的位置，糾正后為10010。第22頁/共63頁10010+1101001000由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，10111，信息碼中有一位出錯(cuò)，根據(jù)判決2，出錯(cuò)位置就是檢驗(yàn)碼組中0所對應(yīng)的位置，糾正后為11010第23頁/共63頁10010+0110111111由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，11111,1的個(gè)數(shù)大于1,結(jié)果錯(cuò)誤,不能糾正第24頁/共63頁10000+0101001010檢驗(yàn)碼中1的個(gè)數(shù)>1，根據(jù)判決4，無法判斷和糾錯(cuò)第25頁/共63頁

3.3.5循環(huán)冗余校驗(yàn)編碼（CRC）

CyclicRedundancychecking(CRC)循環(huán)冗余校驗(yàn)，又稱多項(xiàng)式碼。在循環(huán)冗余校驗(yàn)中，不是通過將各比特位相加來得到期望的校驗(yàn)，而是通過在數(shù)據(jù)單元末尾加一串冗余比特，稱作循環(huán)冗余校驗(yàn)碼或循環(huán)冗余校驗(yàn)余數(shù)，使得整個(gè)數(shù)據(jù)單元可以被另一個(gè)預(yù)定的二進(jìn)制數(shù)所整除。第26頁/共63頁1.CRC校驗(yàn)基本思想

CRC校驗(yàn)的基本思想是：

(1)根據(jù)欲發(fā)的k位信息生成一個(gè)r比特的序列，稱為幀校驗(yàn)序列FCS（FramecheckingSeries）。（2）求出實(shí)際發(fā)送的數(shù)據(jù)幀（k+r位），這個(gè)幀所對應(yīng)二進(jìn)制序列恰好能夠被某個(gè)預(yù)先確定的數(shù)（生成多項(xiàng)式）整除。（3）接收器用相同的數(shù)（生成多項(xiàng)式）去除傳來的幀。如果無余數(shù)，則認(rèn)為無差錯(cuò)；如果余數(shù)不為0，剛認(rèn)為傳輸出錯(cuò)。第27頁/共63頁奇偶校驗(yàn)對一個(gè)字符校驗(yàn)一次，適合異步通訊；而CRC對一個(gè)數(shù)據(jù)塊（frame）校驗(yàn)一次，適合同步通訊。在串行同步通信中，幾乎都使用這種校驗(yàn)方法。如磁盤信息的讀/寫等。2.CRC校驗(yàn)常用場合

第28頁/共63頁CRC碼生成和校驗(yàn)基本分為三步：第一步：在數(shù)據(jù)單元(k位）的末尾加上r個(gè)0。r是一個(gè)比預(yù)定除數(shù)的比特位數(shù)(r十1)少1的數(shù)。第二步：采用二進(jìn)制除法將新的加長的數(shù)據(jù)單元（k+r位)除以除數(shù)。由此除法產(chǎn)生的余數(shù)就是循環(huán)冗余碼校驗(yàn)碼。3.CRC碼的生成

第29頁/共63頁第三步：求CRC循環(huán)冗余校驗(yàn)碼(K+r)被除數(shù)+r(余數(shù))如果余數(shù)位數(shù)小于r，最左的缺省位數(shù)為0。如果余數(shù)為0,則r=0。CRC碼的生成

第30頁/共63頁CRC碼校驗(yàn)：到達(dá)接收方的數(shù)據(jù)單去除以用來產(chǎn)生循環(huán)冗余校驗(yàn)余數(shù)的G（X）。如果余數(shù)0，將通過檢驗(yàn)。如果余數(shù)非零，將通不過檢驗(yàn)。4.CRC碼的校驗(yàn)

第31頁/共63頁

任何一個(gè)二進(jìn)制數(shù)序列可以和一個(gè)只含有0和1兩個(gè)系數(shù)的代數(shù)多項(xiàng)式建立起一一對應(yīng)的關(guān)系。因此，用來求CRC碼的那個(gè)除數(shù)通常用多項(xiàng)式來表示。原因如下：代數(shù)多項(xiàng)式很短可以通過多項(xiàng)式來進(jìn)行概念的數(shù)學(xué)證明。5.多項(xiàng)式第32頁/共63頁多項(xiàng)式

任何一個(gè)n位的二進(jìn)制數(shù)都可以用一個(gè)n-1次的多項(xiàng)式來表示,這種多項(xiàng)式叫碼多項(xiàng)式（又叫信息多項(xiàng)式）

。碼多項(xiàng)式與二進(jìn)制序列之間的一一對應(yīng)關(guān)系：（an-1an-2……a1a0）N

A(x)=an-1Xn-1+an-2Xn-2+……+a1X+a0X0碼多項(xiàng)式第33頁/共63頁多項(xiàng)式二進(jìn)制序列實(shí)例以n=3位二進(jìn)制數(shù)為例

二進(jìn)制數(shù)對應(yīng)多項(xiàng)式

000

001

010

011 100 101

111

01xx+1x2x2+1x2+x+11011011x6+x4+x3+x+1x5+x4+x2+x110110第34頁/共63頁碼多項(xiàng)式運(yùn)算法則:二進(jìn)制碼多項(xiàng)式的加減運(yùn)算為⊕模2加運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對應(yīng)項(xiàng)系數(shù)進(jìn)行模2加減。乘除運(yùn)算與普通多項(xiàng)式類似；模2加減：即各位做不帶進(jìn)位、借位的按位加減。這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算。即加法和減法等價(jià)。碼多項(xiàng)式第35頁/共63頁生成多項(xiàng)式G(x):求CRC碼時(shí)所用的“除數(shù)”所對應(yīng)的多項(xiàng)式叫生成多項(xiàng)式。在串行通信中通常使用下列三種生成多項(xiàng)式G（X）來產(chǎn)生CRC碼。CRC-16：G(x)=X16+X15+X2+1，美國二進(jìn)制同步系統(tǒng)中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推薦。CRC-32：G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+1X7+X5+X4+X2+X+1碼多項(xiàng)式第36頁/共63頁循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過程。CRC校驗(yàn)器的功能完全像發(fā)生器一樣，當(dāng)收到附加了CRC碼的數(shù)據(jù)后，做同樣的模2除法。如果余數(shù)是全0，則將CRC碼丟棄，接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù)。6.CRC碼生成器和校驗(yàn)器

第37頁/共63頁CRC校驗(yàn)碼的生成器和校驗(yàn)器r個(gè)比特0數(shù)據(jù)g(x)CRC校驗(yàn)碼r+1r余數(shù)先發(fā)數(shù)據(jù)位后發(fā)校驗(yàn)位g(x)余數(shù)r+1r數(shù)據(jù)0接收，非0拒絕數(shù)據(jù)發(fā)送方接收方第38頁/共63頁0G(X)第39頁/共63頁111010100011010CRC校驗(yàn)碼信息碼

CRC冗余校驗(yàn)碼第40頁/共63頁7.CRC碼性能

CRC碼是很有效的差錯(cuò)校驗(yàn)方法。除了正好數(shù)據(jù)塊的比特值是按除數(shù)值變化的錯(cuò)誤外，循環(huán)冗余校驗(yàn)(CRC)將檢測出其他所有錯(cuò)誤。而且，常用的CRC除數(shù)通常有17，或是33個(gè)比特，使得不可檢測的錯(cuò)誤可能降低到幾乎近于零。CRC接收電路再配上適當(dāng)?shù)挠布娐凡粌H可以檢錯(cuò)，而且可以糾錯(cuò)，糾錯(cuò)能力很強(qiáng)特別適合檢測突發(fā)性錯(cuò)誤，在數(shù)據(jù)通信中得到較廣泛的應(yīng)用。第41頁/共63頁檢錯(cuò)性能能檢測出全部單個(gè)錯(cuò)誤能檢測出全部隨機(jī)二位錯(cuò)誤能檢測出全部奇數(shù)個(gè)錯(cuò)誤能檢測出全部長度小于k位的突發(fā)錯(cuò)誤能以[1-（1/2）k-1]概率檢測出長度為（k+1）位的突發(fā)性錯(cuò)誤第42頁/共63頁課堂練習(xí)題設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）=X5+X2+1，試求出信息序列1101010101011的循環(huán)校驗(yàn)碼CRC（要求寫出計(jì)算步驟）。第43頁/共63頁設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）=X5+X4+X2+1，試求出信息序列1010001100的CRC循環(huán)校驗(yàn)碼（要求寫出計(jì)算步驟）。第44頁/共63頁3.3.6卷積碼1.概述2.編碼器3.解碼器第45頁/共63頁1.概述前面介紹的編碼方法都是線性分組碼，即監(jiān)督碼只負(fù)責(zé)監(jiān)督檢驗(yàn)本碼組中的信息碼元。如果每組的監(jiān)督碼元不但與本組碼的信息碼元有關(guān)，而且還與前面若干組信息碼元有關(guān)，即不是分組校驗(yàn)而是每個(gè)監(jiān)督碼元對它的前后碼元都實(shí)行監(jiān)督，前后相連，具有連環(huán)監(jiān)督的作用；因此我們稱為連環(huán)碼，即卷積碼。卷積碼由P.Elias于1955年最先提出，整個(gè)編解碼過程一環(huán)扣一環(huán)，連鎖地進(jìn)行下去。第46頁/共63頁2.編碼器aiai-1…a2a1a0R2R1信息入口連環(huán)碼輸出模2加法器ab…b3a3b2a2b1a1b0a0移位寄存器移位寄存器b0=a0b1=a0⊕a1b2=a1⊕a2

b3=a2⊕a3…bi=ai-1⊕ai第47頁/共63頁2.編碼器（1）編碼器輸出過程第一次，前半拍開關(guān)接到a輸出a0，后半拍開關(guān)倒向b輸出b0=a0⊕0=a0第二次，前半拍開關(guān)接到a輸出a1，后半拍開關(guān)倒向b輸出b1=a1⊕a0……第i次，前半拍開關(guān)接到a輸出ai，后半拍開關(guān)倒向b輸出bi=ai⊕ai-1

第48頁/共63頁2.編碼器（2）連環(huán)碼結(jié)構(gòu)：信息碼: an-1an-2……ai……a1a0

監(jiān)督碼

bn-1bn-2……bi……b1b0連環(huán)碼輸出序列

bn-1an-1…biai…b2a2b1a1b0a0

即“信息碼監(jiān)督碼信息碼……”，一個(gè)信息碼與一個(gè)校驗(yàn)碼構(gòu)成一組但每個(gè)校驗(yàn)碼bi=ai⊕ai-1除了與本組碼有關(guān)還與前一組信息碼有關(guān)，故稱為卷積碼。第49頁/共63頁第50頁/共63頁3.解碼器R1R2R3&a’b’接收到的監(jiān)督碼計(jì)算出的監(jiān)督碼判決電路123解碼輸出解碼輸入Si

Si-1連環(huán)碼入口第51頁/共63頁解碼器解碼思路：移位寄存器R1、R2及模2加法器1構(gòu)成與發(fā)送端一樣的編碼器，用來計(jì)算監(jiān)督碼和解碼輸出。用模2加法器2將計(jì)算出的監(jiān)督碼與接收到的監(jiān)督碼進(jìn)行比較，即先對ai’編碼產(chǎn)生新的監(jiān)督碼bi’’，再與bi’異或,if結(jié)果為0then正確else出錯(cuò)。根據(jù)第2步的輸出進(jìn)行判決，由判決電路完成由判決結(jié)果通過加法器3輸出結(jié)果第52頁/共63頁

解碼器設(shè)接收的碼序列…b3’a3’b2’a2’b1’a1’b0’a0’其解碼過程為：（1）第零拍，前半拍電子開關(guān)倒向a’,移位寄存器R1移出a0’,R2移出0，故加法器1結(jié)果生成一個(gè)a0’⊕0=a0’。后半拍電子開關(guān)倒向b’結(jié)果,接收到b0’，生成S0=b0’（=a0’）⊕a0’，R3為0故與門輸出0又R2輸出為0，所以加法器3輸出為0第53頁/共63頁

解碼器（2）第一拍前半拍電子開關(guān)倒向a’，R1移出工a1’,R2移出a0’加法器1輸出a1’⊕a0’后半拍電子開關(guān)倒向b’，加法器2輸入b1’,加法器2輸出

S1=

b1

’⊕（a1’⊕a0’）在第一拍后半期當(dāng)b1

’出現(xiàn)在輸入端時(shí)，就可對a0’做判斷。第54頁/共63頁解碼器（3）第二拍前半拍電子開關(guān)倒向a’，R1移出工a2’,R2移出a1’，加法器1輸出a2’⊕a1’后半拍電子開關(guān)倒向b’，加法器2輸入b2’加法器2輸出

S2=

b2

’⊕（a2’⊕a1’）在第二拍后半期當(dāng)b2

’出現(xiàn)在輸入端時(shí)，就可對a1’做判斷。（4

）依次類推，當(dāng)b3’出現(xiàn)在輸入端時(shí)，就可對a2’做判斷……規(guī)則如P69。第55頁/共63頁解碼方程模2加法器2的輸出對我們判決正確性至關(guān)重要。第56頁/共63頁解碼器判決規(guī)則：當(dāng)Si及Si+1都為“0”時(shí)，a