第6章BCH和RS碼本章內(nèi)容：6.1有限域6.2BCH碼6.3RS碼6.4BCH和RS碼的仿真實(shí)例§6.1有限域6.1.1有限域的定義阿貝爾群（AbelianGroup）對于集合，定義符號“”表示一種二進(jìn)制運(yùn)算，如果滿足下面的條件則稱該集合為阿貝爾群：該運(yùn)算具有交換律。即對于任意，有；該運(yùn)算具有結(jié)合律。即對于任意，有；該運(yùn)算具有可以用“0”表示的幺元（IdentityElement）。即對于任意，有；對于任意一個元素，均存在元素滿足，其中元素稱為的加法逆。因此，一個阿貝爾群通常可以記作。注意：阿貝爾群也可以改用符號“

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

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

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

【例6-2】利用有限域上的素多項(xiàng)式來構(gòu)造擴(kuò)展域。【解】上階小于3的所有多項(xiàng)式構(gòu)成的擴(kuò)展域?yàn)?/p>

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

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

(6-4)式中是滿足的最小整數(shù)。由上式可知，除了之外的其它所有根均具有形式（），所有這些根都稱為的共軛。具有相互共軛關(guān)系的所有元素被稱為屬于同一個共軛類。可以證明：一個有限域中任意元素的共軛均會具有相同的階，于是本原元素的共軛也會是本原元素。但是，具有相同階的元素之間卻不一定是共軛關(guān)系。求解元素的最小多項(xiàng)式的步驟：確定共軛類，即所有具有形式的元素，式中，是滿足的最小正整數(shù)；使用下式來確定，該式便是以的共軛類為根的首一多項(xiàng)式。上述步驟獲得的最小多項(xiàng)式一定會是系數(shù)在上的素多項(xiàng)式。【例6-5】確定中所有元素的共軛類與最小多項(xiàng)式。【解】由表6-6可知，如果元素是一個本原元素，因?yàn)椋裕谑窃撛氐墓曹楊悶椋渥钚《囗?xiàng)式為

對于