信息與編碼理論 第2版 課件 6.1 有限域

第6章BCH和RS碼本章內(nèi)容：6.1有限域6.2BCH碼6.3RS碼6.4BCH和RS碼的仿真實例§6.1有限域6.1.1有限域的定義阿貝爾群（AbelianGroup）對于集合，定義符號“”表示一種二進(jìn)制運算，如果滿足下面的條件則稱該集合為阿貝爾群：該運算具有交換律。即對于任意，有；該運算具有結(jié)合律。即對于任意，有；該運算具有可以用“0”表示的幺元（IdentityElement）。即對于任意，有；對于任意一個元素，均存在元素滿足，其中元素稱為的加法逆。因此，一個阿貝爾群通?？梢杂涀鳌Ｗ⒁猓喊⒇悹柸阂部梢愿挠梅枴?/p>

”表示的“乘法”運算來定義，此時幺元可以用符號“1”來表示，而該群可以記作，此時元素的乘法逆則可以表示為。有限域（伽羅華域，GaloisField）對于有限個元素構(gòu)成的一個集合，定義了分別用“”和“”表示的加法和乘法兩種二進(jìn)制運算，如果滿足下列條件則稱該集合為有限域：是一個阿貝爾群；也是一個阿貝爾群，即集合中的非零元素在乘法運算下也構(gòu)成一個阿貝爾群；乘法滿足分配律：。綜上，一個有限域常常記作。顯然，由所有實數(shù)構(gòu)成的集合在正常的加法和乘法運算下是一個域（但不是有限域）；集合在模2加法和乘法運算下構(gòu)成一個有限域，稱為二進(jìn)制域，記作。二進(jìn)制域上的加法和乘法運算規(guī)則如下表：6.1.2域的特征和基域有限域存在的充要條件包含個元素的有限域存在的充要條件是，式中是一個素數(shù)，是一個正整數(shù)。對于有限域該域在同構(gòu)（Isomorphism）意義下是唯一的。這意味著任何兩個相同尺寸的有限域在重新命名元素之后可以相互轉(zhuǎn)化。對于某素數(shù)：當(dāng)時得到的有限域可以表示成該域中的兩種運算是模加法和乘法，例如；當(dāng)時得到的有限域稱為的擴(kuò)展域（ExtensionField），其中，而稱為的基域（GroundField），稱為有限域的特征（Characteristic）。6.1.3有限域上的多項式有限域上的多項式有限域上的階多項式可以表示為

(6-1)式中是取自于上的元素，，且。定義在有限域上的多項式之間的加法和乘法遵循正常的加法和乘法規(guī)則，但是多項式系數(shù)之間的加法和乘法要按照模運算。首一多項式（MonicPolynomial）如果式(6-1)中的，則該多項式稱為首一多項式。不可約多項式（IrreduciblePolynomial）如果定義在上的階多項式不能分解為同一個域上的兩個低階多項式的乘積，則稱該多項式為不可約多項式。例如在有限域上，是一個不可約多項式，而則不是一個不可約多項式，因為。素多項式（PrimePolynomial）同時滿足首一和不可約性質(zhì)的多項式稱為素多項式。多項式的根有限域上的階多項式會有個根（有些可能是重根）。6.1.4擴(kuò)展域的結(jié)構(gòu)對于有限域上的多項式，根據(jù)定義可知階小于的多項式一共有個，其中包括和兩個特殊多項式。擴(kuò)展域的生成假設(shè)是一個上的階素多項式，那么由上所有階小于的多項式組成一個集合，該集合中元素之間的運算遵循正常的加法和模的多項式乘法，這樣得到的多項式集合構(gòu)成了一個有限域：該有限域顯然是的一個擴(kuò)展域?！纠?-1】利用有限域上的素多項式來構(gòu)造擴(kuò)展域?！窘狻匡@然，上階小于2的所有多項式為：0，1，和。這些元素構(gòu)成的集合便是所求的擴(kuò)展域：

(6-2)元素之間的加法和乘法運算規(guī)則分別如下面兩表所示。表6-2GF(4)的加法表6-3GF(4)的乘法所有非零元素均可以表示成的某次冪：

【例6-2】利用有限域上的素多項式來構(gòu)造擴(kuò)展域?！窘狻可想A小于3的所有多項式構(gòu)成的擴(kuò)展域為

(6-3)容易驗證，該域中所有非零元素都可以寫成的某次冪的形式：，，，，，，另外，中各元素也可以用式(6-3)中各個多項式對應(yīng)的長度為3的系數(shù)向量來表示。所以，擴(kuò)展域中各元素共有三種等價的表示方法，如下頁的表6-4所示。表6-4GF(8)元素的三種表示當(dāng)計算擴(kuò)展域中元素之間加法的時候，使用多項式形式或向量形式比較簡便：當(dāng)計算元素之間乘法的時候，使用冪形式比較簡便：6.1.5本原元素和本原多項式元素的階（Order）對于任意一個非零元素，滿足等式的最小整數(shù)稱為元素的階。可以證明等式一定成立，所以元素的階的最大值等于。本原元素（PrimitiveElement）如果的某個非零元素的階為，則稱該元素為本原元素。本原元素最為重要的特性是：其各次冪可以生成所在有限域的所有非零元素。本原元素不是唯一的。本原多項式（PrimitivePolynomial）設(shè)由素多項式生成，如果是的一個本原元素，則稱為本原多項式?？梢宰C明：任意階的本原多項式都存在。所以對于任意的正整數(shù)和任意一個素數(shù)，均可以生成為本原元素的擴(kuò)展域，也就說該域中所有的非零元素都可以表示為

，在后面的內(nèi)容中，均假設(shè)有限域是由本原多項式生成的。【例6-3】和都是上的兩個4階素多項式，二者都可以用來生成，請判斷它們是不是本原多項式?！窘狻恐恍枧袛嘞路謩e由和生成的有限域中元素是否為本原元素即可。（1）首先考查由生成的，元素的各次冪分別為：，，，，，，，，，，，，，，所以是本原元素，從而可知是本原多項式。（2）接著來考查由生成的，在該種情況下元素的各次冪分別為：，，，，所以此時的階為5，不是本原元素，于是可知不是本原多項式。本原多項式的另一種定義可以證明，上的任意階素多項式均可以整除。但是，也可能整除，其中。例如，素多項式可以整除，也可以整除。令表示可以使素多項式整除的最小整數(shù)，如果，則是一個本原多項式。該定義表明：當(dāng)時，本原多項式不能整除。顯然，階本原多項式的所有根都將是的本原元素。常用的本原多項式下表給出了時的一些本原多項式：表6-5常用本原多項式【例6-4】利用本原多項式來構(gòu)造，如果是的一個根，請給出的所有元素?！窘狻恳驗槭潜驹囗検降母砸彩堑囊粋€本原元素，于是的所有非零元素都可以寫作的形式，其中。表6-6給出了中元素的三種等價表示形式。表6-6GF(16)的元素，，，四個元素的階均為5；，兩個元素的階為3；，，，，，，，八個元素的階是15，故均為本原元素。6.1.6最小多項式和共軛元素最小多項式（MinimalPolynomial）某個域元素的最小多項式是指以該元素為根的基域上最低階的首一多項式。設(shè)是上的一個非零元素，則的最小多項式是指系數(shù)在上，且滿足的最低階首一多項式。顯然，是上一個素多項式，可以整除上以為根的所有其它多項式，例如是上滿足的任意一個多項式，則其可以表示成。共軛（Conjugates）和共軛類（ConjugacyClass）任意元素的最小多項式可以表示為

(6-4)式中是滿足的最小整數(shù)。由上式可知，除了之外的其它所有根均具有形式（），所有這些根都稱為的共軛。具有相互共軛關(guān)系的所有元素被稱為屬于同一個共軛類?？梢宰C明：一個有限域中任意元素的共軛均會具有相同的階，于是本原元素的共軛也會是本原元素。但是，具有相同階的元素之間卻不一定是共軛關(guān)系。求解元素的最小多項式的步驟：確定共軛類，即所有具有形式的元素，式中，是滿足的最小正整數(shù)；使用下式來確定，該式便是以的共軛類為根的首一多項式。上述步驟獲得的最小多項式一定會是系數(shù)在上的素多項式?！纠?-5】確定中所有元素的共軛類與最小多項式?！窘狻坑杀?-6可知，如果元素是一個本原元素，因為，所以，于是該元素的共軛類為，其最小多項式為

對于