具有最優(yōu)自相關(guān)值四元序列的構(gòu)造

衡子靈, 岳 勤

(南京航空航天大學(xué) 理學(xué)院,江蘇 南京 211100)

周期偽隨機(jī)序列在信息安全領(lǐng)域中有著廣泛的應(yīng)用,如擴(kuò)頻通信系統(tǒng)、流密碼學(xué)等．大量文獻(xiàn)研究了序列的編碼和密碼性質(zhì),如序列的跡表示[1]、具有較大線性復(fù)雜度序列的構(gòu)造[2]、分圓序列自相關(guān)值的計(jì)算[3]、具有最優(yōu)自相關(guān)值序列的構(gòu)造[4-5]等．本文主要研究序列的構(gòu)造．序列的構(gòu)造方法有很多,如用分圓的方法構(gòu)造分圓序列[6]以及通過差集[4]和差族[7]構(gòu)造序列．本文的構(gòu)造主要基于Gray映射和組合理論．

信號在輸送時(shí),被編制成一串脈沖信號,需要把特定的位置與其他位置明顯地分開來,數(shù)學(xué)上使用具有良好自相關(guān)性能的周期序列來實(shí)現(xiàn),如完備二元序列．任給一個(gè)周期為正奇數(shù)p且具有最優(yōu)自相關(guān)值的二元序列,本文構(gòu)造出了周期為N=2np(n任意)的四元序列,其自相關(guān)值為3值．特別地，當(dāng)n=1時(shí),構(gòu)造出的四元序列具有最優(yōu)的自相關(guān)值和平衡特性,而且我們的構(gòu)造方法和文獻(xiàn)[8]不同．此外,本文還構(gòu)造出了新的四元序列族,且關(guān)于Welch界幾乎最優(yōu)．

1 序列的相關(guān)值

對于正整數(shù)q和N,令{g(t)}是周期為N的q元序列，定義{g(t)}的自相關(guān)值函數(shù)為

令A(yù)k={t|g(t)=k,0≤t

我們知道,具有最優(yōu)自相關(guān)值的周期為奇數(shù)N的二元序列的自相關(guān)值分布為

此外,具有最優(yōu)自相關(guān)值的周期為偶數(shù)N的四元序列的自相關(guān)值分布為

或

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

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

規(guī)定當(dāng)i=j時(shí),τ≠0.Welch給出了Cs,max的一個(gè)下界[9],即

2 Gray映射

已知p為任意正奇數(shù),n為任意正整數(shù),且gcd(2n,p)=1．由中國剩余定理知,有環(huán)同構(gòu)

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

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

由于具有最優(yōu)自相關(guān)值的二元序列都有平衡特性,從而

或

(1)

已知{a(t)}和{b(t)}都是周期為N的二元序列,那么可以構(gòu)造周期為N的四元序列{q(t)},其中q(t)=φ[a(t),b(t)],t=0,…,N-1.對于兩個(gè)周期相同的四元序列,它們的互相關(guān)值有如下關(guān)系.

引理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的互相關(guān)值為

其中Ra,c(τ),Rb,d(τ)分別表示{a(t)},{b(t)}的互相關(guān)值和{c(t)},{d(t)}的互相關(guān)值．

3 四元序列的構(gòu)造

定理1令{s(t)}是一個(gè)周期為奇數(shù)p的二元序列,且具有最優(yōu)的自相關(guān)值,D是{s(t)}的一個(gè)特征集．對于任意正整數(shù)n且gcd(2n,p)=1,定義兩個(gè)周期為N=2np的二元序列{a(t)},{b(t)},其中

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

(2)

證對于τ=0,顯然Rq(τ)=2np.根據(jù)引理1,

因此,需要分別計(jì)算出Ra(τ),Rb(τ),Ra,b(τ),和Rb,a(τ).

根據(jù)定義,可設(shè)

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

從而可以得出

令t=(t0,t1)和τ=(τ0,τ1)其中t0,τ0∈Z2n,t1,τ1∈Zp.根據(jù)b(t)的定義得

當(dāng)t0∈2Z2n時(shí),b(t)=s(t1),t1≡t(modp)；當(dāng)t0∈(1+2Z2n)時(shí),b(t)=1-s(t1),t1≡t(modp).

那么{b(t)}的自相關(guān)值函數(shù)為

若τ0∈2Z2n,則

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

因此

同樣,{a(t)}和{b(t)}的自相關(guān)值函數(shù)為

當(dāng)τ0∈2Z2n時(shí),

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

當(dāng)τ0∈(1+2Z2n)時(shí),

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

綜上,可得(2)式.定理1證畢．

定理2令定理1中n=1,則周期為N=2p的四元序列{q(t)}具有最優(yōu)的自相關(guān)值和平衡特性,其自相關(guān)值Rq(τ)及{q(t)}分布分別為

或

證只證明{q(t)}的分布情況,根據(jù)定義,再根據(jù)(1),容易得出q(t)的分布．

在定理2中,{s(t)}可以取任意周期為奇數(shù)的具有最優(yōu)自相關(guān)值的二元序列,從而可以構(gòu)造出很多具有最優(yōu)自相關(guān)值的四元序列．下面給出一個(gè)具體的例子．

例1令{s(t)}是一個(gè)周期為63的二元m序列,從而{s(t)}具有最優(yōu)的自相關(guān)值,其中

{s(t)}={000001000011000101001111010001110010010110111011001101010111111}，

因此，根據(jù)定理2可得出

{a(t)}={0000010000110001010011110100011100100101101110110011010101111110000010000110001

01001111010001110010010110111011001101010111111},

{b(t)}={0101000101100100000110100001001001110000111011100110000000101011010111010011011

11100101111011011000111100010001100111111101010}.

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

{q(t)}={0101030101230103030123230301032301210303212321230123030303232321010121010321012

12103232121012321030121230323032103212121232323}.

其自相關(guān)值Rq(τ)及{q(t)}分布分別為

4 四元序列族的構(gòu)造

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

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

為了估計(jì)出Cq,max,需要下面的引理,其證明與定理1相仿．

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

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

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

根據(jù)ai(t)的定義,容易得出

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

令t=(t0,t1),τ=(τ0,τ1),其中t0,τ0∈Z2，t1,τ1∈Zp.當(dāng)τ0=0時(shí),

當(dāng)τ0=1時(shí),可以類似得到Rbi,bj(τ)=-Rai,aj(τ).

從而

本文給出了四元序列的一個(gè)構(gòu)造,構(gòu)造出的四元序列具有最優(yōu)的自相關(guān)值．此外,構(gòu)造出了關(guān)于Welch界幾乎最優(yōu)的四元序列族．下一步嘗試用四元序列構(gòu)造出相關(guān)性較好的二元序列．

參考文獻(xiàn):

[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].徐州師范大學(xué)學(xué)報(bào):自然科學(xué)版,2011,29(3):9.

[7] 衡子靈,岳勤.新的差族和幾乎差族的構(gòu)造[J].江蘇師范大學(xué)學(xué)報(bào):自然科學(xué)版,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.