通信原理II第7次課課件

1、10.5 BCH碼BCH碼是1959年由霍昆格姆（Hocquenghem）、1960年由博斯（Bose）和查得胡里（Chandhari）分別獨立提出的，這三人姓氏的開頭字母B、C、H就是BCH碼名稱的來歷。BCH碼是一類重要的循環(huán)碼，具有糾正多個錯誤的能力。既然BCH碼是循環(huán)碼的子類，那么它一定符合循環(huán)碼的構(gòu)碼規(guī)律。例10.5.1 分析碼長的二進制循環(huán)碼的生成多項式結(jié)構(gòu)。解：本例題利用循環(huán)碼生成多項式的特性來構(gòu)造循環(huán)碼。將因式分解，得 顯然，含有1次到14次多項式因子，且其常數(shù)項皆不為0，即都滿足生成多項式的3個條件，由它們可以構(gòu)成碼長為15的（15,14），（15,13），（15,1）循環(huán)碼

2、。例如，利用下列生成多項式能構(gòu)造出（15,5）循環(huán)碼?？梢钥吹?，（15,5）循環(huán)碼的生成多項式是幾個既約因式合并成的一個次非既約因式。在這些生成多項式中，有的可以生成BCH碼，有的只能產(chǎn)生一般循環(huán)碼。本節(jié)將運用多項式域的相關(guān)知識，簡要介紹循環(huán)碼的另一種構(gòu)碼方法，分析利用多項式在二元擴域上的根來構(gòu)造循環(huán)碼的原理，加深對BCH碼生成多項式的理解。10.5.1 多項式域 研究BCH碼需要一定的近世代數(shù)知識，這里，僅簡要介紹編碼理論中最基本、最重要的二元擴域有關(guān)概念。1. 預(yù)備知識在討論多項式域之前，先介紹幾個術(shù)語。(1) 二元伽邏華域二元集合，在模2加、模2乘運算下構(gòu)成一個域，稱為二元伽邏華（Gal

3、ois）域，記做。其中，加法“”和乘法“”的運算規(guī)則如下：從定義上看，域是一個集合兩種運算，同時要求這兩種運算滿足結(jié)合律、交換律、分配律等運算規(guī)則和封閉性條件。(2) 既約多項式對于系數(shù)屬于上的多項式，若除了常數(shù)C以及外，不能被該數(shù)域上的任何其他多項式整除，則稱為該數(shù)域上的既約多項式。(3) 本原多項式若次多項式滿足如下條件，則稱為本原多項式。 為既約的，即不可分解； 可整除,； 除不盡,。2. 多項式域的存在性(1) 若是次既約多項式，則次數(shù)小于的多項式的全體，在模2加、模乘運算下構(gòu)成一個多項式域，寫做。 多項式域的集合是次數(shù)小于的多項式的全體。域上的域元素是系數(shù)屬于上的多項式， 稱是域的擴

4、域，稱為擴域的基域。 多項式“+”和多項式乘“”運算規(guī)則為 對于域元素和，多項式“+”定義為： （10.5.1） 多項式乘“”定義為： （10.5.2）由式（10.5.2）不難看出，域元素是次數(shù)小于的多項式，是由既約多項式產(chǎn)生的。 域的階是指域元素的個數(shù)，擴域有個元素，其中，為正整數(shù)。(2) 若是次本原多項式，則以為模的乘運算所生成的多項式域里至少存在一個域元素（稱為本原元），它的各次冪構(gòu)成了域的全部（共個）非零域元素。例10.5.2 次數(shù)小于的多項式在模2加、模乘運算下構(gòu)成多項式域。 多項式域共有16個域元素：0，1， 。 驗證一下運算的封閉性。比如，域元素與域元素模乘，有于是得，它是域上的

5、另一個域元素。 由于又是本原的，故多項式域中的15個非零域元素可表示成。本原元是多項式域中的一個域元素，并且滿足，即是本原多項式的根。 利用關(guān)系式，可將的各次冪化做的低于4次多項式（盡管本身就是多項式）。比如，與冪次對應(yīng)的多項式見表10.5.1。還可以將多項式的系數(shù)抽出后順序排列成一個碼組，這樣一來，一個域元素共有三種表示形式：的各次冪、多項式和比特碼組。表10.5.1 本原多項式的根生成的域元素各次冪的多項式多項式系數(shù)（比特碼組）1(0001)(0010)(0100)(1000)(0011)(0110)(1100)(1011)(0101)(1010)(0111)(1110)(1111)(11

6、01)(1001)3. 多項式的根與最小多項式(1) 域上所有非零元素，都是多項式的根。即以根為一次項完全分解： （10.5.3）(2) 多項式一定可以分解成若干最小多項式之積： （10.5.4）綜合式（10.5.3）、（10.5.4）可得下列關(guān)系式： （10.5.5）例10.5.3 由本原多項式生成的多項式域上全部非零元素為，按式（10.5.3）多項式可完全分解為一次項之積：可以看到，根和所對應(yīng)的最小多項式如下： 根 根 根 根 在例10.5.1中，生成多項式、又可以表示成：10.5.2 BCH碼設(shè)計原理1. BCH碼的生成多項式 若循環(huán)碼的生成多項式具有如下形式： （10.5.6）則由此生

7、成的循環(huán)碼稱為BCH碼。式（10.5.6）中，為糾錯個數(shù)，為最小多項式，LCM（Least Common Multiple）是最小公倍式的縮寫。 是多項式的根所對應(yīng)的最小多項式，若選取的根是連續(xù)奇冪次的根（即），則所得的可以生成一個BCH碼，否則就是一般的循環(huán)碼。例10.5.3中的生成多項式中含有3個連續(xù)奇次冪的根，則由生成的循環(huán)碼是（15,5）BCH碼。而由產(chǎn)生的（15,5）循環(huán)碼是一般循環(huán)碼。 BCH碼的碼長或者是的因子。碼長為的BCH碼稱為本原BCH碼，碼長是因子的BCH碼稱為非本原BCH碼。對于糾正個（隨機）差錯的本原BCH碼，其生成多項式為 （10.5.7）BCH碼的核心是其生成多項

8、式中含有個連續(xù)奇次冪的根，則該碼的最小距離。該結(jié)論稱為BCH碼限定理。這種碼生成多項式與最小碼距的密切關(guān)系，使設(shè)計者可以根據(jù)對的要求，輕易地構(gòu)造出具有預(yù)定糾錯能力的碼。2. BCH碼的糾錯能力當碼長確定后，BCH碼的糾錯能力的選擇并不是任意的，而要受到一定限制。 糾錯能力的下限 （10.5.8）也就是說，BCH碼的監(jiān)督碼元最多為位。 糾錯能力的上限 （10.5.9）3. 本原BCH碼設(shè)計當碼長及糾錯能力給定后，就可以構(gòu)造出符合要求的本原BCH碼?？紤]到求出最小多項式是十分麻煩的事，工程實踐中可通過查表得到相關(guān)數(shù)據(jù)。，連續(xù)奇冪次根所對應(yīng)的最小多項式如表10.5.2所示。例10.5.4 設(shè)計一個碼

9、長及糾錯能力的二進制本原BCH碼。 解：顯然，未超過式（10.5.9）規(guī)定的糾錯能力上限。 ，故。查表10.5.2找到個連續(xù)奇次冪之根所對應(yīng)的最小多項式分別是：，和。于是，該本原BCH碼生成多項式為 ，所以，這就是BCH碼。表10.5.2 多項式域中連續(xù)冪次根所對應(yīng)的最小多項式i 最小多項式i 最小多項式i最小多項式i最小多項式m =2 1(0,1,2) m=3 1(0,1,3) 3(0,2,3) m=4 1(0,1 ,4) 3(0,1,2,3,4) 5(0,1,2) 7(0,3,4)m=5 111(0,2,5)(0,1,3,4,5) 315(0,2,3,4,5)(0,3,5) 5(0,1,2

10、,4,5) 7(0,1,2,3,5)m=6 1 921(0,1,6)(0,2,3)(0,1,2) 31123(0,1,2,4,6)(0,2,3,5,6)(0,1,4,5,6) 51327(0,1,2,5,6)(0,1,3,4,6)(0,1,3) 71531(0,3,6)(0,2,4,5,6)(0,5,6)m=7 1 9192955(0,3,7)(0,1,2,3,4,5,7)(0,1,6,7)(0,1,3,5,7)(0,2,3,4,5,6,7) 311213163(0,1,2,3,7)(0,2,4,6,7)(0,2,5,6,7)(0,4,5,6,7)(0,4,7) 5132343(0,2,3,4

11、,7)(0,1,7)(0,6,7)(0,1,2,5,7) 7152747(0,1,2,4,5,6,7)(0,1,2,3,5,6,7)(0,1,4,6,7)(0,3,4,5,7)m=8 1 9172537475987119(0,2,3,4,8)(0,2,3,4,5,7,8)(0,1,4)(0,1,3,4,8)(0,1,2,3,4,6,8)(0,3,5,7,8)(0,2,3,6,8)(0,1,5,7,8)(0,3,4) 311192739516191127(0,1,2,4,5,6,8)(0,1,2,5,6,7,8)(0,2,5,6,8)(0,1,2,3,4,5,8)(0,3,4,5,6,7,8)(

12、0,1,2,3,4)(0,1,2,3,6,7,8)(0,2,4,5,6,7,8)(0,4,5,6,8) 513212943536395(0,1,4,5,6,7,8)(0,1,3,5,8)(0,1,3,7,8)(0,2,3,7,8)(0,1,6,7,8)(0,1,2,7,8)(0,2,3,4,6,7,8)(0,1,2,3,4,7,8) 7152331455585111(0,3,5,6,8)(0,1,2,4,6,7,8)(0,1,5,6,8)(0,2,3,5,8)(0,3,4,5,8)(0,4,5,7,8)(0,1,2)(0,1,3,4,5,6,8) 說明：（1）上表時的“21（0,1,3,7,8

13、）”表示上域元素所對應(yīng)的最小多項式是，依次類推。（2）由上表所有最小多項式的積及對應(yīng)的最小多項式可得出的因式分解。比如時，先從表中查出對應(yīng)的最小多項式，將它們合起來就是因式分解式：4. BCH碼編碼 BCH碼的編碼過程與一般循環(huán)碼一樣，同樣可以用帶反饋的移位寄存器來實現(xiàn)。10.5.4 RS碼RS碼以它的發(fā)現(xiàn)者里德-索洛蒙（Reed-Solomon）的姓氏開頭字母命名，是一類具有很強糾錯能力的多進制（多元）本原BCH碼。1. RS碼參數(shù)進制本原RS碼具有如下參數(shù)碼長： 監(jiān)督碼元數(shù)： 最小碼距： 2. RS碼生成多項式RS碼的生成多項式含有個連續(xù)冪次的根，一次根式就是最小多項式： （10.5.10

14、）例10.5.5 試構(gòu)造一個能糾3個錯誤，碼長為15的RS碼。解：由RS碼的參數(shù)可知，該碼的監(jiān)督位位數(shù)。因此，該碼為(,)RS碼。RS碼的構(gòu)造方法可分解為如下幾個步驟：(1) 建立進制碼元與擴域上域元素之間的對應(yīng)關(guān)系。由于碼長，可斷定(,)RS碼的碼元是十六進制的。由關(guān)系式算出，利用本原多項式產(chǎn)生一個擴域。這樣一來，每個碼元都可以看成是擴域中的一個域元素，兩者之間的一一對應(yīng)關(guān)系見表10.5.1。(2) 根據(jù)設(shè)計糾錯能力，計算出生成多項式。，說明RS碼的生成多項式有6個連續(xù)冪次根，由式（10.5.10）得： 在上式的運算中用到了關(guān)系式以及二元擴域的一些運算規(guī)則，比如,等。(3) 編出碼組。 設(shè)信

15、息碼為，則RS碼多項式為從而得到上的編碼序列為3. RS碼的糾錯能力 從實際應(yīng)用考慮，一般取為2的冪次。當，可以輕易地將進制（,）RS碼變換成二進制RS衍生（,）碼。當采用RS衍生碼作為信道傳輸碼時，譯碼器不但能糾正個隨機錯誤，還可以糾正突發(fā)錯誤。例10.5.6 若利用二進制信道傳輸一個能糾正3個隨機差錯的(,)RS碼，如題圖所示。試分析其糾錯的能力。信息碼（15, 9）RS碼編碼器（60, 36）編碼器（15, 9）RS碼譯碼器（60, 36）譯碼器二進制編碼信道解：由于碼長， ，則(,)RS碼對應(yīng)的二進制衍生碼是（,）碼。若以二進制（,）碼作為信道傳輸碼，那么它與原(,)RS碼一樣能糾任意3個隨機差錯，同時也能糾正長度小于等于9的任何突發(fā)差錯。這是因為接收端RS譯碼時，先要將二進制衍生碼還原成進制RS碼，每個十六進制碼元對應(yīng)4二進制碼元。信道上長度為9的突發(fā)差錯最多使三個十六進制碼元出錯，所以可以被糾正。而當突法差錯長度為1