GMW序列和WG序列及WG序列间的互相关特性.doc

第28卷第7期通信学报Vol.28 No.72007年7月Journal on CommunicationsJuly 2007GMW序列和WG序列及WG序列间的互相关特性佟鑫，温巧燕(北京邮电大学 理学院，北京 100876) 摘要：对于奇数n，研究了Gordon-Mills-Welch (GMW) 序列与Welch-Gong (WG) 序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数。研究表明：GMW序列与WG序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数最终均与m-序列与其采样序列间的互相关函数相关；并且在一定条件下，WG序列间的互相关函数可为3-值或5-值的。另外，给出了GMW序列与WG序列间互相关函数的最大峰值。关键词：理想自相关序列；Gordon-Mills-Welch序列；Welch-Gong序列；采样；互相关函数中图分类号：TN918.1文献标识码：A文章编号：1000-436X（2007）07-0118-05Cross-correlation properties between GMW and WG sequencesand that of WG sequencesTONG Xin, WEN Qiao-yan(Science School, Beijing University of Posts and Telecommunications, Beijing 100876,China)Abstract：For odd n, the cross-correlations between Gordon-Mills-Welch (GMW) sequences and Welch-Gong (WG) sequences (decimated WG sequences with one particular exponent) and that of WG sequences were investigated. It shows that the calculations of the cross-correlation between GMW sequences and WG sequences (decimated WG sequences with one particular exponent) and that of WG sequences were all related to the cross-correlation of m-sequences and their decimations. Moreover, the cross-correlation of WG sequences can be 3-valued or 5-valued under a certain condition. Furthermore, the maximum magnitude of the cross-correlation between GMW sequences and WG sequences were given.Key words：ideal autocorrelation sequences; Gordon-Mills-Welch sequences; Welch-Gong sequences; decimation; cross-correlation25第7期佟鑫等：GMW序列和WG序列及WG序列间的互相关特性1231引言收稿日期：2007-01-10；修回日期：2007-05-20基金项目：国家自然科学基金资助项目（60373059）；国家高技术研究发展计划(“863”计划)基金资助项目(2006AA01Z419)；国家自然科学基金重大研究计划基金资助项目（90604023）；教育部高等学校博士点基金资助项目（20040013007）Foundation Items: The National Natural Science Foundation of China(6037059); The National High Technology Research and Development Program of China (“863”Program) (2006AA01Z419); The Major Research Plan of the National Natural Science Foundation of China (90604023); The National Research Foundation for the Doctoral Program of Higher Education of China (20040013007)具有良好自相关函数和互相关函数的序列在码分多址（CDMA）、数字水印、序列密码和宽带卫星通信中都有广泛的应用。在CDMA通信中，具有良好相关性的扩频序列可以抵抗系统中的主要干扰用户间的多址干扰（MAI）。另一方面，具有良好相关特性的序列作为密钥流生成器应用于序列密码中，可以抵抗互相关攻击。二元理想自相关序列是自相关函数为2-值且在非零延迟取值为的序列，其自相关函数达到了近似完美状态。近年来，对于理想自相关序列的研究引起了国内外许多学者的广泛关注，相继设计出许多周期为的二元理想自相关序列。例如：m-序列，Gordon-Mills- Welch (GMW)序列1，Welch-Gong (WG)序列2，Dillon- Dobbertin（DD）序列3，以及hyperoval序列4等，这些序列在扩频通信和密码学领域中都有广泛的应用。对于奇数n，人们已研究了由同一本原多项式生成的m-序列和GMW序列间的互相关函数5，2个GMW序列间的互相关函数6，m-序列和DD序列间的互相关函数3，m-序列与WG或与其某一采样序列间的互相关函数7,8。最近，Hertel在文献9中研究了2个DD序列间的互相关函数，并提出了任意2个理想自相关序列间的互相关函数最大峰值下界的猜测。随后，她又在文献10中研究了GMW序列和DD序列间的互相关函数。本文首先研究了GMW序列与WG序列间的互相关函数以及GMW序列与WG某一采样序列间的互相关函数，并给出了GMW序列与WG序列间互相关函数的最大峰值。其次，本文分析了WG序列间的互相关函数。经研究，GMW序列与WG序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数最终均与m-序列与其采样序列间的互相关函数相关；并且在一定条件下，WG序列间的互相关函数可为3-值或5-值的。2基本概念设是含有个元素的有限域，表示从到的迹函数，即。定义1周期为2n-1的2个二元序列a=ai和b=bi间的互相关函数定义为，当a=b时，称函数为序列a的自相关函数。定义2若周期为的二元序列a的自相关函数满足称序列a是理想自相关序列。设是中的本原元，从到的函数与上周期为的二元序列a=是一一对应的，只需令，。因此，在本文中函数与上周期为的二元序列的概念可以相互转化。相应地，也可定义2个函数间的互相关函数。定义3函数和间的互相关函数定义为 , 当=时，称函数为函数的自相关函数。定义4若函数的自相关函数满足称函数是理想自相关函数。设函数为从到的函数，记在y点处的Walsh谱为, 定义5设序列a=ai和b=bi，若, ，则称序列b是序列a的s-采样，记为a(s)。若序列a与函数对应，则序列a(s)与函数对应，简记为。3GMW序列和Welch-Gong序列的互相关函数对于奇数n，本节分别讨论了2个理想自相关序列GMW序列与WG序列间的互相关函数以及GMW序列与WG某一采样序列间的互相关函数。定义6设, WG函数定义为，其中，定义7设,GMW函数定义为引理19设,和是到的函数，且是理想自相关函数，则 (1)特别地，当时，得到广义Parseval等式9引理27设奇数,则m-序列与WG序列间互相关函数为，(2)引理31 设，则m-序列与GMW序列间互相关函数为：定理1设奇数, ,，则有进一步，如果存在i，使得 ，则 证明由引理1、引理2和引理3知如果存在i，使得，则有 (3)式(3)中，因故有= 证毕。注1 由定理1，GMW序列与WG序列间的互相关函数与m-序列与GMW序列间的互相关函数相关，再由引理3，GMW序列与WG序列间的互相关函数最终可转化为m-序列与其采样序列间的互相关函数。定义8设,，若 ，则称幂函数在上是最大非线性的。定理210设为奇数，正整数d和e使得幂函数和分别在和上是最大非线性的，则推论1设奇数, ,。如果存在i，使得，则 证明令，经定理1得因另外，因，其中,，z满足 故有 ，再经引理3并由Gold序列的Walsh谱的分布可得最后，由定理2知推论1成立。 证毕。注2 Hertel在文献9中由计算机的计算结果提出了任意2个理想自相关函数和间的互相关函数最大峰值的下界的猜测： ? 由推论1易见，当m取值较小时，GMW序列与WG序列间互相关函数的最大峰值是较理想的，可以应用于CDMA通信和密码学领域中。下面研究GMW序列与WG的某一采样序列间的互相关函数引理49设和是到的函数，,，则有 (4)引理58设奇数,，则m-序列与WG采样序列间互相关函数为，(5)定理3设奇数, ,特别地，若且存在i使得 ，则有证明由引理1和引理4，当 时，再经引理2和引理5与定理1的证明方法类似可得 注3 由定理3和引理3，当采样因子且满足存在i使得时，GMW序列与WG 的s-采样序列间的互相关函数最终也可约化为m-序列与其采样序列间的互相关函数。推论2n, d, k, s同定理3，则证明因Kasami幂指数, ，故是三值的，即 ，且 。又因= 则幂函数在上是最大非线性的，经定理2可得推论2的结论。证毕。4Welch-Gong序列之间的互相关函数引理68设n为奇数，整数，。令，。若对取值为如下3种情形之一：；，则 ,为5-值的。定理4设n为奇数，WG序列间的互相关函数为进而，时，WG序列间的互相关函数是3-值的，即；而当取值为引理6中3种情形之一时，WG序列间的互相关函数是5-值的，即, 证明易见，当时，WG序列间的互相关函数是3-值的；而当取值为引理6中3种情形之一时，经引理6，WG序列间的互相关函数是5-值的, 。综上，可知定理结论成立。 证毕。5结束语对于奇数n，本文研究了GMW序列与WG序列（及WG某一采样序列）间的互相关函数以及WG序列间的互相关函数。与文献10得到的结论类似，GMW序列与WG序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数最终均与m-序列与其采样序列间的互相关函数相关。并且在一定条件下，WG序列间的互相关函数可为3-值或5-值的。另外，本文还给出了GMW序列与WG序列间互相关函数的最大峰值，可见当n具有较小因子时，其互相关函数的最大峰值也较小，适合应用于CDMA通信和密码学领域中。参考文献：1GORDON B, MILLS W H, WELCH L R. Some new difference sets J. Canadian Journal of Mathematics, 1962, 14: 614625.2NO J S, GOLOMB S W, GONG G, et al. Binary pseudorandom sequences of period 2m1 with ideal autocorrelation J. IEEE Trans Inform Theory, 1998, 44 (2): 814-817.3DILLON J F, DOBBERTIN H. New cyclic difference sets with singer parameters J. Finite Fields Applications, 2004, 10(3):342-389.4MASCHIETTI A. Difference sets and hyperovals J. Designs Codes and Cryptography, 1998, 14: 89-98.5GAMES R A. Crosscorrelation of m-sequences and GMW-sequences with the same primitive polynomial J. Discrete Applied Mathematics, 1985, 12: 139-146.6ANTWEILER M. Cross-correlation of p-ary GMW sequences J. IEEE Trans Inform Theory, 1994, 40: 1253-1261.7GONG G, GOMLOMB S W. The decimation-Hadamard transform of two-level autocorrelation sequences J. IEEE Trans Inf Theory, 2002, 48(2): 853-865.8YU Y N, GONG G. Crosscorrelation propertie