差錯檢測和糾正技術
資料在傳輸的過程中難免會出現差錯（比如經過路由轉發時），是以我們需要一些差錯檢測和糾正技術來檢測資料中的差錯并糾正，使接收方收到正确的資料，也避免發送方對資料進行重傳。
下圖是差錯檢測和糾正的場景示意圖。
在發送結點為了保護資料中比特免受差錯，使用差錯檢測和糾正比特（Error-Detection and-Correction，EDC）來增強資料D。通常需要受保護的資料不僅包括從網絡層傳遞下來需要通過鍊路傳輸的資料報，而且包括鍊路幀首部中的鍊路級的尋址資訊、序号和其他字段。
鍊路級幀中的D和EDC都被發送至接收結點。接收結點接收到比特序列D'和EDC'。因為在傳輸中，比特可能發生翻轉是以導緻D'和EDC'與初始的D和EDC不同。
在接收方這邊，它的挑戰是在僅知D'和DEC'的情況下，就判斷D'和初始的D是否一緻。差錯檢測和糾正技術也使接收方檢測出已經出現的比特差錯，但也可能有
未檢出比特差錯（undetected bit error），也就是說，接收方接收的資訊中還會包含比特差錯。是以我們要選擇一個差錯檢測方案使這種事情發生的機率很小。一般而言，差錯檢測和糾正技術越複雜，開銷也就越大。
下面介紹傳輸資料中檢查差錯的3種技術。奇偶校驗（它用來描述差錯檢測和糾正背後隐含地基本思想）、檢驗和方法（通常更多地應用于應用層）和循環備援檢測（通常更多地應用于擴充卡中的鍊路層）。
奇偶校驗
也許差錯檢測最簡單的方式就是用單個奇偶校驗位（parity bit）。在偶校驗方案中，發送方隻需包含一個附加的比特，選擇它的值，使得這d+1個比特（初始資訊加上一個校驗比特）中1的總數為偶數。對于奇校驗方案，選擇校驗位比特值使得有奇數個1。
下圖是1比特偶校驗。
采用單個奇偶校驗位的方式，接收方操作也很簡單。統計d+1中比特為1的個數，在采用偶校驗方法中如果出現了奇數個1，接收方知道至少出現了一個比特差錯，準确地說為，出現了
奇數個比特差錯。
倘若出現了偶數個比特差錯，這将會導緻出現未檢出的差錯。經過測量，這種差錯經常以“突發”形式聚集在一起，是以我們需要一個更健壯的差錯檢測方案（實踐中也是使用更健壯的方案）。在介紹實踐中使用的方案，我們繼續介紹奇偶校驗的一種簡單的一般化方案，深入了解糾錯技術。
下圖顯示的是單比特奇偶檢驗方案的二維一般化方案。d個比特被劃分為i行j列。對每行每列計算奇偶值。産生i+j+1奇偶比特構成了鍊路層幀的差錯檢測比特。比特被改變的行和列都可以檢測出現差錯，并且還可以利用存在奇偶校驗差錯的列和行的索引來實際識别發生差錯的比特并糾正它。
現在假設初始d比特中出現了單個比特差錯。下圖是一個例子。
接收方檢測和糾錯的能力被稱為前向糾錯（Forward Error Correction，FEC）。這些技術通常用于如音頻CD這樣的音頻存儲和回放裝置中。接收方發現錯誤可以立即糾錯，避免了使發送方重傳資料，這對實時網絡應用和具有長傳播時延的鍊路（如深空間鍊路）很有幫助。
檢驗和
在檢驗和技術中，将d比特資料作為一個k比特整數的序列處理。
一個簡單的檢驗和方法就是将這k比特整數加起來，并且用得到的和作為差錯檢測比特。
檢驗和需要相對較小的分組開銷。
網際網路檢驗和（Internet checksum）便是基于這種方法，即資料的位元組作為16比特的整數對待并求和。這個和的反碼形成了攜帶在封包段首部的檢驗和字段。
接收方通過對接收的資料（包括檢驗和）的和 取反碼，并且檢測其結果結果是否全為1比特來檢測檢驗和。如果這些比特中有任何比特為0，就可以訓示錯誤。
循環備援檢測
如今的計算機網絡中廣泛地應用的差錯檢測技術基于循環備援檢測（Cyclic Redundancy Check，CRC）編碼。CRC編碼也稱為 多項式編碼（polynomial code） ，該編碼能夠将發送的比特串看作為系數是0和1一個多項式，對比特串的操作被解釋為多項式運算。
CRC編碼操作如下
考慮d比特資料D，發送結點要将它發送給接收結點。
發送方和接收方首先必須商議一個r+1比特模式，稱為生成多項式（generator），将其表示為G，要求G的最高有效位為1（最左邊）。
對于一個給定的資料段D，發送方要選擇r個附加比特R，并将它們附加到D上使得得到的d+r比特模式（被解釋成一個二進制數）用模2算術恰好能被G整除。在接收方這邊，用G除以接收到的d+r比特，如果餘數不為0，接收友善知道了差錯，若餘數為0，則接收資料。
所有CRC采用模2運算算術，在加法中不進位，減法中不借位，即等價于異或運算（XOR），乘法和除法也相同。并且，D*2^k XOR R産生如上圖所示的d+r比特模式。
舉例說明
如上圖所示，D = 101110，d = 6，G = 1001，和r = 3的情況下計算R。得出R = 011。
于是發送方會傳輸9個比特101110011。
國際标準已經定義了8,12,16和32比特生成多項式G。其中CRC-32 32比特的标準被多種鍊路級IEEE協定采用。
每個CRC标準都可以檢測小于r+1比特的突發錯誤（意味着所有連續的r比特或者更少的差錯都可以檢測到）。每個CRC标準也能檢測任何奇數個比特差錯。
《計算機網絡 自頂向下方法》學習筆記
每天進步一點點，不要停止前進的腳步~