具有最优自相关值四元序列的构造

衡子灵, 岳 勤

(南京航空航天大学 理学院,江苏 南京 211100)

周期伪随机序列在信息安全领域中有着广泛的应用,如扩频通信系统、流密码学等．大量文献研究了序列的编码和密码性质,如序列的迹表示[1]、具有较大线性复杂度序列的构造[2]、分圆序列自相关值的计算[3]、具有最优自相关值序列的构造[4-5]等．本文主要研究序列的构造．序列的构造方法有很多,如用分圆的方法构造分圆序列[6]以及通过差集[4]和差族[7]构造序列．本文的构造主要基于Gray映射和组合理论．

信号在输送时,被编制成一串脉冲信号,需要把特定的位置与其他位置明显地分开来,数学上使用具有良好自相关性能的周期序列来实现,如完备二元序列．任给一个周期为正奇数p且具有最优自相关值的二元序列,本文构造出了周期为N=2np(n任意)的四元序列,其自相关值为3值．特别地，当n=1时,构造出的四元序列具有最优的自相关值和平衡特性,而且我们的构造方法和文献[8]不同．此外,本文还构造出了新的四元序列族,且关于Welch界几乎最优．

1 序列的相关值

对于正整数q和N,令{g(t)}是周期为N的q元序列，定义{g(t)}的自相关值函数为

令Ak={t|g(t)=k,0≤t

我们知道,具有最优自相关值的周期为奇数N的二元序列的自相关值分布为

此外,具有最优自相关值的周期为偶数N的四元序列的自相关值分布为

或

已知Ωs={{si(t)}|0≤i

Cs,max=max{|Rsi,sj(τ)|{si(t)},{sj(t)}∈Ω,0≤τ

规定当i=j时,τ≠0.Welch给出了Cs,max的一个下界[9],即

2 Gray映射

已知p为任意正奇数,n为任意正整数,且gcd(2n,p)=1．由中国剩余定理知,有环同构

此外,对于加群Z2n有陪集分解，Z2n=2Z2n∪(1+2Z2n).

令φ:Z2×Z2→Z4为Gray映射的逆,即

由于具有最优自相关值的二元序列都有平衡特性,从而

或

(1)

已知{a(t)}和{b(t)}都是周期为N的二元序列,那么可以构造周期为N的四元序列{q(t)},其中q(t)=φ[a(t),b(t)],t=0,…,N-1.对于两个周期相同的四元序列,它们的互相关值有如下关系.

引理1[10]令{a(t)},{b(t)},{c(t)},{d(t)}都是周期为N的二元序列．定义四元序列{u(t)}和{v(t)},其中u(t)=φ[a(t),b(t)],v(t)=φ[c(t),d(t)],对任意的t=0,…,N-1成立．那么u和v的互相关值为

其中Ra,c(τ),Rb,d(τ)分别表示{a(t)},{b(t)}的互相关值和{c(t)},{d(t)}的互相关值．

3 四元序列的构造

定理1令{s(t)}是一个周期为奇数p的二元序列,且具有最优的自相关值,D是{s(t)}的一个特征集．对于任意正整数n且gcd(2n,p)=1,定义两个周期为N=2np的二元序列{a(t)},{b(t)},其中

由此定义周期为N=2np的四元序列{q(t)},其中q(t)=φ[a(t),b(t)],t=0,1,…,2np-1.那么四元序列{q(t)}的自相关值为3值,其自相关值分布如下:

(2)

证对于τ=0,显然Rq(τ)=2np.根据引理1,

因此,需要分别计算出Ra(τ),Rb(τ),Ra,b(τ),和Rb,a(τ).

根据定义,可设

a(t)=s(t′),t′≡t(modp),t=0,1,…,2np-1.

从而可以得出

令t=(t0,t1)和τ=(τ0,τ1)其中t0,τ0∈Z2n,t1,τ1∈Zp.根据b(t)的定义得

当t0∈2Z2n时,b(t)=s(t1),t1≡t(modp)；当t0∈(1+2Z2n)时,b(t)=1-s(t1),t1≡t(modp).

那么{b(t)}的自相关值函数为

若τ0∈2Z2n,则

若τ0∈(1+2Z2n),则

因此

同样,{a(t)}和{b(t)}的自相关值函数为

当τ0∈2Z2n时,

=nRs(τ1)-nRs(τ1)=0.

当τ0∈(1+2Z2n)时,

同理得出Rb,a(τ)=0.

综上,可得(2)式.定理1证毕．

定理2令定理1中n=1,则周期为N=2p的四元序列{q(t)}具有最优的自相关值和平衡特性,其自相关值Rq(τ)及{q(t)}分布分别为

或

证只证明{q(t)}的分布情况,根据定义,再根据(1),容易得出q(t)的分布．

在定理2中,{s(t)}可以取任意周期为奇数的具有最优自相关值的二元序列,从而可以构造出很多具有最优自相关值的四元序列．下面给出一个具体的例子．

例1令{s(t)}是一个周期为63的二元m序列,从而{s(t)}具有最优的自相关值,其中

{s(t)}={000001000011000101001111010001110010010110111011001101010111111}，

因此，根据定理2可得出

{a(t)}={0000010000110001010011110100011100100101101110110011010101111110000010000110001

01001111010001110010010110111011001101010111111},

{b(t)}={0101000101100100000110100001001001110000111011100110000000101011010111010011011

11100101111011011000111100010001100111111101010}.

根据定理1,q(t)=φ[a(t),b(t)],可以得出

{q(t)}={0101030101230103030123230301032301210303212321230123030303232321010121010321012

12103232121012321030121230323032103212121232323}.

其自相关值Rq(τ)及{q(t)}分布分别为

4 四元序列族的构造

令Ωs={{si(t)}|0≤i

由此构造四元序列族Ωq={{qi(t)}|0≤i

为了估计出Cq,max,需要下面的引理,其证明与定理1相仿．

定理3对二元序列族Ωs={{si(t)}|0≤i

Ωa={{ai(t)}|0≤i

{si(t)},{ai(t)},{bi(t)}定义如上,则Cq,max≤2Cs,max.

根据ai(t)的定义,容易得出

Rai,aj(τ)=2Rsi,sj(τ).

令t=(t0,t1),τ=(τ0,τ1),其中t0,τ0∈Z2，t1,τ1∈Zp.当τ0=0时,

当τ0=1时,可以类似得到Rbi,bj(τ)=-Rai,aj(τ).

从而

本文给出了四元序列的一个构造,构造出的四元序列具有最优的自相关值．此外,构造出了关于Welch界几乎最优的四元序列族．下一步尝试用四元序列构造出相关性较好的二元序列．

参考文献:

[1] No J S,Lee H K,Chung H,et al.Trace representation of Legendre sequences of Mersenne prime period[J].IEEE Trans Inf Theory,1996,42(6):2254.

[2] Hu Liqin,Yue Qin,Wang Minghong.The linear complexity of Whiteman’s generalized cyclotomic sequences of periodpm+1qn+1[J].IEEE Tran Inf Theory,2012,58(8):5534.

[3] Hu Liqin,Yue Qin.Autocorrelation value of Whiteman generalized cyclotomic sequence[J].J Math Res Appl,2012,32(4):415.

[4] Tang Xiaohu,Ding Cunsheng.New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value[J].IEEE Trans Inf Theory,2010,56(12):6398.

[5] Zeng Fanxin,Zeng Xiaoping,Zeng Xiangyong,et al.Several types of sequences with optimal autocorrelation properties[J].IEICE Trans Fundamentals,2013,E96-A(1):367.

[6] 曹静,岳勤.GF(3)上一类几乎平衡的6阶分圆序列[J].徐州师范大学学报:自然科学版,2011,29(3):9.

[7] 衡子灵,岳勤.新的差族和几乎差族的构造[J].江苏师范大学学报:自然科学版,2013,31(2):9.

[8] Lim T,No J.New construction of quaternary sequences with good correlation using binary sequences with good correlation[J].IEICE Trans Fundamentals,2011,E94-A(8):1701.

[9] Helleseth T,Kumar P V.Handbook of coding theory[M].Amsterdam,The Netherlands:Elsevier,1998:1765.

[10] Krone S M,Sarwate D V.Quadriphase sequences for spread spectrum multiple-access communiction[J].IEEE Trans Inf Theory,1984,IT-30(3):520.

[11] Kim Y S,Jang J W,Kim S H,et al.New families ofM-ary sequences with low correlation constructed from Sidel’nikov sequences[J].IEEE Trans Inf Theory,2008,54(8):137.