1、一.CyclicRedundancyCheck什么是CRC?循環(huán)碼c(x)>g(x)的倍數(shù)，使得我們可以用圖9.3.3這樣的除法電路方便地得到伴隨式s(x>另外對(duì)于(n,k)循環(huán)碼，g(x淮xn+1的因子，這一點(diǎn)是循環(huán)性的來(lái)源，正是它使得具有循環(huán)關(guān)系的錯(cuò)誤圖樣可以共享識(shí)別電路。如果我們只想檢錯(cuò)，不打算糾錯(cuò)，則可以不要求g(x)>xn+1的因子。事先選定一個(gè)r次的g(x),將任意k個(gè)信息碼組u(x叩類似圖9.3.2這樣的編碼器編成系統(tǒng)碼，得到一個(gè)長(zhǎng)為n=k+r的碼c(x),則c(x)是g(x)的倍數(shù)。這就是CRC。由于k是任意的，因此g(x)將不一定是xk+1=xn+1的因子，

2、故cx)的循環(huán)移位xic(x)mod(xn+1評(píng)一定是g(x)的倍數(shù)，即循環(huán)封閉的特性不能保證，即CRC不是循環(huán)碼。但因?yàn)檫@種方法直接源自循環(huán)碼，所以歸在循環(huán)碼中。CRC常用的生成多項(xiàng)式見(jiàn)表9.3.4CRC編譯碼器CRC編碼器就是系統(tǒng)碼的循環(huán)碼編碼器，如圖9.3.5所示。CRC接收端(檢錯(cuò))和循環(huán)碼譯碼器相同，但因?yàn)橹皇菣z錯(cuò)，所以不需要識(shí)別非0錯(cuò)誤圖樣，不需要糾錯(cuò)電路，只需要識(shí)別余式是不是全零，如圖9.3.6所示。CRC的檢錯(cuò)能力1. CRC的編碼結(jié)果是一個(gè)(k+r,k價(jià)組碼。前面講過(guò)，分組碼可保證檢出e=dm.-1個(gè)錯(cuò)。但用最小碼距來(lái)判斷CRC的檢錯(cuò)能力是很不充分的，因?yàn)镃RC的最小碼距有可

3、能很小。線性分組碼的最小碼距是非0碼的最小碼重。碼重就是b(x)g(x)(b(x)#0,b(x)的次數(shù)不超過(guò)k-1)中系數(shù)不為0的項(xiàng)的個(gè)數(shù)，例如x4+x的碼重是2。假如存在某個(gè)b(x),使得b(xb(x)=xm+1,則最小碼距僅為2。如果出現(xiàn)xm1+xm2+1,m1Am2A0,則最小碼距僅為3。而k的任意性不能排除這種情況的發(fā)生。注意前面我們說(shuō)的是保證,檢出e位錯(cuò),不是只能檢出e位錯(cuò)。2. CRC的編碼結(jié)果有2k種不同，它們都是g(x)的倍數(shù)。信道中可能發(fā)生的非全0錯(cuò)誤圖樣共有2n-1=2k4r-1種。當(dāng)錯(cuò)誤圖樣能被g(x)整除，也即錯(cuò)誤圖樣自身是編碼器的可能輸出之一時(shí)，這樣的錯(cuò)誤將騙過(guò)接收端

4、。這種錯(cuò)誤圖樣的個(gè)數(shù)是2k-1個(gè)，占總錯(cuò)誤圖樣的2k1比例為2+1*2,例如：CRC-16不能檢出的錯(cuò)誤圖樣只是總可能錯(cuò)誤圖樣的-1,約2kr-1216為六萬(wàn)分之一。3. 上述的討論不涉及信道中發(fā)生的錯(cuò)誤是隨機(jī)錯(cuò)還是突發(fā)錯(cuò)。突發(fā)錯(cuò)的定義是：錯(cuò)誤只出現(xiàn)在連續(xù)L個(gè)比特內(nèi)(這L個(gè)不一定都錯(cuò)，但這L個(gè)之外無(wú)錯(cuò))。突發(fā)長(zhǎng)度為L(zhǎng)的突發(fā)錯(cuò)的錯(cuò)誤圖樣可以表示為xmex)的形式，其中e'(x)=xL,+1。注意到如果e'(x)的次數(shù)L1小于g(x)的次數(shù)r,則e'(x)不可能被g(x)整除，同樣xme'(x)也不能被g(x)整除。因此crc可保證檢出長(zhǎng)度不超過(guò)r+1=n-k+1的

5、突發(fā)錯(cuò)。比如CRC-16可以檢出一切突發(fā)長(zhǎng)度不超過(guò)16位的突發(fā)錯(cuò)。二.BCH碼BCH碼是循環(huán)碼的一個(gè)子集，它的特點(diǎn)是(1)存在系統(tǒng)的方法設(shè)計(jì)各種需要的碼。表9.4.1和表9.4.2是根據(jù)這些設(shè)計(jì)方法設(shè)計(jì)出的結(jié)果。注1:對(duì)于一般的線性分組碼，我們沒(méi)有一套系統(tǒng)的方法來(lái)回答像“設(shè)計(jì)一個(gè)(n,k)碼使它能保證糾t個(gè)錯(cuò)”這樣的問(wèn)題。許多情況下，我們甚至不能判斷這個(gè)問(wèn)題有解還是無(wú)解。BCH能。注2:表9.4.1和表9.4.2中給出了八進(jìn)制表示的g(x)。例如對(duì)于BCH(15,11),表中給出的生成多項(xiàng)式是23,代表二進(jìn)制的010011,即g(x)=x4+x+1(2)存在一些實(shí)用的譯碼算法三.RS碼迄今為止

6、，我們談?wù)摰亩际嵌M(jìn)制編碼。前述的分組碼、線性分組碼、循環(huán)碼、BCH碼的概念也可以是多進(jìn)制的。q進(jìn)制編碼中的“數(shù)”不再是0、1,而是0、1、q-1。所有二進(jìn)制編碼中的概念都可以拿到這里。比如生成矩陣、監(jiān)督矩陣、生成多項(xiàng)式等。唯一的差別是：現(xiàn)在不是GF(2)上的運(yùn)算，而是GF(q)上的運(yùn)算。雖然GF(2)上的運(yùn)算就是普通十進(jìn)制運(yùn)算的結(jié)果模二，但GF(q)上的運(yùn)算不一定是普通運(yùn)算模q。要想完全弄明白這些，你需要學(xué)更多的有限域(伽羅華域，GaloisField)方面的知識(shí)。RS碼是q進(jìn)制BCH的一個(gè)子類。四.加長(zhǎng)與縮短實(shí)際中可能會(huì)遇到這樣的情形，所設(shè)計(jì)出的編碼的長(zhǎng)度由于硬件位數(shù)或者其它原因感到不很方

7、便。比如BCH可以給出(31,21)這樣的設(shè)計(jì)，但設(shè)計(jì)硬件時(shí)也許更希望編碼是32位的。此時(shí)可以把BCH(31,21)的編碼結(jié)果再做一次偶校驗(yàn)補(bǔ)上一個(gè)校驗(yàn)位，從而形成一個(gè)(32,21)編碼。這樣的操作叫加長(zhǎng)。接收端可以不理睬這個(gè)增加的校驗(yàn)比特，仍然按BCH(31,21)譯碼以便能夠繼續(xù)使用BCH的譯碼算法。不過(guò)這個(gè)比特也可以利用，比如至少可以用來(lái)判斷BCH譯碼的結(jié)果是否正確。如果我們?cè)O(shè)計(jì)出的是BCH(17,9),相應(yīng)也有縮短的操作使它變成一個(gè)(16,8)編碼。具體做法是，把BCH（17,9）的系統(tǒng)碼編碼器的9個(gè)輸入信息位中的最高位固定為0（實(shí)際輸入的只有8位信息），編碼結(jié)果（是17位）的最高位自

8、然也是固定的0,這個(gè)已知的比特沒(méi)有必要傳送，故可刪去，從而使編碼器實(shí)際的輸出只有16位。譯碼端在收到16位后，在最高位補(bǔ)上一個(gè)0,再按BCH（17,9）去譯碼，譯碼結(jié)果刪去最高位，得到發(fā)送的8位信息。如果BCH（17,9）的譯碼結(jié)果最高位不是0（即譯碼器以為最高位有錯(cuò)），則知道譯錯(cuò)了。Fig. 2用（17,9）譯碼器來(lái)譯（16,8）編碼人薄左£9 一注1:如果不借助BCH的設(shè)計(jì)，直接設(shè)計(jì)（32,21）或者（16,8）線性分組碼將不是一件容易的事情。如果不借助BCH的譯碼器，設(shè)計(jì)出來(lái)以后怎么譯也可能是個(gè)問(wèn)題。注2:循環(huán)碼經(jīng)過(guò)上述的加長(zhǎng)或者縮短后一般不再有循環(huán)封閉性。例如將生成多項(xiàng)式為3X+x+1的（7,4）循環(huán)雙明碼增加一位偶校驗(yàn)成為（8,4）碼。（7,