天天看點

計算機網絡:差錯控制

比特在傳輸過程中可能會産生差錯,1可能會變成0,0也可能會變成1,這就是比特差錯。比特差錯是傳輸差錯中的一種。

通常利用編碼技術進行差錯控制,主要有兩類:自動重傳請求ARQ和前向糾錯FEC。

  • 在 ARQ方式中,接收端檢測到差錯時,就設法通知發送端重發,直到接收到正确的碼字為止。
  • 在FEC方式中,接收端不但能發現差錯,而且能确定比特串的錯誤位置,進而加以糾正。

是以,差錯控制又可分為檢錯編碼和糾錯編碼。

檢錯編碼

檢錯編碼都采用備援編碼技術,其核心思想是在有效資料(資訊位)被發送前,先按某種關系附加一定的備援位,構成一個符合某一規則的碼字後再發送。當要發送的有效資料變化時,相應的備援位也随之變化,使得碼字遵從不變的規則。接收端根據收到的碼字是否仍符合原規則來判斷是否出錯。

常見的檢錯編碼有奇偶校驗碼和循環備援碼。

1.奇偶校驗碼

奇偶校驗碼是奇校驗碼和偶校驗碼的統稱,是一種最基本的檢錯碼。它由n-1位資訊元和1位校驗元組成,如果是奇校驗碼,那麼在附加一個校驗元後,碼長為n的碼字中“1”的個數為奇數,這是奇數校驗碼 ;如果是偶校驗碼,那麼在附加一個校驗元以後,碼長為n的碼字中“1”的個數為偶數。它隻能檢測奇數位的出錯情況,(如果有一組剛好出錯,1的奇偶卻不變,則無法查清楚是否出錯)。

2.循環備援碼

循環備援碼 (Cyclic Redundancy Code, CRC) 又 稱多項式碼。一個 k 位幀可以視為從

到 $ X^{0}$ 的 k 次多項式的系數序列, 這個多項式的階數為 k-1, 例如, 1110011 有 7 位, 表示成多項式是

給定一個m bit的幀或封包, 發送器生成一個r bit的序列,稱為幀檢驗序列(FCS) 就是餘數。這樣所形成的幀将由m+r比特組成。發送方和接收方事先商定一個多項式G(x)(最高位和最低位必須為1),使這個帶檢驗碼的幀剛好能被預先确定的多項式G(x)整除。接收方用相同的多項式去除收到的幀,如果無餘數,那麼認為無差錯。

假設一個幀有m位,其對應的多項式為Mx),則計算備援碼的步驟如下:

  1. 加0。假設G(x)的階為r(階數是指最高位的次數,不是總式子的長度),在幀的低位端加上r個0。
  2. 模2除。利用模2除法(就是異或),用G(x)對應的資料串去除1)中的資料串,得到的餘數即為備援碼(共r位,前面的0不可省略)。
計算機網絡:差錯控制

注意:循環備援碼(CRC)是具有糾錯功能的,隻是資料鍊路層僅使用了它的檢錯功能,檢測到幀出錯則直接丢棄。

糾錯編碼

最常見的糾錯編碼是海明碼,其實作原理是在有效資訊位中加入幾個校驗位形成海明碼,并把海明碼的每個二進制位配置設定到幾個奇偶校驗組中。當某一位出錯後,就會引起有關的幾個校驗位的值發生變化,這不但可以發現錯位,而且能指出錯位的位置,為自動糾錯提供依據。

現以資料碼 1010 為例講述海明碼的編碼原理和過程。

(1) 确定海明碼的位數

設 n 為有效資訊的位數, k 為校驗位的位數, 則資訊位 n 和校驗位 k 應滿足

(若要檢測兩位錯, 則需再增加 1 位校驗位, 即 k+1 位)

海明碼位數為

成立, 則 n 、 k 有效。設資訊位為

, 共 4 位, 校驗位為

, 共 3 位, 對應的海明碼為

(2)确定校驗位的分布

規定校驗位

在海明位号為

的位置上, 其餘各位為資訊位, 是以有:

的海明位号為

, 即

$ P_{2}$ 的海明位号為 $ 2{i-1}=2{1}=2$ , 即

$ P_{3}$ 的海明位号為

, 即

将資訊位按原來的順序揷入, 則海明碼各位的分布如下:

(3) 分組以形成校驗關系

每個資料位用多個校驗位進行校驗, 但要滿足條件: 被校驗資料位的海明位号等于校驗該數 據位的各校驗位海明位号之和。另外, 校驗位不需要再被校驗。分組形成的校驗關系如下。

計算機網絡:差錯控制
(4) 校驗位取值

校驗位

的值為第 i 組 (由該校驗位校驗的資料位) 所有位求異或。 根據(3)中的分組有

是以, 1010 對應的海明碼為 1010010(下畫線為校驗位, 其他為資訊位)。

(5)海明碼的校驗原理

每個校驗組分别利用校驗位和參與形成該校驗位的資訊位進行奇偶校驗檢查, 構成 k 個校驗方程:

的值為 “ 000 ”, 則說明無錯; 否則說明出錯, 且這個數就是錯誤位的位号, 如

, 說明第 1 位出錯, 即

繼續閱讀