crc可以检出奇数个错误_计算机网络最新章节_陈虹著_掌阅小说网
4.3 差錯控制技術(shù)
物理層的任務(wù)是接收一個原始的比特流，并準備將它傳輸?shù)侥康牡亍Ｔ趥鬏斶^程中傳輸?shù)谋忍亓鱾€數(shù)和內(nèi)容可能會發(fā)生變化，即產(chǎn)生差錯，但目前已有的物理層協(xié)議對傳輸?shù)谋忍亓鞑⒉贿M行任何檢測和糾錯，即物理層并不保證這個比特流的正確傳輸，物理層傳輸產(chǎn)生的差錯將由數(shù)據(jù)鏈路層負責(zé)檢測和糾錯。
4.3.1 差錯產(chǎn)生的原因
差錯是指通信接收方收到的數(shù)據(jù)與發(fā)送方實際發(fā)出的數(shù)據(jù)不一致的現(xiàn)象。這種差錯一般是由通信信道的噪聲產(chǎn)生的，通信信道的噪聲分為熱噪聲和沖擊噪聲兩種。熱噪聲是由傳輸介質(zhì)導(dǎo)體的電子熱運動產(chǎn)生的，它的特點是：時刻存在，幅度較小且強度與頻率無關(guān)，但頻譜很寬，是一類隨機噪聲。由熱噪聲引起的差錯稱為隨機差錯。與熱噪聲相比，沖擊噪聲幅度較大，是引起傳輸差錯的主要原因。沖擊噪聲的持續(xù)時間要比數(shù)據(jù)傳輸中的每個比特發(fā)送時間長(如外界磁場的變換、電源開關(guān)的跳變等)，因而沖擊噪聲可能會引起相鄰多個數(shù)據(jù)位出錯。沖擊噪聲引起的傳輸差錯稱為突發(fā)差錯，它的特點是：差錯呈突發(fā)狀，影響一批連續(xù)的數(shù)據(jù)位。計算機網(wǎng)絡(luò)中的差錯主要是指突發(fā)差錯。
4.3.2 差錯控制方法
差錯控制是指在數(shù)據(jù)通信過程中能發(fā)現(xiàn)或糾正差錯，將差錯限制在盡可能小的允許范圍內(nèi)。常用的差錯控制方法有反饋檢測、自動重傳請求(Automatic Repeat reQuest，ARQ)和前向糾錯(Forward Error Correction，FEC)。
1.反饋檢測
反饋檢測方法又稱回送校驗法，雙方在進行數(shù)據(jù)傳輸時，接收方將接收到的數(shù)據(jù)重新發(fā)回發(fā)送方，由發(fā)送方檢查是否與原始數(shù)據(jù)完全相符。如不相符，則發(fā)送方發(fā)送一個控制信息通知接收方刪去出錯的數(shù)據(jù)，并重新發(fā)送該數(shù)據(jù)；如相符，則發(fā)送下一個數(shù)據(jù)。其原理如圖4-5所示。反饋檢測的特點是：原理簡單，實現(xiàn)容易，可靠性強，但開銷大，信道利用率低。
圖4-5 反饋檢測原理
a)無差錯情況 b)出錯情況
2.自動重傳請求
自動重傳請求是計算機網(wǎng)絡(luò)中較常采用的差錯控制方法。自動重傳請求的原理是：發(fā)送方將要發(fā)送的數(shù)據(jù)附加上一定的冗余檢錯碼一并發(fā)送，接收方則根據(jù)檢錯碼對數(shù)據(jù)進行差錯檢測，如發(fā)現(xiàn)差錯，則接收方返回重傳請求的信息，發(fā)送方在收到請求重傳的信息后，重新傳送數(shù)據(jù)；如沒有發(fā)現(xiàn)差錯，則發(fā)送下一個數(shù)據(jù)幀，如圖4-6所示。為保證通信正常進行，還需引入計時器(防止整個數(shù)據(jù)幀或反饋信息丟失)和幀編號(以防止接收方多次收到同一幀并遞交給網(wǎng)絡(luò)層)。自動重傳請求的特點是：使用檢錯碼(常用的有奇偶校驗碼和CRC碼等)，必須是雙向信道，發(fā)送方需設(shè)置緩沖器。
圖4-6 自動重傳請求原理
a)無差錯情況 b)出錯情況
3.前向糾錯
前向糾錯的原理是發(fā)送方將要發(fā)送的數(shù)據(jù)附加上一定的冗余糾錯碼一并發(fā)送，接收方則根據(jù)糾錯碼對數(shù)據(jù)進行差錯檢測，如發(fā)現(xiàn)差錯，由接收方進行糾正。前向糾錯的特點是使用糾錯碼(糾錯碼編碼效率低且設(shè)備復(fù)雜)，單向信道，發(fā)送方無須設(shè)置緩沖器。
4.3.3 差錯控制編碼
差錯控制編碼的原理是：發(fā)送方對準備傳輸?shù)臄?shù)據(jù)進行抗干擾編碼，即按某種算法附加上一定的冗余位，構(gòu)成一個碼字后再發(fā)送。接收方收到數(shù)據(jù)后進行校驗，即檢查信息位和附加的冗余位之間的關(guān)系，以檢查傳輸過程中是否有差錯發(fā)生。差錯控制編碼分檢錯碼和糾錯碼兩種，檢錯碼是能自動發(fā)現(xiàn)差錯的編碼，糾錯碼是不僅能發(fā)現(xiàn)差錯而且能自動糾正差錯的編碼。計算機網(wǎng)絡(luò)中常用的差錯控制編碼是奇偶校驗碼、循環(huán)冗余碼和海明碼。
1.奇偶校驗碼
奇偶校驗碼是一種通過增加冗余位使得碼字中“1”的個數(shù)恒為奇數(shù)或偶數(shù)的編碼方法。在實際使用時又可分為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗等。
1)垂直奇偶校驗。垂直奇偶校驗又稱為縱向奇偶校驗，它是將要發(fā)送的整個信息塊分為定長
p
位的若干段(比如說
q
段)，在每段后面按“1”的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位奇偶校驗位，如圖4-7所示。在信息(
I
11
，
I
21
，…，
I
p
1
，
I
12
，
I
22
，…，
I
p
2
，…，
I
1
q
，…，
I
pq
)中，每
p
位構(gòu)成一段(即圖4-7中的一列)，共有
q
段(即共有
q
列)。每段加上一位奇偶校驗冗余位，即圖中的
r
i
。
圖4-7 垂直奇偶校驗
r
i
的編碼規(guī)則為：
偶校驗：
r
i
=
I
1
i
+
I
2
i
+…+
I
pi
(i=1，2，3，…，q)
奇校驗：
r
i
=
I
1
i
+
I
2
i
+…+
I
pi
+1 (
i
=1，2，3，…，
q
)
說明：式中的“+”為模2加，即異或運算，只求本位和，進位丟棄。
圖4-7中箭頭給出了串行發(fā)送的順序，即逐位先后次序為
I
11
，
I
21
，…，
I
p
1
，
r
1
，
I
12
，
I
22
，…，
I
p
2
，
r
2
，…，
I
1
q
，
I
2
q
，…，
I
pq
，
r
q
。在編碼和校驗過程中，用硬件方法或軟件方法很容易實現(xiàn)上述連續(xù)半加運算，而且可以邊發(fā)送邊產(chǎn)生冗余位；同樣，在接收方也可以邊接收邊進行校驗后去掉校驗位。
垂直奇偶校驗方法能檢測出每列中的所有奇數(shù)位錯，但檢測不出偶數(shù)位錯。對于突發(fā)錯誤，奇數(shù)位錯與偶數(shù)位錯的發(fā)生概率接近于相等，因而對差錯的漏檢率接近于1/2。
2)水平奇偶校驗。為了降低對突發(fā)錯誤的漏檢率，可以采用水平奇偶校驗方法。水平奇偶校驗又稱為橫向奇偶校驗，它是對各個信息段的相應(yīng)位橫向進行編碼，產(chǎn)生一個奇偶校驗冗余位，如圖4-8所示。
圖4-8 水平奇偶校驗
r
i
編碼規(guī)則為：
偶校驗：
r
i
=
I
i
1
+
I
i
2
+…+
I
iq
(i=1，2，3，…，p)
奇校驗：
r
i
=
I
i
1
+
I
i
2
+…+
I
iq
+1 (
i
=1，2，3，…，
p
)
若每個信息段就是一個字符的話，這里的
q
就是發(fā)送信息塊中的字符數(shù)。
水平奇偶校驗不但可以檢測出各段同一位上的奇數(shù)位錯，而且還能檢測出突發(fā)長度<
p
的所有突發(fā)錯誤。按發(fā)送順序，從圖4-8可以看出“突發(fā)長度<
p
”的突發(fā)錯誤必然分布在不同的行中，且每行一位，所以可以檢出差錯，它的漏檢率比垂直奇偶校驗方法低。
3)水平垂直奇偶校驗。同時進行水平奇偶校驗和垂直奇偶校驗就構(gòu)成了水平垂直奇偶校驗，又稱為縱橫奇偶校驗，如圖4-9所示。
圖4-9 水平垂直奇偶校驗
若水平垂直都采用偶校驗，則
r
i
,
j
的編碼規(guī)則如下。
r
i
,
q
+1
=
I
i
1
+
I
i
2
+…+
I
iq
(i=1，2，3，…，p)
r
p
+1,
j
=
I
1
j
+
I
2
j
+…+
I
pj
(j=1，2，3，…，q)
r
p
+1,
q
+1
=
r
p
+1,1
+
r
p
+1,2
+…+
r
p
+1,
q
=
r
1,
q
+1
+
r
2,
q
+1
+…+
r
p
,
q
+1
水平垂直奇偶校驗?zāi)軝z測出所有3位或3位以下的錯誤(因為此時至少在某一行或某一列上有一位錯)、奇數(shù)位錯、突發(fā)長度≤
p
+1的突發(fā)錯誤以及很大一部分偶數(shù)位錯。測量表明，這種方式的編碼可使誤碼率降至原誤碼率的百分之一到萬分之一。水平垂直奇偶校驗不僅可檢錯，還可用來糾正部分差錯。例如，數(shù)據(jù)塊中僅存在1位錯時，便能確定出錯碼的位置就在某行和某列的交叉處，從而可以糾正它。
2.循環(huán)冗余碼
循環(huán)冗余校驗方法是數(shù)據(jù)通信中差錯檢測的重要方法，它對隨機錯碼和突發(fā)錯碼均能以較低的冗余度進行嚴格檢查。
(1)循環(huán)冗余碼的計算方法
循環(huán)冗余校驗碼(Cyclic Redundancy Check，CRC)也稱為多項式碼，簡稱CRC校驗碼。在發(fā)送方產(chǎn)生一個循環(huán)冗余校驗碼，附加在信息位后面一起發(fā)送到接收方，接收方將收到的信息按發(fā)送方形成循環(huán)冗余校驗碼相同的算法進行校驗以檢測是否出錯。
其計算過程如下：
1)確定信息多項式
M
(
x
)。將待發(fā)送的二進制位串看成是一個多項式的系數(shù)，該多項式稱為信息多項式
M
(
x
)。任何一個由二進制數(shù)位串組成的代碼都可以和一個只含有0和1兩個系數(shù)的多項式建立一一對應(yīng)關(guān)系，一個
k
位數(shù)據(jù)幀可以看成是從
x
k
-1
到
x
0
的
k
次多項式的系數(shù)序列，這個多項式的階數(shù)為
k
-1，最高位(最左邊)是
x
k
-1
項的系數(shù)，下一位是
x
k
-2
的系數(shù)，依次類推。
例如：若信息位為1011011(7位)，則
M
(
x
)=1×
x
6
+0×
x
5
+1×
x
4
+1×
x
3
+0×
x
2
+1×
x
1
+1×
x
0
=
x
6
+
x
4
+
x
3
+
x
+1；同樣，若
M
(
x
)=
x
5
+
x
4
+
x
2
+1，則對應(yīng)的二進制位串為110101。
2)確定一個素多項式
G
(
x
)。
G
(
x
)稱為生成多項式，生成多項式的作用是和信息多項式進行計算產(chǎn)生余數(shù)多項式。生成多項式的最高位和最低位必須是1。目前，國際標準中生成多項式有以下幾類。
CRC-12：
x
12
+
x
11
+
x
3
+
x
2
+
x
+1
CRC-16：
x
16
+
x
15
+
x
2
+1
CRC-CCITT-1：
x
16
+
x
12
+
x
5
+1
CRC-32：
x
32
+
x
26
+
x
23
+
x
22
+
x
16
+
x
12
+
x
11
+
x
10
+
x
8
+
x
7
+
x
5
+
x
4
+
x
2
+
x
+1
3)計算余數(shù)多項式
R
(
x
)。設(shè)
G
(
x
)為
r
階，發(fā)送方計算
x
r
M
(
x
)
/G
(
x
)(模2除法)，得到余數(shù)多項式
R
(
x
)，商舍掉。依據(jù)群論的相關(guān)理論，可以證明
R
(
x
)具有發(fā)現(xiàn)錯誤的能力。
4)形成碼元多項式
C
(
x
)。發(fā)送方將
R
(
x
)附在
M
(
x
)之后，組成碼元多項式
C
(
x
)，然后將其發(fā)送出去。
5)接收方檢驗。當接收方收到碼元多項式
C′
(
x
)后，計算
C′
(
x
)
/G
(
x
)(模2除法)，得到新的余數(shù)多項式
R′
(
x
)。如果
R′
(
x
)=0，則認為傳輸沒有錯誤，否則，可以確定傳輸中產(chǎn)生了差錯。
目前，CRC校驗已由成熟的硬件完成，因此校驗速度很快，冗余度也不大，是應(yīng)用最廣泛的一種校驗碼。
設(shè)信息位為
m
位，生成多項式
G
(
x
)為
r
階，則計算CRC校驗碼的步驟簡化如下。
1)在信息碼尾部附加
r
個0，成為
m
+
r
位二進制位串，相應(yīng)多項式為
x
r
·
M
(
x
)。
2)按模2除法用
G
(
x
)對應(yīng)的位串去除
x
r
·
M
(
x
)對應(yīng)的位串，得到余數(shù)
R
(
x
)所對應(yīng)的位串。
3)按模2加法從
x
r
M
(
x
)對應(yīng)的位串中加上得到的余數(shù)
R
(
x
)所對應(yīng)的位串，其結(jié)果就是要傳送的帶CRC校驗碼的數(shù)據(jù)。
【例4-1】設(shè)信息位
M
=101001101，生成多項式
G
(
x
)=
x
4
+
x
3
+
x
+1，試計算信息
M
的CRC校驗碼
。
【解】
由已知
，r
=4，生成多項式
G(x)
對應(yīng)的位串為11011
。x
r
M(x)
對應(yīng)的位串為1010011010000。利用短除法計算如下：
余數(shù)
R
為0010
(
補足
r
=4位
)，
因此，信息
M
=101001101的CRC校驗碼為
1010011010000+0010=101001101
0010
。
【例4-2】在數(shù)據(jù)傳輸過程中，若接收方收到發(fā)送方發(fā)送的信息為10110011010，其生成多項式
G
(
x
)=
x
4
+
x
3
+1，問接收方收到的數(shù)據(jù)是否正確？(寫出判斷依據(jù)和推演過程
)
【解】
由題意知，在數(shù)據(jù)通信過程中采用的是循環(huán)冗余校驗碼
(
CRC碼
)
進行數(shù)據(jù)檢錯。發(fā)送方在發(fā)送的數(shù)據(jù)塊中加入足夠的冗余位以滿足檢錯需要。用數(shù)據(jù)多項式與生成多項式
G(x)
進行運算得到校驗和
(
余數(shù)
)，
將校驗和附加在數(shù)據(jù)幀尾部，并使帶有校驗和的幀所對應(yīng)的多項式能被
G(x)
除盡，然后將帶有校驗和的數(shù)據(jù)幀發(fā)送出去，當接收方接收時，用
G(x)
去除它，若余數(shù)為0，則表示傳輸正確，否則表示傳輸出錯。
本題中，如果接收信息
/G(x)，
余數(shù)為0，則收到的數(shù)據(jù)正確，否則出錯。
因為
G(x)
=
x
4
+
x
3
+1，其對應(yīng)的位串為11001，所以10110011010/11001的模2除法的推演過程如下：
10110011010/11001的模2除的余數(shù)
R
=0，因此，接收數(shù)據(jù)正確。
(2)循環(huán)冗余碼的檢錯能力
CRC碼的檢錯能力隨著生成多項式
G
(
x
)的不同而不同。在CRC碼中如果使用
r
位校驗碼，生成多項式
G
(
x
)的次數(shù)應(yīng)為
r
，且生成多項式
G
(
x
)必須包含常數(shù)項“1”，否則校驗碼的最低有效位(Least Significant Bit，LSB)將始終為0。如何選擇一個好的生成多項式需要一定的數(shù)學(xué)理論，這里只進行簡要分析。
1)發(fā)送方發(fā)送的CRC碼多項式可以寫成
C
(
x
)=
M
(
x
)·
G
(
x
)=
x
n-k
·
M
(
x
)+
R
(
x
)
式中，
n
為CRC碼的總位數(shù)；
M
(
x
)為信息碼多項式；
G
(
x
)為生成多項式；
R
(
x
)為余數(shù)多項式。
2)如果發(fā)送的
C
(
x
)在傳輸過程中產(chǎn)生了差錯，使接收方收到的消息變成了
C′
(
x
)，即產(chǎn)生了差錯。則接收方收到的消息可以表示為
C′
(
x
)=
C
(
x
)+
E
(
x
)
式中，
E
(
x
)為差錯多項式。
3)接收方用
C′
(
x
)除以
G
(
x
)，則可得
C′
(
x
)
/G
(
x
)=［
C
(
x
)+
E
(
x
)］
/G
(
x
)
用
C
(
x
)=
M
(
x
)·
G
(
x
)代入得
C′
(
x
)
/G
(
x
)=［
M
(
x
)·
G
(
x
)］
/G
(
x
)+
E
(
x
)
/G
(
x
)
因此，當接收到的碼字無差錯，即
E
(
x
)=0時，
C′
(
x
)將被
G
(
x
)整除。當接收到的碼字出現(xiàn)差錯，而差錯的數(shù)目在碼的檢錯范圍內(nèi)時，將有
E
(
x
)
/G
(
x
)=
Q
e
(
x
)+
R
e
(
x
)
/G
(
x
)
式中，
Q
e
(
x
)是
E
(
x
)被
G
(
x
)所除而得的商；
R
e
(
x
)為其余數(shù)。這時
C′
(
x
)
/G
(
x
)=
Q′
(
x
)+
Q
e
(
x
)+
R
e
(
x
)
/G
(
x
)=
Q
(
x
)+
R
e
(
x
)
/G
(
x
)
式中，
Q′
(
x
)是
C′
(
x
)被
G
(
x
)所除而得的商。
因此，接收方可以根據(jù)余數(shù)
R
e
(
x
)是否為零來判斷接收碼字是否有錯。
當然，接收到的有差錯碼字也有可能被
G
(
x
)整除，此時的差錯碼字就無法檢出，這種錯誤稱為不可檢錯誤。不可檢錯誤中的錯碼數(shù)必定超過了這種編碼的檢錯能力。
如果生成多項式
G
(
x
)選擇得當，CRC是一種很有效的差錯校驗方法。理論上可以證明
G
(
x
)選擇得當?shù)腃RC碼的檢錯能力具有以下特點。
1)能檢出全部1位錯(單錯)，即
E
(
x
)中只有一個“1”。假設(shè)信息位序列中某一位有錯，由于
G
(
x
)的
x
0
項為1，因此，
E
(
x
)除以
G
(
x
)的余數(shù)
R
e
(
x
)必定不為0。
2)能檢出全部離散的2位錯(雙錯)，即
E
(
x
)中有離散的兩個“1”。假設(shè)信息位序列中有第
i
位和第
j
位錯，且有
i
<
j
，那么，只要選取的
G
(
x
)是不能整除二項式(
x
j-i
+1)的多項式，且其階(
n-k
)>(
j-i
)，就可以檢出全部的雙錯。
3)能檢出奇數(shù)個錯，即
E
(
x
)中有1、3、5、…個“1”。因為奇數(shù)項錯誤多項式必不含因子(
x
+1)，所以只要選取的
G
(
x
)含有(
x
+1)因子，即可檢出全部奇數(shù)個錯。
4)能檢出全部長度小于等于(
n-k
)的突發(fā)錯。
5)能以相當大的概率檢出長度大于
r
(校驗位長度)的連續(xù)的突發(fā)錯。
例如，采用CRC-16的CRC碼可以檢出全部1位錯、2位錯、奇數(shù)個錯；全部16位或16位以下突發(fā)錯；99.997%的17位突發(fā)錯以及99.998%的18位或更長的突發(fā)錯。
CRC除了能檢查出離散錯外，還能檢查出位數(shù)相當長的突發(fā)錯。
3.海明碼
在數(shù)據(jù)通信過程中，解決差錯問題的另一種方法就是在每個待發(fā)送的數(shù)據(jù)塊上附加足夠的冗余信息，如果出錯，使接收方能夠推導(dǎo)出發(fā)送方實際送出的應(yīng)該是什么樣的比特串。
海明碼是一種可以糾正一位差錯的編碼。對于
m
位數(shù)據(jù)位(信息位)，若增加
r
位冗余位(校驗位)，則組成總長度為
n
位(
n
=
m
+
r
)的編碼，稱為
n
位碼字。為了能糾正單比特錯，
m
和
r
之間應(yīng)該滿足一定的關(guān)系。對于
m
位數(shù)據(jù)位，其有效碼字有2
m
個，對于每一個有效碼字，均附加一個固定的
r
位的冗余位，形成一個特定的
n
(
n
=
m
+
r
)位碼字。當且僅當其中一位改變時，都可以形成
n
個無效但可以糾錯的碼字(知道出錯的位置)，即有
n
+1個可識別的碼字(1個有效碼字，
n
個無效但可識別的碼字)。
對于
m
位數(shù)據(jù)位產(chǎn)生的2
m
個有效碼字，共有2
m
(
n
+1)個可識別的碼字，2
n
個可識別及不可識別(出錯的)的碼字，因此有2
m
(
n
+1)≤2
n
，將
n
=
m
+
r
代入，得
m
+
r
+1≤2
r
為了糾正單比特錯，
m
和
r
應(yīng)該滿足上述關(guān)系式。
海明碼的編碼方法是將碼字內(nèi)的各位從最右邊開始按順序依次編號，第1位為1，第2位為2，…，第
n
位為
n
，其中編號為2
i
的位(1，2，4，8，…)為海明碼的校驗位，即海明碼校驗位不是附加在數(shù)據(jù)位的頭或尾，而是分散在數(shù)據(jù)位中，分別占用2
i
位置。其余位順序填入
m
位數(shù)據(jù)。每個校驗位的取值應(yīng)使得包括自身在內(nèi)的一些位的集合服從規(guī)定的奇偶性，因此，海明碼利用的原理仍是奇偶檢驗原理。下面舉例說明海明碼的形成方法。
例如，設(shè)信息位
m
=7，則由
m
+
r
+1≤2
r
，得
r
=4，所以海明碼長
n
=11位，設(shè)海明碼字為x11x10x9x8x7x6x5x4x3x2x1，其中x1、x2、x4和x8為海明校驗碼，計算海明碼的校驗位方法可以采用如圖4-10所示的形式，海明碼校驗位編碼(校驗表達式)計算表達式如下。
x1=x3+x5+x7+x9+x11
x2=x3+x6+x7+x10+x11
x4=x5+x6+x7
x8=x9+x10+x11
接收方驗證收到的信息是否正確，采用的方法是重新計算海明碼校驗位
xi
′，但采用海明碼監(jiān)督表達式進行計算，海明碼監(jiān)督表達式如下。
圖4-10 海明碼校驗碼形成示意圖
x1′=x1+x3+x5+x7+x9+x11
x2′=x2+x3+x6+x7+x10+x11
x4′=x4+x5+x6+x7
x8′=x8+x9+x10+x11
若
xi′
=0(
i
=1，2，4，8，…)，則表示該信息傳輸正確，
xi
′中任何一位不為0，則表示該信息傳輸出錯，出錯位為
xi′
值，如
xi′
=110，則表示出錯位是x6。如果信息位出錯則需糾正，校驗位出錯則不需糾正。
海明碼編碼方法不唯一，編號1既可從左也可從右開始，但解碼與編碼需一一對應(yīng)。
【例4-3】假定傳送信息位
M
為1010110，求它的海明碼
。
【解】
已知信息位
M
的位數(shù)
m
=7，設(shè)冗余位為
r
位，根據(jù)公式
m
+
r
+1≤2
r
計算得
：r
=4
海明碼：
計算海明碼校驗位：
x1=x3+x5+x7+x9+x11=0+1+0+1+1=1
x2=x3+x6+x7+x10+x11=0+1+0+0+1=0
x4=x5+x6+x7=1+1+0=0
x8=x9+x10+x11=1+0+1=0
所以，計算得到海明碼為：101
00110001?
【例4-4】假定傳送信息位
M
為8位，接收方收到的信息為101110100110，試判斷該傳輸是否出錯？如果出錯是否需要糾正？并求出發(fā)送方發(fā)送的原始信息
。
【解】
已知信息位
M
的位數(shù)
m
=8，設(shè)冗余位為
r
位，根據(jù)公式
m
+
r
+1≤2
r
計算得
：r
=4
接收方收到的信息為1 0 1 1 1 0 1 0 0 1 1 0
x12 x11 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1
判斷接收方收到的信息是否正確，需要根據(jù)海明碼監(jiān)督表達式計算
xi
′，若
xi′
=0
(i
=1，2，4，8
，…)，
則表示該信息傳輸正確，否則出錯。
海明碼監(jiān)督表達式計算如下：
x1′=x1+x3+x5+x7+x9+x11=0+1+0+0+1+0=0
x2′=x2+x3+x6+x7+x10+x11=1+1+1+0+1+0=0
x4′=x4+x5+x6+x7+x12=0+0+1+0+1=1
x8′=x8+x9+x10+x11+x12=1+1+1+0+1=0
因為得到的計算結(jié)果x8′ x4′ x2′ x1′為：0100，不為0，因此，該傳輸存在錯誤。監(jiān)督碼值為0100，即為4，則出錯位為x4，而x4是校驗位，因此，不需糾錯。
因此，發(fā)送方發(fā)送的原始信息是10111010
1
110。
海明碼屬于分組碼，分組碼是一組固定長度的碼組，一般用符號(
n
，
k
)表示，其中
n
是碼組的總位數(shù)，又稱為碼組的長度(碼長)，
k
是碼組中信息碼元的數(shù)目，
r
=
n-k
為碼組中的監(jiān)督碼元數(shù)目。通常用于前向糾錯。
在采用糾錯碼或檢錯碼的編碼方案中，基本的數(shù)據(jù)處理單元通常稱為碼字，由數(shù)據(jù)比特和冗余比特構(gòu)成。兩個碼字之間對應(yīng)比特取值不同的比特個數(shù)稱為這兩個碼字的海明距離。例如，10101和00110從第一位開始依次有第1位、第4位、第5位不同，則海明距離為3。海明距離表明：假設(shè)兩個碼字的海明距離為
d
，則需要
d
個比特差錯才能將其中一個碼字轉(zhuǎn)換成另一個碼字。
在一個有效編碼集中，任意兩個碼字的海明距離的最小值(
d
min
)稱為該編碼集的海明距離。一種編碼的檢錯能力和糾錯能力取決于它的海明距離。為了檢測
d
個比特錯，需要使用海明距離為
d
+1的編碼方案，因為在這種編碼方案中，
d
個單比特錯不可能將一個有效碼字改編成另一個有效碼字。當接收方接收到一個無效碼字時，就知道已經(jīng)發(fā)生了傳輸錯誤。同樣，為了糾正
d
個比特錯，需要使用海明距離為2
d
+1的編碼方案，因為在這種編碼方案中，合法碼字之間的距離足夠遠，即使發(fā)生了
d
個比特錯，仍然更接近于原始碼字而不是其他碼字，從而可以唯一確定原來的碼字以達到糾錯的目的。
d
min
與分組碼的糾、檢錯能力存在以下關(guān)系。
● 當
d
min
≥
e
+1時，可檢出
e
個錯誤。
● 當
d
min
≥2
t
+1時，具有糾正
t
個錯誤的能力。
● 當
d
min
≥
t
+
e
+1
(e
>
t)
時，具有同時檢出
e
個錯誤、糾正
t
個錯誤的能力。
63Oq6IAujjHZoZ65HNTBWPuMsQzkYnMUW9x6jkOv5M6keRxLt5xvskwAGRBkXYpj
總結(jié)
以上是生活随笔為你收集整理的crc可以检出奇数个错误_计算机网络最新章节_陈虹著_掌阅小说网的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python数据展示平台_Python获
- 下一篇： vue js 定义对象_JS标准内置对象