環(huán)Fp＋uFp上的廣義Reed－Muller碼

尹 水， 朱士信

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

環(huán)Fp＋uFp上的廣義Reed－Muller碼

尹 水， 朱士信

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

Reed－Muller碼是一類非常重要的代數(shù)碼，具有很好的代數(shù)和組合性質(zhì)。文章首次將Reed－Muller碼的概念引入環(huán)Fp＋uFp上，定義了更一般的Reed－Muller碼URM（p，r，m），給出了它的跡表示，并研究了它的對偶碼以及兩者之間的關(guān)系。特別地，當(dāng)p＝2時，得到了一些更好的性質(zhì)。

Reed－Muller碼；Kerdock碼；Preparata碼；Galois環(huán)；跡表示

0 引 言

Reed－Muller碼首先是由Muller在1954年提出的，之后Reed在其基礎(chǔ)上得到了一種新的分組碼，稱為Reed－Muller碼。它最大的優(yōu)點是易于解碼，因而在通信中具有廣泛的應(yīng)用前景，一直是人們關(guān)注的熱點。文獻(xiàn)［1］中詳細(xì)介紹了二元Reed－Muller碼，根據(jù)布爾函數(shù)給出了一個簡單直觀的定義，并研究了它的一些基本性質(zhì)及應(yīng)用。

近年來，有限環(huán)尤其是有限鏈環(huán)上的代數(shù)編碼理論引起了許多學(xué)者的興趣［2－6］。隨著Z4環(huán)上編碼理論的研究日趨成熟，人們逐漸探索出一種研究有限鏈環(huán)上的Reed－Muller碼的方法［7－9］。文獻(xiàn) ［10］首 次 在 環(huán)Fp＋uFp上 引 入Kerdock碼和Preparata碼的相關(guān)概念，給出了該環(huán)上 Kerdock碼Kp，m和 Preparata碼Pp，m的 定義，證明了它們互為對偶碼。特別地，當(dāng)p＝2時，建立了環(huán)F2＋uF2上的這2類碼與二元r階Reed－Muller碼之間的聯(lián)系，即它們的剩余碼分別為R（1，m）和R（m－2，m），且R（1，m）為環(huán)R2上Kerdock碼K2，m的線性子碼的Gray象。

本文在此基礎(chǔ)上進(jìn)一步加以研究，將Reed－Muller碼的概念引入環(huán)Fp＋uFp上，給出了更一般的Reed－Muller碼URM（p，r，m）的定義，并且研究了一些相關(guān)的性質(zhì)。

1 預(yù)備知識

記Rp＝Fp＋uFp，其中p為素數(shù)，F(xiàn)p為有限域，u2＝0，規(guī)定其上的加法和乘法為域Fp上的加法和乘法。

令＝｛（x1，x2，…，xn）｜xi∈Rp，i＝1，2，…，n｝。環(huán)Rp上一個長為n的p元線性碼定義為Rp－模的一個加法子模，簡稱為Rp－線性碼。環(huán)Rp上任一非零的Rp－線性碼C都等價于矩陣

生成的Rp－線性碼，其中A、B1、B2、C為Fp上的矩陣。顯然C的類型為，且其碼字個數(shù)

對于?x＝（x1，x2，…，xn），y＝（y1，y2，…，yn）∈，定義x和y的內(nèi)積為x·y＝x1y1＋x2y2＋…＋xnyn。若x·y＝0，則稱x與y正交。稱C⊥＝｛x∈｜?y∈C，x·y＝0｝為C的對偶碼。對于環(huán)Rp上的線性碼C，如果對于?（c0，c1，…，cn－1）∈C，都有（cn－1，c0，c1，…，cn－2）∈C，那么稱C為環(huán)Rp上的循環(huán)碼，簡稱為Rp－循環(huán)碼。環(huán)中的碼字（c0，c1，…，cn－1）與Rp［x］／（xn－1）中的多項式c0＋c1x＋…＋cn－1xn－1一一對應(yīng)，從而環(huán)Rp上長為n的循環(huán)碼與Rp［x］／（xn－1）的理想一一對應(yīng)，在不引起混淆的情況下，認(rèn)為這2種表達(dá)是一樣的。

在環(huán)Rp中，任意元素c都可唯一地表示成c＝a＋ub，其中a，b∈Fp。稱＝a為c的模u約化。更一般地，稱ˉh（x）＝的模u約化。若（x）是Fp［x］中的不可約多項式，則稱h（x）是Rp［x］中的基本不可約多項式；若（x）是Fp［x］中的m次本原多項式，則稱h（x）是Rp［x］中的m次基本本原多項式。稱（x）＝xdeg（h（x））h（1／x）為h（x）的互反多項式。對于Rp［x］中首一的m次基本本原多項式h（x），稱Rp［x］／（h（x））為環(huán)Rp的 Galois擴環(huán)，記為GR（Rp，m）。GR（Rp，m）中的任一元素γ都可以唯一表示成γ＝α＋uβ，其中α，β∈Fpm。

本文仍然沿用文獻(xiàn)［10］中關(guān)于跡映射的記號，定義Galois環(huán)GR（Rp，m）上的Frobenius映射為：

易證f是環(huán)GR（Rp，m）上的環(huán)自同構(gòu)，f的固定元素恰好全為環(huán)Rp中的元素，并且f的階為m。定義從環(huán)GR（Rp，m）到環(huán)Rp的跡映射為：

顯然Tr是線性的，且為滿射。

2 環(huán)Fp＋uFp上的Reed－Muller碼

2.1 相關(guān)定義與命題

令m為一個大于等于2的整數(shù)，n＝pm－1。設(shè)h（x）為多項式環(huán)Rp［x］中首一的m次基本本原多項式，且h（x）｜（－1），那么在 Galois環(huán)GR（Rp，m）＝Rp［x］／（h（x））中存在h（x）的一個根ζ，并且ζ的階為pm－1，h（x）的m個不同的根為ζ，ζp，…。對于（m＋1）×pm階矩陣

將它的列依序標(biāo)號為∞，0，1，2，…，n－1，如果ζj＝c1j＋c2jζ＋…＋cmjζm－1（j＝∞，0，1，…，n－1），其中cij∈Rp（i＝1，2，…，m），這里約定ζ∞＝0，那么用（c1j，c2j，…，cmj）′替代ζj，將它的行依序標(biāo)號為0，1，2，…，m。記該矩陣的第i個行向量為xi，那么xi（i＝0，1，2，…，m）為環(huán)Rp上的pm－元組，其中x0為全1的pm－元組。簡便起見，定義2個向量之間的分量積為：（a∞，a0，a1，…，an－1）（b∞，b0，b1，…，bn－1）＝ （a∞b∞，a0b0，a1b1，…，an－1bn－1）。

定義1 設(shè)整數(shù)m≥2，n＝pm－1，0≤r≤m，那么在環(huán)Rp上由所有形如…（1≤i1＜i2＜…＜is≤m，0≤s≤r）的pm－元組生成的Rp－線性碼，稱為環(huán)Rp上的r階 Reed－Muller碼，記為URM（p，r，m）。這里約定：當(dāng)s＝0時，有

根據(jù)定義1，立即可以得到命題1～命題4。

命題1 對于任意整數(shù)0≤r≤m，URM（p，r，m）的類型為，其中

命題2 環(huán)Rp上的1階Reed－Muller碼為環(huán)Rp上的 Kerdock碼，即 URM（p，1，m）＝Kp，m。

證明 當(dāng)r＝1時，由定義1及文獻(xiàn)［10］中定義1可知，URM（p，1，m）的生成矩陣即為Kp，m的生成矩陣，得證。

當(dāng)p＝2時，環(huán)R2上的r階Reed－Muller碼URM（2，r，m）有一些很好的性質(zhì)。

命題3 環(huán)R2上的2m個2m－元組…（1≤i1＜i2＜…＜is≤m，0≤s≤m），構(gòu)成了自由R2－模的一組基。

證明 證明與文獻(xiàn)［8］中引理10.3類似。

記 URM（p，r，m）的剩余碼為：

那么有命題4。

命題4 URM（2，r，m）的剩余碼等價于二元r階 Reed－Muller碼R（r，m），即＝R（r，m）。

證明 由定義1可知，當(dāng)p＝2時，對于任意的c＝a＋ub∈URM（2，r，m），都存在∈R2（1≤i1＜i2＜…＜is≤m，0≤s≤r），使得：

那么，c的模u約化為：

這里的∈F2。顯然，a＝∈，由c的任意性可知，是由所有形如…（1≤i1＜i2＜…＜is≤m，0≤s≤r）的2m－元組生成的。不難證明，如果寫成矩陣形式，那么與二元r階Reed－Muller碼R（r，m）的生成矩陣是等價的，所以＝R（r，m）。

證畢。

2.2 定理1及其證明

文獻(xiàn)［10］的重要結(jié)果之一是給出了環(huán)Rp上Kerdock碼Kp，m和 Preparata碼Pp，m的 跡 表 示，自然地，本文也將給出環(huán)Rp上的r階Reed－Muller碼 URM（p，r，m）的跡表示。

在這里，引入p－重量的概念。令正整數(shù)j的p進(jìn)制展開為j＝，其中λi∈Fp且λt≠0。稱λ0，λ1，λ2，…，λt之中非零項的個數(shù)為j的p－重量，記為ωp（j），即

另外，定義0的p－重量ωp（0）＝0。特別地，如果正整數(shù)j的p進(jìn)制展開式的系數(shù)滿足λ0，λ1，λ2，…，λt－1＝0或1，且λt＝1，那么就將j記為j（2），稱它的p－重量為二元p－重量，記為（j），顯然（j）＝。同樣地，定義0的二元p－重量（0）＝0。

設(shè)正整數(shù)m為某一固定的值，令整數(shù)r和s滿足0≤r，s≤pm－2。如果存在非負(fù)整數(shù)i，使得pir≡s（modpm－1），則r與s等價。顯然，這定義了整數(shù)集｛0，1，2，…，pm－2｝上的一個等價關(guān)系，稱這些等價類為模pm－1的分圓陪集。容易看出，如果r和s屬于同一個分圓陪集，那么就有ωp（r）＝ωp（s）。特別地，如果r可記為r（2），且和s屬于同一個分圓陪集，那么s也可記為s（2），且有（r）＝（s）。稱分圓陪集中取值最小的一個數(shù)為該分圓陪集的代表元。

令Γ＝｛0，1，2，…，pm－2｝，Γ（2）表示Γ中可記為j（2）的元素的集合，則有定理1。

定理1 設(shè)整數(shù)m≥2，n＝pm－1，那么URM（p，0，m）是長為pm的Rp－重復(fù)碼｛｜a∈Rp｝，且當(dāng)1≤r≤m時，URM（p，r，m）是由URM（p，0，m）以及所有形如

的pm－元組生成的，其中j∈Γ（2）取遍模pm－1的分圓陪集中滿足（j）≤r的陪集的代表元集，而ρj取遍Galois環(huán)GR（Rp，m）。

證明 由定義1知，

現(xiàn)令1≤r≤m，將題設(shè)中由URM（p，0，m）以及所有形如

的pm－元組生成的Rp－線性碼，記為Cp，r。

當(dāng)r＝1時，由命題2，URM（p，1，m）＝Kp，m，再由文獻(xiàn)［10］中的定理1可知：

因此 URM（p，1，m）＝Cp，1。由定義1，URM（p，1，m）是由，x1，x2，…，xm生成的，對于每一個xi（i＝1，2，…，m），都存在唯一的σi∈GR（Rp，m），使得：

下證當(dāng)r＝2時的情形，需證 URM（p，2，m）＝Cp，2。

由定義1可得：

當(dāng)r＝1時，有 URM（p，1，m）＝Cp，1?Cp，2，因此＋∈Cp，2。

易知：

對于k∈｛∞，0，1，2，…，n－1｝，由跡映射的定義可得：

則可將xixj寫成如下形式：

顯然，當(dāng)l＝0時，（2）＝1，則

而當(dāng)1≤l≤m－1時（1＋pl）＝2，則

從而xixj∈Cp，2（1≤i＜j≤m），因此 URM（p，2，m）?Cp，2。

另一方面，將刪去Cp，2中碼字第∞位置分量所得的刪減碼記為。那么，顯然是由以及所有形如

（Tr（ρjζ0），Tr（ρjζj），Tr（ρjζj·2），…，Tr（ρjζj（n－1）））的（pm－1）－元組生成的Rp－線性碼，其中j∈Γ（2）取遍模pm－1的分圓陪集中滿足（j）≤2的陪集的代表元集，而ρj取遍Galois環(huán)GR（Rp，m）。類似于文獻(xiàn)［10］中的定理1，容易驗證，中所有元素對應(yīng)的多項式都能被多項式（x）零化，其中，而（x）是多項式h2（x）的的互反多項式，則有：

令g2（x）為多項式

的互反多項式，即

記環(huán)Rp上由g2（x）生成的循環(huán)碼為C。那么，（x）即為C的校驗多項式，故有Cp，2?C，從而URM（p，2，m）?Cp，2?C。易證：

又根據(jù)命題1可知，當(dāng)r＝2時，URM（p，2，m）的類型為 （，所 以 有｜URM （p，2，m）｜＝（＝ （p2＝｜C｜。 綜 上 可 得，URM（p，2，m）＝Cp，2＝C。

對于r≥3時的情形，可以同上類似地證明。

證畢。

事實上，定理1是環(huán)Rp上的r階Reed－Muller碼URM（p，r，m）（0≤r≤m）的一個等價定義，給出了其中元素的跡表示。由上述定理的證明，立即可以得到下列推論。

推論1 記環(huán)Rp上刪去URM（p，r，m）中碼字第∞位置分量所得的刪減碼為URM（p，r，m）－，那么 URM（p，r，m）－為Rp－循環(huán)碼，其生成多項式為：

其中，εr＝±1。

推論2 設(shè)整數(shù)m≥2，那么對于任意的c＝（c∞，c0，c1，…，cn－1）∈URM（p，r，m），當(dāng)p≥3時，在環(huán)Rp上，對于任意整數(shù)0≤r≤m，都有：

而當(dāng)p＝2時，在環(huán)R2上，（1）式對于0≤r≤m－1成立。

證明 只需證明定理1中給出的URM（p，r，m）的所有生成元都滿足（1）式即可。首先，m≥2，對于，在環(huán)Rp上有：

其次，對于 URM（p，r，m）的所有生成pm－元組，則有：

其中，（2）式的最后一步是因為ζn＝＝1，若p≥3，則對于任意0≤r≤m，j∈Γ（2），（j）≤r≤m，都有≠1；而若p＝2，則對于0≤r≤m－1，（j）≤r≤m－1，有≠1。證畢。

注意，對于推論2，當(dāng)p＝2，r＝m時，如果（j）＝m，那么j＝1·20＋1·21＋…＋1·2m－1＝2m－1，此時分式的分母為1－＝1－＝1－1＝0。

2.3 定理2及其證明

定理2 設(shè)整數(shù)m≥2，n＝pm－1，0≤r≤m－1，則有URM（p，m－r－1，m）?URM（p，r，m）⊥。

證明 首先，證明全1的pm－元組∈URM（p，m－r－1，m）屬于 URM（p，r，m）⊥。顯然，·＝0。此外，還需證明與定理1中給出的 URM（p，r，m）的所有生成pm－元組都正交。由推論2可知＝0，其中j∈Γ（2），（j）≤r。因此，1pm∈URM（p，r，m）⊥。

下面證明任意的c＝（c∞，c0，c1，…，cn－1）∈URM（p，m－r－1，m）都屬于 URM（p，r，m）⊥。由前面的約定ζ∞＝0，則有Tr（ρjζ∞）＝Tr（0）＝0，從而易證：

因此，只需證明 URM（p，m－r－1，m）中任意滿足c∞＝0的c都屬于 URM（p，r，m）⊥即可。令c＝（0c＇），其中c＇＝（c0，c1，…，cn－1），顯然c＇∈URM （p，m－r－1，m）－。 由 推 論 1，URM（p，m－r－1，m）－為Rp－循環(huán)碼，其生成多項式為：

其中εm－r－1＝±1。所以，gm－r－1（x）｜c（x），其中c（x）＝c0＋c1x＋…＋cn－1xn－1。

則c（x）fm－r－1（x）＝0。因此，c（x）屬于以多項式（x）為生成多項式的Rp－循環(huán)碼的對偶碼，且有：

根據(jù)推論1，以gr（x）為生成多項式的Rp－循環(huán)碼是 URM（p，r，m）－，因而c（x）∈（URM（p，r，m）－）⊥。由于c∞＝0，因此c∈URM（p，r，m）⊥。故有：

證畢。

特別地，當(dāng)p＝2時，有以下結(jié)論。

推論3 設(shè)整數(shù)m≥2，n＝2m－1，0≤r≤m－1，則有 URM（2，m－r－1，m）＝URM（2，r，m）⊥。

證明 由定理2可得，URM（2，m－r－1，m）?URM（2，r，m）⊥。

顯然 URM（2，r，m）⊥與 URM（2，m－r－1，m）類型一致，所以 URM（2，m－r－1，m）＝URM（2，r，m）⊥。

推論4 URM（p，m－2，m）?Pp，m，特別地，有 URM（2，m－2，m）＝P2，m。

證明 由定理2、命題2及文獻(xiàn)［10］中定理2可得：

特別地，當(dāng)p＝2時，由推論3有：

3 結(jié)束語

有限環(huán)上的Reed－Muller碼不僅在理論上可以用來構(gòu)造一些很好的碼，如Kerdock碼、Preparata碼以及Goethals碼等，而且在實際中也有著廣泛的應(yīng)用，因而具有很大的研究價值。本文將Reed－Muller碼的概念引入環(huán)Fp＋uFp上，給出了更一般的Reed－Muller碼 URM（p，r，m）的定義，用一個等價定義給出了其中元素的跡表示，并且研究了其他的一些相關(guān)性質(zhì)。至于更一般的有限環(huán)上的Reed－Muller碼，還有待于進(jìn)一步加以研究。

［1］Macwilliams F J，Sloane N J A.The theory of error－correcting codes［M］.Amsterdam：North Holland Publishing Co，1977：370－479.

［2］Bonnecaze A，Udaya P.Cyclic codes and self－dual codes overF2＋uF2［J］.IEEE Trans Inform Theroy，1999，45（4）：1250－1255.

［3］Gaborit P.Mass formulas for self－dual codes overZ4andFq＋uFqrings［J］.IEEE Trans Inform Theroy，1996，42（4）：1222－1228.

［4］Qian Jianfa，Zhang Lina，Zhu Shixin.Cyclic codes overFp＋uFp＋…＋uk－1Fp［J］.IEICE Trans Fundamentals，2005，E88－A：795－797.

［5］李富林，朱士信.環(huán)Fp＋uFp＋…＋ukFp上的準(zhǔn)循環(huán)碼［J］.合 肥 工 業(yè) 大 學(xué) 學(xué) 報：自 然 科 學(xué) 版，2009，32（11）：1766－1768.

［6］湯道安，朱士信，唐永生.環(huán)F2＋uF2＋…＋ukF2上的自對偶碼［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（3）：478－480.

［7］Hammons A R，Kumar P V，Calderbank A R，et al.TheZ4－linearity of Kerdock，Preparata，Goethals，and related codes［J］.IEEE Trans Inform Theroy，1994，40（3）：301－319.

［8］Wan Zhexian.Quaternary codes［M］.Singapore：World Scientific，1997：113－176.

［9］Bhaintwal M，Wasan S K.Generalized Reed－Muller codes overZq［J］.Designs Codes Cryptogr，2010，54（2）：149－166.

［10］吳 波，朱士信，李 平.環(huán)Fp＋uFp上的Kerdock碼和Preparata碼［J］.電子學(xué)報，2008，36（7）：1364－1367.

Generalized Reed－Muller codes over the ringFp＋uFp

YIN Shui， ZHU Shi－xin
（School of Mathematics，Hefei University of Technology，Hefei 230009，China）

Reed－Muller codes form a very important family of algebraic codes that have very nice algebraic and combinatorial properties.In this paper，the concept of the Reed－Muller code is first introduced into the ringFp＋uFp，which is denoted by URM（p，r，m）.Its trace representation is given，and its dual code and the relationship between them are studied.Especially，some better properties are obtained whenp＝2.

Reed－Muller code；Kerdock code；Preparata code；Galois ring；trace representation

O157.4

A

1003－5060（2012）04－0571－06

10.3969／j.issn.1003－5060.2012.04.031

2011－07－25；

2011－09－16

尹 水（1987－），男，安徽宿松人，合肥工業(yè)大學(xué)碩士生；

朱士信（1962－），男，安徽樅陽人，博士，合肥工業(yè)大學(xué)教授，博士生導(dǎo)師.

（責(zé)任編輯 張淑艷）