海明碼是壹種可以糾正壹位差錯的編碼。它是利用在信息位為k位,增加r位冗余位,構成壹個n=k+r位的碼字,然後用r個監督關系式產生
的r個校正因子 來區分無錯和在碼字中的n個不同位置的壹位錯。它必需滿足以下關系式:
2r>=n+1 或 2r>=k+r+1
海明碼的編碼效率為:
R=k/(k+r)
式中 k為信息位位數
r為增加冗余位位數
2.海明碼的生成與接收
方法壹:
1)海明碼的生成。
例1.已知:信息碼為:"0010"。海明碼的監督關系式為:(推導過程略)
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
求:海明碼碼字。
________________________________________________________________
註:如果K=4,那麽
s0=a0+a1+a3+a4+a6
s1=a0+a2+a3+a5+a6
s2=a1+a2+a3+a7
s3=a4+a5+a6+a7
______________________________________________________________________
解:1)由監督關系式知冗余碼為a2a1a0。
2)冗余碼與信息碼合成的海明碼是:"0010a2a1a0"。
設S2=S1=S0=0,由監督關系式得:
a2=a4+a5+a6=1
a1=a3+a5+a6=0
a0=a3+a4+a6=1
因此,海明碼碼字為:"0010101"
2)海明碼的接收。
例2.已知:海明碼的監督關系式為:
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
接收碼字為:"0011101"(n=7)
求:發送端的信息碼。
解:1)由海明碼的監督關系式計算得S2S1S0=011。
2)由監督關系式可構造出下面錯碼位置關系表:
S2S1S0 錯碼位置
000 無錯
001 a0
010 a1
100 a2
011 a3
101 a4
110 a5
111 a6
3)由S2S1S0=011查表得知錯碼位置是a3。
4)糾錯--對碼字的a3位取反得正確碼字:"0 0 1 0 1 0 1"
5)把冗余碼a2a1a0刪除得發送端的信息碼:"0010"
3)由S2S1S0=011查表得知錯碼位置是a3。
4)糾錯--對碼字的a3位取反得正確碼字:"0 0 1 0 1 0 1"
5)把冗余碼a2a1a0刪除得發送端的信息碼:"0010"
方法二:(不用查表,方便編程)
例題:
.已知海明碼的監督關系式為:
S2=a2+a3+a4+a6
S1=a1+a4+a5+a6
S0=a0+a3+a4+a5
接收端收到的碼字為a6a5a4a3a2a1a0=1010100,問在最多壹位錯的情況下發送端發送的碼字是什麽?(寫出推演過程)。
答案:
1.(1)根據海明碼的監督關系式
S2=a2+a3+a4+a6
S1=a1+a4+a5+a6
S0=a0+a3+a4+a5,得下表:
S2S1S0
000
001
010
011
100
101
110
111
錯誤位置
無錯
a0
A1
a5
a2
a3
a6
a4
(2)將a6a5a4a3a2a1a0=1010100分別代入海明碼的監督關系式
得:(其中“+”號表示異或運算);
s2=1+0+1+1=1
s1=0+1=0+1=0
s0=0+0+1+0=1
即s2s1s0=101
(3)查表可知:接收到的比特序列第4位有錯,正確的應是:
a6a5a4a3a2a1a0=1011100
某公司采用壹條租用專線(Leased line)與在外地的分公司相連,使用的MODEN的數據傳輸率為2400bps,現有數據12*106 字節,若以異步
方式傳送,不加校驗位,1位停止位則最少需要多少時間(以秒為單位)才能傳輸完畢?
答: 以異步方式傳送壹個字節數據,需要加1位起始位,1位停止位,實際需要傳送8+2=10位. 故: (12*106*10)/2400 =5*104秒
若10Mbps的CSMA/CD局域網的節點最大距離為2.5Km,信號在媒體中的傳播速度為2*108 m/s,求該網的最短幀長
解答: 10Mbps表示 每秒鐘傳輸10*106 位數據 ,
CSMA/CD,信號需要返回才能知道有沒有碰撞,所以傳輸壹次信號需要兩倍距離, 先算出信號在節點完整傳輸壹次所需要的時間: 2*(2.5*103)/2*108 =2.5*10-5 秒 ,然後算出幀長 =2.5*10-5 * 10*106 =250bit
** 某令牌環媒體長度為10Km,信號傳播速度為200m/us,數據傳輸率為4Mbps,環路上***有50個站點,每個站點的接口引入1位延遲,
試計算環的比特長度.
解答: {(10*10^3 )/(200*10^6)} * 4*10^6 =0.2*10^3=200bit
200+50*1=250bit
壹***是250比特
用速率為1200bps的調制解調器(無校驗位,壹位停止位),則每分鐘最多傳輸的漢字是多少(漢字為雙字節)
解答:(1200*60)/{(8+2)*2}=3600個
設信息碼為101 ,采用生成多項式G(X)為G(X)=X^4+X^3+X^2+X+1,生成的循環碼是多少?
解答:略 1011101
在數據傳輸過程中,若接收方收到發送方送來的信息為11010110111,生成多項式G(X)=X4+X3+x+1,接收方收到的數據是否
正確?(寫出判斷依據及推演過程)。
解答:(1)因為G(X)=X4+X3+x+1,故其對應的二進制比特串為11011
(2)又因為接收到的信息為11010110111,故可有二進制除法。
(3)11010110111÷11011(除法的詳細過程略)
(4)因上述除法的余數為0,故接收到的信息為正確信息。即發送過程中未出現錯誤
設LAN采用路由器與X.25 網相連,現在路由器每秒轉發200個分組,分組長度為X.25網的標準128字節,問:
(1)路由器的轉發速率是多少Mbps?
(2)計算壹分鐘內的通信費用(通信量按段來計算,每段64字節,需0.03元)
解答:(1)路由器的轉發速率為
200(分組/秒)*128(字節/分組)
=2560字節/秒
=2560*8位/秒
=0.02048Mbps
(2)壹分鐘傳輸的費用
={(2560*60)/ 64} * 0.03
=72元/分鐘