相控序列的快速生成算法与实现及Gold序列搜索
|
摘要
具有优良相关性，大线性复杂度，平衡性，长周期的伪随机
序列广泛应用于CDMA系统，扩跳频通信系统。相控序列是一
种新的性能优越的伪随机序列。长为（2~n-1）~2的相控序列线性复杂
度不小于n（2~n-1），互相关和异相自相关为五值｛1，1±2~n，1±2~(n+1)｝，
一族序列有（2~n-1）个，且每个序列都是平衡的。
生成相控序列的关键是生成GMW序列。通过预置本原元向
量表达的初始值，不断的进行向量循环移位来生成有限域中的元
素。生成有限域中所有元素后，即可按迹函数计算出GMW序列。
生成GMW序列后便可生成与相控序列相伴的交织序列。将长为
（2~n-1）~2的与相控序列相伴的交织序列排成（2~n-1）行（2~n-1）列，用
长为（2~n-1）的GMW序列与相控序列相伴的交织序列每一行模2
相加，即得一个相控序列。改变长为（2~n-1）的GMW序列的初始
相位即得不同的相控序列（这也是相控序列名称的由来），且彼此
移位不等价。我们根据上述算法在赛扬400MHz的计算机上实现
了12秒内生成66960个长为961相控序列。
本文还提出了对相控序列的改进。改进后的相控序列线性复
杂度比改进前相控序列的线性复杂度大几倍，而平衡性，相关性，
每一族的序列数与改进前相同。
我们用计算机搜索了生成长为31，63，127，511，1023，2047，
8191的Gold序列所需的全部m序列优选对，计算所得数目比其
它文献给出的数目多。
Pseudo-random sequences with optimal properties such as correlation, high linear spans, balance and long period are widely used in CDMA system, spread spectrum and hopping communication systems. Phase-Controlled (PC) sequence is a new kind of sequence with perfect properties. The PC sequences with period of (2n~1)2 have linear spans no less than n(2~?), five cross-correlation and out-of phase auto-correlation values of { 1,1 ?~, 1 ?n+1 },number of (2敆l) sequences in one family and exact balance for each sequence.
Generating GMW sequences is the key to generate PC sequences. By initiating the values of vector description for a primitive element, all finite field elements could be generated by continue cyclic shifting, GMW sequences then could be generated by trace function calculation. And interleaved sequences can be generated after the GMW sequences generated. By rearranging the interleaved sequence with length of (2n~l)2 as an array of (2~?) rows and (2~?) columns and adding GMW sequence with period of (2~?) to each row of the array, a PC sequence could be constructed. Other PC sequences could be constructed by changing the phase of the GMW sequence, this is the name of phase-controlled sequence comes from, and all these PC sequences are not shift equivalent. 66960 PC sequences have been generated by personal computer with CPU of Celeron 400 MHz in less than 12 seconds.
The PC sequences are improved in this paper. The linear span of the improved PC sequences is a few times as large as the unimproved by computer simulation verifying and the other properties, such as the balance, the correlation and the number counts in one family, are as same as the unimproved.
Also we have searched Gold sequences with different periods of 31,63,127,511,1023,2047,8191 .The number of Gold codes searched is more than that of some other references [12] [22] presented.
序列广泛应用于CDMA系统，扩跳频通信系统。相控序列是一
种新的性能优越的伪随机序列。长为（2~n-1）~2的相控序列线性复杂
度不小于n（2~n-1），互相关和异相自相关为五值｛1，1±2~n，1±2~(n+1)｝，
一族序列有（2~n-1）个，且每个序列都是平衡的。
生成相控序列的关键是生成GMW序列。通过预置本原元向
量表达的初始值，不断的进行向量循环移位来生成有限域中的元
素。生成有限域中所有元素后，即可按迹函数计算出GMW序列。
生成GMW序列后便可生成与相控序列相伴的交织序列。将长为
（2~n-1）~2的与相控序列相伴的交织序列排成（2~n-1）行（2~n-1）列，用
长为（2~n-1）的GMW序列与相控序列相伴的交织序列每一行模2
相加，即得一个相控序列。改变长为（2~n-1）的GMW序列的初始
相位即得不同的相控序列（这也是相控序列名称的由来），且彼此
移位不等价。我们根据上述算法在赛扬400MHz的计算机上实现
了12秒内生成66960个长为961相控序列。
本文还提出了对相控序列的改进。改进后的相控序列线性复
杂度比改进前相控序列的线性复杂度大几倍，而平衡性，相关性，
每一族的序列数与改进前相同。
我们用计算机搜索了生成长为31，63，127，511，1023，2047，
8191的Gold序列所需的全部m序列优选对，计算所得数目比其
它文献给出的数目多。
Pseudo-random sequences with optimal properties such as correlation, high linear spans, balance and long period are widely used in CDMA system, spread spectrum and hopping communication systems. Phase-Controlled (PC) sequence is a new kind of sequence with perfect properties. The PC sequences with period of (2n~1)2 have linear spans no less than n(2~?), five cross-correlation and out-of phase auto-correlation values of { 1,1 ?~, 1 ?n+1 },number of (2敆l) sequences in one family and exact balance for each sequence.
Generating GMW sequences is the key to generate PC sequences. By initiating the values of vector description for a primitive element, all finite field elements could be generated by continue cyclic shifting, GMW sequences then could be generated by trace function calculation. And interleaved sequences can be generated after the GMW sequences generated. By rearranging the interleaved sequence with length of (2n~l)2 as an array of (2~?) rows and (2~?) columns and adding GMW sequence with period of (2~?) to each row of the array, a PC sequence could be constructed. Other PC sequences could be constructed by changing the phase of the GMW sequence, this is the name of phase-controlled sequence comes from, and all these PC sequences are not shift equivalent. 66960 PC sequences have been generated by personal computer with CPU of Celeron 400 MHz in less than 12 seconds.
The PC sequences are improved in this paper. The linear span of the improved PC sequences is a few times as large as the unimproved by computer simulation verifying and the other properties, such as the balance, the correlation and the number counts in one family, are as same as the unimproved.
Also we have searched Gold sequences with different periods of 31,63,127,511,1023,2047,8191 .The number of Gold codes searched is more than that of some other references [12] [22] presented.
引文
1． Gong Guang, Theory and Application of q-ary Interleaved Sequences.IEEE IT-41,1995(2) .
2． 万哲先等，非线性移位寄存器。北京：科学出版社，1978
3． 肖国镇等，伪随机序列及其应用。北京：国防工业出版社，1985
4． Gold R.,Optimal binary sequences for spread spectrum multiplexing.IEEE Trans on IT.1967,13: 619-621
5． Scholtz,R A et al., GMW sequence. IEEE Trans on IT,1984,IT-30(3) : 548-553
6． Klapper A,et al ., Cascated GMW sequences. IEEE Trans on IT ,1993,39: 177-183
7． Kasami T.Weight, Distribution of Bose-Chaudhuri-Hocquenghen Code, In Combinational Mathematical and Its Applications,Chapel Hill,NC: Univ of North Carolina Press,1969
8． Olsen J D,et al , Bent-function sequences. IEEE Trans on IT , 1982,28:858-864
9． NO J S ,et al, A new faminy of binary pseudorandom sequences having optimal periodic correlation properity and large linear span.IEEE Trans on IT, 1989,35: 371-379
10． Richard A. GAMES, Crosscorelation of m-sequences and GMW-sequences with the same primitive polynomial, Discrete Applied Mathematics 12 (1985) , 139-146
11． 朱近康，非线性扩频序列，通信学报，1993，NO14，56-67
12． 朱近康，扩展频谱通信及应用，中国科技大学出版社，1993
13． R.A. Games.An algebraic construction of sonar sequence using M sequence, SIAM J.Alg. Disc.Math.,Vol 8,no.4,pp.753-761, Oct. 1987
14． 王新梅消国镇 纠错码--原理与方法西安电子科技大学 出版社1996
15． 查光明，扩频通信，西安电子科技大学出版社，1992
16． 杨义先，最佳信号理论与设计，人民邮电出版社，1996
17． 周亮，通信抗干扰的一些新形式，现代军事通信，1999，Vol．7
No．3，32-33
18． 杨义先，密钥设计的迹函数方法，电子学报，1995，Vol．21 No．4，12
19． 李世鹏，朱近康，一类新的性能优越的伪随机序列，电子学报， 1993，Vol．14，No．1
20． Klapper A,et al. Cascated GMW sequences. IEEE Trans, 1993,IT-39(1) : 177-183．
21． 康凯，伪随机序列设计的迹函数方法和交错方法的研究，电子 科大学位论文，1999
22． 杨留清，张闽申，徐菊英，数字移动通信系统，人民邮电出 版社，1998
23． 胡健栋，郑朝晖，龙必起，李兴明，码分多址与个人通信，1996
24． Jong-Seon No., Generalization of GMW Sequences and No Sequences. IEEE, IT-42,1996,1
25． Xiang. Q.,. On Balanced Binary Sequences with Two Level Auto Correlation Functions. IEEE IT-44,1998, 11
26． 查光明，潘孟涵，m序列优选对的计算机实现及平衡戈尔德码 组，1985，电子科大学报增刊二，34-45
27． 朱近康，杨干宁，用迹函数构造曲面序列，电子学报，Vol 16， No2． 1988
28． 万哲先，代数与编码，科学出版社，1979年
29． 钟义信，伪噪声编码通信，人民邮电出版社，1979年3月
30． 林可祥等编著，伪随机码的原理与应用，人民邮电出版社，1978 年12月
31． Jovan. Dj. golic, Periods of interleaved and nonuniformly decimated sequences, IEEE Trans. Inform. Theory, 1998,44(3) : 1257
32． Gong, G, Porto, A. Di, Wolfowicz, W., Galois linear group sequences, LA Comunicazione, Note Recensioni Notizie, 1993． XLII, 83
2． 万哲先等，非线性移位寄存器。北京：科学出版社，1978
3． 肖国镇等，伪随机序列及其应用。北京：国防工业出版社，1985
4． Gold R.,Optimal binary sequences for spread spectrum multiplexing.IEEE Trans on IT.1967,13: 619-621
5． Scholtz,R A et al., GMW sequence. IEEE Trans on IT,1984,IT-30(3) : 548-553
6． Klapper A,et al ., Cascated GMW sequences. IEEE Trans on IT ,1993,39: 177-183
7． Kasami T.Weight, Distribution of Bose-Chaudhuri-Hocquenghen Code, In Combinational Mathematical and Its Applications,Chapel Hill,NC: Univ of North Carolina Press,1969
8． Olsen J D,et al , Bent-function sequences. IEEE Trans on IT , 1982,28:858-864
9． NO J S ,et al, A new faminy of binary pseudorandom sequences having optimal periodic correlation properity and large linear span.IEEE Trans on IT, 1989,35: 371-379
10． Richard A. GAMES, Crosscorelation of m-sequences and GMW-sequences with the same primitive polynomial, Discrete Applied Mathematics 12 (1985) , 139-146
11． 朱近康，非线性扩频序列，通信学报，1993，NO14，56-67
12． 朱近康，扩展频谱通信及应用，中国科技大学出版社，1993
13． R.A. Games.An algebraic construction of sonar sequence using M sequence, SIAM J.Alg. Disc.Math.,Vol 8,no.4,pp.753-761, Oct. 1987
14． 王新梅消国镇 纠错码--原理与方法西安电子科技大学 出版社1996
15． 查光明，扩频通信，西安电子科技大学出版社，1992
16． 杨义先，最佳信号理论与设计，人民邮电出版社，1996
17． 周亮，通信抗干扰的一些新形式，现代军事通信，1999，Vol．7
No．3，32-33
18． 杨义先，密钥设计的迹函数方法，电子学报，1995，Vol．21 No．4，12
19． 李世鹏，朱近康，一类新的性能优越的伪随机序列，电子学报， 1993，Vol．14，No．1
20． Klapper A,et al. Cascated GMW sequences. IEEE Trans, 1993,IT-39(1) : 177-183．
21． 康凯，伪随机序列设计的迹函数方法和交错方法的研究，电子 科大学位论文，1999
22． 杨留清，张闽申，徐菊英，数字移动通信系统，人民邮电出 版社，1998
23． 胡健栋，郑朝晖，龙必起，李兴明，码分多址与个人通信，1996
24． Jong-Seon No., Generalization of GMW Sequences and No Sequences. IEEE, IT-42,1996,1
25． Xiang. Q.,. On Balanced Binary Sequences with Two Level Auto Correlation Functions. IEEE IT-44,1998, 11
26． 查光明，潘孟涵，m序列优选对的计算机实现及平衡戈尔德码 组，1985，电子科大学报增刊二，34-45
27． 朱近康，杨干宁，用迹函数构造曲面序列，电子学报，Vol 16， No2． 1988
28． 万哲先，代数与编码，科学出版社，1979年
29． 钟义信，伪噪声编码通信，人民邮电出版社，1979年3月
30． 林可祥等编著，伪随机码的原理与应用，人民邮电出版社，1978 年12月
31． Jovan. Dj. golic, Periods of interleaved and nonuniformly decimated sequences, IEEE Trans. Inform. Theory, 1998,44(3) : 1257
32． Gong, G, Porto, A. Di, Wolfowicz, W., Galois linear group sequences, LA Comunicazione, Note Recensioni Notizie, 1993． XLII, 83