基于二次高斯和的增信碼重量分布

衡子靈, 陳輔靈, 李德祥, 劉奮進

(長安大學理學院，西安 710064)

0 引言

令q為素數p的方冪，Fqm表示有qm個元素的有限域，α為Fqm的本原元。

0.1 線性碼和循環碼

對于集合C ?Fnq，如果C是Fq上的線性子空間，則稱C為q元線性碼。這里n稱為線性碼C的碼長，子空間C的維數k稱為該碼的信息位數，k/n稱為該碼的傳輸效率。線性碼C的另一個重要參數是最小漢明距離d，它可以用來刻畫碼的檢錯和糾錯能力。對于線性碼來說，最小距離恰好等于其中所有非零碼字漢明重量的最小值[1]。定義線性碼C的對偶碼為

其中〈c⊥,c〉表示這兩個向量的內積。如果線性碼C的對偶碼的最小距離d⊥≥3，則稱C為射影碼。編碼理論中的一個基本數學問題是構作性能良好的線性碼，即希望效率k/n大以及最小距離d大，但是n、k、d相互制約，它們之間滿足一些界，比如球填充界、Singleton 界、Griesmer 界等[1–2]。如果參數為[n,k,d+1]的線性碼不存在，則稱參數為[n,k,d]的碼為最優碼，參數是[n,k,d ?1]的碼為幾乎最優碼。令Ai表示[n,k,d]碼C中所有重量為i的碼字個數，則序列(1,A1,A2,···,An)稱為C的重量分布，1+A1z+A2z2+···+Anzn稱為C的重量多項式。重量分布是編碼理論中的重要研究課題之一，它不僅可以刻畫碼的檢錯能力和糾錯能力，而且可以計算碼檢錯和糾錯的誤碼率[3]。一般來說，計算碼的重量分布是一件困難的事情。近年來，大量文獻研究了一些特殊線性碼的重量分布[4–14]。

循環碼是一類具有高效編碼和譯碼算法的重要線性碼，在通信和數據存儲系統等領域被廣泛應用。若對于任意的碼字c = (c0,c1,···,cn?1)∈C，其循環移位總滿足(cn?1,c0,···,cn?2)∈C，則稱線性碼C為循環碼。如果把碼字c=(c0,c1,···,cn?1)寫成多項式

則C為q元循環碼當且僅當C為主理想環Fq[x]/〈xn ?1〉的一個理想。從而循環碼C都可以表示成主理想C=〈g(x)〉，其中g(x)∈Fq[x]為首1 多項式，且g(x)|(xn ?1)。多項式g(x)稱為循環碼C的生成多項式，h(x):=(xn ?1)/g(x)稱為C的校驗多項式。校驗多項式的次數等于循環碼的維數，借助于代數學知識，大量文獻研究了循環碼[4–8,11–14]。

0.2 線性碼的增信碼

令C為Fq上參數是[n,k,d]的線性碼且其生成矩陣為G，設長度為n的全1 向量1 =(1,1,···,1)不是C中的碼字，定義～C為由矩陣

生成的線性碼，線性碼～C稱為C的增信碼[15]。顯然增信碼～C的參數為[n,k+1]，從而～C的信息位數大于C的信息位數。一般來說，確定增信碼～C的最小距離和重量分布是一件困難的事情，這可能需要知道原始碼C的完全重量分布信息[15]。當q= 2 時，容易得出～C的最小距離

其中wmax表示C中的最大漢明重量。顯然～C和C具有不同的參數和重量分布，從而增信碼是構造新碼的重要方法之一。最近，文獻[16]研究了一類不可約循環碼的增信碼，這類增信碼是具有三個非零重量的射影碼；文獻[17]研究了一類循環碼的增信碼，這類增信碼關于Griesmer 界最優且其對偶碼是幾乎MDS 碼。

0.3 本文主要工作

令q為奇素數的方冪，令Trqm/q表示從Fqm到Fq的跡函數，其中

定義一類q元可約循環碼

根據Delsarte 定理[3]知，這類循環碼的校驗多項式為mα?1(x)m(?α)?1(x)，其中mα?1(x)、m(?α)?1(x)分別表示α?1和(?α)?1的極小多項式。顯然mα?1(x)和m(?α)?1(x)的次數均為m，從而C的參數為[qm ?1,2m]。當m為奇數時，文獻[13]中定理7 證明了C是一類具有兩個非零重量的循環碼，且C在q=3 時是射影碼。

1) 借助于二次高斯和精確刻畫出了增信碼～C在偶數m和奇數m兩種情形下的重量分布；

2) 證明了～C的對偶碼關于球填充界最優或幾乎最優，且～C在偶數m和奇數m兩種情形下都是射影碼；

3) 給出了循環碼C的完全重量分布。

1 有限域上特征與特征和

令p為素數，e為正整數且q=pe，令ζp表示本原p次復單位根，定義有限域Fq的加法特征為加法群Fq到復乘法群C?的同態映射?，即?滿足

對任意的a ∈Fq，函數

即為Fq的一個加法特征[1]。此外，集合{?a:a ∈Fq}給出了Fq的全部q個不同的加法特征且構成一個群。如果a= 0，則稱?0為Fq的平凡加法特征；如果a= 1，則稱?1為Fq的典范加法特征。顯然?a(x)=?1(ax),a ∈Fq。加法特征的正交關系如下[18]

令F?q= Fq{0}且β為Fq的本原元，有限域Fq的乘法特征為乘法群F?q到復乘法群C?的同態映射

Fq的所有乘法特征可如下給出

其中0≤j ≤q ?2。特別地，ψ0稱為平凡乘法特征，η:=ψ(q?1)/2稱為二次乘法特征。乘法特征的正交關系如下[18]

令ψ為Fq的乘法特征，?為Fq的加法特征。定義有限域Fq上的高斯和如下

對于非平凡特征?，稱G(η,?)為Fq上的二次高斯和。高斯和G(ψ,?)的精確值僅僅在一些特殊情形下是清楚的，下面給出二次高斯和的精確值。

引理1[18]令q=pe，e為正整數且p為奇素數，令?1為Fq的典范加法特征，那么

引理2[18]令?為Fq的非平凡加法特征，其中q為奇素數的方冪。令f(x) =a2x2+a1x+a0∈Fq[x]且a2/=0，則

2 增信碼～C 的參數和重量分布

規定一些符號如下：令χ1、?1分別表示有限域Fqm和Fq的典范加法特征，q=pe，p為奇素數。令η、η′分別表示有限域Fqm和Fq的二次乘法特征。

下面研究式(1)中定義的增信碼～C的重量分布。

對任意碼字

根據加法特征的正交關系以及跡函數的傳遞性，可知其漢明重量

定義一類特征和如下

則

其中

從而計算～C的重量分布只需研究特征和S(a,b,c)和S(aα,?bα,c)的分布即可。下面分兩種情形進行討論。

2.1 當m 為偶數時

在本部分中，令m為正偶數。由于q為奇數且m為偶數，故任意的y ∈F?q都滿足η(y)=1。根據引理2，可知

類似可以得到

根據引理1，可知

對于固定的元素c ∈Fq，下面給出S(a,b,c)+S(aα,?bα,c)當(a,b)取遍Fqm×Fqm時值的分布。

下面的引理很容易證明，這里證明略去。

引理3 令q為奇素數p的方冪，則如下的等式成立

根據式(3)、式(4)和引理3 可直接得出下面的結論。

引理4 令c ∈Fq為任意固定元素，m為偶數。如果(a,b)取遍Fqm×Fqm中元素，則S(a,b,c)+S(aα,?bα,c)值的分布見表1，其中

表1 引理4 中S(a,b,c)+S(aα,?bα,c)的值的分布(c ∈Fq 為固定元素)

本部分的主要結論如下。

定理1 令m為偶數且q=pe，其中p為奇素數，則循環碼～C是

射影循環碼且其重量分布見表2，其中

表2 定理1 中～C 的重量分布

此外，若q ＞3，則～C的對偶碼的參數為[qm ?1,qm ?2m ?2,3≤?d⊥≤4]，且對偶碼關于球填充界最優或幾乎最優。

證明 根據加法特征的正交關系

根據公式(2)和引理4，即可得到表2 中～C的重量分布。由于

根據表2，可知

從而，容易得出～C的最小距離

現在證明～C是射影碼。顯然，對偶碼～C⊥的最小距離?d⊥不可能為1。根據對偶碼的定義，～C⊥中存在重量為2 的碼字，當且僅當存在u1,u2∈F?q以及兩個整數t1和t2(0≤t1＜t2≤qm ?2)，使得

根據上述方程組第一個和第三個式子可得出t1=t2，這與t1＜t2矛盾。從而?d⊥≥3，故～C是射影碼。若q ＞3，根據球填充界[1]，可知

容易得出?d⊥≤4，從而～C⊥的參數為[qm ?1,qm ?2m ?2,3≤d⊥≤4]，且～C⊥關于球填充界最優或幾乎最優。

推論1 令m為偶數且q=pe，其中p為奇素數，則C為

循環碼且其重量分布見表3，其中

表3 推論1 中C 的重量分布

此外，C⊥為[qm ?1,qm ?1?2m,2]循環碼。

證明 對任意碼字

根據公式(2)，可知其漢明重量

顯然T(0) =q ?1。根據引理4 容易得出S(a,b,0)+S(aα,?bα,0)的值的分布，從而容易得出C的重量分布和最小距離。根據C的重量分布和文獻[19]中的Pless Power Moments 可以得出其對偶碼的最小距離為2。

下面給出由Magma 生成的一些例子，它們與上述定理的結果一致。

例1 令p= 3,e= 1 且m= 2，則～C為參數是[8,5,2]的三元循環碼且其重量多項式為1+8z2+56z4+64z5+80z6+16z7+18z8，其對偶碼～C⊥為[8,3,4]三元循環碼。根據http://codetables.de/中的Code Tables 可知，～C和～C⊥均為幾乎最優碼。此外，C為[8,4,2]三元循環碼且其重量多項式為1+8z2+24z4+32z6+16z8，其對偶碼的參數為[8,4,2]。

例2 令p= 5,e= 1 且m= 2，則～C為參數是[24,5,8]的五元循環碼且其重量多項式為

其對偶碼的參數為[24,20,2]。

2.2 當m 為奇數時

在本部分中，令m為奇數。由于q為奇數且m為奇數，則任意y ∈F?q都滿足η(y) =η′(y)。根據引理2 以及乘法特征的正交關系

類似可以得到

根據引理1 可知

以及

取任意固定元素c ∈Fq，下面給出S(a,b,c)+S(aα,?bα,c)的值的分布。

引理5 令m為奇數，如果(a,b)取遍Fqm×Fqm中元素，則S(a,b,0)+S(aα,?bα,0)值的分布為

證明 令c=0，則根據公式(5)和公式(6)，可知

則容易得出S(a,b,0)+S(aα,?bα,0)的值的分布。

引理6 令m為奇數，若(a,b,c)取遍Fqm×Fqm×F?q中元素，則S(a,b,c)+S(aα,?bα,c)值的分布見表4，其中

表4 引理6 中S(a,b,c)+S(aα,?bα,c)值的分布

證明 對任意c ∈F?q, 根據公式(5)和(6)可得

若(a,b)跑遍Fqm×Fqm且c為固定元素，則S(a,b,c)+S(aα,?bα,c)的值的分布為

其中每一個非零重量的頻數可由引理3 得出。注意到如果c是F?q中的平方元，則η′(c) =1；如果c是F?q中的非平方元，則η′(c)=?1。從而當(a,b,c)取遍Fqm×Fqm×F?q中的元素時，S(a,b,c)+S(aα,?bα,c)值的分布即可得出。

定理2 令m ≥3 為奇數且q=pe，其中p為奇素數，則～C為

射影循環碼且其重量分布見表5，其中

表5 定理2 中～C 的重量分布

此外，如果q ＞3，則～C的對偶碼是[qm ?1,qm ?2m ?2,3≤?d⊥≤4]循環碼且關于球填充界最優或幾乎最優。

證明 根據公式(2)和引理5、引理6，可直接得出表5 中～C重量分布。由于m ≥3，則有

根據表5 可知

從而～C的最小距離?d=(qm?1(q ?1))/2。類似于定理1 的證明，容易得出～C為射影碼且其對偶碼的參數為[qm ?1,qm ?2m ?2,3≤?d⊥≤4]。根據球填充界可知，對偶碼最優或幾乎最優。

根據定理2 容易得出下面的推論。

推論2 令m ≥3 為奇數且q=pe，其中p為奇素數，則C為

循環碼且其重量分布見表6。如果q=3，其對偶碼的參數為[3m ?1,3m ?2m ?1,3]；如果q ＞3，其對偶碼的參數為[qm ?1,qm ?2m ?1,2]。

表6 推論2 中C 的重量分布

證明 對任意碼字

根據公式(2)可知其漢明重量

顯然T(0)=q ?1。根據引理5 即可得到S(a,b,0)+S(aα,?bα,0)值的分布，從而容易得出C的重量分布。根據文獻[13]即可得到其對偶碼的參數。

下面給出由Magma 生成的一些例子，它們與上述定理的結果一致。

例3 令p= 3,e= 1 且m= 3，則～C為參數是[26,7,9]的三元循環碼且其重量多項式為

其對偶碼～C⊥為[26,19,3]三元循環碼。此外，C為[26,6,9]三元循環碼且其重量多項式為1+52z9+676z18，其對偶碼的參數為[26,20,3]。

例4 令p= 5,e= 1 且m= 3，則～C為參數是[124,7,50]的五元循環碼且其重量多項式為

其對偶碼～C⊥為[124,117,3]五元循環碼。根據http://codetables.de/中的Code Tables 可知，～C⊥為最優碼。此外，C為[24,4,8]五元循環碼且其重量多項式為1 + 248z50+15 376z100，其對偶碼的參數為[124,118,2]。

2.3 循環碼C 和～C 的比較

定理1、定理2 和推論1、推論2 分別給出了循環碼C和～C在兩種情形下的參數和重量分布。容易看出，無論m是奇數還是偶數，循環碼C和其增信碼～C具有相同的最小漢明距離。現在比較C的碼率R和～C的碼率～R，顯然

從而增信碼～C的傳輸效率優于C。

此外，根據推論1、推論2，只有當q=3 且m為奇數時，C才為射影碼，其他情形下都是非射影碼。而根據定理1、定理2，增信碼～C總是射影碼。

綜上，本文所研究的增信碼在上述兩方面優于原碼C。

3 C 的完全重量分布

二元碼的完全重量分布即為其重量分布，但非二元碼的完全重量分布與重量分布不同。完全重量分布是編碼理論中的重要研究課題之一，國內外很多文獻研究了一些循環碼或線性碼的完全重量分布[21–24]。

下面給出循環碼

的完全重量分布。對任意c ∈Fq，記

類似于公式(2)的推導過程，可得

根據公式(7)和引理4 可直接得出m為偶數時，C的完全重量分布。

定理3 令m為偶數，如果(a,b)取遍Fqm×Fqm中元素，則碼C的完全重量分布見表7，其中

表7 定理3 中循環碼C 的完全重量分布

令β為Fq的本原元，下面給出m為奇數時，C的完全重量分布。

定理4 令m為奇數，如果(a,b)取遍Fqm×Fqm中元素，則碼C的完全重量分布見表8，其中

表8 定理4 中循環碼C 的完全重量分布

證明 若(a,b)取遍Fqm×Fqm中元素且c為非零固定元素，則由引理6 的證明過程可得S(a,b,?c)+S(aα,?bα,?c)的值的分布為

從而，根據公式(7)即可得到C的完全重量分布。

4 總結

本文主要利用有限域上特征的性質、二次高斯和等數論工具研究了循環碼C的增信碼～C，不僅給出了～C的參數和重量分布，而且給出了C的完全重量分布，增信碼～C的對偶碼關于球填充界最優或幾乎最優。特別地，增信碼～C和原碼C具有相同的最小距離，但～C的傳輸效率更高。原碼C僅僅當q= 3 且m為奇數時為射影碼，而增信碼～C在所有情形下總是射影碼。