多項(xiàng)式域編碼(修改)

1、1有限域多項(xiàng)式碼有限域多項(xiàng)式碼2匯報(bào)內(nèi)容匯報(bào)內(nèi)容Reed-Muller碼循環(huán)碼31948年，年，Bell實(shí)驗(yàn)室的實(shí)驗(yàn)室的C.E.Shannon發(fā)表的發(fā)表的通信的數(shù)學(xué)理論通信的數(shù)學(xué)理論，是關(guān)，是關(guān)于現(xiàn)代信息理論的奠基性論文，它的發(fā)表標(biāo)志著信息與編碼理論這一學(xué)科于現(xiàn)代信息理論的奠基性論文，它的發(fā)表標(biāo)志著信息與編碼理論這一學(xué)科的創(chuàng)立。的創(chuàng)立。Shannon在該文中指出，任何一個(gè)通信信道都有確定的信道容量在該文中指出，任何一個(gè)通信信道都有確定的信道容量C，如果通信系統(tǒng)所要求的傳輸速率如果通信系統(tǒng)所要求的傳輸速率R小于小于C，則存在一種編碼方法，當(dāng)碼長(zhǎng)，則存在一種編碼方法，當(dāng)碼長(zhǎng)n充分大并應(yīng)用最大似然譯

2、碼（充分大并應(yīng)用最大似然譯碼（MLD，MaximumLikelihoodDecoding）時(shí)，）時(shí)，信息的錯(cuò)誤概率可以達(dá)到任意小。信息的錯(cuò)誤概率可以達(dá)到任意小。Shannon指出了可以通過(guò)差錯(cuò)控制碼在信息傳輸速率不大于信道容量指出了可以通過(guò)差錯(cuò)控制碼在信息傳輸速率不大于信道容量的前提下實(shí)現(xiàn)可靠通信，但卻沒(méi)有給出具體實(shí)現(xiàn)差錯(cuò)控制編碼的方法。的前提下實(shí)現(xiàn)可靠通信，但卻沒(méi)有給出具體實(shí)現(xiàn)差錯(cuò)控制編碼的方法。20世紀(jì)世紀(jì)40年代，年代，R.Hamming和和M.Golay提出了第一個(gè)實(shí)用的差錯(cuò)控制編碼方提出了第一個(gè)實(shí)用的差錯(cuò)控制編碼方案，使編碼理論這個(gè)應(yīng)用數(shù)學(xué)分支的發(fā)展得到了極大的推動(dòng)。案，使編碼理論這

3、個(gè)應(yīng)用數(shù)學(xué)分支的發(fā)展得到了極大的推動(dòng)。4雖然漢明碼的思想是比較先進(jìn)的，但是它也存在許多難以接受的缺點(diǎn)。雖然漢明碼的思想是比較先進(jìn)的，但是它也存在許多難以接受的缺點(diǎn)。首先，漢明碼的編碼效率比較低，它每首先，漢明碼的編碼效率比較低，它每4個(gè)比特編碼就需要個(gè)比特編碼就需要3個(gè)比特的個(gè)比特的冗余校驗(yàn)比特。冗余校驗(yàn)比特。另外，在一個(gè)碼組中只能糾正單個(gè)的比特錯(cuò)誤。另外，在一個(gè)碼組中只能糾正單個(gè)的比特錯(cuò)誤。Reed-Muller碼是碼是Muller為交換電路的設(shè)計(jì)和錯(cuò)誤檢測(cè)于為交換電路的設(shè)計(jì)和錯(cuò)誤檢測(cè)于1954年首先提年首先提出的，此后出的，此后Reed在在Muller提出的分組碼的基礎(chǔ)上得到了一種新的分組

4、碼，提出的分組碼的基礎(chǔ)上得到了一種新的分組碼，稱(chēng)為稱(chēng)為Reed-Muller碼，簡(jiǎn)記為碼，簡(jiǎn)記為RM碼，將它用于通信和數(shù)據(jù)存儲(chǔ)領(lǐng)域，并設(shè)碼，將它用于通信和數(shù)據(jù)存儲(chǔ)領(lǐng)域，并設(shè)計(jì)出了計(jì)出了RM碼的第一個(gè)頁(yè)碼算法，也就是著名的大數(shù)邏輯譯碼算法。在碼的第一個(gè)頁(yè)碼算法，也就是著名的大數(shù)邏輯譯碼算法。在1969年到年到1977年之間，年之間，RM碼在火星探測(cè)方面得到了極為廣泛的應(yīng)用。即使在今碼在火星探測(cè)方面得到了極為廣泛的應(yīng)用。即使在今天，天，RM碼也具有很大的研究?jī)r(jià)值，其快速的譯碼算法非常適合于光纖通信碼也具有很大的研究?jī)r(jià)值，其快速的譯碼算法非常適合于光纖通信系統(tǒng)。系統(tǒng)。5Reed-Muller碼的優(yōu)點(diǎn)

5、碼的優(yōu)點(diǎn)相比漢明碼和格雷碼能夠糾正多個(gè)隨機(jī)錯(cuò)誤，同時(shí)，它的譯碼算法也相比漢明碼和格雷碼能夠糾正多個(gè)隨機(jī)錯(cuò)誤，同時(shí)，它的譯碼算法也比較簡(jiǎn)單，可以在很低的譯碼復(fù)雜度下，獲得較好的誤碼性能。比較簡(jiǎn)單，可以在很低的譯碼復(fù)雜度下，獲得較好的誤碼性能。678兩個(gè)兩個(gè)n重重x，y之間，對(duì)應(yīng)位取值不同的個(gè)數(shù)稱(chēng)為它們之間的漢明距離；之間，對(duì)應(yīng)位取值不同的個(gè)數(shù)稱(chēng)為它們之間的漢明距離；n重重x中非零碼元的個(gè)數(shù)，稱(chēng)為它們的漢明重量，簡(jiǎn)稱(chēng)距重，用中非零碼元的個(gè)數(shù)，稱(chēng)為它們的漢明重量，簡(jiǎn)稱(chēng)距重，用w（x）表示表示9r階的階的Reed-Muller碼碼R(r,m)，是，是n,k,d碼，碼，n=2m,k=1,d=2（m-r）

6、 考慮兩個(gè)極端情況，即階數(shù)為考慮兩個(gè)極端情況，即階數(shù)為0和和m。0階的階的Reed-Muller碼碼R(0,m)=0,1，因此，因此0階階Reed-Muller碼只是長(zhǎng)度為碼只是長(zhǎng)度為2m的的0或或1的重復(fù)碼。而的重復(fù)碼。而m階的階的Reed-Muller碼碼R(m,m)則包括了長(zhǎng)度為則包括了長(zhǎng)度為2m的所有二進(jìn)制向量。的所有二進(jìn)制向量。10Reed-Muller碼的構(gòu)造方法可以描述如下：碼的構(gòu)造方法可以描述如下：首先，產(chǎn)生如下的長(zhǎng)為首先，產(chǎn)生如下的長(zhǎng)為2m的二元向量的二元向量 0=000； 1=111； x1=111000; x2=111000111000; xm=10101010向量向量1

7、和和0分別是長(zhǎng)為分別是長(zhǎng)為2m的全的全1和全和全0的向量，向量的向量，向量x1則有則有2(m-1)個(gè)個(gè)1， 2(m-1)個(gè)個(gè)0，x2為為2(m-2)個(gè)個(gè)1，之后，之后2(m-2)個(gè)個(gè)0，再重復(fù)，再重復(fù)2(m-2)個(gè)個(gè)1和和2(m-2)個(gè)個(gè)0。由此遞推得，。由此遞推得，xi由由2(m-i)個(gè)個(gè)1之后之后2(m-i)個(gè)個(gè)0構(gòu)成并重復(fù)構(gòu)成并重復(fù) 直至達(dá)到長(zhǎng)度直至達(dá)到長(zhǎng)度2m。11為了定義為了定義Reed-Muller碼碼R(r,m)的編碼矩陣，首先令矩陣的第一行為的編碼矩陣，首先令矩陣的第一行為1，即長(zhǎng)度即長(zhǎng)度2m的全的全1向量，如果向量，如果r為為0，則它是矩陣唯一的一行。如果，則它是矩陣唯一的一

8、行。如果r為為1，則在，則在R(0,m)的矩陣中添加的矩陣中添加m行行x1,x2,x3xm。例例1：當(dāng)：當(dāng)m=3，我們得到，我們得到R(1,3)的生成矩陣：的生成矩陣：010101013001100112000011111111111111xxx12將將x1x2=(11000000),x1x3=（10100000),x2x3=（10001000）添加到矩陣）添加到矩陣中后，得到中后，得到R(2,3)的矩陣：的矩陣：000100013200000101310000001121010101013001100112000011111111111111xxxxxxxxx13添加添加x1x2x3=（10

9、000000）到矩陣，得到）到矩陣，得到R(3,3)的矩陣：的矩陣：00000001321000100013200000101310000001121010101013001100112000011111111111111xxxxxxxxxxxx14Reed-Muller碼的編碼直接簡(jiǎn)單，生成矩陣碼的編碼直接簡(jiǎn)單，生成矩陣M為為nk大小。我們發(fā)送的大小。我們發(fā)送的信息長(zhǎng)度為信息長(zhǎng)度為k，設(shè)為，設(shè)為m= 則生成的則生成的 是矩陣是矩陣M中的第中的第i行行, 是編碼后的碼字是編碼后的碼字M的第的第n個(gè)碼元。個(gè)碼元。例例2：如果發(fā)送的信息：如果發(fā)送的信息m=(0110),在在R(1,3)的情況下，得

10、到它的碼字為：的情況下，得到它的碼字為：0 *(11111111) + 1 * (11110000) + 1 * (11001100) + 0 *(10101010) = (00111100)2mod1,nkiiinmRCmmmmk.,321cnRin,15Reed-Muller碼的譯碼比編碼復(fù)雜得多，編碼與譯碼的理論建立在漢明碼的譯碼比編碼復(fù)雜得多，編碼與譯碼的理論建立在漢明距離的基礎(chǔ)上，漢明距離定義為兩個(gè)向量之間取值不同的位數(shù)，在距離的基礎(chǔ)上，漢明距離定義為兩個(gè)向量之間取值不同的位數(shù)，在R(r,m)碼碼中，任意兩個(gè)向量之間的距離都為中，任意兩個(gè)向量之間的距離都為2（m-r）,譯碼的基礎(chǔ)建立

11、在與接收碼譯碼的基礎(chǔ)建立在與接收碼字最接近的碼字是原始發(fā)送碼字這一假設(shè)之上，因此，當(dāng)要糾正字最接近的碼字是原始發(fā)送碼字這一假設(shè)之上，因此，當(dāng)要糾正e個(gè)錯(cuò)誤時(shí)，個(gè)錯(cuò)誤時(shí)，任意兩個(gè)向量之間的漢明距離應(yīng)大于任意兩個(gè)向量之間的漢明距離應(yīng)大于2e。這種譯碼方法并不高效，但是算法的實(shí)現(xiàn)直接而不復(fù)雜。它檢查矩陣這種譯碼方法并不高效，但是算法的實(shí)現(xiàn)直接而不復(fù)雜。它檢查矩陣中每一行，利用邏輯值的大多數(shù)來(lái)決定這一行是否被用來(lái)編碼，這使得我中每一行，利用邏輯值的大多數(shù)來(lái)決定這一行是否被用來(lái)編碼，這使得我們確定出錯(cuò)很少的編碼產(chǎn)生的碼字是什么以及原始信息是什么成為可能。們確定出錯(cuò)很少的編碼產(chǎn)生的碼字是什么以及原始信息是

12、什么成為可能。16這種譯碼算法的具體步驟如下：這種譯碼算法的具體步驟如下：步驟一：選擇步驟一：選擇R(r,m)生成矩陣中的一行階數(shù)為生成矩陣中的一行階數(shù)為r，找到這一行的，找到這一行的2(m-r)個(gè)特征向量，然后對(duì)接收碼字和這些特征向量中的每一個(gè)進(jìn)行點(diǎn)積運(yùn)算。個(gè)特征向量，然后對(duì)接收碼字和這些特征向量中的每一個(gè)進(jìn)行點(diǎn)積運(yùn)算。步驟二：找到這些點(diǎn)積結(jié)果中占大多數(shù)的值，用它作為矩陣中這一行步驟二：找到這些點(diǎn)積結(jié)果中占大多數(shù)的值，用它作為矩陣中這一行的系數(shù)。的系數(shù)。步驟三：從生成矩陣的最底行開(kāi)始，對(duì)每一行進(jìn)行步驟一和步驟二，步驟三：從生成矩陣的最底行開(kāi)始，對(duì)每一行進(jìn)行步驟一和步驟二，除了最高一行，之后給

13、每一行乘以得出的系數(shù)構(gòu)成一個(gè)新的矩陣除了最高一行，之后給每一行乘以得出的系數(shù)構(gòu)成一個(gè)新的矩陣My。將。將My與接收到的碼字相加，如果結(jié)果向量中與接收到的碼字相加，如果結(jié)果向量中1多于多于0則生成矩陣最高一行的系則生成矩陣最高一行的系數(shù)為數(shù)為1，反之則為，反之則為0。給最高一行乘以它的系數(shù)，然后添加到。給最高一行乘以它的系數(shù)，然后添加到My矩陣中，便矩陣中，便得到了原始的碼字，于是我們可以判斷錯(cuò)誤，而由生成矩陣的最高行開(kāi)始得到了原始的碼字，于是我們可以判斷錯(cuò)誤，而由生成矩陣的最高行開(kāi)始到最底行的系數(shù)構(gòu)成的向量即為原始信息。到最底行的系數(shù)構(gòu)成的向量即為原始信息。17為了得到生成矩陣中任一行的特征向

14、量，用為了得到生成矩陣中任一行的特征向量，用r表示該行向量，用表示該行向量，用E表示表示生成矩陣中不屬于生成矩陣中不屬于r的所有向量的所有向量xi的集合，特征向量就是與的集合，特征向量就是與E中向量中向量 , 有關(guān)的有關(guān)的向量。向量。例如，在例如，在R(2,4)的生成矩陣中，最后一行與的生成矩陣中，最后一行與x3x4有關(guān)，所以特征向量與有關(guān)，所以特征向量與 x1，x2 ，x1 ，x2 的結(jié)合有關(guān)，即：的結(jié)合有關(guān)，即： x1x2，x1x2 ，x2x1 ，x1x2 ，特征向量，特征向量與生成矩陣中除了與之有關(guān)的向量之外的任一行，都有點(diǎn)積為與生成矩陣中除了與之有關(guān)的向量之外的任一行，都有點(diǎn)積為0。1

15、81920循環(huán)碼是一種特殊的循環(huán)碼是一種特殊的線性分組碼線性分組碼，屬于線性分組碼的一個(gè)重要子類(lèi)，屬于線性分組碼的一個(gè)重要子類(lèi)，也是目前研究最為透徹的一類(lèi)碼，大多數(shù)有實(shí)用價(jià)值的糾錯(cuò)碼都是循環(huán)碼。也是目前研究最為透徹的一類(lèi)碼，大多數(shù)有實(shí)用價(jià)值的糾錯(cuò)碼都是循環(huán)碼。循環(huán)碼與一般的線性分組碼相比具有以下優(yōu)點(diǎn)：循環(huán)碼的編碼及譯碼易于循環(huán)碼與一般的線性分組碼相比具有以下優(yōu)點(diǎn)：循環(huán)碼的編碼及譯碼易于用簡(jiǎn)單的具有反饋連接的移位寄存器來(lái)實(shí)現(xiàn)。用簡(jiǎn)單的具有反饋連接的移位寄存器來(lái)實(shí)現(xiàn)。212.1.1 2.1.1 線性生成碼原理簡(jiǎn)介線性生成碼原理簡(jiǎn)介線性分組碼的構(gòu)成方式是把信息序列分成每線性分組碼的構(gòu)成方式是把信息序

16、列分成每k 個(gè)碼元一段，并由這個(gè)碼元一段，并由這k 個(gè)碼元按一定規(guī)則產(chǎn)生個(gè)碼元按一定規(guī)則產(chǎn)生r 個(gè)校驗(yàn)位，組成長(zhǎng)度為個(gè)校驗(yàn)位，組成長(zhǎng)度為n = k + r 的碼字，用的碼字，用(n, k) 表示信息碼元與校驗(yàn)位之間為線性關(guān)系。一個(gè)表示信息碼元與校驗(yàn)位之間為線性關(guān)系。一個(gè)n,k線性分組碼，線性分組碼，是把從信源輸出的以是把從信源輸出的以k個(gè)碼元為一組的信息組個(gè)碼元為一組的信息組m，通過(guò)信道編碼器后，通過(guò)信道編碼器后，變成長(zhǎng)度為變成長(zhǎng)度為nk的碼組（碼字）的碼組（碼字）c作為作為n,k線性分組碼的一個(gè)碼字線性分組碼的一個(gè)碼字。22設(shè)設(shè)GF(q)是一個(gè)含有是一個(gè)含有q個(gè)元素的有限數(shù)域，若每位碼元的取

17、值有個(gè)元素的有限數(shù)域，若每位碼元的取值有q種（取自種（取自GF(q)），則信息組），則信息組m共有共有 種不同的狀態(tài)，因此，需要種不同的狀態(tài)，因此，需要 個(gè)碼個(gè)碼字字c。而長(zhǎng)為。而長(zhǎng)為n的數(shù)組共有的數(shù)組共有 個(gè)，二進(jìn)制時(shí)個(gè)，二進(jìn)制時(shí)(q=2)共有共有 個(gè)。顯然，個(gè)。顯然， 個(gè)個(gè)n維維向量組成有限域向量組成有限域GF(q)上的一個(gè)上的一個(gè)n維線性空間維線性空間V，編碼就是要在這個(gè)，編碼就是要在這個(gè)n維維線性空間中選出線性空間中選出 個(gè)向量作為合法碼字，其余的個(gè)向量作為合法碼字，其余的 - 個(gè)向量為禁用碼字。個(gè)向量為禁用碼字。如果選出的如果選出的 個(gè)作為合法碼字的向量的集合構(gòu)成了個(gè)作為合法碼字的向

18、量的集合構(gòu)成了V的一個(gè)的一個(gè)k維線性維線性子空間，則稱(chēng)它是一個(gè)子空間，則稱(chēng)它是一個(gè)q進(jìn)制進(jìn)制n,k線性分組碼。線性分組碼。如果值取自如果值取自GF(q)上的上的n,k分組碼的分組碼的 個(gè)碼字的集合個(gè)碼字的集合C，便構(gòu)成了有，便構(gòu)成了有限域限域GF(q)上的上的n維線性空間維線性空間V的一個(gè)的一個(gè)k維線性子空間，則稱(chēng)維線性子空間，則稱(chēng)C是一個(gè)是一個(gè)q進(jìn)制進(jìn)制n,k線性分組碼。線性分組碼。23設(shè)有設(shè)有(n,k)線性分組碼線性分組碼C，如果它的任意一個(gè)碼字的每一次循環(huán)移位仍，如果它的任意一個(gè)碼字的每一次循環(huán)移位仍然是然是C中的一個(gè)碼字，則稱(chēng)中的一個(gè)碼字，則稱(chēng)C為循環(huán)碼。也即，如果為循環(huán)碼。也即，如果

19、C=(cncn-1c2c1)是循是循環(huán)碼環(huán)碼C的一個(gè)碼字，那么的一個(gè)碼字，那么C=(cn-1cn-2c1cn) 等也都是等也都是C的碼字時(shí)，則所有的碼字時(shí)，則所有這些具有循環(huán)特性的碼字的全體便構(gòu)成了循環(huán)碼這些具有循環(huán)特性的碼字的全體便構(gòu)成了循環(huán)碼C。24循環(huán)碼具有線性碼的一般性質(zhì)循環(huán)碼具有線性碼的一般性質(zhì)(即封閉性指一種線性分組碼的任即封閉性指一種線性分組碼的任意兩個(gè)碼組之和仍是該分組碼的另一個(gè)碼組意兩個(gè)碼組之和仍是該分組碼的另一個(gè)碼組)外，還具有循環(huán)性，即循外，還具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位環(huán)碼中任一碼組循環(huán)一位(將最右端碼元移至左端，或反之將最右端碼元移至左端，或反之)以后，仍以

20、后，仍為該碼組中的一個(gè)碼組。為該碼組中的一個(gè)碼組。(n，k)循環(huán)碼表示其中信息位為循環(huán)碼表示其中信息位為k，監(jiān)督位為，監(jiān)督位為n-k位。位。循環(huán)碼的主要特點(diǎn)是：循環(huán)碼的主要特點(diǎn)是：理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)；理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)；實(shí)現(xiàn)簡(jiǎn)單：可利用循環(huán)移位特性在工程上進(jìn)行編、譯碼；實(shí)現(xiàn)簡(jiǎn)單：可利用循環(huán)移位特性在工程上進(jìn)行編、譯碼； 循環(huán)碼的描述方式有很多，但在工程上最有用的是采用多項(xiàng)式的描循環(huán)碼的描述方式有很多，但在工程上最有用的是采用多項(xiàng)式的描述方法。述方法。25設(shè)有循環(huán)碼字設(shè)有循環(huán)碼字C=(cncn-1c2c1) ，則可以用一個(gè)次數(shù)不超過(guò)，則可以用一

21、個(gè)次數(shù)不超過(guò)n-1的多項(xiàng)式的多項(xiàng)式惟一確定，其相應(yīng)的多項(xiàng)式可表示為：惟一確定，其相應(yīng)的多項(xiàng)式可表示為： 由循環(huán)碼的特性可知，若由循環(huán)碼的特性可知，若C =(cncn-1c2c1)是循環(huán)碼是循環(huán)碼C的一個(gè)碼字，則的一個(gè)碼字，則C(1) =(cn-1c1cn) 也是該循環(huán)碼的一個(gè)碼字，它的碼多項(xiàng)式為：也是該循環(huán)碼的一個(gè)碼字，它的碼多項(xiàng)式為： 比較式兩式，得：比較式兩式，得： 121( )nnC xc xc xc (1)111( )nnnCxcxc xc261(1)11( )( )111nnnnnnnncxc xcxC xCxccxxx (1)( )( )mod(1)nCxxC xx ( )( )(

22、 )mod(1)iinCxx C xx 該式說(shuō)明，碼字循環(huán)一次的碼多項(xiàng)式該式說(shuō)明，碼字循環(huán)一次的碼多項(xiàng)式C(1)(x)是原碼多項(xiàng)式是原碼多項(xiàng)式 乘乘x后再除后再除以以xn+1所得的余式，即：所得的余式，即： 由此可以推知，由此可以推知，C(x)的的i 次循環(huán)移位次循環(huán)移位C(i)(x) 是原碼多項(xiàng)式是原碼多項(xiàng)式C(x) 乘乘xi 后再后再除以除以xn+1所得的余式，即：所得的余式，即： 27例例4： (7,3)循環(huán)碼的循環(huán)移位循環(huán)碼的循環(huán)移位循環(huán)次數(shù)碼字碼多項(xiàng)式000000000011101 x4+x3+x2+110111010 x(x4+x3+x2+1)mod(x7+1) =x5+x4+x3

23、+x21110100 x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231101001 x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141010011 x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150100111 x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161001110 x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x28 循環(huán)碼可由它的一個(gè)循環(huán)碼可由它的一個(gè)n-k次首一多項(xiàng)式次首一多項(xiàng)式g(x) 來(lái)確定，因此稱(chēng)它為碼來(lái)確定，因此稱(chēng)它為碼的生成多項(xiàng)式，即：的生成多項(xiàng)式，即： 碼的生成

24、多項(xiàng)式具有如下性質(zhì)：碼的生成多項(xiàng)式具有如下性質(zhì)： 在在(n,k)循環(huán)碼中，循環(huán)碼中， n-k 次碼多項(xiàng)式是最低次的碼多項(xiàng)式。次碼多項(xiàng)式是最低次的碼多項(xiàng)式。 在在(n,k)循環(huán)碼中，循環(huán)碼中， g(x) 是惟一是惟一n-k次多項(xiàng)式，次多項(xiàng)式， 。 在在(n,k)循環(huán)碼中，每個(gè)碼多項(xiàng)式循環(huán)碼中，每個(gè)碼多項(xiàng)式C(x) 都是都是g(x)的倍式。的倍式。 任意任意(n,k)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g(x) 一定整除一定整除xn+1 。 10( )n kn kg xgxg xg 00g29在循環(huán)碼的碼多項(xiàng)式中，每一個(gè)能整除在循環(huán)碼的碼多項(xiàng)式中，每一個(gè)能整除xn+1的的(n-k)次首一多項(xiàng)式次首

25、一多項(xiàng)式都是該都是該碼的生成多項(xiàng)式碼的生成多項(xiàng)式，記為，記為g(x) 。將。將g(x)經(jīng)過(guò)經(jīng)過(guò)k-1次循環(huán)移位，共得次循環(huán)移位，共得到到k個(gè)碼多項(xiàng)式：個(gè)碼多項(xiàng)式： g(x) 、 xg(x) 、 xk-1g(x) 。這。這k 碼多項(xiàng)式顯然是碼多項(xiàng)式顯然是相互獨(dú)立的，于是得到循環(huán)碼的相互獨(dú)立的，于是得到循環(huán)碼的生成矩陣生成矩陣G(x)： 12( )( )( )( )( )kkxg xxg xG xxg xg x 30 例例 5 ： 求二進(jìn)制求二進(jìn)制 (7,3) 循環(huán)碼的生成多項(xiàng)式。循環(huán)碼的生成多項(xiàng)式。 解：分解多項(xiàng)式解：分解多項(xiàng)式x7+1，取其四次首一多項(xiàng)式作為生成多項(xiàng)式：，取其四次首一多項(xiàng)式作為

26、生成多項(xiàng)式： x7+1=(x+1)(x3+x+1)(x3+x2+1) 可將一次和任一個(gè)三次多項(xiàng)式的乘積作為生成多項(xiàng)式：可將一次和任一個(gè)三次多項(xiàng)式的乘積作為生成多項(xiàng)式：g(x)=(x+1)(x3+x2+1)=x4+x2+x+1或或 g(x)= =(x+1)(x3+x+1)=x4+x3+x2+131系統(tǒng)循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼的生成矩陣系統(tǒng)的一致校驗(yàn)矩陣是系統(tǒng)的一致校驗(yàn)矩陣是例例6： 以以g(x)=(x3+x+1)為生成多項(xiàng)式生成一個(gè)為生成多項(xiàng)式生成一個(gè)(7,4)循環(huán)碼，要求生成的循循環(huán)碼，要求生成的循 環(huán)碼是系統(tǒng)碼。環(huán)碼是系統(tǒng)碼。 解：由定義得對(duì)應(yīng)給定解：由定義得對(duì)應(yīng)給定g(x)的循環(huán)碼的一般

27、生成矩的循環(huán)碼的一般生成矩陣為：陣為：kGIP Tn kHPI 1011000 (1)0101100 (2)0010110 (3)0001011 (4)G 32 對(duì)矩陣對(duì)矩陣G的行進(jìn)行運(yùn)算，將第、行相加后作為第的行進(jìn)行運(yùn)算，將第、行相加后作為第1行，第、行，第、行相加后作為第行相加后作為第2行，得：行，得： 對(duì)應(yīng)：對(duì)應(yīng)： 這樣，就得到系統(tǒng)循環(huán)碼的生成矩陣和一致校驗(yàn)矩陣。這樣，就得到系統(tǒng)循環(huán)碼的生成矩陣和一致校驗(yàn)矩陣。 01000101 (1)(3)(4)0100111(2)(4)00101100001011G 0111010001110101101001H 在數(shù)據(jù)通信中，信息都是先劃分成小塊再

28、組裝成幀后在數(shù)據(jù)通信中，信息都是先劃分成小塊再組裝成幀后(或叫分組、包等，或叫分組、包等，僅名稱(chēng)不同而已僅名稱(chēng)不同而已)在線路上統(tǒng)計(jì)復(fù)用傳送或存入共同物理介質(zhì)的，幀尾一般在線路上統(tǒng)計(jì)復(fù)用傳送或存入共同物理介質(zhì)的，幀尾一般都留有都留有8、12、16或或32位用作差錯(cuò)校驗(yàn)。如把一幀視為一個(gè)碼字，則其校位用作差錯(cuò)校驗(yàn)。如把一幀視為一個(gè)碼字，則其校驗(yàn)位長(zhǎng)度驗(yàn)位長(zhǎng)度 不變而信息位不變而信息位 和碼長(zhǎng)和碼長(zhǎng) 是可變的，其結(jié)構(gòu)符合是可變的，其結(jié)構(gòu)符合 縮短循環(huán)碼的特點(diǎn)。只要以一個(gè)選定的縮短循環(huán)碼的特點(diǎn)。只要以一個(gè)選定的 循環(huán)碼為基礎(chǔ)，改變循環(huán)碼為基礎(chǔ)，改變 的值，就能得到任何信息長(zhǎng)度的幀結(jié)構(gòu)，而糾錯(cuò)能力保持

29、不變。這種應(yīng)用的值，就能得到任何信息長(zhǎng)度的幀結(jié)構(gòu)，而糾錯(cuò)能力保持不變。這種應(yīng)用下的縮短循環(huán)碼稱(chēng)為下的縮短循環(huán)碼稱(chēng)為循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼(Cyclic Redundancy Check，CRC)。 nkkn(,)n i ki( , )n ki2.7.1 2.7.1 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼是系統(tǒng)的縮短循環(huán)碼，碼的結(jié)構(gòu)如圖所示。循環(huán)冗余校驗(yàn)碼是系統(tǒng)的縮短循環(huán)碼，碼的結(jié)構(gòu)如圖所示。 圖圖 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼(CRC)結(jié)構(gòu)結(jié)構(gòu) 圖中，碼字用碼多項(xiàng)式圖中，碼字用碼多項(xiàng)式 表示，表示， 是是 除以除以 后的余式，后的余式， 為為 次多項(xiàng)式，它們之間滿足：次多項(xiàng)式，它們

30、之間滿足： 。雖然循環(huán)冗余。雖然循環(huán)冗余校驗(yàn)碼指的是整個(gè)碼字校驗(yàn)碼指的是整個(gè)碼字 ，但人們習(xí)慣上僅把校驗(yàn)部分稱(chēng)為，但人們習(xí)慣上僅把校驗(yàn)部分稱(chēng)為CRC碼。碼。 如果傳輸過(guò)程無(wú)差錯(cuò)，則接收碼字如果傳輸過(guò)程無(wú)差錯(cuò)，則接收碼字 應(yīng)等于發(fā)送碼字應(yīng)等于發(fā)送碼字 這時(shí)這時(shí) 能被能被 整除；如果不能被整除，則說(shuō)明在傳輸過(guò)程中出整除；如果不能被整除，則說(shuō)明在傳輸過(guò)程中出現(xiàn)了誤碼?，F(xiàn)了誤碼。 ( )C x( )r x( )n kxm x( )g xnk( )( )( )n kC xxm xr x( )C x( )C x( )g x( )C x例例7：某：某CRC的生成多項(xiàng)式為的生成多項(xiàng)式為 。如果想發(fā)送一串信息。

31、如果想發(fā)送一串信息“110001”的前的前6位，并加上位，并加上CRC校驗(yàn)，發(fā)送碼字校驗(yàn)，發(fā)送碼字 應(yīng)如何安排，應(yīng)如何安排，接收碼字接收碼字 又如何校驗(yàn)？又如何校驗(yàn)？解：本題信息碼字多項(xiàng)式解：本題信息碼字多項(xiàng)式 ， ，從生成多項(xiàng)式，從生成多項(xiàng)式 的的階數(shù)得校驗(yàn)位數(shù)等于階數(shù)得校驗(yàn)位數(shù)等于4，因此，因此 。 將將 除以除以 得余式得余式 ： 于是，發(fā)送碼字多項(xiàng)式于是，發(fā)送碼字多項(xiàng)式 對(duì)應(yīng)對(duì)應(yīng)的發(fā)送碼字為的發(fā)送碼字為(1100011100)。 4( )1g xxx( )C x( )r x54( )1m xxx6k( )g x10n( )nkxm x( )g x( )r x45432( )( )mod

32、 ( ) (1)mod ( ) n kr xxm xg xxxxg xxx( )( )( )n kC xxm xr x98432xxxxx在接收端，在接收端，CRC校驗(yàn)實(shí)際上就是做除法運(yùn)算：如果傳輸過(guò)程無(wú)差錯(cuò)，則校驗(yàn)實(shí)際上就是做除法運(yùn)算：如果傳輸過(guò)程無(wú)差錯(cuò)，則 能被能被 整除，余式為整除，余式為“0”；如果余式不為；如果余式不為“0”，則說(shuō)明一定有差錯(cuò)。，則說(shuō)明一定有差錯(cuò)。 例例8 假設(shè)假設(shè) ，即信息碼字為，即信息碼字為(1011001)， ，求，求CRC校驗(yàn)碼。由題得：校驗(yàn)碼。由題得： 用用 去除去除 ，有，有： ( )g x643( )1m xxxx43( )1g xxx410874( )

33、 x m xxxxx( )g x4( )x mx( )C x經(jīng)相除后得到的最后余數(shù)經(jīng)相除后得到的最后余數(shù)1010就是冗余校驗(yàn)碼就是冗余校驗(yàn)碼 。所以，發(fā)送碼字。所以，發(fā)送碼字(10110011010)。 需要注意的是，這里所涉及的運(yùn)算與前面一樣都是模需要注意的是，這里所涉及的運(yùn)算與前面一樣都是模2運(yùn)算。運(yùn)算。如果例子中的發(fā)送碼字如果例子中的發(fā)送碼字(10110011010)經(jīng)傳輸后受噪聲的干擾，在接收端變經(jīng)傳輸后受噪聲的干擾，在接收端變成為成為(10110011100)。求余式的除法如下：。求余式的除法如下： ( )r x求得余式不為零，相當(dāng)于在發(fā)送碼字上加了差錯(cuò)圖樣求得余式不為零，相當(dāng)于在發(fā)

34、送碼字上加了差錯(cuò)圖樣“00000000110”。差錯(cuò)圖樣相應(yīng)的多項(xiàng)式為差錯(cuò)圖樣相應(yīng)的多項(xiàng)式為 。有差錯(cuò)時(shí)，接收端收到的不再。有差錯(cuò)時(shí)，接收端收到的不再是是 ，而是，而是 + 。由于：。由于： 若若 ，則這種差錯(cuò)就能檢測(cè)出來(lái)，若，則這種差錯(cuò)就能檢測(cè)出來(lái)，若 ，那么由于接收到，那么由于接收到的碼字多項(xiàng)式仍然可被的碼字多項(xiàng)式仍然可被 整除，錯(cuò)誤就檢測(cè)不出來(lái)，也即發(fā)生了漏檢。整除，錯(cuò)誤就檢測(cè)不出來(lái)，也即發(fā)生了漏檢。理論上可以證明，循環(huán)冗余校驗(yàn)碼的檢錯(cuò)能力如下：理論上可以證明，循環(huán)冗余校驗(yàn)碼的檢錯(cuò)能力如下： 可檢測(cè)出所有奇數(shù)個(gè)錯(cuò)；可檢測(cè)出所有奇數(shù)個(gè)錯(cuò)； 可檢測(cè)出所有單比特和雙比特的錯(cuò)；可檢測(cè)出所有單比特

35、和雙比特的錯(cuò)； 2( ) e xxx( )C x( )Cx( )e x ( )+ ( ) ( ) ( )=+ ( ) ( ) ( )C xe xC xe xg xg xg x( )( )e x0g x ( )( )e x0g x ( )g x 可檢測(cè)出所有小于、等于校驗(yàn)碼長(zhǎng)度可檢測(cè)出所有小于、等于校驗(yàn)碼長(zhǎng)度 的突發(fā)錯(cuò)誤；的突發(fā)錯(cuò)誤； 對(duì)于對(duì)于 位的突發(fā)性錯(cuò)誤，查出概率為位的突發(fā)性錯(cuò)誤，查出概率為 ； 對(duì)于多于對(duì)于多于 位的突發(fā)性錯(cuò)誤，查出概率為位的突發(fā)性錯(cuò)誤，查出概率為 。由此可以看出，只要選擇足夠的冗余校驗(yàn)位，可以使得漏檢率減到任意由此可以看出，只要選擇足夠的冗余校驗(yàn)位，可以使得漏檢率減到任

36、意小的程度。小的程度。循環(huán)冗余編碼法在數(shù)據(jù)傳輸中得到了最廣泛的應(yīng)用。循環(huán)冗余編碼法在數(shù)據(jù)傳輸中得到了最廣泛的應(yīng)用。CRC本身具有糾錯(cuò)本身具有糾錯(cuò)功能，但網(wǎng)絡(luò)中一般不用其糾錯(cuò)功能，僅用其強(qiáng)大的檢錯(cuò)功能，檢出錯(cuò)誤功能，但網(wǎng)絡(luò)中一般不用其糾錯(cuò)功能，僅用其強(qiáng)大的檢錯(cuò)功能，檢出錯(cuò)誤后要求重發(fā)。后要求重發(fā)。 nk1nk(1)1 2r1nk1 2rCRC-12，其生成多項(xiàng)式：，其生成多項(xiàng)式：CRC-16，其生成多項(xiàng)式：，其生成多項(xiàng)式：CRC-CCITT，其生成多項(xiàng)式：，其生成多項(xiàng)式：CRC-32，其生成多項(xiàng)式：，其生成多項(xiàng)式： 循環(huán)冗余校驗(yàn)碼的編譯碼過(guò)程通常用采用硬件來(lái)實(shí)現(xiàn)，因?yàn)槌ㄟ\(yùn)算易循環(huán)冗余校驗(yàn)碼的編

37、譯碼過(guò)程通常用采用硬件來(lái)實(shí)現(xiàn)，因?yàn)槌ㄟ\(yùn)算易于用移位寄存器和模于用移位寄存器和模2加法器來(lái)實(shí)現(xiàn)，可以達(dá)到比較高的處理速度。隨著集加法器來(lái)實(shí)現(xiàn)，可以達(dá)到比較高的處理速度。隨著集成電路工藝的發(fā)展，循環(huán)冗余碼的產(chǎn)生和校驗(yàn)均有集成電路產(chǎn)品，發(fā)送端成電路工藝的發(fā)展，循環(huán)冗余碼的產(chǎn)生和校驗(yàn)均有集成電路產(chǎn)品，發(fā)送端能夠自動(dòng)生成能夠自動(dòng)生成CRC碼，接收端可自動(dòng)校驗(yàn)，速度大大提高。碼，接收端可自動(dòng)校驗(yàn)，速度大大提高。 121132( )1g xxxxxx16152( )1g xxxx16155( )1g xxxx322623221612111087542( )1g xxxxxxxxxxxxxxx目前廣泛使用的

38、目前廣泛使用的CRC碼已成國(guó)際標(biāo)準(zhǔn)，生成多項(xiàng)式主要有下述四種：碼已成國(guó)際標(biāo)準(zhǔn)，生成多項(xiàng)式主要有下述四種： BCH碼是一類(lèi)最重要的循環(huán)碼，能糾正多個(gè)隨機(jī)錯(cuò)誤。這種碼可以是碼是一類(lèi)最重要的循環(huán)碼，能糾正多個(gè)隨機(jī)錯(cuò)誤。這種碼可以是二進(jìn)制碼，也可以是非二進(jìn)制碼。二進(jìn)制碼，也可以是非二進(jìn)制碼。BCH碼具有糾錯(cuò)能力強(qiáng)，構(gòu)造方便，編、譯碼易于實(shí)現(xiàn)等一系列優(yōu)點(diǎn)。碼具有糾錯(cuò)能力強(qiáng)，構(gòu)造方便，編、譯碼易于實(shí)現(xiàn)等一系列優(yōu)點(diǎn)。二進(jìn)制本原二進(jìn)制本原BCH碼具有下列參數(shù)：碼具有下列參數(shù)： (碼長(zhǎng)碼長(zhǎng)) （監(jiān)督元位數(shù)）（監(jiān)督元位數(shù)） （最小碼距）（最小碼距） 式中式中 和糾錯(cuò)能力和糾錯(cuò)能力 是任意的正整數(shù)。是任意的正整數(shù)。

39、 BCH碼的碼長(zhǎng)為碼的碼長(zhǎng)為 或或 的因子，通常稱(chēng)前者為的因子，通常稱(chēng)前者為本原本原BCH碼碼，稱(chēng)后者為非本原，稱(chēng)后者為非本原BCH碼碼。 min2121mnnkmtdt(3)m1(2)mt21mn21mn2.7.2 BCH2.7.2 BCH碼碼 BCH碼的基本特點(diǎn)是其生成多項(xiàng)式碼的基本特點(diǎn)是其生成多項(xiàng)式 包含包含 個(gè)連續(xù)冪次的根，個(gè)連續(xù)冪次的根，由該由該 生成的循環(huán)碼，其糾錯(cuò)能力不小于生成的循環(huán)碼，其糾錯(cuò)能力不小于 。由于碼的生成多項(xiàng)式與。由于碼的生成多項(xiàng)式與碼的最小距離有關(guān)，容易根據(jù)糾錯(cuò)能力要求來(lái)直接確定碼的構(gòu)造，因此，碼的最小距離有關(guān)，容易根據(jù)糾錯(cuò)能力要求來(lái)直接確定碼的構(gòu)造，因此，它是一

40、類(lèi)應(yīng)用廣泛的差錯(cuò)控制碼。它是一類(lèi)應(yīng)用廣泛的差錯(cuò)控制碼。 這里我們重點(diǎn)討論這里我們重點(diǎn)討論BCH碼的實(shí)際應(yīng)用，即利用已知的碼的實(shí)際應(yīng)用，即利用已知的BCH碼表格，碼表格，構(gòu)造出對(duì)應(yīng)生成多項(xiàng)式的構(gòu)造出對(duì)應(yīng)生成多項(xiàng)式的BCH碼。碼。( )g x2t( )g xt（1 1）最小多項(xiàng)式）最小多項(xiàng)式43令令是是GF(2GF(2m m) )中的一個(gè)元素，某個(gè)形成循環(huán)周期并對(duì)中的一個(gè)元素，某個(gè)形成循環(huán)周期并對(duì)的所有根均滿的所有根均滿足足m(m()=0)=0的最低多項(xiàng)式的最低多項(xiàng)式m(x),m(x),稱(chēng)為稱(chēng)為的最小多項(xiàng)式。這個(gè)最小多項(xiàng)式是既的最小多項(xiàng)式。這個(gè)最小多項(xiàng)式是既約的。而且，當(dāng)約的。而且，當(dāng)為為m(x)

41、m(x)的根時(shí)，的根時(shí)， 2 2, , 4 4，8 8，也比是也比是m(x)m(x)的根的根以以GF(2GF(24 4) )為例，當(dāng)有根為例，當(dāng)有根a a時(shí)時(shí), ,則則a,aa,a2 2,a,a2222=a=a4 4, a, a2323=a=a8 8, ,均為根均為根(a(a2424=a=a16 16 =a=a不是新根不是新根) )。因此，包括全部根的最小多項(xiàng)式為：。因此，包括全部根的最小多項(xiàng)式為：m mi i(x)=(x)=(x+ax+a)(x+a)(x+a2 2) (x+a) (x+a4 4) (x+a) (x+a8 8) ) =x =x4 4+ x+ x3 3 (a+a(a+a2 2 +

42、a+a4 4 +a+a8 8)+ x)+ x2 2(a(a3 3 +a+a5 5+a+a9 9 +a+a6 6+a+a10 10 +a+a1212) ) +x(a+x(a14 14 +a+a1313+a+a11 11 +a+a7 7) +a) +a151544利用利用GF(2GF(24 4) )域中域中a a4 4+a+a +1=0+1=0所生成的所生成的元素表元素表，可以將上式簡(jiǎn)化為，可以將上式簡(jiǎn)化為: : m mi i(x)= x(x)= x4 4+x+x +1+1當(dāng)當(dāng)a a3 3 時(shí)，則時(shí)，則2 2 a a6 6 ， 2222 a a1212， 2323 a a24 24 a a9 9

43、，均為根，均為根( (2424 a a48 48 a a3 3 不是新根不是新根) )。因此，類(lèi)似地得到。因此，類(lèi)似地得到m m3 3(x)=(x+a(x)=(x+a3 3) (x+a) (x+a5 5) (x+a) (x+a9 9) (x+a) (x+a1212)=x)=x4 4+ x+ x3 3 + x+ x2 2 +x+1 +x+1同理同理a a5 5 時(shí)，則時(shí)，則2 2 a a10 10 也為根也為根( (4 4 a a2020 a a5 5 不是新根不是新根) )。因此。因此m m5 5(x)=(x+a(x)=(x+a5 5) (x+a) (x+a1010) = x) = x2 2 +x+1 +x+1由于由于x x1616 +1 +1(x+1)(x(x+1)(x2 2 +x+1)(x +x+1)(x4 4+x+1)(x+x+1)(x4 4+ x+ x3 3