數字數據通信的錯誤檢測與修正
在數字數據通信中,由發送器發送的數據信號禎(Frame)在經由網絡傳到接收器后,由于多種原因可能導致錯誤位(bit errors)的出現,因此必須由接收器采取一定的措施探測出所有的錯誤位,并進而采取一定的措施予以修正。一、錯誤檢測的基本原理(Principle of Error Check)
發送器向所發送的數據信號禎添加錯誤檢驗碼(Check Bits),并取該錯誤檢測碼作為該被傳輸數據信號的函數;接收器根據該函數的定義進行同樣的計算,然后將兩個結果進行比較:如果結果相同,則認為無錯誤位;否則認為該數據禎存在有錯誤位。
一般說來,錯誤檢測可能出現三種結果:
1. 在所傳輸的數據禎中未探測到,也不存在錯誤位
2. 所傳輸的數據禎中有一個或多個被探測到的錯誤位,但不存在未探測到的錯誤位
3. 被傳輸的數據禎中有一個或多個沒有被探測到的錯誤位。
顯然我們希望盡可能好地選擇該檢測函數,使檢測結果可靠,即:所有的錯誤最好都能被檢測出來;如檢測出現無錯結果,則應不再存在任何未被檢測出來的錯誤。
實際采用的錯誤檢測方法主要有兩類:奇偶校驗(Parity)和CRC循環冗余校驗(Cyclic Redundancy Check)。
二、奇偶校驗(Parity)
1.單向奇偶校驗
單向奇偶校驗(Row Parity)由于一次只采用單個校驗位,因此又稱為單個位奇偶校驗(Single Bit Parity)。發送器在數據禎每個字符的信號位后添一個奇偶校驗位,接收器對該奇偶校驗位進行檢查。典型的例子是面向ASCII碼的數據信號禎的傳輸,由于ASCII碼是七位碼,因此用第八個位碼作為奇偶校驗位。
單向奇偶校驗又分為奇校驗(Odd Parity)和偶校驗(Even Parity),發送器通過校驗位對所傳輸信號值的校驗方法如下:奇校驗保證所傳輸每個字符的8個位中1的總數為奇數;偶校驗則保證每個字符的8個位中1的總數為偶數。
顯然,如果被傳輸字符的7個信號位中同時有奇數個(例如1、3、5、7)位出現錯誤,均可以被檢測出來;但如果同時有偶數個(例如2、4、6)位出現錯誤,單向奇偶校驗是檢查不出來的。
一般在同步傳輸方式中常采用奇校驗,而在異步傳輸方式中常采用偶校驗。
2.雙向奇偶校驗
為了提高奇偶校驗的檢錯能力,可采用雙向奇偶校驗(Row and Column Parity),也可稱為雙向冗余校驗(Vertical and Longitudinal Redundancy Checks)。
三、CRC循環冗余校驗(Cyclic Redundancy Check)
1.CRC循環冗余校驗的基本原理
發送器和接收器約定選擇同一個由n+1個位組成的二進制位列P作為校驗列,發送器在數據禎的K個位信號后添加n個位(n < K)組成的FCS禎檢驗列(Frame Check Sequence),以保證新組成的全部信號列值可以被預定的校驗二進制位列P的值對二取模整除;接收器檢驗所接收到數據信號列值(含有數據信號禎和FCS禎檢驗列)是否能被校驗列P對二取模整除,如果不能,則存在傳輸錯誤位。P被稱為CRC循環冗余校驗列,正確選擇P可以提高CRC冗余校驗的能力。(注:對二取模的四則運算指參與運算的兩個二進制數各位之間凡涉及加減運算時均進行XOR異或運算,即:1 XOR 1=0,0 XOR 0=0,1 XOR 0=1)。可以證明,只要數據禎信號列M和校驗列P是確定的,則可以唯一確定FCS禎檢驗列(也稱為CRC冗余檢驗值)的各個位。
FCS幀檢驗列可由下列方法求得:在M后添加n個零后對二取模整除以P所得的余數。
例如:如要傳輸的M=7位列為1011101,選定的P校驗二進制位列為10101(共有n+1=5位),對應的FCS幀校驗列即為用1011101 0000(共有M+n=7+4=11位)對二取模整除以10101后的余數0111(共有n=4位)。因此,發送方應發送的全部數據列為10111010111。接收方將收到的11位數據對二取模整除以P校驗二進制位列10101,如余數非0,則認為有傳輸錯誤位。
2.CRC循環冗余校驗標準多項式P(X)
為了表示方便,實用時發送器和接收器共同約定選擇的校驗二進制位列P常被表示為具有二進制系數(1或0)的CRC標準校驗多項式P(X)。
(1)CRC循環冗余校驗常用的標準多項式P(X)
常用的CRC循環冗余校驗標準多項式如下:
CRC(16位) = X^16+X^15+X^2+1
CRC(CCITT) = X^16+X^12+X^5+1
CRC(32位) =X^32+X^26+X^23+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1
以CRC(16位)多項式為例,其對應校驗二進制位列為1 1000 0000 0000 0101。
注意:這兒列出的標準校驗多項式P(X)都含有(X+1)的多項式因子;各多項式的系數均為二進制數,所涉及的四則運算仍遵循對二取模的運算規則。
(2)CRC循環冗余校驗標準多項式P(X)的檢錯能力
CRC循環冗余校驗具有比奇偶校驗強得多的檢錯能力。可以證明:它可以檢測出所有的單個位錯、幾乎所有的雙個位錯、低于P(X)對應二進制校驗列位數的所有連續位錯、大于或等于P(X)對應二進制校驗列位數的絕大多數連續位錯。
但是,當傳輸中發生的錯誤多項式E(X)能被校驗多項式P(X)對二取模整除時,它就不可能被P(X)探測出來,例如當E(X)=P(X)時。
四、錯誤修正(Error Correction)
對數據信號禎傳輸過程中的位錯進行修正的方法主要有兩種:
1. 由發送器提供錯誤修正碼,然后由接收器自己修正錯誤
2. 在接收器發現接收到的錯誤禎中有位錯誤時,通知發送器重新發送數據信號禎。
前一種方法中的錯誤修正碼需要發送器由被傳送數據信號禎計算得到,然后添加到數據禎的后面,其長度幾乎等于數據位數,導致效率降低50%,實際采用不多;一般采用后一種較為有效的重發送方法。
數據交換技術(Data Switching Technology)
在數據通信線路中,最簡單的形式是在由某種傳輸介質直接連接的兩臺設備之間進行通信。但在長距離通信中,從源站發出的數據一般還需要經過網絡中一個或多個用作交換設備的中間結點,由相應結點的交換設備把數據從一個結點傳送到另一個結點,直至到達目的站。通常我們將交換網絡中所有通信的發送方與接收方的主機均簡稱為站,而將通信交換設備簡稱為結點。這些結點以不規則的網狀結構用傳輸線路互相連接起來,而每個站點都連接到某個結點上。
在交換網絡中,站點之間需要通過有關結點之間的數據交換才能實現數據通信,基本的交換技術有兩類:電路交換與存儲轉發,存儲轉發又可以分為報文交換和分組交換,分組交換則可分為面向連接的虛電路傳輸和無連接的數據報傳輸。目前,最具有發展前景的是高速分組交換技術。
posted on 2007-01-03 11:26 Timothy 閱讀(922) 評論(0) 編輯 收藏 所屬分類: 經典概念