低碰撞區跳頻序列平均部分漢明相關理論界研究

牛憲華1，曾柏森

(1.西華大學數學與計算機學院， 四川 成都 610039；2. 中國聯通成都市分公司網絡優化中心， 四川 成都 610036)

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

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

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

1 定義和理論界

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

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

(1)

其中，下標j+τ按模N運算，并且只考慮正時延。

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

(2)

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

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

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

(3)

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

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

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

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

(4)

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

(5)

其中，I=?NM/q」。

可以看出，當M=1時，Lempel-Greenberger界是Peng-Fan界的特殊情況。如果跳頻序列集的相關性滿足Peng-Fan界取等號，稱這個跳頻序列集為最優跳頻序列集?，F有序列構造結果中，有很多跳頻序列集[7-10]滿足Peng-Fan界。

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

(6)

(7)

為簡化和方便，令Aa=Aa(S)，Ac=Ac(S)。

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

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

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

(8)

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

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

(9)

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

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

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

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

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

(10)

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

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

低碰撞區跳頻序列是低相關區擴頻序列在跳頻通信系統中的推廣。低碰撞區跳頻序列作為一個新的研究方向，近年來引起國內外學者的興趣。

對于任意跳頻序列集S，令整數HLa≥0，HLc≥0，跳頻序列集S的周期漢明相關低碰撞區LHZ、周期漢明自相關低碰撞區LAHZ和周期漢明互相關低碰撞區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}

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

2006年，D.Y.Peng等[13]推導了低碰撞區跳頻序列集周期漢明相關的理論界。

引理5(Peng-Fan-Lee 界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構成的集合，LHZ是序列集S關于周期漢明相關函數的低碰撞區。對于任意整數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 界的特殊情況。關于Peng-Fan-Lee界最優的低碰撞區跳頻序列集近年來也有許多構造結果[14-17]。

考慮低碰撞區跳頻序列集的周期部分漢明相關性質，可以得到如下定義。

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

for0<τ≤T,0≤j

for0≤τ≤T,0≤j

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

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

2009年，作者[18]推導了低碰撞區跳頻序列集最大周期部分漢明相關理論界。

引理6(Niu-Peng-Liu界) 令F是一個大小為q的頻隙集，S為F上M個長度為N的跳頻序列構成的集合，相關窗長度為L(L≤N)，LPHZ為跳頻序列集S的周期部分漢明相關低碰撞區，那么對于任意正整數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」。

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

2 低碰撞區跳頻序列平均周期部分漢明相關理論界

首先給出低碰撞區跳頻序列集平均周期部分漢明相關的定義。

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

(15)

(16)

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

(17)

(18)

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

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

(19)

(20)

其中，I=?NM/q」。

證明：對于任意正整數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」。那么，基于低碰撞區跳頻序列集平均周期部分漢明相關的定義，有：

證畢。

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

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

(21)

(22)

其中，I=?NM/q」。

定理1和推理1給出了低碰撞區跳頻序列集平均周期部分漢明相關和平均周期漢明相關的理論界。理論界的提出對設計具有優異平均周期部分漢明相關和平均周期漢明相關的低碰撞區跳頻序列有很好的指導意義。

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

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

3 結束語

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

[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.