一類大集合p元低相關(guān)序列集的線性復(fù)雜度研究

陳 俊，陳 運(yùn)，吳 震

(1. 西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 成都 610031; 2. 成都信息工程學(xué)院信息安全研究所 成都 610225)

具有大線性復(fù)雜、大集合容量(family size)和低相關(guān)特性的偽隨機(jī)序列被廣泛應(yīng)用于碼分多址通信系統(tǒng)[1]。在碼分多址通信系統(tǒng)中，序列之間較低的相關(guān)特性可以降低來自同一信道其他用戶的干擾；較多的序列數(shù)目可以增加系統(tǒng)的容量；而較大的線性復(fù)雜度可以抵抗基于Berlekamp-Massey算法進(jìn)行的攻擊，從而提高系統(tǒng)的安全性。因此，構(gòu)造同時(shí)具有低相關(guān)性特、大線性復(fù)雜和大集合容量的偽隨機(jī)序列集成為一個(gè)重要的研究課題。

人們已經(jīng)構(gòu)造出許多具有低相關(guān)特性的p(p是奇素?cái)?shù))元序列集，如文獻(xiàn)[2-10]中的序列集，但這些序列的線性復(fù)雜度都很低。

最近，文獻(xiàn)[11]和文獻(xiàn)[12]分別構(gòu)造了具有低相關(guān)特性和大集合容量的p元序列集(r)S ，但未給出序列的線性復(fù)雜度。本文中，證明了當(dāng)參數(shù)r選取適當(dāng)?shù)闹禃r(shí)，該序列集中的序列的線性復(fù)雜度遠(yuǎn)大于幾類已知的非二元序列集的線性復(fù)雜度，并給出了線性復(fù)雜度的精確值或下界。

1 基本概念

令GF(pn)表示含有 pn個(gè)元素的有限域。設(shè)正整數(shù)n,m,e滿足n me，定義從GF(pn)到GF(pm)的跡函數(shù)為：

2 序列集的構(gòu)造

3 序列的線性復(fù)雜度

表1 幾類周期為p n－1的p元序列集

從表1可以看出，文獻(xiàn)[3-7]中的序列具有最優(yōu)的相關(guān)特性，但線性復(fù)雜度很小。文獻(xiàn)[8-10]中的序列與本文序列都具有次最優(yōu)的相關(guān)特性，但本文序列具有更大的集合容量和線性復(fù)雜度。

4 結(jié) 論

本文構(gòu)造了一類具有大線性復(fù)雜度、大集合容量的p元低相關(guān)序列集，該序列集突出的優(yōu)點(diǎn)是同時(shí)具有大線性復(fù)雜度、大集合容量和p元低相關(guān)3個(gè)性質(zhì)，特別是線性復(fù)雜度遠(yuǎn)遠(yuǎn)大于幾類已知p元序列的線性復(fù)雜度。將該類序列用于碼分多址通信系統(tǒng)，可以提高系統(tǒng)的安全性。

[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.

編 輯 張 俊