第二章-數據通信基礎
計算機網絡採用數據通信方式傳輸數據。數據通信和電話網絡中的語音通信不同,也和無線電廣播通信不同,它有其自身的規律和特點。數據通信技術的發展與計算機技術的發展密切相關,又互相影響,形成了一 門獨立的學科。這門學科主要研究對計算機中的二進制數據進行傳輸、交換和處理的理論、方法以及實現技術。本章講述數據通信的基本理論和基礎知識,為學習以後各章內容做好準備。
2.1 數據通信的基本概念
通信的目的就是傳遞信息。通信中產生和發送信息的一 端叫作信源,接收信息的 一 端叫作信宿,信源和信宿之間的通信線路稱為信道。信息在進入信道時要變換為適合信道傳輸的形式,在進入信宿時又要變換為適合信宿接收的形式。信道的物理性質不同,對通信的速率和傳輸質量 的 影響也不同 。另外,信息在傳輸過程中可能會受到外界的干擾,把這種干擾稱為噪聲。不同的物理信道受各種干擾的影響不同,例如,如果信道上傳輸的是電信號,就會受到外界電磁場的干擾,光纖信道則基本不受電磁場干擾。以上描述的通信模式忽略了具體通信中的物理過程和技術細節,得到如圖 2-1 所示的通信系統模型。
作為一般的通信系統,信源產生的信息可能是模擬數據,也可能是數字數據。模擬數據取連續值,而數字數據取離散值。在數據進入信道之前要變成適合傳輸的電磁信號,這些信號也可以是模擬的或數字的。模擬信號是隨時間連續變化的信號,這種信號的某種參量 (如幅度、相位和頻率等)可以表示要傳送的信息。電話機送話器輸出的話音信號、電視攝像機產生的圖像信號等都是模擬信號。數字信號只取有限個離散值,而且數字信號之間的轉換幾乎是瞬時的,數字信號以某一瞬間的狀態表示它們傳送的信息。
如果信源產生的是模擬數據並以模擬信道傳輸,則叫作模擬通信;如果信源發出的是模擬數據且以數字信號的形式傳輸,那麼這種通信方式叫數字通信。如果信源發出的是數字數據,當然也可以有兩種傳輸方式,這時無論是用模擬信號傳輸或是用數字信號傳輸都叫作數據通信。可見,數據通信是專指信源和信宿中數據的形式是數字的,在信道中傳輸時可以根據需要採用模擬傳輸方式或數字傳輸方式。
在模擬傳輸方式中,數據進入信道之前要經過調製,變換為模擬的調製信號。由千調製信號的頻譜較窄,因此信道的利用率較高。模擬信號在傳輸過程中會衰減,還會受到噪聲的干擾,如果用放大器將信號放大,混入的噪聲也被放大了,這是模擬傳輸的缺點。在數字傳輸方式中,可以直接傳輸二進制數據或經過二進制編碼的數據,也可以傳輸數字化了的模擬信號。因為數字信號只取有限個離散值,在傳輸過程中即使受到噪聲的干擾,只要沒有畸變到不可辨認的程度,就可以用信號再生的方法進行恢復,對某些數碼的差錯也可以用差錯控制技術加以消除。所以,數字傳輸對千信號不失真地傳送是非常有好處的。另外,數字設備可以大規模集成,比複雜的模擬設備便宜得多。然而,傳輸數字信號比傳輸模擬信號所要求的頻帶要寬得多,因而信道利用率較低。
2.2 信道特性
2 .2.1 信道帶寬
模模擬信道的帶寬如圖 2-2 所示。信道帶寬其中, _f1_是信道能通過的最低頻率,_f2_是信道能通過的最高頻率,兩者都是由信道的物理特性決定的。當組成信道的電路製成了,信道的帶寬就決定了。為了使信號傳輸中的失真小一些,信道要有足夠的帶寬。
數字信道是一種離散信道,它只能傳送取離散值的數字信號。信道的帶寬決定了信道中能不失真地傳輸的脈衝序列的最高速率。一個數字脈衝稱為一個碼元,用碼元速率表示單位時間內信號波形的變換次數,即單位時間內通過信道傳輸的碼元個數。若信號碼元寬度為 T 秒,則碼元速率 B=l/T。碼元速率的單位叫波特 (Baud), 所以碼元速率也叫波特率。早在 1924 年,貝爾實驗室的研究員亨利·奈奎斯特 (Harry Nyquist) 就推導出了有限帶寬無噪聲信道的極限波特率,稱為尼奎斯特定理。若信道帶寬為 w, 則尼奎斯特定理指出最大碼元速率為
奈奎斯特定理指定的信道容量也叫作奈奎斯特極限,這是由信道的物理特性決定的。超過奈奎斯特極限傳送脈衝信號是不可能的,所以要進一步提高波特率必須改善信道帶寬。碼元攜帶的信息橘由碼元取的離散值的個數決定。若碼元取兩個離散值,則一個碼元攜帶1 位信息。若碼元可取 4 種離散值,則一個碼元攜帶兩位信息。總之,一個碼元攜帶的信息 量n (位)與碼元的種類數 N 有如下關係
單位時間內在信道上傳送的信息量(位數)稱為數據速率。在一定的波特率下提高速率的途徑是用一個碼元表示更多的位數。如果把兩位編碼為一個碼元,則數據速率可成倍提高。有公式
其中,R 表示數據速率,單位是每秒位 (bps 或 b/s) 。
數據速率和波特率是兩個不同的概念。僅當碼元取兩個離散值時兩者的數值才相等。對與普通電話線路,帶寬為 3000Hz, 最高波特率為 6000Baud, 最高數據速率可隨著調製方式的不同而取不同的值。這些都是在無噪聲的理想情況下的極限值。實際信道會受到各種噪聲的干擾,因而遠遠達不到按奈奎斯特定理計算出的數據傳送速率。香衣 (Shannon) 的研究表明,有噪聲信道的極限數據速率可由下面的公式計算
這個公式叫作香衣定理,其中, W 為信道帶寬, S 為信號的平均功率, N 為噪聲平均功率,S/N 叫作信噪比。由於在實際使用中 S 與 N 的比值太大,故常取其分貝數(dB) 。分貝與信噪比的關係為
例如,當 S/N=1000時,信噪比為 30dB 。這個公式與信號取的離散值的個數無關,也就是說,無論用
什麼方式調製,只要給定了信噪比,則單位時間內最大的信息傳輸霾就確定了。例如,信道帶寬為 3000Hz, 信噪比為 30dB, 則最大數據速率為
這是極限值,只有理論上的意義。實際上,在 3000Hz 帶寬的電話線上數據速率能達到 9600bps就很不錯了。
綜上所述,有兩種帶寬的概念,在模擬信道,帶寬按照公式 計算,例如 CATV 電纜的帶寬為 600MHz 或 1000MHz; 數字信道的帶寬為信道能夠達到的最大數據速率,例如以太網的帶寬為 10Mbps 或 100Mbps 。兩者可互相轉換。
2.2.2 誤碼率
在有噪聲的信道中,數據速率的增加意味著傳輸中出現差錯的概率增加。用誤碼率來表示傳輸二進制位時出現差錯的概率。誤碼率可用下式表示
在計算機通信網絡中,誤碼率一般要求低千 10-6, 即平均每傳送 l 兆位才允許錯 l 位。在誤碼率低於一定的數值時,可以用差錯控制的辦法進行檢查和糾正。
2.2.3 信道延遲
信號在信道中傳播,從源端到達宿端需要一定的時間。這個時間與源端和宿端的距離有關,也與具體信道中的信號傳播速度有關。以後考慮的信號主要是電信號,這種信號一般以接近光速的速度 (300m/µs) 傳播,但隨傳輸介質的不同而略有差別。例如,在電纜中的傳播速度一般為光速的 77%, 即 200m/µs 左右。
一般來說,考慮信號從源端到達宿端的時間是沒有意義的,但對千一種具體的網絡,我們經常對該網絡中相距最遠的兩個站之間的傳播時延感興趣。這時除了要計算信號傳播速度外,還要知道網絡通信線路的最大長度。例如,500m 同軸電纜的時延大約是 2.5µs, 而衛星信道的時延大約是 270ms 。時延的大小對某些網絡應用(例如交互式應用)有很大影響。
2.3 傳輸介質
計算機網絡中可以使用各種傳輸介質來組成物理信道。這些傳輸介質的特性不同,因而使用的網絡技術不同,應用的場合也不同。下面簡要介紹各種常用的傳輸介質的特點。
2 .3 .1 雙絞線
雙絞線由粗約 1mm 的互相絕緣的一對銅導線絞扭在一起組成,對稱均勻地絞扭可以減少線對之間的電磁干擾。這種雙絞線大量使用在傳統的電話系統中,適用千短距離傳輸,若超過幾千米,就要加入中繼器。在局域網中可以使用雙絞線作為傳輸介質,如果選用高質量的芯線,採用適當的驅動和接收技術,安裝時避開噪聲源,在幾百米之內數據的傳輸速率可達每秒幾十兆位。
雙絞線分為屏蔽雙絞線和無屏蔽雙絞線,如圖 2-3 所示。常用的無屏蔽雙絞線電纜 (Unshielded Twisted Pa ir , UTP) 由不同顏色的(橙、綠、藍、棕) 4 對雙絞線組成 。 屏蔽雙絞線(Shielded Twisted Pair , STP) 電纜的外層由鋁箱包裹著,價格相對高一些,並且需要支持屏蔽功能的特殊連接器和適當的安裝技術,但是傳輸速率比相應的無屏蔽雙絞線高。國際電氣工業協會 (EIA)定義了雙絞線電纜各種不同的型號,計算機綜合佈線使用的雙絞線種類如表 2 - 1 所示 。
由千雙絞線價格便宜,安裝容易,適用千結構化綜合佈線,所以得到了廣泛使用。 通常在局域網中使用的無屏蔽雙絞線的傳送速率是 lOMbps 或 lOOMbps, 隨著 網卡技術的發展 , 短距離甚至可以達到 lOOOMbps 。
2.3.2 同軸電纜
同軸電纜的芯線為銅質導線,外包一層絕緣材料,再外面是由細銅絲組成的網狀外導體,最外面加一層絕緣塑料保護層,如圖 2-4 所示 。 芯線與網狀導體同軸,故名同軸電纜 。 同軸電纜的這種結構,使它具有高帶寬和極好的噪聲抑制特性 。
在局域網中常用的同軸電纜有兩種,一種是特性阻抗為 50.Q 的同軸電纜,用千傳輸數字信號,例如 RG-8 或 RG-11 粗纜和RG-58 細纜。粗同軸電纜適用千大型局域網,它的傳輸距離長,可靠性高,安裝時不 需要切斷電纜,用夾板裝置夾在計算機需要連接的位置。但粗纜必須安裝外收發器,安裝難度大,總體造價高。細纜則容易安裝,造價低,但安裝時要切斷電纜,裝上BNC 接頭,然後連接在 T 型連接器兩端,所以容易產生接觸不良或接頭短路的隱患,這是以太網運行中常見的故障。
通常把表示數字信號的方波所固有的頻帶稱為基帶,所以這種電纜也叫基帶同軸電纜,直接傳輸方波信號稱為基帶傳輸。由千計算機產生的數字信號不適合長距離傳輸,所以在信號進入信道前要經過編碼器進行編碼,變成適合千傳輸的電磁代碼。經過編碼的數字信號到達接收端,再經譯碼器恢復為原來的二進制數字數據。基帶系統的優點是安裝簡單而且價格便宜,但由於在傳輸過程中基帶信號容易發生畸變和衰減,所以傳輸距離不能太長。一般在 1 km 以內,典型的數據速率是 10Mbps 或100Mbps 。
常用的另一種同軸電纜是特性阻抗為 75.Q 的 CATV 電纜(RG-59), 用於傳輸模擬信號,這種電纜也叫寬帶同軸電纜。所謂寬帶,在電話行業中是指比 4kHz 更寬的頻帶,而這裡是泛指模擬傳輸的電纜網絡 。要把計 算機產生的比特流變成模擬信號在 CATV 電纜上傳輸,在發送端和接收端要分別加入調製器和解調器。採用適當的調製技術,一個 6MHz 的視頻信道的數據速率可以達到 36Mbps 。通常採用頻分多路技術 (FDM), 把整個 CATV 電纜的帶寬 (1000MHz)劃分為多個獨立的信道,分別傳輸數據、聲音和視頻信號,實現多種通信業務。這種傳輸方式稱為綜合傳輸,適合於在辦公自動化環境中應用。
寬帶系統與基帶系統的主要區別是模擬信號經過放大器後只能單向傳輸。為了實現網絡節點間的相互連通,有時要把整個帶寬劃分為兩個頻段,分別在兩個方向上傳送信號,這叫分裂配置。有時用兩根電纜分別在兩個方向上傳送,這叫雙纜配置。雖然兩根電纜比單根電纜的價格要貴一些(大約貴 15%), 但信道容量卻提高 1 倍多。無論是分裂配置還是雙纜配置都要使用一個叫作端頭 (headend) 的設備。該設備安裝在網絡的一端,它從一個頻率(或一根電纜)接收所有站發出的信號,然後用另一個頻率(或電纜)發送出去。
寬帶系統的優點是傳輸距離遠,可達幾十千米,而且可同時提供多個信道。然而和基帶系統相比,它的技術更復雜,需要專門的射頻技術人員安裝和維護,寬帶系統的接口設備也更昂貴。
2.3.3 光纜
光纜由能傳送光波的超細玻璃纖維製成,外包一層比玻璃折射率低的材料。進入光纖的光
波在兩種材料的界面上形成全反射,從而不斷地向前傳播,如圖 2-5所示。
光纖信道中的光源可以是發光二極管 (Light Emitting Diode, LED) 或注入式激光 極管
(Injection Laser Diode, ILD) 。這兩種器件在有電流通過時都能發出光脈衝,光脈衝通過光導纖
維傳播到達接收端。接收端有一個光檢測器 光電二極管,它遇光時產生電信號,這樣就形
成了一個單向的光傳輸系統,類似於單向傳輸模擬信號的寬帶系統。如果採用另外的互連方式,
把所有的通信節點通過光纜連接成一個環,環上的信號雖然是單向傳播,但任一節點發出的信
息其他節點都能收到,從而也達到了互相通信的目的,如圖2-6 所示。
光波在光導纖維中以多種模式傳播,不同的傳播模式有不同的電磁場分佈和不同的傳播路
徑,這樣的光纖叫多模光纖(如圖 2-7(a) 所示)。光波在光纖中以什麼模式傳播,這與芯線和包
層的相對折射率、芯線的直徑以及工作波長有關。如果芯線的直徑小到光波波長大小,則光纖
就成為波導,光在其中無反射地沿直線傳播,這種光纖叫單模光纖 (如圖 2-7(b) 所示)。 模光纖比多模光纖的價格更貴。
光導纖維作為傳輸介質,其優點是很多的。首先是它具有很高的數據速率、極寬的頻帶、
低誤碼率和低延遲。數據傳輸速率可達1000Mbps, 甚至更高,而誤碼率比同軸電纜可低兩個數量級,只有 。其次是光傳輸不受電磁干擾,不可能被偷聽,因而安全和保密性能好。最後,光纖重量輕、體積小、鋪設容易。
2.3.4 無線信道
前面提到的由雙絞線、同軸電纜和光纖等傳輸介質組成的信道可統稱為有線信道。這裡要
講到的信道都是通過空間傳播信號,稱之為無線信道。無線信道包括微波、紅外和短波信道,
下面簡略介紹這3種信道的特點。
微波通信系統可分為地面微波系統和衛星微波系統,兩者的功能相似,但通信能力有很大
的差別。地面微波系統由視距範圍內的兩個互相對準方向的拋物面天線組成,長距離通信則需
要多箇中繼站組成微波中繼鏈路。在計算機網絡中使用地面微波系統可以擴展有線信道的連通
範圍,例如在大樓頂上安裝微波天線,使得兩個大樓中的局域網互相連通,這可能比挖地溝埋
電纜的花費更少。
通信衛星可看作是懸在太空中的微波 中繼站。衛星上的轉發器把波束對準地球上的一定區
域,在此區域中的衛星地面站之間就可互相通信。 地面站以一定的頻率段向衛星發送信息(稱
為上行頻段),衛星上的轉發器將接收到的信號放大並變換到另一個頻段上(稱下行頻段)發
回地面接收站。這樣的衛星通信系統可以在一定的區域內組成廣播式通信網絡,特別適合千海
上、空中、礦山、油田等經常移動的工作環境。衛星傳輸供應商可以將衛星信道劃分成許多子
信道出租給商業用戶,用戶安裝甚小孔徑終端系統 (VSAT) 組成衛星專用網,地面上的集中
站作為收發中心與用戶交換信息
微波通信的頻率段為吉兆段的低端,一般是 1~11GHz, 因而它具有帶寬高、容 大的特
點。由千使用了高頻率,因此可使用小型天線,便千安裝和移動。不過微波信號容易受到電磁
干擾,地面微波通信也會造成相互之間的干擾,大氣層中的雨雪會大量吸收微波信號,當長距
離傳輸時會使得信號衰減以至無法接收。另外,通信衛星為了保持與地球自轉同步,一般停在
36 000km 的高空 這樣長的距離會造成 240~280ms 的時延,在利用衛星信道組網時,這樣長的時
延是必須考慮的因素。
最新採用的無線傳輸介質要算紅外線了(如圖 2-8 所示 )。紅外傳輸系統利用牆壁或屋頂反射
紅外線從而形成整個房間內的廣播通信系統。這種系統所用的紅外光發射器和接收器常見千電
視機的遙控裝置中。紅外通信的設備相對便宜 ,可獲得高的帶寬,這是這種通信方式的優點。
其缺點是傳輸距離有限,而且易受室 內空氣狀態(例如有煙霧等)的影響。
無線電短波通信早已用在計算機網絡中了,已經建成的無線通信局域網使用了甚高頻
C30~300MHz) 和超高頻 (300~3000M應)的電視廣播頻段,這個頻段的電磁波是以直線方
式在視距範圍內傳播的,所以用作局部地區的通信是適宜的。早期的無線電局域網(例如
ALOHA系統)是中心式結構一—有一個類似於通信衛星那樣的中心站,每一個主機節點都把天
線對準中心站,並以頻率Ji 向中 心站發送信息,這就是上行線路;中 心站向各主機節點發送信
息時採用另外一個頻率兒進行廣播,這叫下行線路。採用這種網絡通信方式要解決好上行線路
中由千兩個以上的站同時發送信息而發生衝突的問題。後來的無線電局域網採用分佈式結構——沒有中心站,節點機的天線是沒有方向
的,每個節點機都可以發送或接收信息。這種
通信方式適合千由微機工作站組成的資源分
布系統,在不便千建設有線通信線路的地方可
以快速建成計算機網絡。短波通信設備比較便
宜,便於移動,沒有像地面微波站那樣的方向
性,並且中繼站可以傳送很遠的距離。但是,
這種情況容易受到電磁干擾和地形地貌的影
響,而且帶寬比微波通信要小。
2.4 數據編碼
二進制數字信息在傳輸過程中可以採用不同的代碼,各種代碼的抗噪聲特性和定時功能各不相同,實現費用也不一樣。下面介紹幾種常用的編碼方案,如圖2-9所示。
1. 單極性碼
在這種編碼方案中,只用正的(或負的)電壓表示數據。例如,在圖 2-9 中用+3V 表示二
進制數字 "0", 用0V 表示二進制數字 "1" 。單極性碼用在電傳打字機 (TTY) 接口以及 PC與TTY 兼容的接口中,這種代碼需要單獨的時鐘信號配合定時,否則,當傳送一長串0或1時,發送機和接收機的時鐘將無法定時,單極性碼的抗噪聲特性也不好。
2. 極性碼
在這種編碼方案中,分別用正電壓和負 電壓表示二進制數 "0" 和"1"。例如,在圖 2-9 中用
+3V 表示二進制數字 "0", 用-3V 表示二進制數字 "1" 。這種代碼的電平差比單極碼大,因而抗干擾特性好,但仍然需要另外的時鐘信號。
3. 雙極性碼
在雙極性編碼方案中,信號在3個電平(正、負、零)之間變化。一種典型的雙極性碼就
是所謂的信號交替反轉編碼 (Alternate Mark Inversion, AMI) 。在 AMI 信號中,數據流中遇到
"1"時使電平在正和負之間交替翻轉 ,而遇到 "0" 時則保持零電平。雙極性是三進制信號編
碼方法,它與二進制編碼相比抗噪聲特性更好。 AMI 有其內在的檢錯能力,當正負脈衝交替出
現的規律被打亂時容易識別出來,這種情況叫AMI 違例 。這種編碼方案的缺點是當傳送長串"0"
時會失去位同步信息。對此稍加改進的一種方案是 "6 零取代“雙極性碼 B6ZS 即把連續 "0"
用一組代碼代替。這一組代碼中若含有 AMI 違例,便可以被接收機識別出來。
4. 歸零碼
在歸零 (Return to Zero, RZ) 中,碼元中間的信號迴歸到零電平,因此,任意兩個碼元
之間被零電平隔開。與以上僅在碼元之間有電平轉換的編碼方案相比,這種編碼方案有更好的
噪聲抑制特性。因為噪聲對電平的干擾比對電平轉換的干擾要強,而這種編碼方案是以識別電
平轉換邊來判別 "0" 和" I "信號的。圖 2-9 中表示出的是一種雙極性歸零碼。可以看出,從
正電平到零電平的轉換邊表示碼元 "0 "'從負電平到零電平的轉換邊表示碼元 "1 "'同時每
位碼元中間都有電平轉換,使得這種編碼成為自定時的編碼。
5. 雙相碼
雙相碼要求每一位中都要有一個電平轉換。因而這種代碼的最大優點是自定時,同時雙相
碼也有檢測錯誤的功能,如果某一位中間缺少了電平翻轉,則被認為是違例代碼。
6. 不歸零碼
圖2-9 中所示的不歸零碼 (Not Return to Zero, NRZ) 的規律是當" 1 "出現時電平翻轉, 當"0" 出現時電平不翻轉。因而數據 "1" "0" 的區別不是高低電平,而是電平是否轉換。
這種代碼也叫差分碼,用在終端到調制解調器的接口中。這種編碼的特點是實現起來簡單而且費用低 ,但不是自定時的。
7.曼徹斯特編碼
曼徹斯特編碼 (Manchester Code) 是一種雙相碼。在圖 2-9 中,用 高電平到低電平的轉換
邊表示 "0", 用低電平到高電平的轉換邊表示 "1 "'相反的表示也是允許的。位中間的電平轉
換邊既表示了數據代碼,同時也作為定時信號使用。曼徹斯特編碼用在以太網中。
8. 差分曼徹斯特編碼
這種編碼也是一種雙相碼,和曼徹斯特編碼不同的是,這種碼元中間的電平轉換邊只作為
定時信號,不表示數據。數據的表示在千每一位開始處是否有電平轉換:有電平轉換表示 "0",
無電平轉換表示 "1" 。差分曼徹斯特編碼用在令牌環網中。
從曼徹斯特碼和差分曼徹斯特碼的圖形中可以看出,這兩種雙相碼的每一個碼元都要調製
為兩個不同的電平,因而調製速率是碼元速率的2倍。這對信道的帶寬提出了更高的要求,所
以實現起來更困難也更昂貴。但由千其良好的抗噪聲特性和自定時功能,在局域網中仍被廣泛
使用。
9. 多電平編碼
這種編碼的碼元可取多個電平之一,每個碼元可代表幾個二進制位。例如,令 M=2", 設M=4, 則n=2 。若表示碼元的脈衝取4 個電平之 ,則一個碼元可表示兩個二進制位。與雙相
碼相反,多電平碼的數據速率大千波特率,因而可提高頻帶的利用率。但是這種代碼的抗噪聲
特性不好,在傳輸過程中信號容易畸變到無法區分。
在數據通信中,選擇什麼樣的數據編碼要根據傳輸的速度、信道的帶寬、線路的質量以及
實現的價格等因素綜合考慮。
10. 4B/5B 編碼
在曼徹斯特編碼和差分曼徹斯特編碼中,每位中間都有一次電平跳變,因此波特率是數據
速率的兩倍。對千 100Mbps 的高速網絡,如果採用這類編碼方法,就需要 200 兆的波特率,其硬件成本是 100 兆波特率硬件成本的 5~10倍。
為了提高編碼的效率,降低電路成本,可以採用 4B/5B 編碼 這種編碼方法的原理如圖 2-10所示。
這實際上是一種兩級編碼方案 系統中使用不歸零碼,在發送到傳輸介質之前要變成見1就翻不歸零碼(NRZ-1) NRZ-1 代碼序列中1的個數越多,越能提供同步定時信息,但如果遇
到長串的0, 則不能提供同步信息。所以在發送到介質之前還需經過一次 4B/5B 編碼,發送器掃描要發送的位序列,4位分為一組, 然後按照表 2-2 的對應規則變換成5位的代碼。
5位二進制代碼的狀態共有 32 種,在表2-2 中選用的5位代碼中1的個數都不少千兩個。這就保證了在介質上傳輸的代碼能提供足夠多的同步信息。另外,還有 8B/10B 編碼等方法,其原理是類似的。
2.5 數字調製技術
數字數據不僅可以用方波脈衝傳輸,也可以用模擬信號傳輸。用數字數據調製模擬信號叫作數字調製。這一節講述簡單的數字調製技術。
可以調製模擬載波信號的3個參數——幅度、頻移和相移來表示數字數據。在電話系統中
就是傳輸這種經過調製的模擬載波信號的。3種基本模擬調製方式如圖2-11所示。
1. 幅度鍵控 (ASK)
按照這種調製方式,載波的幅度受到數字數據的調製而取不同的值,例如對應二進制 "0",
載波振幅為 "0"; 對應二進制 "1 "'載波振幅取 "1" 。調幅技術雖然實現起來簡單,但抗干擾
性能較差
2. 頻移鍵控 (FSK)
按照數字數據的值調製載波的頻率叫作頻移鍵控。例如,對應二進制 "0" 的載波頻率為, 對應二進制 "1" 的載波頻率為
。這種調製技術的抗干擾性能好,但佔用的帶寬較大。在
有些低速調制解調器中,用這種調製技術把數字數據變成模擬音頻信號傳送。
3. 相移鍵控 (PSK)
用數字數據的值調製載波相位,這就是相移鍵控 。例如,用 180 相移表示 "1 ";用0相移表示0。這種調製方式抗干擾性能好,而且相位的變化也可以作為定時信息來同步發送機和接
收機的時鐘。碼元只取兩個相位值叫2相調製,碼元可取4個相位值叫4相調製。4相調製時,一個碼元代表兩位二進制數(如表 2-3 所示)。採用4相或更多相的調製能提供較高的數據速率,但實現技術更復雜。
可見,數字調製的結果是模擬信號的某個參量(幅度 、頻率或相位)取離散值。這些值與
傳輸的數字數據是對應的,這是數字調製與傳統的模擬調製不同的地方。
4 . 正交幅度調製
所謂正交幅度調製 (Quadrature Amplitude Modulation, QAM) 就是把兩個幅度相同但相位相差90° 的模擬信號合成為一個模擬信號。表 2-4 的例子是把 ASK和PSK 技術結合起來,形
成幅度相位複合調製,這也是一種正交幅度調製技術。由千形成了 16 種不同的碼元,所以每一個
碼元可以表示4位二進制數據,使得數據速率大大提高。
2.6 脈衝編碼調製
模擬數據通過數字信道傳輸時效率高、失真小,而且可以開發新的通信業務,例如,在數
字電話系統中可以提供語音信箱功能。把模擬數據轉化成數字信號,要使用 叫作編碼解碼器
(Codec) 的設備。這種設備的作用和調制解調器的作用相反,它是把模擬數據(例如聲音、圖
像等)變換成數字信號,經傳輸到達接收端再解碼還原為模擬數據。用編碼解碼器把模擬數據
變換為數字信號的過程叫模擬數據的數字化。常用的數字化技術就是脈衝編碼調製技術 (Pul se
Code Modulation, PCM), 簡稱脈碼調製。
2.6.1 取樣
每隔一定的時間,取模擬信號的當前值作為樣本,該樣本代表了模擬信號在某一時刻的瞬
時值。一系列連續的樣本可用來代表模擬信號在某一區間隨時間變化的值。以什麼樣的頻率取樣,才能得到近似千原信號的樣本空間呢?奈奎斯特取樣定理告訴我們:如果取樣速率大千模
擬信號最高頻率的兩倍,則可以用得到的樣本空間恢復原來的模擬信號,即
其中,為取樣頻率,
為取樣週期,
為信號的最高頻率。
2.6.2 量化
取樣後得到的樣本是連續值,這些樣本必須量化為離散值,離散值的個數決定了量化的精度。在圖 2-12 中,把量
化的等級分為 16 級,用 0000~1111 這16 個二進制數分別
代表 0.1 ~1.6 這 16 個不同的電平幅度。
2.6.3 編碼
把量化後的樣本值變成相應的二進制代碼,可以得到相
應的二進制代碼序列,其中每個二進制代碼都可用一個脈衝串 (4 位)來表示,這4位一組的脈衝序列就代表了經 PCM 編碼的模擬信號。
由上述脈碼調製的原理可以看出,取樣的速率是由模擬信號的最高頻率決定的,而量化級
的多少則決定了取樣的精度。在實際使用中,希望取樣的速率不要太高,以免編碼解碼器的工
作頻率太快;也希望量化的等級不要太多,能滿足需要就行了,以免得到的數據量太大 ,所以
這些參數都取下限值。例如,對聲音信號數字化時,由千話音的最高頻率是 4kHz, 所以取樣速率是8kHz 。對話音樣本用 128 個等級量化,因而每個樣本用7位二進制數字表示。在數字信道上
傳輸這種數字化了的話音信號的速率是 7 X 8000=56kbps 。如果對電視信號數字化,由於視頻信
號的帶寬更大 (6MHz), 取樣速率就要求更高,假若量化等級更多,對數據速率的要求也就更
高了。、
2.7 通信方式和交換方式
2.7.1 數據通信方式
1. 通信方向
按數據傳輸的方向分,可以有下面 3 種不同的通信方式。
(1) 單工通信。在單工信道上,信息只能在一個方向傳送,發送方不能接收,接收方也不能發送。信道的全部帶寬都用千由發送方到接收方的數據傳送。無線電廣播和電視廣播都是單 工通信的例子。
(2) 半雙工通信。在半雙工信道上,通信的雙方可交替發送和接收信息,但不能同時發送 和接收。在一段時間內,信道的全部帶寬用千在一個方向上傳送信息,航空和航海無線電臺以 及無線對講機等都是以這種方式通信的。這種方式要求通信雙方都有發送和接收能力,因而比 單工通信設備昂貴,但比全雙工設備便宜。在要求不是很高的場合,多采用這種通信方式,雖 然轉換傳送方向會帶來額外的開銷。
(3) 全雙工通信。這是一種可同時進行雙向信息傳送的通信方式,例如現代的電話通信就 是這樣的。全雙工通信不僅要求通信雙方都有發送和接收設備,而且要求信道能提供雙向傳輸 的雙倍帶寬,所以全雙工通信設備最昂貴。
2. 同步方式
在通信過程中,發送方和接收方必須在時間上保持同步才能準確地傳送信息。前面曾提到 過信號編碼的同步作用,這叫碼元同步。另外,在傳送由多個碼元組成的字符以及由許多字符 組成的數據塊時,通信雙方也要就信息的起止時間取得一致。這種同步作用有兩種不同的方式, 因而對應了兩種不同的傳輸方式。
(1) 異步傳輸。即把各個字符分開傳輸,字符之間插入同步信息。這種方式也叫起止式, 即在字符的前後分別插入起始位("0 ")和停止位(" l ")'如圖 2-13 所示。起始位對接收方的 時鐘起置位作用。接收方時鐘置位後只要在 8~11 位的傳送時間內準確,就能正確接收一個字 符。最後的停止位告訴接收方該字符傳送結束,然後接收方就可以檢測後續字符的起始位了。 當沒有字符傳送時,連續傳送停止位。 加入校驗位的目的是檢查傳輸中的錯誤,一般使用奇偶校驗。異步傳輸的優點是簡單,但 是由千起止位和檢驗位的加入會引入 20%~30%的開銷,傳輸的速率也不會很高。
(2) 同步傳輸。異步傳輸不適合於傳送大的數據塊(例如磁盤文件),同步傳輸在傳送連 續的數據塊時比異步傳輸更有效。按照這種方式,發送方在發送數據之前先發送一串同步字符 SYNC, 接收方只要檢測到連續兩個以上 SYNC 字符就確認已進入同步狀態,準備接收信息。隨後的傳送過程中雙方以同一頻率工作(信號編碼的定時作用也表現在這裡),直到傳送完指 示數據結束的控制字符。這種同步方式僅在數據塊的前後加入控制字符 SYNC. 所以效率更高。 在短距離高速數據傳輸中,多采用同步傳輸方式。
2.7.2 交換方式
一個通信網絡由許多交換節點互連而成。信息在這樣的網絡中傳輸就像火車在鐵路網絡中 運行一樣,經過一系列交換節點(車站),從一條線路交換到另一條線路,最後才能到達目的 地。交換節點轉發信息的方式可分為電路交換、報文交換和分組交換 3 種。
1. 電路交換
這種交換方式把發送方和接收方用一系列鏈路直接連通(如圖 2-14 所示)。電話交換系統 就是採用這種交換方式。當交換機收到一個呼叫後就在網絡中尋找一條臨時通路供兩端的用戶 通話,這條臨時通路可能要經過若干個交換局的轉接,並且一旦建立連接就成為這一對用戶之 間的臨時專用通路,其他用戶不能打斷,直到通話結束才拆除連接。
早期的電路交換機採用空分交換技術。圖 2-15 表示由 n 條全雙工輸入輸出線路組成的縱 橫交換矩陣,在輸入線路和輸出線路的交叉點處有接觸開關。每個站點分別與一條輸入線路和 一條輸出線路相連,只要適當控制這些交叉觸點的通斷,就可以控制任意兩個站點之間的數據 交換。這種交換機的開關數拯與站點數的平方成正比,成本高,可靠性差,已經被更先進的時 分交換技術取代了。
時分交換是時分多路複用技術在交換機中的應用。圖 2-16 所示為常見的 TOM 總線交換, 每個站點都通過全雙工線路與交換機相連,當交換機中的某個控制開關接通時該線路獲得一個 時槽,線路上的數據被輸出到總線上。在數字總線的另一端按照同樣的方法接收各個時槽上的 數據。
電路交換的特點是建立連接需要等待較長的時間。由千連接建立後通路是專用的,因而不 會有其他用戶的干擾,不再有等待延遲。這種交換方式適合千傳輸大量的數據,傳輸少量信息 時效率不高。
2. 報文交換
這種方式不要求在兩個通信節點之間建立專用通路。節點把要發送的信息組織成一個數據 包——報文,該報文中含有目標節點的地址,完整的報文在網絡中一站一站地向前傳送。每一 個節點接收整個報文,檢查目標節點地址,然後根據網絡中的“交通情況”在適當的時候轉發 到下一個節點。經過多次的存儲—轉發,最後到達目標節點(如圖 2-17 所示),因而這樣的網 絡叫存儲-轉發網絡。其中的交換節點要有足夠大的存儲空間(一般是磁盤),用於緩衝接收到 的長報文。交換節點對各個方向上收到的報文排隊,尋找下一個轉發節點,然後再轉發出去, 這些都帶來了排隊等待延遲。報文交換的優點是不建立專用鏈路,線路是共享的,因而利用率 較高,這是由通信中 的等待時延換來的 。
3. 分組交換
在這種交換方式中數據包有固定的長度,因而交換節點只要在內存中開闢一個小的緩衝區 就可以了。在進行分組交換時,發送節點先要對傳送的信息分組,對各個分組編號,加上源地 址和目標地址以及約定的分組頭信息,這個過程叫作信息的打包。一次通信中的所有分組在網 絡中傳播又有兩種方式,一種叫數據報 (Datagram), 另一種叫虛電路 CVntualC江cuit), 下面分別 介紹。
(I) 數據報。類似千報文交換,每個分組在網絡中的傳播路徑完全是由網絡當時的狀況隨 機決定的。因為每個分組都有完整的地址信息,如果不出意外都可以到達目的地。但是,到達 目的地的順序可能和發送的順序不一致。有些早發的分組可能在中間某段交通擁擠的鏈路上耽 擱了,比後發的分組到得遲,目標主機必須對收到的分組重新排序才能恢復原來的信息。 一般 來說,在發送端要有一個設備對信息進行分組和編號,在接收端也要有一個設備對收到的分組 拆去頭、尾並重排順序,具有這些功能的設備叫分組拆裝設備 (PacketAssembly and Disassembly device, PAD), 通信雙方各有一個。
(2) 虛電路。類似千電路交換,這種方式要求在發送端和接收端之間建立一條邏輯連接。 在會話開始時,發送端先發送建立連接的請求消息,這個請求消息在網絡中傳播,途中的各個 交換節點根據當時的交通狀況決定取哪條線路來響應這一請求,最後到達目的端。如果目的端 給予肯定的回答,則邏輯連接就建立了。以後發送端發出的一系列分組都走這一條通路,直到 會話結束,拆除連接。 與電路交換不同的是,邏輯連接的建立並不意味著其他通信不能使用這 條線路,它仍然具有鏈路共享的優點。
按虛電路方式通信,接收方要對正確收到的分組給予回答確認,通信雙方要進行流暈控制 和差錯控制,以保證按順序正確接收,所以虛電路意味著可靠的通信。當然, 它涉及更多的技 術,需要更大的開銷。也就是說,它沒有數據報方式靈活,效率不如數據報方式高。
虛電路可以是暫時的,即會話開始建立,會話結束拆除,這叫作虛呼叫;也可以是永久的, 即通信雙方一開機就自動建立連接,直到一方請求釋放才斷開連接,這叫作永久虛電路。
虛電路適合於交互式通信,這是它從電路交換那裡繼承的優點。數據報方式更適合於單向 地傳送短消息,採用固定的、短的分組相對千報文交換是一個重要的優點。除了交換節點的存 儲緩衝區可以小一些外,也帶來了傳播時延的減小。分組交換也意味著按分組糾錯,發現錯誤 只需重發出錯的分組,使通信效率提高。廣域網絡一般都採用分組交換方式,按交換的分組數 收費,而不是像電話網那樣按通話時間收費,這當然更適合計算機通信的突發式特點。有些網絡同時提供數據報和虛電路兩種服務,用戶可根據需要選用。
2.8 多路複用技術
多路複用技術是把多個低速信道組合成一個高速信道的技術。這種技術要用到兩個設備, 其中,多路複用器 (Multiplexer) 在發送端根據某種約定的規則把多個低帶寬的信號複合成一 個高帶寬的信號;多路分配器 (Demultiplexer) 在接收端根據同一規則把高帶寬信號分解成多 個低帶寬信號。多路複用器和多路分配器統稱多路器,簡寫為 MUX, 如圖 2-18 所示。 只要帶寬允許,在已有的高速線路上採用多路複用技術可以省去安裝新線路的大筆費用, 因而現今的公共交換電話網 (PSTN) 都使用這種技術,有效地利用了高速幹線的通信能力。
當然,也可以相反地使用多路複用技術,即把一個高帶寬的信號分解到幾個低速線路上同 時傳輸,然後在接收端合成為原來的高帶寬信號。例如,兩個主機可以通過若干條低速線路連 接,以滿足主機間高速通信的要求。
2.8.1 頻分多路複用
頻分多路複用是在一條傳輸介質上使用多個頻率不同的模擬載波信號進行多路傳輸,這些 載波可以進行任何方式的調製,如 ASK、 FSK、 PSK 以及它們的組合。每一個載波信號形成了 一個子信道,各個子信道的中心頻率不相重合,子信道之間留有一定寬度的隔離頻帶(如圖 2-19 所示)。
頻分多路技術早已用在無線電廣播系統中,在有線電視系統 (CATV) 中也使用頻分多路 技術。一根 CATV 電纜的帶寬大約是 1 000MHz, 可傳送多個頻道的電視節目,每個頻道 6.5MHz 的帶寬中又劃分為聲音子通道、視頻子通道以及彩色子通道。每個頻道兩邊都留有一定的苦戒 頻帶,防止相互串擾。
FDM 也用在寬帶局域網中。電纜帶寬至少要劃分為不同方向上的兩個子頻帶,甚至還可以 分出一定帶寬用千某些工作站之間的專用連接。
2.8.2 時分多路複用
時分多路複用 CT皿e Division Multiplexing, TDM) 要求各個子通道按時間片輪流地佔用 整個帶寬(如圖 2-20 所示)。時間片的大小可以按一次傳送一位、一個字節或一個固定大小的 數據塊所需的時間來確定。
時分多路技術可以用在寬帶系統中,也可以用在頻分制下的某個子通道上。時分制按照子 通道的動態利用情況又可分為兩種,即同步時分和統計時分。在同步時分制下,整個傳輸時間 被劃分為固定大小的週期。每個週期內,各子通道都在固定位置佔有一個時槽。這樣,在接收 端可以按約定的時間關係恢復各子通道的信息流。當某個子通道的時槽來到時,如果沒有信息 要傳送,這一部分帶寬就浪費了 。 統計時分制是對同步時分制的改進,特別把統計時分制下的 多路複用器稱為集中器,以強調它的工作特點。在發送端,集中器依次循環掃描各個子通道。 若某個子通道有信息要發送則為它分配一個時槽,若沒有就跳過,這樣就沒有空槽在線路上傳 播了。然而,需要在每個時槽加入一個控制字段,以便接收端可以確定該時槽是屬千哪個子通 道的。
2.8.3 波分多路複用
波分多路複用 (Wave Division Multiplexing, WDM) 使用在光纖通信中,不同的子信道用 不同波長的光波承載,多路複用信道同時傳送所有子信道的波長。這種技術在網絡中要使用能 夠對光波進行分解和合成的多路器, 如圖 2-21 所示。
2.8.4 數字傳輸系統
在介紹脈碼調製時曾提到,對 4kHz 的話音信道按 8kHz 的速率採樣, 128 級量化,則每個 話音信道的比特率是 56kbps。為每一個這樣的低速信道安裝一條通信線路太不划算了,所以在 實際中要利用多路複用技術建立更高效的通信線路。在美國和日本使用很廣的一種通信標準是 貝爾系統的飛載波(如圖 2-22 所示)。載波也叫一次群,它把 24 路話音信道按時分多路的原理複合在一條 l.544Mbps 的高速信 道上。該系統的工作是這樣的,用一個編碼解碼器輪流對 24 路話音信道取樣、量化和編碼, 將一個取樣週期中 (125µs) 得到的 7 位一組的數字合成一串,共 7X24 位長。這樣的數字串在 送入高速信道前要在每一個 7 位組的後面插入一個信令位,千是變成了 8X24==192 位長的數字 串。這 192 位數字組成一幀,最後再加入一個幀同步位,故幀長為 193 位。每 125µs 傳送一幀, 其中包含了各路話音信道的一組數字,還包含了總共 24 位的控制信息以及 1 位幀同步信息。 這樣,不難算出飛載波的各項比特率。對每一路話音信道來說,傳輸數據的比特率為 7b/125µs== 56 kbps, 傳輸控制信息的比特率為 1b/125µs==8 kbps, 總的比特率為 193 b/125µs=l.544 Mbps。
載波還可以多路複用到更高級的載波上,如圖 2-23 所示。 4 個 1.544 Mbps 的
信道結 合成 1 個6.312Mbps 的
信道,多增加的位 (6.312-4X 1.544=0.136) 是為了組幀和差錯恢復。與此類似, 7 個
信道組合成 1 個
信道, 6 個
信道組合成 1 個
信道。
ITU-T 的 El 信道的數據速率是 2.048Mbps C如圖 2-24 所示)。這種載波把 32 個 8 位一組 的數據樣本組合成125µs 的基本幀,其中 30 個子信道用千話音傳送數據,兩個子信道 (CHO 和 CH16) 用於傳送控制信令,每 4 幀能提供 64 個控制位。除了北美和亞洲的日本外, El 載 波在其他地區得到了廣泛使用。
按照 ITU-T 的多路複用標準, E2 載波由 4 個 El 載波組成,數據速率為 8.448Mbps。 E3 載波由 4 個 E2 載波組成,數據速率為 34.368Mbps。 E4 載波由 4 個 E3 載波組成,數據速率為 139.264Mbps。 E5 載波由 4 個 E4 載波組成,數據速率為 565.148Mbps。
2.8.5 同步數字系列
光纖線路 的 多 路複用標準有兩個, 美 國標準叫作同步光纖網絡 (Synchronous Optical Network, SONET); ITU-T 以 SONET 為基礎制訂出的國際標準叫作同步數字系列 (Synchronous Digital Hierarchy, SDH) 。 SDH 的基本速率是 155.52Mbps, 稱為第 1 級同步傳遞模塊 ( Synchronous Transfer Module), 即 STM-L 相當於 SONET 體系中的 OC-3 速率,如表 2-5 所示。
2.9 差錯控制
無論通信系統如何可靠,都不能做到完美無缺。因此, 必須考慮怎樣發現和糾正信號傳輸 中 的差錯。 這一節從應用角度介紹差錯控制的基本原理和方法。
通信過程中出現的差錯可大致分為兩類: 一類是由熱噪聲引起的隨機錯誤;另一類是由衝 擊噪聲引起的突發錯誤。 通信線路中的熱噪聲是由電子的熱運動產生的,香衣關千噪聲信道傳 輸速率的結論就是針對這種噪聲的。 熱噪聲時刻存在,具有很寬的頻譜,且幅度較小。通信線路的信噪比越高,熱噪聲引起的差錯越少。這種差錯具有隨機性,影響個別位。
衝擊噪聲源是外界的電磁干擾,例如打雷閃電時產生的電磁干擾,電焊機引起的電壓波動 等。衝擊噪聲待續的時間短而幅度大,往往引起一個位串出錯。根據它的特點,稱其為突發性 差錯。
此外,由千信號幅度和傳播速率與相位、頻率有關而引起的信號失真,以及相鄰線路之間 發生串音等都會產生差錯,這些差錯也具有突發性的特點。
突發性差錯影響局部,而隨機性差錯總是斷續存在,影響全局。所以要儘量提高通信設備 的信噪比,以滿足要求的差錯率。此外,要進一步提高傳輸質量,就需要採用有效的差錯控制 辦法。這一節介紹的檢錯和糾錯碼只是可靠性技術中的一種,它廣泛地使用在數據通信中。
2.9.1 檢錯碼
奇偶校驗是最常用的檢錯方法,其原理是在 7 位的 ASCII 代碼後增加一位,使碼字中 1 的 個數成奇數(奇校驗)或偶數(偶校驗)。經過傳輸後,如果其中一位(甚至奇數個位)出錯, 則接收端按同樣的規則就能發現錯誤。這種方法簡單實用,但只能對付少量的隨機性錯誤。
為了能檢測突發性的位串出錯,可以使用校驗和的方法。這種方法把數據塊中的每個字節 當作一個二進制整數,在發送過程中按模 256 相加。數據塊發送完後,把得到的和作為校驗字 節發送出去。接收端在接收過程中進行同樣的加法,數據塊加完後用自已得到的校驗和與接收 到的校驗和比較,從而發現是否出錯。實現時可以用更簡單的辦法,例如在校驗字節發送前, 對累加器中的數取 2 的補碼。這樣,如果不出錯,接收端在加完整個數據塊以及校驗和後累加 器中是 0。這種方法的好處是由千進位的關係,一個錯誤可以影響到更高的位,從而使出錯 位對校驗字節的影響擴大了。可以粗略地認為,隨機的突發性錯誤對校驗和的影響也是隨機 的。出現突發錯誤而得到正確的校驗字節的概率是 1/256, 於是就有 255 : 1 的機會能檢查出任 何錯誤。
2.9.2 海明碼
1950 年,海明 (Hamming) 研究了用冗餘數據位來檢測和糾正代碼差錯的理論和方法。按 照海明的理論,可以在數據代碼上添加若干冗餘位組成碼字。碼字之間的海明距離是一個碼字 要變成另一個碼字時必須改變的最小位數。例如, 7 位 ASCII 碼增加一位奇偶位成為 8 位的碼 字,這 128 個 8 位的碼字之間的海明距離是 2。所以,當其中一位出錯時便能檢測出來。兩位 出錯時就變成另外一個碼字了。
海明用數學分析的方法說明了海明距離的幾何意義, n 位的碼字可以用 n 維空間的超立方體的一個頂點來表示。兩個碼字之間的海明距離就是超立方體的兩個對應頂點之間的一條邊, 而且這是兩頂點(兩個碼字)之間的最短距離,出錯的位數小千這個距離都可以被判斷為就 近的碼字。這就是海明碼糾錯的原理,它用碼位的增加(因而通信量增加)來換取正確率的 提高。
按照海明的理論,糾錯碼的編碼就是要把所有合法的碼字盡蜇安排在 n 維超立方體的頂點 上,使得任意一對碼字之間的距離儘可能大。
如果任意兩個碼字之間的海明距離是 d, 則所有 小千等千 d-1 位的錯誤都可以檢查出來,所有小千 d/2 位的錯誤都可以糾正。一個自然的推論 是,對於某種長度的錯誤串,要糾正它就要用比僅僅檢測它多一倍的冗餘位。 如果對千 m 位的數據增加 k 位冗餘位,則組成 n=m+k 位的糾錯碼。對千 2m個有效碼字中 的每一個,都有 n 個無效但可以糾錯的碼字。這些可糾錯的碼字與有效碼字的距離是 1, 含單 個錯誤位。這樣,對千一個有效的消息總共有 n+l 個可識別的碼字。這 n+l 個碼字相對於其他 2m-1 個有效消息的距離都大千 1 。這意味著總共有 2m (n+l)個有效的或者可糾錯的碼字。顯然, 這個數應小於等於碼字的所有可能的個數,即 2飛千是,有
因為,得出
對千給定的數據位 m, 上式給出了 K 的下界,即要糾正單個 錯誤 K 必須取的最小值。海明建議了一種方案可以達到這個下界, 並能直接指出錯在哪一位。首先把碼字的位從 1 到 n 編號,並把 這個編號表示成二進制數,即 2 的幕之和 。然後對 2 的每一個幕 設置一個奇偶位。例如,對千 6 號位,由千 6=110 (二進制),所 以 6 號位參加第 2 位和第 4 位的奇偶校驗,而不參加第 1 位的奇 偶校驗。類似地, 9 號位參加第 1 位和第 8 位的校驗而不參 加第 2 位或第 4 位的校驗。海明把奇偶校驗分配在 1 、 2、 4、 8 等位置上,其他位放置數據。 下面根據圖 2-25 舉例說明編碼的 方法。
假設傳送的信息為 1001011, 把各個數據放在 3、 5、 6、 7、 9、 10、 11 等位置上, 1、 2、 4、 8 位留作校驗位。
根據圖 2-25, 3、 5、 7、 9、 11 的二進制編碼的第一位為 1, 所以 3、 5、 7、 9、 11 號位參加第 1 位校驗,若按偶校驗計算, 1 號位應為 1 。
如果這個碼字傳輸中出錯,比如說 6 號位出錯,即變成:
當接收端按照同樣的規則計算奇偶位時,發現 l 和 8 號位的奇偶性正確, 2 和 4 號位的奇 偶性不對,於是 2+4= 6, 立即可確認錯在 6 號位。
在上例中, k=4, 因而 m<24- 4 - I= 1 L 即數據位可用到 11 位,共組成 15 位的碼字,可檢 測出單個位的錯誤。
2.9.3 衍環冗餘校驗碼
所謂循環碼是這樣一組代碼,其中任一有效碼字經過循環移位後得到的碼字仍然是有效 碼字,不論是右移或左移,也不論移多少位。例如,若是有效碼字,則
等都是有效碼字。循環冗餘校驗碼 ( Cyclic Redundancy Check, CRC) 是一種循環碼,它有很強的檢錯能力,而且容易用硬件實現,在局域網中有廣 泛應用。
首先介紹 CRC 怎樣實現,然後對它進行一些數學分析,最後說明 CRC 的檢錯能力。 CRC 可以用圖 2-26 所示的移位寄存器實現。移位寄存器由 K 位組成,還有幾個異或門和一條反饋回 路。圖 2-26 所示的移位寄存器可以按 CCITT-CRC 標準生成 16 位的校驗和。寄存器被初始化 為 O, 數據從右向左逐位輸入。當一位從最左邊移出寄存器時就通過反饋迴路進入異或門和後 續進來的位以及左移的位進行異或運算。 當所有 m 位數據從右邊輸入完後再輸入 k 個 0 (本例 中 k=l6)。最後,當這一過程結束時,移位寄存器中就形成了校驗和。 K位的校驗和跟在數據位 後邊發送,接收端可以按同樣的過程計算校驗和並與接收到的校驗和比較,以檢測傳輸中的差錯。
以上描述的計算校驗和方法可以用一種特殊的多項式除法進行分析。 m 個數據位可以看作 階多項式的係數。例如,數據碼字 00101011 可以組成的多項式是
。圖 2-26 中表 示的反饋迴路可表示成另外一個多項式
, 這就是所謂的生成多項式。所有的運算都 按模 2 進行,即
顯然,在這種代數系統中,加法和減法一樣,都是異或運算。用 x 乘一個多項式等千把多 項式的係數左移一位。 可以看出,按圖 2-26 的反饋迴路把一個向左移出寄存器的數據位反饋回 去與寄存器中的數據進行異或運算,等同於在數據多項式上加上生成多項式,因而也等同千從 數據多項式中減去生成多項式。以上給出的例子,對應千下面的長除法:
得到的校驗和是 9509H。千是看到,移位寄存器中的過程和以上長除法在原理上是相同的, 因而可以用多項式理論來分析 CRC 代碼,這就使得這種檢錯碼有了嚴格的數學基礎。
把數據碼字形成的多項式叫數據多項式 , 按照一定的要求可給出生成多項式
。用
除
可得到商多項式
和餘多項式
,實際傳送的碼字多項式是
由於使用了模 2 算術,, 於是接收端對
計算的校驗和應為 0。如果有差錯, 則接收到的碼字多項式包含某些出錯位
, 可表示成
由於可以被
整除,如果
不能被
整除,則說明
, 即有錯誤出現。 然而,若
也能被
整除,則有差錯而檢測不到 。
數學分析表明, 應該有某些簡單的特性,才能檢測出各種錯誤。例如,若
包含的 項數大於1, 則可以檢測單個錯;若
含有因子
, 則可檢測出所有奇數個錯。最後得出的最重要的結論是:具有
個校驗位的多項式能檢測出所有長度小於等於
的突發性差錯。
為了能對不同場合下的各種錯誤模式進行校驗,已經研究出了幾種 CRC 生成多項式的國際 標準。
CRC-CCITT
CRC-16
CRC-12
CRC-32
其中, CRC-32 被用在許多局域網中。