低碰撞區(qū)跳頻序列平均部分漢明相關(guān)理論界研究

牛憲華1，曾柏森

(1.西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院， 四川 成都 610039；2. 中國聯(lián)通成都市分公司網(wǎng)絡(luò)優(yōu)化中心， 四川 成都 610036)

跳頻(frequency-hopping, FH)多址擴(kuò)頻系統(tǒng)具有抗干擾、抗截獲、安全和多址接入的性能，并能與頻譜資源共享，在軍事無線電通信、移動通信、現(xiàn)代雷達(dá)和聲納回聲定位系統(tǒng)中有廣泛應(yīng)用[1-3]。對于跳頻通信系統(tǒng)，通常要求發(fā)射機(jī)之間的相互干擾(mutual interference ,MI)盡可能地保持在低水平。當(dāng)多個發(fā)射機(jī)在同一時刻使用相同的頻率發(fā)射信號時，就會產(chǎn)生相互干擾，而跳頻通信系統(tǒng)相互干擾的大小嚴(yán)重依賴于跳頻序列的漢明相關(guān)性；因此，為準(zhǔn)確分析跳頻通信系統(tǒng)的性能，必須仔細(xì)研究跳頻序列的漢明相關(guān)特性。跳頻序列集的漢明相關(guān)值與頻隙個數(shù)、序列長度、序列個數(shù)等參數(shù)有關(guān)，這些參數(shù)受理論界的限制。跳頻序列理論界是跳頻序列集性能優(yōu)異的評價標(biāo)準(zhǔn)，對跳頻序列設(shè)計(jì)具有重要的指導(dǎo)意義。

由于跳頻系統(tǒng)中同步時間的有限性以及硬件的復(fù)雜性，通常跳頻序列相關(guān)窗的長度小于所選序列的周期，而且相關(guān)窗的長度會隨著信道條件的變化而變化；所以部分漢明相關(guān)比全周期漢明相關(guān)能更好地衡量系統(tǒng)的性能[4]。

對于異步跳頻通信系統(tǒng)，希望每個跳頻序列在整個周期內(nèi)沒有碰撞，但是由跳頻序列集漢明相關(guān)函數(shù)的理論界可知，滿足條件的跳頻序列的數(shù)目非常少，不能滿足較多用戶的使用。如果將跳頻序列的漢明相關(guān)值限制在零時延附近的一個小的時延范圍內(nèi)，就能構(gòu)造出較多漢明相關(guān)性能好、序列長度長的跳頻序列。這正是低碰撞區(qū)跳頻序列的基本思想[5]。為方便區(qū)分，本文將考慮全部時延的跳頻序列稱為常規(guī)跳頻序列，把考慮低碰撞區(qū)的跳頻序列稱為低碰撞區(qū)跳頻序列。本文主要研究低碰撞區(qū)跳頻序列集的平均周期部分漢明相關(guān)理論界。

1 定義和理論界

設(shè)F={f1,f2, …,fq}是一個大小為q的頻點(diǎn)集,S是由F上M個長度為N的跳頻序列組成的集合。對于任意的f1，f2∈F，令

對于S中任意2個跳頻序列x=(x0,x1,…,xN1),y=(y0,y1,…,yN1)∈S,x和y在相對時延為τ時的周期漢明相關(guān)函數(shù)Hxy(τ)定義為

(1)

其中，下標(biāo)j+τ按模N運(yùn)算，并且只考慮正時延。

對于一個跳頻序列集S，序列集的最大周期漢明自相關(guān)Ha(S)和最大周期漢明互相關(guān)Hc(S)分別定義為：

(2)

為簡化和方便，令Ha=Ha(S)，Hc=Hc(S)。

早在1974年，A. Lempel 等[3]建立了單個跳頻序列最大周期漢明自相關(guān)的理論界。

引理1(Lempel-Greenberger界) 令F是一個大小為q的頻隙集，對于一個F上長度為N的跳頻序列x，有

(3)

其中，r是N模q的最小非負(fù)剩余。

2004年，D.Y.Peng等[6]推導(dǎo)了跳頻序列集最大周期漢明相關(guān)的理論界。

引理2(Peng-Fan 界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，有：

(N-1)qHa+(M-1)NqHc≥(NM-q)N

(4)

(N-1)MHa+(M-1)NMHc≥2INM-(I+1)Iq

(5)

其中，I=?NM/q」。

可以看出，當(dāng)M=1時，Lempel-Greenberger界是Peng-Fan界的特殊情況。如果跳頻序列集的相關(guān)性滿足Peng-Fan界取等號，稱這個跳頻序列集為最優(yōu)跳頻序列集?，F(xiàn)有序列構(gòu)造結(jié)果中，有很多跳頻序列集[7-10]滿足Peng-Fan界。

平均漢明相關(guān)是衡量跳頻序列集的另一個重要參數(shù)。對于任意跳頻序列集S，序列集的平均周期漢明自相關(guān)Aa(S)和平均周期漢明互相關(guān)Ac(S)分別定義為：

(6)

(7)

為簡化和方便，令A(yù)a=Aa(S)，Ac=Ac(S)。

2008年，D.Y.Peng等[11]推導(dǎo)了跳頻序列集平均周期漢明相關(guān)的理論界。

引理3(Peng-Peng-Tang-Niu 界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，有

q(N-1)Aa+qN(M-1)Ac≥(NM-q)N

(8)

Peng-Peng-Tang-Niu 界首次考慮了跳頻序列的平均漢明相關(guān)性質(zhì)。如果跳頻序列集的平均漢明相關(guān)性滿足Peng-Peng-Tang-Niu界取等號，稱這個跳頻序列集關(guān)于平均漢明相關(guān)的理論界是最優(yōu)的。

對于任意2個跳頻序列x=(x0,x1,…,xN1),y=(y0,y1,…,yN1)∈S，x和y在相對時延為τ、相關(guān)窗起點(diǎn)為j、長度為L時的部分漢明相關(guān)函數(shù)定義為

(9)

當(dāng)x=y時，Hxy(j|L;τ)稱為部分漢明自相關(guān)函數(shù)；當(dāng)x≠y時，則稱為部分漢明互相關(guān)函數(shù)。如果j=0 并且L=N，式(9)表示式(1)中定義的周期漢明相關(guān)函數(shù)。

對于跳頻序列集S，序列集的最大部分漢明自相關(guān)Pa(L)和最大部分漢明互相關(guān)Pc(L)分別定義為：

為簡化和方便，在不引起混淆的情況下，令Pa=Pa(L)，Pc=Pc(L)。

2004年，Y.C. Eun等[4]給出了跳頻序列最大周期部分漢明自相關(guān)的理論界。

引理4(Eun-Jin-Hong-Song界) 令F是一個大小為Q的頻隙集, 對于F上長度為N，相關(guān)窗長度為L的跳頻序列，有

(10)

其中，r是N模q的最小非負(fù)剩余。

可以看出，當(dāng)L=N時，Lempel-Greenberger界是Eun-Jin-Hong-Song界的特殊情況。對于給定的相關(guān)窗長度L(1≤L≤N)，如果序列集S的最大周期部分漢明相關(guān)函數(shù)滿足Eun-Jin-Hong-Song界取等號成立，那么就稱跳頻序列集S關(guān)于最大周期部分漢明相關(guān)函數(shù)的理論界是最優(yōu)的。目前已經(jīng)構(gòu)造出幾類關(guān)于Eun-Jin-Hong-Song界最優(yōu)的跳頻序列集[4,12]。

低碰撞區(qū)跳頻序列是低相關(guān)區(qū)擴(kuò)頻序列在跳頻通信系統(tǒng)中的推廣。低碰撞區(qū)跳頻序列作為一個新的研究方向，近年來引起國內(nèi)外學(xué)者的興趣。

對于任意跳頻序列集S，令整數(shù)HLa≥0，HLc≥0，跳頻序列集S的周期漢明相關(guān)低碰撞區(qū)LHZ、周期漢明自相關(guān)低碰撞區(qū)LAHZ和周期漢明互相關(guān)低碰撞區(qū)LCHZ分別定義為：

LHZ=min{LAHZ,LCHZ}

LAHZ=max{T|Hxx(τ)≤HLa,for0<τ≤T,?x∈S}

LCHZ=max{T|Hxy(τ)≤HLc,for0≤τ≤T,?x,y∈S,x≠y}

當(dāng)HLa=HLc=0時，S的低碰撞區(qū)稱為S的無碰撞區(qū)NHZ。一個具有LHZ≥0或NHZ≥0的跳頻序列集S稱為關(guān)于周期漢明相關(guān)的低碰撞區(qū)跳頻序列集或無碰撞區(qū)跳頻序列集。

2006年，D.Y.Peng等[13]推導(dǎo)了低碰撞區(qū)跳頻序列集周期漢明相關(guān)的理論界。

引理5(Peng-Fan-Lee 界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，LHZ是序列集S關(guān)于周期漢明相關(guān)函數(shù)的低碰撞區(qū)。對于任意整數(shù)Z，0≤Z≤LHZ，有

qZHa+q(M-1)(Z+1)Hc≥(Z+1)NM-Nq

(11)

NMZHa+NM(M-1)(Z+1)Hc≥(Z+1)[(2I+1)NM-(I+1)Iq]-N2M

(12)

其中，I=?NM/q」。

跳頻序列的Peng-Fan 界和Lempel-Greenberger界都是Peng-Fan-Lee 界的特殊情況。關(guān)于Peng-Fan-Lee界最優(yōu)的低碰撞區(qū)跳頻序列集近年來也有許多構(gòu)造結(jié)果[14-17]。

考慮低碰撞區(qū)跳頻序列集的周期部分漢明相關(guān)性質(zhì)，可以得到如下定義。

令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，對于任意給定相關(guān)窗L(L≤N)，令正整數(shù)PLa(L)≥0，PLc(L)≥0，那么跳頻序列集S的周期部分漢明相關(guān)低碰撞區(qū)LPHZ(L)、周期部分漢明自相關(guān)低碰撞區(qū)LPAHZ(L)和周期部分漢明互相關(guān)低碰撞區(qū)LPCHZ(L)分別定義為：

for0<τ≤T,0≤j

for0≤τ≤T,0≤j

特別地，當(dāng)j=0且L=N時，序列集S的周期部分漢明相關(guān)低碰撞區(qū)、周期部分漢明自相關(guān)低碰撞區(qū)和周期部分漢明互相關(guān)低碰撞區(qū)分別是上面定義的跳頻序列集的周期漢明相關(guān)低碰撞區(qū)、周期漢明自相關(guān)低碰撞區(qū)和周期漢明互相關(guān)低碰撞區(qū)。

為簡便，在不引起混淆的情況下，令PLa=PLa(L),PLc=PLc(L)，LPHZ=LPHZ(L)。

2009年，作者[18]推導(dǎo)了低碰撞區(qū)跳頻序列集最大周期部分漢明相關(guān)理論界。

引理6(Niu-Peng-Liu界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，相關(guān)窗長度為L(L≤N)，LPHZ為跳頻序列集S的周期部分漢明相關(guān)低碰撞區(qū)，那么對于任意正整數(shù)Z，0≤Z≤LPHZ，有：

qZPLa+q(M-1)(Z+1)PLc≥(Z+1)LM-Lq

(13)

MNZPLa+M(M-1)N(Z+1)PLc≥(Z+1)L[(2I+1)M-I(I+1)q/N]-LMN

(14)

其中，I=?NM/q」。

現(xiàn)有的Lempel-Greenberger界、Peng-Fan 界、Peng-Fan-Lee 界和Eun-Jin-Hong-Song界都是Niu-Peng-Liu界的特殊情況。Niu-Peng-Liu界是跳頻序列集關(guān)于最大周期漢明相關(guān)和最大周期部分漢明相關(guān)的現(xiàn)階段最完整的理論界，而對于跳頻序列集平均漢明相關(guān)性質(zhì)的理論界，現(xiàn)階段只有Peng-Peng-Tang-Niu界考慮了常規(guī)跳頻序列集的平均周期漢明相關(guān)；因此，本文將主要考慮低碰撞區(qū)跳頻序列集的平均部分漢明相關(guān)，構(gòu)造低碰撞區(qū)跳頻序列集平均部分漢明相關(guān)的理論界。

2 低碰撞區(qū)跳頻序列平均周期部分漢明相關(guān)理論界

首先給出低碰撞區(qū)跳頻序列集平均周期部分漢明相關(guān)的定義。

定義1令F是一個大小為q的頻隙集，S是F上由M個長度為N的跳頻序列組成的集合，相關(guān)窗長度為L(L≤N)，LPHZ為跳頻序列集S的周期部分漢明相關(guān)低碰撞區(qū)，那么對于任意正整數(shù)Z，0≤Z≤LPHZ，將：

(15)

(16)

分別稱為低碰撞區(qū)跳頻序列集S的周期部分漢明自相關(guān)總碰撞次數(shù)和周期部分漢明互相關(guān)總碰撞次數(shù)。跳頻序列集S在低碰撞區(qū)的平均周期部分漢明自相關(guān)和平均周期部分漢明互相關(guān)可表示為：

(17)

(18)

下面給出本文的重要定理，即低碰撞區(qū)跳頻序列集平均周期部分漢明自相關(guān)和平均周期部分漢明互相關(guān)理論界。

定理1令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，相關(guān)窗長度為L(L≤N)，LPHZ為跳頻序列集S的周期部分漢明相關(guān)低碰撞區(qū)，那么對于任意正整數(shù)Z，0≤Z≤LPHZ，有：

(19)

(20)

其中，I=?NM/q」。

證明：對于任意正整數(shù)Z，0≤Z≤LPHZ，有

NM+(1/L)Sa+(2/L)Sc≥(Z+1)NM2/q

NM+(1/L)Sa+(2/L)Sc≥(Z+1)[(2I+1)M-I(I+1)q/N]

其中，I=?NM/q」。那么，基于低碰撞區(qū)跳頻序列集平均周期部分漢明相關(guān)的定義，有：

證畢。

在定理1中，令j=0，L=N，則跳頻序列集S的周期部分漢明相關(guān)低碰撞區(qū)LPHZ即為序列集S的周期漢明相關(guān)低碰撞區(qū)LHZ，由此可以得到低碰撞區(qū)跳頻序列集平均周期漢明相關(guān)函數(shù)的理論界。

推論1令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構(gòu)成的集合，相關(guān)窗長度為L(L≤N)，LHZ為跳頻序列集S的周期漢明相關(guān)低碰撞區(qū)，那么對于任意正整數(shù)Z，0≤Z≤LHZ,有：

(21)

(22)

其中，I=?NM/q」。

定理1和推理1給出了低碰撞區(qū)跳頻序列集平均周期部分漢明相關(guān)和平均周期漢明相關(guān)的理論界。理論界的提出對設(shè)計(jì)具有優(yōu)異平均周期部分漢明相關(guān)和平均周期漢明相關(guān)的低碰撞區(qū)跳頻序列有很好的指導(dǎo)意義。

例1令q=7，N=7，M=6，L=7，LPHZ=6，代入定理1中可得

令頻隙集F={0, 1, 2, 3, 4, 5, 6}, 可構(gòu)造跳頻序列集S={S0,S1,S2,S3,S4,S5}, 其中，S0=0116166，S1=0225255，S2=0334344，S3=0443433，S4=0552522，S5=0661611。序列集的部分漢明相關(guān)值為

3 結(jié)束語

本文構(gòu)造了低碰撞區(qū)跳頻序列平均部分漢明相關(guān)的理論界，通過理論界給出了跳頻序列集序列長度、序列個數(shù)、頻隙個數(shù)、平均周期部分漢明自相關(guān)和平均周期部分漢明互相關(guān)所滿足的理論約束關(guān)系。已有理論界都可以看作是本文理論界的特殊情況，新理論界的提出對于跳頻序列的設(shè)計(jì)和評估有很好的指導(dǎo)意義。

[1] Fan P Z, Darnell M. Sequence Design for Communications Applications[M]. London: RSP John Wiley & Sons Inc, 1996:271-350.

[2] Golomb S W, Gong G. Signal Design for Good Correlation: for Wireless Communication, Cryptography and Radar[M]UK: Cambridage Univ Press,2005:402-417.

[3] Lempel A , Greenberger H. Families of Sequence with Optimal Hamming Correlation Properties[J].IEEE Trans Inf Theory,1974, 20:90-94.

[4] Eun Y C , Jin S Y , Hong Y P , et al. Frequency Hopping Sequences with Optimal Partial Autocorrelation Properties[J].IEEE Trans Inf Theory, 2004, 50:2438-2442.

[5] Wang X N, Fan P Z. A Class of Frequency Hopping Sequences with no Hit Zone[C]// Proceeding of the 4th International Conference on Parallel and Distributed Computing, Applications and Technologies. Chengdu, China：IEEE Press, 2003: 896-898.

[6] Peng D Y , Fan P Z. Lower Bounds on the Hamming Auto-and Cross Correlations of Frequency Hopping Sequences[J].IEEE Trans Inf Theory, 2004,50:2149-2154.

[7] Ding C, Fuji-Hara R, Fujiwara Y, et al. Sets of Frequency Hopping Sequences: Bounds and Optimal Constructions[J] .IEEE Trans Inf Theory,2009,55:3297-3304.

[8] Ge G N, Miao Y, Yao Z X. Optimal Frequency Hopping Sequences: Auto-and Cross-correlation Properties[J]. IEEE Trans Inf Theory,2009, 55: 867-879.

[9] Chung J H, Yang K. New Frequency-hopping Sequence Sets with Optimal Average and Good Maximum Hamming Correlations[J].IET Communications,2012,6:2048-2053.

[10] Zeng X Y, Cai H, Tang X H, et al. A Class of Optimal Frequency Hopping Sequences with New Parameters[J].IEEE Trans Inf Theory,2012,58 :4899-4907.

[11] Peng D Y , Peng T , Tang X H , et al. A Class of Optimal Frequency Hopping Sequences Based on the Theory of Power Residues[J]. Proceeding of the 5thInternational Conference on Sequences and their Applications Lexington, 2008,5203:188-196.

[12]Niu X H , Peng D Y , Zhou Z C. Frequency/time Hopping Sequence Sets with Optimal Partial Hamming Correlation Properties[J]. Science China,2012,55(10):2207-2215.

[13] Peng D Y , Fan P Z , Lee M H. Lower Bounds on the Periodic Hamming Correlations of Frequency Hopping Sequences with Low Hit Zone[J]. Science in China: Series F Information Sciences,2006, 49(2):1-11.

[14] Ma W P, Sun S H. New Designs of Frequency Hopping Sequences with Low Hit Zone[J]. Designs, Codes and Cryptography,2010, 60:145-153.

[15] Niu X H, Peng D Y, Zhou Z C. New Classes of Optimal Low Hit Zone Frequency Hopping Sequences with New Parameters by Interleaving Technique[J]. IEICE Transactions on Fundamentals,2012, 95:1835-1842.

[16] Niu X H, Peng D Y, Zhou Z C. New Classes of Optimal Frequency Hopping Sequence Sets with Low Hit Zone[J]. Advances in Mathematics of Communications,2013, 7 :293-310.

[17] Chung J H, Yang K. New Classes of Optimal Low-hit-zone Frequency-hopping Sequence Sets by Cartesian Product[J]. IEEE Trans Inf Theory, 2013, 59: 726-732.

[18] Niu X H , Peng D Y, Liu F. Lower Bounds on the Periodic Partial Correlations of Frequency Hopping Sequences with Partial Low Hit Zone[C]//The Fourth International Workshop on Signal Design and Its Applications in Communications (IWSDA’2009). Fukuoka, Japan:[s.n.], 2009: 84-87.