一、關于糾錯與檢錯

糾正數據傳輸中出現的錯誤原則上可有兩種做法：一是直接采用糾錯碼對某些錯碼進行糾正；二是利用檢錯碼（校驗碼）進行檢錯，然后對出錯幀進行重傳。糾錯碼以增加附加比特，也即降低傳輸效率為代價，換來糾錯能力。糾錯碼在某些場合較有實用價值，如單工信道，由于收方即使檢測到錯誤也不可能通知發方重傳，要想保證傳輸內容的正確性，只好采用糾錯碼。在大多數情況下，采用檢錯碼加重傳的方式效率更高，特別是在通信誤碼率較低的場合。

最簡單的檢錯方式為奇偶校驗法，即在每個數據塊上增加1個奇偶位，當數據塊中出現奇數個比特錯時能被檢測出來，因此能檢測到差錯的概率只有0.5，這很難被接受。改進措施可以采取將每個數據塊組成一個n位寬和k位高的長方形的矩陣來發送。按列計算奇偶并將各列的奇偶校驗位放在一起，作為矩陣的最后一行，而發送時則按行進行。數據塊到達時，收方檢測所有的奇偶位。假若其中任何之一錯了，就需要重傳整個塊。這樣做，對非單比特突發性錯（多比特連續錯）在橫行的發送中可能影響到數列的單個比特，而容易被相關列中的奇偶校驗位檢測出來。

這種方法能夠檢測長度為n的非單個突發性差錯，長度大于n的突發性連續差錯將不會被檢測到（注意：一個突發性非單比特錯并不是意味著所有的位都出錯了，但至少第1和最后1位出錯），因為每列中就可能出現偶數個比特錯，該列的奇偶校驗不能檢查出偶比特錯。假若一個塊被一個長的突發干擾或多個較短突發干擾所破壞，n列中每1列的奇偶值碰巧都正確的概率為0.5，那么，這個出錯塊被當作正確數據接受的概率是2 ^-n。

欲進一步了解差錯控制編碼原理的請進入。

二、關于循環冗余校驗碼（CRC）

盡管上述策略有時已經足夠了，但在實踐中廣泛采用的是另一種方法，即多項式編碼，也叫循環冗余校驗碼（CRC，Cyclic Redundancy Check）。多項式碼將比特串看成系數只能取0或1的多項式，因此，一個k比特幀可以看成從x ^k-1到x⁰的k項多項式的系數序列。這個多項式的階數為k-1，高位（最左邊）是x ^k-1的系數；下一位是x ^k-2的系數，依次類推。例如，110001具有6位，其中2⁵、2⁴和2⁰的系數為1，相應的多項式表示為x ⁵+ x ⁴+ x ⁰。

1、關于模2運算：為了進行后面的討論，先對多項式運算作一簡要介紹。多項式以2為模運算，加法不進位，減法不借位。模2加法和減法實際上都是進行邏輯“異或”運算。例如下圖2-1-1：

圖2-1-1：以2為模運算法

多項式除法同二進制運算一樣，只要被除數具有和除數同樣多的位，即把除數按模2從被除數中減去（也即按模2進行加法)。

如果采用多項式編碼法，發方和收方必須事先商定一個生成多項式G(x)（Generator polynomial）。生成多項式的最高位（比特）和最低位必須是1。要計算m位的幀M(x)的校驗和（Checksum，也常稱為幀校驗序列（FCS，Frame Check Sequence）），生成多項式必須比該多項式M(x）短。其基本思想是：將校驗和加在幀的末尾，使這個帶校驗和的幀的多項式能被G(x)除盡。顯然，用G(x)除M(x)所得余數作為校驗和（FCS）與M(x)一道組成的帶校驗和的幀一定能被G(x)整除。當收方收到該幀時，用G(x)相除，如果有余數，則表明傳輸有錯。計算校驗和的算法如下表2-1所示。

表2-1：計算校驗和的算法過程

下圖2-1-2演算了幀1101011011被G(x)＝x ⁴+x+1除而獲得余數的計算過程。在圖中，原始幀的比特串M(x)為：1101011011，相應的多項式為：

圖2-1-2：模2除法過程

x ⁹+ x ⁸+ x ⁶+ x ⁴+ x ³+ x¹ + x ⁰

生成多項式的比特串G(x)t：10011，相應的多項式為

x ⁴+ x ¹+ x ⁰

加上4個0的幀為：11010110110000，相應的多項式為：

x ¹³+ x ¹²+ x ¹⁰+ x ⁸+ x ⁷+ x ⁵+ x ⁴

用加0后的幀除以G(x)，經上圖中計算后獲得的余數為：1110，加上4個0的幀與余數相加，即得到用于線路上傳送的幀的比特串T(x)： 11010110111110。在任何除法問題中，如果用被除數減去余數，則剩下的部分能夠被除數除盡。由于T(x)是由被除數減去余數得來的，顯然能被被除數G(x)除盡（模2）。

2、CRC的檢錯能力分析：現在讓我們來分析這種方法的檢錯能力，看看它能夠檢查出什么類型的誤碼。如果出現了1個突發性連續差錯（Burst Errors），記作少E(x)，則收到的多項式會變成T(x)+E (x) 。突發性連續差錯的特點是初始位是“1”，然后是“0”和“1”的某種組合，最后一個比特為“1”。由于E(x)中的每個“1”都會使T(x)中的對應比特變反，因此，如果E (x)中有k個“1”，即會產生k比特的差錯。

由于有E(x)的存在，接收方所收到的幀，將變為帶校驗和的多項式T(x)與E (x)之和。收方用生成多項式G(x)去除收到的幀，即計算[T(x)+E(x)]/ G(x)。由于T(x)/ G(x)余數總是0，所以運算結果就變成E(x)/G(x)的余數。如果E(x)能被G(x)整除，余數為0。這可能有兩種情況：① E(x)=0；② E(x)是G(x)的整數倍。因此，如果收方用余數為移判定傳輸無錯，只有情況②屬于判斷錯誤；情況①則代表確無差錯。

假定傳輸過程中只有單個比特錯，即E(x) = x ⁱ (i為T(x)出錯比特項次），由于G(x)內至少有兩項為1，因此，E(x)/G(x)不可能余數為0，于是所有的單比特差錯都能被查出。

如果發生兩個孤立的單比特差錯，即E(x) = x ⁱ +x ^j（其中i>j）。我們把E(x)改寫成：

E(x)＝x ^j (x ^i-j+1)

如果我們假定G(x)不能被x ^j整除，那么能夠發現兩個比特錯的充分條件是：對小于或等于i-j的最大值（即最大幀長）的任何k值，G(x)都不能除盡x ^k+1。已經知道一些可用于長幀糾錯的簡單低階多項式。例如，對于小于32768（比特）的k值，x¹⁵+x¹⁴+1不可能整除差錯多項式E(x)＝x ^k+1。

如果有奇數個比特錯，E(x)將包括奇數個項（例如，x⁵+x²+1 )。由于奇數項多項式都不能被x+1按模2整除，因此，如果選用x+l的整數倍的多項式做G(x)就能查出所有奇數個比特變反的差錯。為了證明項數為奇數的多項式不能被x+l整除，我們先假定E(x)為奇數項多項式，且能被x+1整除。將E(x)進行因式分解，變成(x+1)Q(x)。現在代人值E(1)=(1+1)Q(1)。因為1+1=0（模2），故E(1)=0。如果E(x)具有奇數個項，用1替換所有的x，按模2相加所產生的結果將總是1，與按上述假設計算的結果E(1)=0相矛盾。因此，奇數的多項式不能被x+l整除。

3、CRC的檢錯能力結論：通過上述分析得到最重要的結論是：r比特的校驗碼能檢查出所有長度≤r的突發性連續差錯。一個長度為k的突發性連續差錯可以表示成x ⁱ（x ^k-1+…+1 )，這里項次i為突發性連續差錯的結束位置距接收到的幀最低階比特的距離（比特數）。如果G(x)包括有x⁰項，它將不能被x ⁱ整除，因此如果圓括號內的表達式的階低于G(x)的階，余數不可能為0。

如果突發性連續差錯長度為r+1，當且僅當突發性連續差錯E(x) 與G(x)一樣時，被G(x)除的余數才可能是0。根據突發性連續差錯的定義，第一位和最后一位必須是1，因此，它是否相等取決于r-1個中間比特的取值。如果所有0或1排列出現的概率均等，則將這個出錯幀當作正確幀接收的概率是1/2 ^r-1。

可以證明：當一個長度大于r+1的突發性連續差錯或幾個較短的突發性連續差錯發生后，假定被破壞后的幀內所有比特值為“1”或“0”出現的模式是等概率的，則一個出錯幀未被檢查出來的概率是1/2 ^r。

目前已有多個生成多項式[G(x)]被列為國際標準。其中CRC-12用作以6比特字符為基礎的幀校驗；其余生成多相式用于以8比特字符為基礎的幀校驗。使用如CRC-16或CRC-CCITT作為生成多項式所產生的16位的校驗和。能查出所有的單比特錯和雙比特錯、所有的奇數比特錯、所有長度等于或小于16比特的突發性連續差錯，99.99%的17比特突發性連續差錯以及99.998%的18比特或18比特以上錯。

盡管校驗和計算看起來相當的復雜，但和提出用一種簡單移位寄存器方法，用硬件來完成對校驗和的檢驗，因而在實踐中幾乎都采用這種硬件來實現。

欲進一步了解循環冗余碼（CRC）多項式標準的請進入。