一、關(guān)于糾錯與檢錯

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

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

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

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

二、關(guān)于循環(huán)冗余校驗碼（CRC）

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

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

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

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

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

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

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

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

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

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

x ⁴+ x ¹+ x ⁰

加上4個0的幀為：11010110110000，相應(yīng)的多項式為：

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

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

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

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

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

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

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

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

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

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

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

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

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

盡管校驗和計算看起來相當(dāng)?shù)膹?fù)雜，但和提出用一種簡單移位寄存器方法，用硬件來完成對校驗和的檢驗，因而在實踐中幾乎都采用這種硬件來實現(xiàn)。

欲進一步了解循環(huán)冗余碼（CRC）多項式標(biāo)準(zhǔn)的請進入。