一類大集合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.

編 輯 張 俊