一類新的3重量的二元線性碼

蔡春彥，亓延峰

(杭州電子科技大學理學院，浙江 杭州 310018)

?

一類新的3重量的二元線性碼

蔡春彥，亓延峰

(杭州電子科技大學理學院，浙江 杭州 310018)

線性糾錯碼在通信和計算機科學中有重要應用，也是密碼理論與技術的重要工具，小重量的線性碼可應用于認證碼、秘密共享協(xié)議、結合方案中.如何構造新的具有好的參數(shù)的線性碼是編碼理論和應用的重要問題.該文考慮小重量碼的構造，給出了一類3重量的二元線性碼，并且確定了這類二元碼的重量分布.

線性碼；重量分布；跡函數(shù)；認證碼；秘密共享協(xié)議

0 引 言

令q=2m，GF(q)表示含有q個元素的有限域，GF(q)*表示GF(q)的乘法群，其中m是正整數(shù).一個[n,k,d]線性碼C是GF(2)n上最小漢明重量為d的k維子空間，其中漢明重量是指碼字的非零的元素個數(shù).稱C為最優(yōu)線性碼[1]，若二元線性碼C的參數(shù)n，k和d滿足線性碼的某個界.一些最優(yōu)線性碼結果參見文獻[2].令Ai表示線性碼C中漢明重量為i的碼字個數(shù)，線性碼C的重量計數(shù)定義為1+A1z+A2z2+…+Anzn，重量分布(1,A1,…,An)是線性碼理論的重要研究課題，可以使用某些算法來估計糾錯能力和誤差檢測與校正的概率.t為(1,A1,…,An)中非零的Ai的個數(shù)，稱線性碼為t重量的線性碼.

如何構造好的線性碼是有意義的問題，一類重要的方法是使用函數(shù)來構造[3-6]，令F(x)∈GF(q)[x]，f(x)=Tr(F(x))，令D={x∈GF(q)*|f(x)=0}={d1,d2,…,dn}，則有碼長為n的線性碼CD={Tr(xd1),Tr(xd2),…,Tr(xdn))∶x∈GF(q)}，其中Tr為從GF(q)到GF(2)上的跡函數(shù)，稱D為CD的定義集合，許多工作是使用不同函數(shù)來構造定義集合從而得到線性碼CD[4-8]，例如F(x)=x2h+1，F(xiàn)(x)=x3+x,F(x)=x2,二次bent函數(shù)f(x),弱正則bent函數(shù)等.本文考慮使用函數(shù)F(x)=x2h+1+x來構造線性碼，得到了3重量的線性碼，這類線性碼包含了文獻[5]的線性碼.

1 新的3重量二元線性碼

本節(jié)使用新的函數(shù)F(x)=x2h+1+x來給出定義集合，從而構造了一類新的3重量二元線性碼，并給出了這類線性碼的相關參數(shù)和重量分布，具體證明在第2節(jié)中給出.

表1 定理1.1中的線性碼的重量分布

例1.1 取(m,h)=(5,1)，則m/l=5，由定理1.1得到[11,5,4]線性碼，其重量計數(shù)為1+9z8+16z10+6z12，此線性碼是最優(yōu)碼，滿足Griesmer界[2].

定理1.2 設m/l為偶數(shù)，當m≡2 mod 4時，線性碼CD是[2m-1-1，m]二元碼，其重量分布見表2；當m≡0 mod 4時，線性碼CD是[2m-1-(-1)m/2l2m/2+l-1-1,m]二元碼，其重量分布見表2.

表2 定理1.2中的線性碼的重量分布

例1.2 取(m,h)=(6,1)，則m/l=6，m≡2 mod 4，由定理1.2得到[31,6,12]線性碼，其重量計數(shù)為1+10z12+47z16+6z20.取(m,h)=(8,2)，則m/l=4，m≡0 mod 4，由定理1.2得到[95,8,32]線性碼，其重量計數(shù)為1+10z32+240z48+5z64.

2 主要定理的證明

本節(jié)主要證明定理1.1及定理1.2，確定定理中線性碼的主要參數(shù)和重量分布.為了更好地證明定理，首先做以下準備工作.

引理2.3 設m/l是偶數(shù)，b∈GF(q)*，m=2e.令f(x)=a2hx22h+ax∈GF(q)[x].

當m/l是偶數(shù)時，令m=2e，則Trl(1)=0.當m≡2 mod 4時，由引理2.3知，Sh(1,1)=0，線性碼CD的長度n=n0-1=2m-1-1.由引理2.2和引理2.3，得到對任意的b∈GF(q)*，線性碼CD碼字cb的重量滿足

wt(cb)=n0-Nb∈{2m-2,2m-2-2m/2+l-2,2m-2+2m/2+l-2}.

當m≡0 mod 4時，由引理2.3知，Sh(1,1)=-(-1)m/2l2m/2+l，線性碼CD的長度n=n0-1=2m-1-(-1)m/2l2m/2+l-1-1.由引理2.2和引理2.3得，對任意的b∈GF(q)*，線性碼CD碼字cb的重量滿足

wt(cb)=n0-Nb∈{2m-2,2m-2-(-1)m/2l2m/2+l-2,2m-2-(-1)m/2l2m/2+l-1}.

3 結束語

本文使用新的函數(shù)得到一類3重量的線性碼.3重量的線性碼可以產(chǎn)生結合方案.定義在有限域GF(p)上的線性碼能夠用來構造秘密共享協(xié)議和認證碼.為了得到好的秘密共享協(xié)議，需要線性碼C滿足wmin/wmax>(p-1)/p，其中wmin和wmax表示最小和最大重量的線性碼.易驗證本文定理中的線性碼滿足wmin/wmax>1/2，可以構造秘密共享協(xié)議.如何使用一般的函數(shù)來構造新的、更好的線性碼是以后的研究方向.

[1]HUFFMAN W C, PLESS V. Fundamentals of error-correcting codes[M]. Cambridge，U.K.: Cambridge University Press,2003:53-99.

[2]GRASSL M. Bounds on the minimum distance of linear codes. [EB/OL].[2016-02-23].http://www.codetables.de.

[3]LI C, YUE Q, LI F. Weight distributions of cyclic codes with respect to pairwise coprime order elements[J]. Finite Fields & Their Applications, 2014, 28: 94-114.

[4]YUAN J, DING C. Secret sharing schemes from three classes of linear codes[J]. Information Theory, IEEE Transactions on, 2006, 52(1): 206-212.

[5]XIANG C. Linear codes from a generic construction[J]. Cryptography and Communications, 2015: 1-15.

[6]DING K, DING C. A class of two-weight and three-weight codes and their applications in secret sharing[J]. Information Theory, IEEE Transactions on, 2015, 61(11): 5835-5842.

[7]ZHOU Z, LI N, FAN C, et al. Linear codes with two or three weights from quadratic bent functions[J]. Designs Codes and Cryptography, 2015: 1-13.

[8]TANG C, LI N, QI Y, et al. Linear codes with two or three weights from weakly regular bent functions[J]. Information Theory, IEEE Transactions on, 2016, 62(3): 1166-1176.

[9]LIDL R, NIEDERREITER H. Finite fields[M]. Cambridge，U.K.: Cambridge University Press, 1997:186-267.

[10]COULTER R S. On the evaluation of a class of Weil sums in characteristic 2[J]. New Zealand Journal of Mathematics, 1999, 28(2): 171-184.

[11]CALDERBANK A R, GOETHALS J M. Three-weight codes and association schemes[J]. Philips Journal of Research,1984,39(4): 143-152.

[12]LLOYD S P. Hamming association schemes and codes on spheres[J]. Siam Journal on Mathematical Analysis, 1980, 1(3): 488-505.

[13]CARLET C, DING C, YUAN J. Linear codes from perfect nonlinear mappings and their secret sharing schemes[J]. Information Theory, IEEE Transactions on, 2005, 51(6): 2089-2102.

[14]DING C, HELLESETH T, KL?V T, et al. A general construction of authentication codes[J]. Information Theory, IEEE Transactions on, 2007, 53(6): 2229-2235.

A New Class of Three-weight Binary Linear Codes

CAI Chunyan, QI Yanfeng

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Linear codes can be applied in consumer electronics, communication and data storage system. Linear codes with few weights are of important in secret sharing, authentication codes and association schemes. How to construct good linear codes is of interesting and important in coding theory and its application. This paper considers linear codes with few weights, presents a new class of three-weight linear codes, and determines parameters and weight distribution of these linear codes. Some of these linear codes are optimal.

linear codes; weight distribution; trace function; authentication codes; secret sharing schemes

10.13954/j.cnki.hdu.2016.06.021

2016-03-21

蔡春彥(1988-)，女，河北衡水人，碩士研究生，密碼學.通信作者：亓延峰講師，E-mail：qiyanfeng07@163.com.

TN911.22

A

1001-9146(2016)06-0096-04