A. 數據鏈路層--概述，檢錯和糾錯
處理傳輸錯誤：差錯檢測和控制
流量控制：基於速率和基於反饋
將比特變為幀，叫成幀
字元計數法
帶位元組/字元填充的標志位元組法
比特填充的比特標志法
物理層編碼違例法
如字元計數法
任何信道，即使是光纖，也會出錯。
單個錯誤：分散在各塊中
突發錯誤：集中在某個塊中
注:突發錯誤比單個錯誤更加難於處理,通常利用處理單個處理的方法來應對突發錯誤。
糾錯碼：發現錯誤，從錯誤中恢復出正確的來。因其需要太多的冗餘位，糾錯開銷太大，在有線網路中極少使用，主要用於無線網路中。
檢錯碼：只能發現錯誤，不能從錯誤中恢復，但可採用重傳
兩種不同的處理方局局友法適用於不同的環境
1 碼字：包含數據位和校驗位的n位單元。
2 海明距離：兩個碼字的海明距離 : 兩個碼字之間不同位的數目。如：10001001 和10110001 的海明距離為3。通過異或（相同為0，不同為1）結果中1個個數。
3 全部碼字的海明距離:全部碼字中任意兩個碼字之間海明距離的最小值。
4 海明距離的意義在於：如果海明距離為d，則一個碼字需要發生d個1位錯誤才能變成另外一個碼字
5 海明距離與檢錯的關系
海明距離為d+1的編碼能檢測出d位差錯。因為在距離為d+1的檢驗碼中，只改變d位
的值，不可能產生另一個合法碼。如奇偶校驗碼，海明距離為2，能查出單個錯。
6 海明距離與檢錯的關系
海明距離為2d+1的編碼，能糾正d位差錯。因為此時，如果一個碼字有d位發生差
錯，它仍然距離原來的碼字距離最近，可以直接恢復為該碼。
注:
1 海明距離越大，檢錯和糾錯能力越強。但合法碼字就減少了，即傳輸效率降低。
每一個碼字從左到右編號，桐槐最左邊為第1位
校驗位和數據位
凡編號為2的乘冪的位是校驗位，如1、2、4、8、16等
其餘是數據位，如3、5、6、7、9等
糾錯需要較多的冗餘位，信道利用率不高。
奇偶校驗碼（海明距離為2，檢1位錯）
互聯網校驗和
循環冗餘校驗碼
一個校驗位（Parity Bit）追加到數據後。
校驗位的值取「0」還是「1」，取決於整個碼字的總的「1」的個數。（奇數還是偶數）。等同於異或運算的結果1個個數。（異或:相同得0，臘賣不同得1）
接收方檢查是否存在單個比特的錯誤
B. 數據鏈路層的問題之一——差錯檢測
第一部分 差錯、 差錯檢測（比特錯）
概括來說，傳輸中的差錯都是由雜訊引起的。
一、原因：
1、全局性
由於線路本身電氣特性所產生的隨機雜訊（熱雜訊），是信道固有的，隨機存在的。
解決辦法：提高信噪比來減少或避免干擾。（對感測器下手）
2、局部性
外界特定的短暫原因所造成的沖擊雜訊，是產生差錯的主要原因。
解決辦法：通常利用編碼技術來解決。
二、輪穗差錯
1、位錯：比特位出錯，1變成0，變成1。
2、幀錯（如：[#1]-[#2]-[#3]）
丟失（收到[#1]-[#3]）
重復（收到[#1]-[#2]-[#2]-[#3]）
失序（收到[#1]-[#3]-[#2]）
3、鏈路層為網路層提供服務
a、無確認無連接服務
通信質量好的有線傳輸鏈路
b、有確認無連接服務
c、有確認面向連接服務
第二部分 差錯檢測（檢錯編碼）
一、奇偶校驗碼（n-1位信息元，1位校驗元）
1、奇校驗碼
「1」的個數為奇數
2、偶校驗碼
「1」的個數亮鏈為偶數
二、循環冗餘碼CRC
1、例子
發送端：
5（要傳的數據）/2（生成多項式）=2......1（FCS幀檢驗序列/冗餘碼）
最終發送數據=要傳的數據+冗餘碼5（要傳的數據）/2（生成多項式）=2......1（FCS幀檢驗序列/冗餘碼）
接收端：
6（接收的數據）/2（生成多項式，同上的）=3......0
余數為0，判定這個幀無錯，就接受；反之，判定這個幀有差錯（無法確定到位），就丟棄。
2、計算冗餘碼
a、加0：假設生成多項式G（x）的階為r，則加r個0；
例如：10011表示成多項式為X4+X1+X0=X4+X1+1，階為4。（多項式N位，階為N-1位）
b、模2除法：數據臘鍵卜加0後除以多項式，余數為冗餘碼/FCS/CRC檢驗碼的比特序列。
異或：同0異1
3、能夠實現無比特差錯的傳輸，但這還不是可靠傳輸。
C. 數據鏈路層的差錯的檢測和恢復(奇偶校驗碼，CRC校驗，校驗和)，各種運算
在原始的物理傳輸線路上傳輸數據信號是有差錯的，存在一定的誤碼率，數據鏈路層存在的目的就是給原始二進制位流增加一些控制信息 ，實現如何在有差錯的線路上進行無差錯傳輸
數據設定為M位，冗餘位設定為R位，如果位數滿足即認為不出錯，如果位數不滿足即肯定出錯
差錯產生的原因
信道的電氣特性引起信號幅度，頻率，相位的畸變，信號反射，串擾，閃電，大功率電機的啟停等
計算機網路中出現的差錯是連續的還是離散的差錯？ → 是連續的突發性的差錯
比如傳了一個這樣的位串0001101001，連續的差錯：比如一共出錯了3位，連續的出錯在一起。離散的差錯：一共出錯了3位，不是連續出的，是分散出的
保證幀正確，按序送交上層（順序要對，不能重復也不能跳幀）。在接收方能夠判斷接收的數據是否正確，若錯誤還可能要恢復錯誤
糾錯控制主要由接收方做，能檢查出錯並定位到是哪兒出錯了
接收方通過反饋機制告訴發送方出錯，發送方通過重發的方式恢復差錯
☆自動糾錯比檢錯反饋重發機制代價大，在發生數據丟失的情況下，只是自動糾錯機制無法進行差錯恢復，還是需要檢錯反饋重發機制
一個幀包括m個數據位，r個校驗位（是冗餘位，和m位的有效數據是無關的），稱為n位碼字（n=m+r），我們希望r盡量短，並且盡量有一個固定長度
加入了冗餘位，使接收方知道有差錯發生，但不知道什麼差錯，然後請求重發
加入了足夠多的冗餘位，使接收方不僅知道有差錯發生，並知道哪些位發生差錯
兩個編碼的海明距離： 兩個編碼不相同位的個數
例：0000000000與0000011111的海明距離是5
編碼方案的海明距離： 編碼方案中任兩個編碼海明距離的最小值
ASCII這樣的連續編碼的海明距離都是1
為檢測d位錯，編碼方案的海明距離應至少為d+1
當發生d位錯時，不會由一種合法編碼變為另一種合法編碼，也就是想要由一種合法編碼變為另一種合法編碼，需要d+1以上出錯
對接收方來講，它判定一個編碼是否出錯的唯一依據是這個編碼是否是一個合法的編碼。即使接收方收到了一個合法的編碼，它也無法判斷是否是一個合法編碼，因為它不知道這個合法編碼原本就是合法的，還是出錯以後也依然是一個合法編碼。因此需要海明距離應至少為d+1
在數據鏈路層一般是不用這種檢錯方法的，因為檢錯率太低
若接收方收到的位元組奇偶結果不正確，就可以知道傳輸中發生了錯誤
增加奇偶校驗位後海明距離由1變為2，因此根據「為檢測d位錯，編碼方案的海明距離應至少為d+1」，可以檢查出一位二進制位的差錯
用這種方法，有一位出錯時，就會由合法編碼（奇校驗時1的個數為奇數，偶校驗時1的個數為偶數）變成一種非合法編碼（奇數校驗時1的個數為偶數，偶校驗時1的個數為奇數）
為糾正d位錯，編碼方案的海明距離應至少為2d+1
當冊差發生d位錯時，出錯編碼仍然最接近於原始的正確編碼
例：現在有一個編碼方案，這個編碼方案之中只有4種合法編碼↓
0000000000
0000011111
1111100000
1111111111
它們之間的海明距離為5，按衫姿嫌照定理，能夠糾正2位錯
假設接收方收到了這樣的編碼：0001100000，很明顯這是個非法編碼，怎麼樣糾正
呢？我們知道出錯的位數是≤ 2位的，它和第一種的海明距離為2，和第二種為7，和
第三種為3，和第四種為8，離它或手最近的是第一種編碼。它採用這種就近恢復的原則將
出錯的編碼恢復到原始編碼
數據鏈路層用的最多的一種檢錯方法
但是高層（網路層，傳輸層）是不用這種檢錯方法的，而用檢驗和的方法
生成多項式G（x）
發方，收方事前約定。這里的約定是數據鏈路層的協議已經定義該協議使用什麼生成多項式
生成多項式的高位和低位必須為1
生成多項式必須比傳輸信息對應的多項式短
（現在最多用的是CRC-32，生成多項式是32位，能否保證生成多項式比傳輸的對應的多項式短呢？從原始數據來講保證不了，但是到數據鏈路層時加了傳輸層的頭，網路層的頭之後肯定能保證大於32位。比如現在的Internet網路，例如在傳輸層使用TCP加20個位元組，在網路層IP又加了20個位元組，已經超過32位了，所以肯定能保證）
理論上來講生成多項式的階越高，檢錯率越高
硬體實現CRC校驗
四個多項式已經成為國際標准
CRC碼（增加的r位冗餘位檢錯碼，即校驗和）加在幀尾（效率比較高），使帶CRC碼的幀的多項式能被G（x）除盡：接收方接收時，用G（x）去除它，若有餘數，則傳輸出錯
• 模2加法運算定義為：（對應於邏輯異或）
0+0=0 0+1=1 1+0=1 1+1=0
例如0101+0011=0110
• 模2減法運算定義為：（對應於邏輯異或）
0-0=0 0-1=1 1-0=1 1-1=0
例如0110-0011=0101
• 模2乘法運算定義為：
0x0=0 0x1=0 1x0=0 1x1=1
• 模2除法運算定義為：
0 ÷1=0 1÷1=1
利用模2減求余數，余數最高位為1，則商1，否則商0，每商1位則余數減少1位，
直到余數位數少於除數位數
按位與運算：
按位與運算符」&」是雙目運算符。其功能是參與運算的兩數各對應的二進位相與。只有對應的兩個二進位均為1時，結果位才為1，否則為0。參與運算的數以補碼方式出現
例如： 9 & 5
00001001（9的二進制補碼）
&
00000101 （5的二進制補碼）
00000001
可見9 & 5 =1
最高位作為符號位，若符號位為0，則表示正數，若符號位為1，則表示負數
其餘各位代表數值本身的絕對值（以二進製表示）
絕對值相同的正數和負數，它們除了符號位不同外，其他各位都相同
一個數如果值為正，則它的反碼與原碼相同
一個數如果值為負，則將其符號位置為1，其餘各位為對原碼相應數據位取反
（取反：二進制中有0和1兩種狀態，取反就是取與當前狀態相反的狀態，1取反等於0,0取反等於1）
正數的補碼與反碼，原碼相同
負數的補碼則將其最高位置為1，其餘各位為對原碼的相應數據位取反，再對整個數加1
即 X為負數時，【X】補 = 【X】反+1
（+0）補 = 00000000
（-0）反 = 11111111
（-0）補 = 11111111 + 1 = 100000000→進位1捨去→00000000
假設用一個位元組表示一個數，補碼的表示範圍為：-128 ----- +127
用反碼表示的最小值為：-128，其反碼為：10000000
用反碼表示的最大值為：+127，其反碼為：01111111
按位或運算符」|」是雙目運算符。其功能是參與運算的兩數各對應的二進位相或。只要對應的兩個二進位有一個為1時，結果位就為1.參與運算的兩個數均以補碼出現
例如：9|5
00001001
| 00000101
00001101（十進制為13）
可見9|5=13
~為單目運算符，具有右結合性。其功能是對參與運算的數的各二進位按位求反
例如：~9
~（0000000000001001）結果為：1111111111110110
按位異或運算符」 ^ 」是雙目運算符。其功能是參與運算的兩數各對應的二進位相異或。當兩對應的二進位相異時，結果為1。參與運算數仍以補碼出現
例如：9^5
00001001
^ 00000101
00001100（十進制為12）
左移運算符」 ＜＜ 」是雙目運算符。其功能是把 」 ＜＜ 」左邊的運算數的各二進位全部左移若干位，由」 ＜＜ 」右邊的數指定移動的位數，高位丟棄，低位補0
例如：a=00000011（十進制3），a ＜＜ 4，結果為：00110000（十進制48）
右移運算符」 ＞＞ 」是雙目運算符。其功能是把」 ＞＞ 」左邊的運算數的各二進制全部右移若干位，」 ＞＞ 」右邊的數指定移動的位數
例如：a=15（00001111），a ＞＞2，結果為00000011（十進制3）
計算方法例：
※CRC碼計算還有一個好處：
我們希望不管m是多少位的，但是冗餘位r是越短越好，而且最好位數是固定的。用這CRC碼的好處就是生成多項式是多少階的，那麼最後的余數（冗餘位）的位數就是多少位。如果是n階的，那麼最後就是4位
循環冗餘校驗法檢驗不出來的錯的情況：收到的位串雖然是錯誤的，但是恰巧能被生成多項式整除，這個時候檢測不出來
適用於高層協議，如IP，TCP，UDP等
校驗碼放在前面或後面影響都不大，所以絕大多數是放在前面的
檢錯率低於循環冗餘校驗法
在↓例子中，如果第1位和第9位同時出錯，或者第2位和第10位同時出錯···出錯，那麼它們取反相加的數是不變的，這個時候是檢查不出錯的。但是網路當中連續突發的錯占絕大部分，這種跳躍性的出錯概率很小，所以檢驗和的檢錯率還是比較高的
高層不用冗餘校驗法的原因是，冗餘校驗法主要採用除的計算方式，比累加的（校驗和）計算方式效率要低，而數據鏈路層用這種方法可以用硬體實現，但是網路層和傳輸層一般只能通過軟體實現，那麼效率就降低了。而且數據鏈路層已經提供了比較可靠的支持，所以高層就可以用這種檢錯率相對低一點的檢錯法
檢驗欄位初值置0，數據拆分成與檢驗欄位等長的分片，不足部分補0，將所有分片逐位取反，並連續累加，丟棄最高進位，計算結果置於檢驗欄位。接收端執行相同的過程（分段處理，取反累加，把累加出的校驗和與校驗碼欄位當中保存的校驗和進行比對，如果是完全一致就沒錯），並將計算結果和傳輸過來的檢驗和進行比較以確定是數據是否出現差錯
D. 數據鏈路層的三個基本內容(幀定界、透明傳輸和差錯檢測)都包含哪些內容
幀的首部必須設有一些特殊的比特組合，使得接收端能夠找出一幀的開始。這也稱為幀定界。幀定界還包含確定幀的結束位置.
網路的各層協議都是相當復雜的。當我們在電腦上編輯好一封郵件後，只要用滑鼠點擊一下「發送」按鈕，這封電子郵件就發送出去了。實際上，我們的電腦要使用好幾個網路協議。可是這些復雜的過程我們都看不見。因此，這些復雜的網路協議對網路用戶來說都是「透明的」。意思是：這些復雜的網路協議雖然都是存在於電腦中，但用戶卻看不見（如果要看，就要使用專門的網路軟體）。
差錯校驗是在數據通信過程中能發現或糾正差錯，把差錯限制在盡可能小的允許范圍內的技術和方法。
包括奇偶校驗碼是一種通過增加冗餘位使得碼字中「枝羨1」的個數為奇數或偶數的編碼方法，它是一種檢錯碼。
水平奇偶校驗的特點及編碼規則
特點：水平奇偶校驗又稱橫向奇偶校驗，它不但大模能檢測出各段同一位上的奇數個錯，而且還能檢測出突發長度<=p的所有突發錯誤。其漏檢率要比垂直奇偶校驗方法低，但實現水平奇偶校驗時，一定要使用數據緩沖器。
水平垂直奇偶校驗的特點及編碼規則
特點：水平垂直奇偶校驗又稱縱橫奇偶校驗。它能檢測出所有3位或3位以下的錯誤、奇數個錯、大部分偶數個錯以及突發長度<=p+1的突發錯。可使誤碼率降至原誤碼率的百分之一到萬分之一。還可以用來糾正部分差錯。有部分偶數個錯不能測出。適猛仿拍用於中、低速傳輸系統和反饋重傳系統。