CRC的檢錯能力

1、一. Cyclic Redundancy Check什么是CRC？循環(huán)碼是的倍數(shù)，使得我們可以用圖9.3.3這樣的除法電路方便地得到伴隨式。另外對于(n,k)循環(huán)碼，是的因子，這一點是循環(huán)性的來源，正是它使得具有循環(huán)關(guān)系的錯誤圖樣可以共享識別電路。如果我們只想檢錯，不打算糾錯，則可以不要求是的因子。事先選定一個r次的，將任意k個信息碼組用類似圖9.3.2這樣的編碼器編成系統(tǒng)碼，得到一個長為的碼，則是的倍數(shù)。這就是CRC。由于k是任意的，因此將不一定是的因子，故的循環(huán)移位不一定是的倍數(shù)，即循環(huán)封閉的特性不能保證，即CRC不是循環(huán)碼。但因為這種方法直接源自循環(huán)碼，所以歸在循環(huán)碼中。CRC常用的生成

2、多項式見表9.3.4CRC編譯碼器CRC編碼器就是系統(tǒng)碼的循環(huán)碼編碼器，如圖9.3.5所示。CRC接收端（檢錯）和循環(huán)碼譯碼器相同，但因為只是檢錯，所以不需要識別非0錯誤圖樣，不需要糾錯電路，只需要識別余式是不是全零，如圖9.3.6所示。CRC的檢錯能力1CRC的編碼結(jié)果是一個分組碼。前面講過，分組碼可保證檢出個錯。但用最小碼距來判斷CRC的檢錯能力是很不充分的，因為CRC的最小碼距有可能很小。線性分組碼的最小碼距是非0碼的最小碼重。碼重就是（，的次數(shù)不超過）中系數(shù)不為0的項的個數(shù)，例如的碼重是2。假如存在某個，使得，則最小碼距僅為2。如果出現(xiàn)，則最小碼距僅為3。而k的任意性不能排除這種情況的

3、發(fā)生。注意前面我們說的是保證檢出e位錯，不是只能檢出e位錯。2CRC的編碼結(jié)果有種不同，它們都是的倍數(shù)。信道中可能發(fā)生的非全0錯誤圖樣共有種。當(dāng)錯誤圖樣能被整除，也即錯誤圖樣自身是編碼器的可能輸出之一時，這樣的錯誤將騙過接收端。這種錯誤圖樣的個數(shù)是個，占總錯誤圖樣的比例為。例如：CRC-16不能檢出的錯誤圖樣只是總可能錯誤圖樣的，約為六萬分之一。3上述的討論不涉及信道中發(fā)生的錯誤是隨機錯還是突發(fā)錯。突發(fā)錯的定義是：錯誤只出現(xiàn)在連續(xù)L個比特內(nèi)（這L個不一定都錯，但這L個之外無錯）。突發(fā)長度為L的突發(fā)錯的錯誤圖樣可以表示為的形式，其中。注意到如果的次數(shù)小于的次數(shù)r，則不可能被整除，同樣也不能被整除

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

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

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

7、（是17位）的最高位自然也是固定的0，這個已知的比特沒有必要傳送，故可刪去，從而使編碼器實際的輸出只有16位。譯碼端在收到16位后，在最高位補上一個0，再按BCH(17,9)去譯碼，譯碼結(jié)果刪去最高位，得到發(fā)送的8位信息。如果BCH(17,9)的譯碼結(jié)果最高位不是0（即譯碼器以為最高位有錯），則知道譯錯了。Fig. 1 (17,9)縮短為(16,8)Fig. 2 用(17,9)譯碼器來譯(16,8)編碼注1：如果不借助BCH的設(shè)計，直接設(shè)計(32,21)或者(16,8)線性分組碼將不是一件容易的事情。如果不借助BCH的譯碼器，設(shè)計出來以后怎么譯也可能是個問題。注2：循環(huán)碼經(jīng)過上述的加長或者縮短后一般不再