這篇筆記專門講數據鏈路層的功能。

2.功能

數據鏈路層的主要任務是讓幀在一段鏈路上或一個網絡中傳輸。

2.1.封裝成幀（組幀）

解決的問題：①幀定界②幀同步③透明傳輸

實現組幀的方法通常有以下種。

2.1.1.字符計數法

原理：在每個幀開頭，用一個定長計數字段來記錄該幀所含的字節數（包含計數字段自身所占用的字節）。

問題：任何一個計數字段出錯，都會導致后續所有幀無法定界。

2.1.2.Byte填充法

原理：使用特定字節來定界一幀的開始與結束。控制字符表示幀的開始；控制字符表示幀的結束。

信息位中如果出現特殊字符（控制字符，控制字符，轉義字符），則發送方要在轉義字符之前填充一個轉義字符來加以區分，接收方要做逆處理。

2.1.3.0bit填充法

在數據鏈路層早期使用的協議中，便是采用這種比特填充的首尾標志法來實現透明傳輸的。

原理：零比特填充法允許數據幀包含任意個數的比特。它使用一個特定的比特串來標志一幀的開始和結束。

為了不使數據字段中出現的比特流被誤判為幀的首尾標志，需要對數據部分做一些處理：發送方需要對幀的數據部分進行處理，每當遇到連續個，就填充個；接受方需要對幀的數據部分進行逆處理，每當遇到連續個，就刪掉后面的。

2.1.4.違規編碼法

在物理層進行比特編碼時，常采用違規編碼法。

局域網 標準就采用了這種方法。

原理：使用“違規信號”，表示幀的開頭、結尾。

例如，采用曼徹斯特編碼時，使用“中間不跳變”作為“違規信號”，標記幀的開頭、結尾。

2.2.差錯控制

差錯控制的目標是發現并解決一個幀內部的“位錯”。

這里的“位錯”指的是比特差錯（傳輸差錯中的一種），即比特在傳輸過程中可能產生差錯，可能變成，也可能變成。

---

常利用編碼技術進行差錯控制。

差錯控制機制	編碼技術（實現差錯控制機制的具體技術方法）
自動重傳請求（Automatic Repeat reQuest,ARQ）：當接收方檢測到差錯時，就設法通知發送方重發，直到收到正確的數據為止。	檢錯編碼
向前糾錯（Forword Error Correction,FEC）：接收方不但能發現差錯，而且能確定錯誤的位置并加以糾正。	糾錯編碼

2.2.1.檢錯編碼

檢錯編碼都采用冗余編碼技術，核心思想是在信息位（幀的“數據部分”）被發送前，按某種關系附加一定的校驗位（為了給幀的“數據部分”檢錯/糾錯而附加的一些冗余比特，在信息位的首部或尾部添加），構成一個符合某一規則的碼字后發送。

當要發送的有效數據變化時，相應的冗余位也隨之變化，使得碼字遵從不變的規則。接收方根據收到的碼字是否仍符合原規則來判斷是否出錯。常見的檢錯編碼有奇偶檢驗碼和循環冗余碼。

奇偶校驗碼是奇校驗碼和偶校驗碼的統稱。

1??組成

奇偶校驗碼由位信息位和位校驗位組成。檢驗位的取值(或)將使整個檢驗碼中的個數為奇數或偶數。

2??約定

發送方和接收方先共同約定是采用奇校驗還是偶校驗。

3??發送方求校驗位

奇校驗碼：附加一個檢驗位后，位的碼字中的個數為奇數。

偶校驗碼：附加一個檢驗位后，位的碼字中的個數為偶數。

4??接收方檢錯

如果發送方和接收方共同約定采用奇校驗的規則，那么接收方的數據鏈路層收到幀之后會檢查這個幀的校驗位和信息位里含有的是不是奇數個。如果是奇數個，就認為沒有錯誤；如果不是奇數個，就認為有錯誤。

如果發送方和接收方共同約定采用偶校驗的規則，那么接收方的數據鏈路層收到幀之后會檢查這個幀的校驗位和信息位里含有的是不是偶數個。如果是偶數個，就認為沒有錯誤；如果不是偶數個，就認為有錯誤。

5??硬件實現

在現實應用中，偶校驗碼要比奇校驗碼更常用，原因是偶校驗很容易用簡單的異或門實現。

偶校驗的硬件實現：各信息進行異或(模加)運算，得到的結果即為偶校驗位。

⊕：異或（模2加）    0 ⊕ 0 = 0       0 ⊕ 1 = 1        1 ⊕ 0 = 1          1 ⊕ 1 = 0

求偶校驗位：

1⊕0⊕0⊕1⊕1⊕0⊕1=0  

1⊕0⊕1⊕0⊕1⊕1⊕1=1  

進行偶校驗（所有位進行異或，若結果為1說明出錯）：  

0⊕1⊕0⊕0⊕1⊕1⊕0⊕1=0

1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0   

1⊕1⊕0⊕1⊕0⊕1⊕1⊕0=1  （可以檢測出奇數位錯誤）

1⊕1⊕0⊕1⊕0⊕1⊕0⊕0=0  （無法檢測出偶數位錯誤）

6??奇偶校驗碼僅能檢測出奇數位錯誤，無糾錯能力。

數據鏈路層廣泛使用循環冗余碼(Cyclic Redundancy Code,CRC)檢錯技術。

1??循環冗余校驗碼由位信息位和位校驗位組成。

2??發送方和接收方先共同約定一個生成多項式(要求最低位必須為)

生成多項式可用位位串【除數】表示，位位串可視為階數為的多項式的系數序列。

=信息碼的長度

=生成式多項式最高次冪=

3??發送方求校驗位：生成

發送方基于待發送的位信息位和，計算出位校驗位（幀檢驗序列）。

---

信息碼左移位，低位補。

對移位后的信息碼，用生成多項式進行模除法，產生余數。

由于除數有位，所以我們會取被除數的高位與除數先“商”一次。

模除法取商的方式比較特別，我們只看被除數的最高位，如果是，就先商。

之后再對后位進行模減（效果與模加相同）的運算，得到余數。

再將被除數的后面一位補到余數的低位。此時的余數最高位是，商。

以此類推。

最后得到的余數為校驗位。

對應的碼為

4??接收方檢錯：檢驗

接收方收到數據和冗余碼后，通過來計算收到的數據和冗余碼是否產生差錯。

收到位數據，與生成多項式模除，計算位余數。

余數為，說明無錯誤；余數非，說明出錯。

---

發送：        記為

接收：        用進行模除，余數為，代表沒有出錯。

接收：        用進行模除，余數為，代表可能是出錯。

5??檢錯糾錯能力

①可檢測出所有奇數個錯誤；

②可檢測出所有雙比特的錯誤；

③可檢測出所有小于等于校驗位長度的連續錯誤；

④若選擇合適的生成多項式，且，則可糾正單比特錯。

對于確定的生成多項式，出錯位與余數是相對應的。

---

為什么叫循環冗余碼？

因為將模除對應的位串，會發現得到的余數在循環。

---

循環冗余碼(CRC)是具有糾錯功能的，只是數據鏈路層僅使用了它的檢錯功能，檢測到幀出錯則直接丟棄，是為了方便協議的實現，因此本節不介紹CRC的檢錯功能。 

2.2.2.糾錯編碼

海明校驗碼

奇偶校驗碼只有個校驗位，只能攜帶種狀態信息(對/錯)。

海明碼有多個校驗位，能攜帶多種狀態信息(對/錯，錯在哪)

海明碼的設計思路是將信息位分組進行偶校驗→多個校驗位→多個校驗位標注出錯位置

1??確定海明碼的位數

設為有效信息的位數，為檢驗位的位數，則信息位和檢驗位應滿足

海明碼位數 成立，則滿足條件。

設信息位為，共位；檢驗位為，共位；

對應的海明碼為 。

2??確定檢驗位的分布

規定檢驗位在海明位號為的位置上，其余各位為信息位，因此有：

的海明碼位號為 ，即為。

的海明碼位號為，即為。