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

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

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

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

欲進(jìn)一步了解差錯(cuò)控制編碼原理的請(qǐng)進(jìn)入。

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

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

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

圖2-1-1：以2為模運(yùn)算法

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

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

表2-1：計(jì)算校驗(yàn)和的算法過(guò)程

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

圖2-1-2：模2除法過(guò)程

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

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

x ⁴+ x ¹+ x ⁰

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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