一类大集合p元低相关序列集的线性复杂度研究

陈 俊，陈 运，吴 震

(1. 西南交通大学信息科学与技术学院 成都 610031; 2. 成都信息工程学院信息安全研究所 成都 610225)

具有大线性复杂、大集合容量(family size)和低相关特性的伪随机序列被广泛应用于码分多址通信系统[1]。在码分多址通信系统中，序列之间较低的相关特性可以降低来自同一信道其他用户的干扰；较多的序列数目可以增加系统的容量；而较大的线性复杂度可以抵抗基于Berlekamp-Massey算法进行的攻击，从而提高系统的安全性。因此，构造同时具有低相关性特、大线性复杂和大集合容量的伪随机序列集成为一个重要的研究课题。

人们已经构造出许多具有低相关特性的p(p是奇素数)元序列集，如文献[2-10]中的序列集，但这些序列的线性复杂度都很低。

最近，文献[11]和文献[12]分别构造了具有低相关特性和大集合容量的p元序列集(r)S ，但未给出序列的线性复杂度。本文中，证明了当参数r选取适当的值时，该序列集中的序列的线性复杂度远大于几类已知的非二元序列集的线性复杂度，并给出了线性复杂度的精确值或下界。

1 基本概念

令GF(pn)表示含有 pn个元素的有限域。设正整数n,m,e满足n me，定义从GF(pn)到GF(pm)的迹函数为：

2 序列集的构造

3 序列的线性复杂度

表1 几类周期为p n－1的p元序列集

从表1可以看出，文献[3-7]中的序列具有最优的相关特性，但线性复杂度很小。文献[8-10]中的序列与本文序列都具有次最优的相关特性，但本文序列具有更大的集合容量和线性复杂度。

4 结 论

本文构造了一类具有大线性复杂度、大集合容量的p元低相关序列集，该序列集突出的优点是同时具有大线性复杂度、大集合容量和p元低相关3个性质，特别是线性复杂度远远大于几类已知p元序列的线性复杂度。将该类序列用于码分多址通信系统，可以提高系统的安全性。

[1] GOLOMB S W, GONG G. Signal designs w ith good correlation: for w ireless communications, cryptography and radar application[M]. Cambridge, U K: Cambridge University Press, 2005.

[2] HELLESETH T. Some results about the crosscorrelation function between two maximal linear sequences[J]. Discrete Math, 1976, 16: 209-232.

[3] JANG J, KIM Y K, NO J S, et al. New fam ily of p-ary sequences w ith optimal correlation property and large linear span[J]. IEEE Trans Inform Theory, 2004, 50(8): 1839-1844.

[4] KUMAR P V, MORENO O. Prime-phase sequences w ith periodic correlation properties better than binary sequences[J]. IEEE Trans Inform Theory, 1991, 37: 603-616.

[5] LIU S C, KOMO J F. Nonbinary kasami sequences over GF(p)[J]. IEEE Trans Inform Theory, 1992, 38: 1049-1412.

[6] MORIUCHI T, IMAMURA K. Balanced nonbinary sequences w ith good periodic correlation properites obtained from modified kumar-moreno sequences[J]. IEEE Trans Inform Theory, 1995, 41: 572-576.

[7] SIDWLNIKOV V M. On mutual correlation of sequences[J].Soviet Math Dokl, 1971, 12(1): 197-201.

[8] SEO E Y, KIM Y S, NO J S, et al. Cross-correlation distribution of p-ary m-sequence and its p+1 decimated sequences w ith shorter period[J]. IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, 2007, E90-A(11): 2568-2574.

[9] TANG X H, UDAYA P, FAN P Z. A new fam ily of nonbinary sequences w ith three-level correlation property and large linear span[J]. IEEE Trans Inform Theory, 2005,51(8): 2906-2914.

[10] TRACHTENBERG H M. On the crosscorrelation functions of maximal linear recurring sequences[D]. Los Angeles: Univ of South Calif, 1970.

[11] ZENG F X. Two classes of large fam iles of sequences w ith low correlation[C]//Proceedings of IWSD A’07. Chengdu:IEEE Press, 2007: 56-60.

[12] GOLOMB S W, GONG G. Signal designs w ith good correlation:for w ireless communications,cryptography and radar application[M]. Cambridge, U K: Cambridge University Press, 2005.

[13] ZENG F X. New sequences w ith low correlation and large fam ily size[J]. IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences,2008, E91-A(9): 2615-2621.

[14] LIDL R, NIEDERREITER H. Introduction to finite fields and their applications[M]. Cambridge: ambridge University Press, 1994.

[15] KLAPPER A. d-form sequences: fam ilies of sequences w ith low correlation values and large linear spans[J]. IEEE Trans Inform Theory, 1995, 41(2): 423-431.

[16] KEY E L. An analysis of the structure and complexity of nonlinear binary sequence generators[J]. IEEE Trans Inform Theory, 1976, 22(6): 732-736.

编 辑 张 俊