基于交織技術(shù)的最優(yōu)低碰撞區(qū)跳頻序列集

凌　龍，牛憲華，胡夢婷，呂　中(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都　610039)

跳頻擴(kuò)頻是擴(kuò)頻通信中一種很常見的擴(kuò)頻方式，具有較好的抗干擾性、安全性、多址性，被廣泛應(yīng)用于藍(lán)牙、軍事通信、移動通信、雷達(dá)和聲納等系統(tǒng)[1-3]。所謂跳頻就是利用偽隨機(jī)序列來對數(shù)據(jù)調(diào)制的載波中心頻率進(jìn)行控制，使其按照一定的順序和速率在一組頻率中進(jìn)行任意隨機(jī)的跳變，相應(yīng)地接收端也按照同樣的順序和速率來進(jìn)行接收并且解調(diào)[4]。通常情況下在碼分多址環(huán)境中，總是希望保持發(fā)射機(jī)之間的相互干擾在盡可能低的水平[5-8]。當(dāng)2個或多個發(fā)射機(jī)同時(shí)在同一頻率上傳輸時(shí)易發(fā)生相互干擾，相互干擾的程度和跳頻序列的漢明相關(guān)性緊密相連；因此，設(shè)計(jì)具有良好的漢明相關(guān)特性的跳頻序列(frequency hopping sequences,FHS)是研究跳頻技術(shù)的重要內(nèi)容。

2003年Ye等[9]首次提出低碰撞區(qū)/零碰撞區(qū)(low hit zone/no hit zone,LHZ/NHZ)跳頻序列的概念。LHZ跳頻序列是一種具有特殊性質(zhì)的跳頻序列，序列在LHZ的漢明相關(guān)性能決定了系統(tǒng)抗多址干擾的能力。有關(guān)LHZ跳頻序列集(frequency hopping sequences sets, FHSS)構(gòu)造的研究有重要意義并取得了一些成果[10-13]，但現(xiàn)有成果中構(gòu)造的序列集序列數(shù)目還不夠大，不能充分利用帶寬。本文基于交織技術(shù)構(gòu)造得到了序列數(shù)目更大的最優(yōu)低碰撞區(qū)跳頻序列集。

1　預(yù)備知識

首先給出跳頻序列漢明相關(guān)函數(shù)的定義。設(shè)F={f0,f1,…,fq-1}是一個大小為q的頻隙集，S是由F上M個長度為N的跳頻序列組成的集合。

定義1設(shè)頻隙集F={f0,f1,…,fq-1}，令x={x0,x1,…,xN-1}，y={y0,y1,…,yN-1}，(xi,yi∈F，i=0,1,…,N-1)為頻隙集F上2個長度為N的跳頻序列，x和y在相對時(shí)延τ的周期漢明互相關(guān)函數(shù)為

(1)

式中：i+τ按模N運(yùn)算；當(dāng)x=y時(shí),H(x,y;τ)稱為周期漢明自相關(guān)函數(shù)；當(dāng)x≠y時(shí),H(x,y;τ)稱為周期漢明互相關(guān)函數(shù)。

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

Ha(S)=max{H(x,x;τ)|x∈S,0<τ

簡記為Ha=Ha(S),Hc=Hc(S),Hm=Hm(S)。

在2004年，Peng等[14]建立了FHSS的最大周期漢明相關(guān)值的下界。

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

(2)

對于任意跳頻序列集S，令整數(shù)Ha≥0,Hc≥0,F是一個大小為q的頻隙集，S為F上M個長度為N的低碰撞區(qū)跳頻序列構(gòu)成的集合，那么S關(guān)于周期漢明相關(guān)函數(shù)的低碰撞區(qū)LH、自相關(guān)低碰撞區(qū)LAH和互相關(guān)低碰撞區(qū)LCH分別定義為：

當(dāng)Ha=Hc=0時(shí)，LH稱為S的零碰撞區(qū)，亦表示成NH。一個具有LH≥0(或NH≥0)的跳頻序列集S稱為LHZ FHSS(或NHZ FHSS)。有關(guān)LHZ或NHZ FHSS構(gòu)造的研究有重要意義并取得了豐富的成果[15-18]。

在2004年，Peng等[19]推導(dǎo)了LHZ跳頻序列集的周期漢明相關(guān)理論界。

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

(3)

在本文中：用(N,q,l,Hm)表示一個序列長度為N，頻隙大小為q,序列數(shù)目為l,最大漢明相關(guān)為Hm的FHSS；用(N,q,l,L,Hm)表示一個序列長度為N，頻隙大小為q,序列數(shù)目為l，LHZ為L,最大漢明相關(guān)為Hm的FHSS。

2　交織序列理論

交織序列理論在1995年由Gong首先提出[20]。

設(shè)A={a0,a1,…,al-1}是一個(N,q,l,Hm) FHSS，e=(e0,e1,…,el-1)是ZN上長度為l的移位序列，則由序列a和移位序列e可以構(gòu)成一個N×l的矩陣

其中下標(biāo)按模N運(yùn)算。把矩陣U中的元素按行讀出，可以得到一個周期為Nl的序列u=(u0,u1,…,uNl-1)。將a稱為基序列，e稱為移位序列，u稱為交織序列。矩陣U是序列u的矩陣表示。為了簡化，把交織序列u表示為

u=I(Le0(a0),Le1(a1),…,Lel-1(al-1))。

其中I表示交織操作。令g=(g0,g1,…,gl-1)為ZN上長度為l的移位序列，可生成交織序列

v=I(Lg0(a0),Lg1(a1),…,Lgl-1(al-1))。

對于時(shí)延τ=lτ1+τ2(0≤τ1

Lτ(v)=I(Lτ1+gτ2(a),…,Lτ1+gl-1(a),

Lτ1+g0+1(a),…,Lτ1+gτ2-1+1(a))，

那么交織序列u和v在時(shí)延τ時(shí)的漢明相關(guān)函數(shù)可以表示為

特別地，當(dāng)τ2=0時(shí)，有

從式(5)和式(6)中，當(dāng)且僅當(dāng)τ2=0時(shí)，交織序列u和v是移位等價(jià)的，等式(7)成立。

ei-gi=ej-gj,0≤?i,j

(7)

定義2Zn上任意2個移位序列e=(e0,e1，…，el-1),g=(g0,g1，…，gl-1)，若等式(7)不成立，則e和g被稱為不等價(jià)移位序列。

引理3基于上述分析，如果交織序列u和v是循環(huán)不等價(jià)的，而且e和g是不等價(jià)移位序列，則Huv(τ)=lHm。

3　最優(yōu)低碰撞區(qū)跳頻序列集的構(gòu)造

此節(jié)將基于上述交織技術(shù)構(gòu)造具有新參數(shù)的最優(yōu)LHZ FHSS。

設(shè)F={f0,,f1,…,fq-1}是一個大小為q的頻隙集，LHZ FHSS的構(gòu)造如下。

構(gòu)造1最優(yōu)LHZ FHSS的構(gòu)造。

步驟1，選擇一個在F={f0,,f1,…,fq-1}上的最優(yōu)A(N,q,l,Hm)，

步驟2，令M,w為2個正整數(shù)，且滿足

構(gòu)造移位序列集H={E,G},有

其中0

步驟3，構(gòu)造最優(yōu)LHZ FHSSS={SA,SB}。

L(j+2l-2)w+(2l-2)(ai)),

其中x=iM+j(0≤i

L(j+r)w+r(al-1)),

其中 0≤j

證明

首先，根據(jù)交織技術(shù)的原理，得出S的序列長度為lN，頻隙大小為q。

其次，序列個數(shù)MS表示為

MS=MA+MB=lM+((w-1)-(2l-2))M=

(w-l+1)M。

證畢。

定理2構(gòu)造1中，如果參數(shù)滿足

則得到的FHSSS是最優(yōu)的(lN,q,(w-l+1)M,l-1,lHm)FHSS。

證明

頻隙集F的大小為q,令Z=LH。FHSSS的最大漢明相關(guān)

根據(jù)Peng-Fan-Lee 界，F(xiàn)HSSS的最優(yōu)漢明相關(guān)Hmo應(yīng)為

所以，當(dāng)

(8)

成立時(shí)，有

因此當(dāng)式(8)成立時(shí)，序列集S是最優(yōu)的(lN,q,(w-l+1)M,l-1,lHm)LHZ FHSS。

證畢。

注1：在構(gòu)造1中，發(fā)現(xiàn)有移位等價(jià)的情況，接下來將消除等價(jià)的移位性。

算法1

輸入：常數(shù)w,M。

輸出：移位序列集H。

步驟1，生成初始移位序列

步驟2，生成等價(jià)的移位序列

步驟3，生成不等價(jià)的移位序列，H′={E′，G′}。

對E={ej|0≤j

說明：對移位序列集E={ej|0≤j1)列執(zhí)行置換變換，得到新的不等價(jià)移位序列集E′,G′都是移位不等價(jià)的。

下面給出一個實(shí)例。

例1選擇一個(56,13,3,4)的FHSSA={a0,a1,a2}如下：

a0={2,2,6,12,1,0,8,12,4,11,3,8,10,1,10,10,4,8,5,0,1,8,7,3,2,1,1,5,11,11,7,1,12,0,5,1,9,2,10,5,3,12,3,3,9,5,8,0,12,5,6,10,11,12,2,8};

a1={4,4,12,11,2,0,3,11,8,9,6,3,7,2,7,7,8,3,10,0,2,3,1,6,4,2,9,10,9,9,1,2,11,0,10,2,5,4,7,10,6,11,6,6,5,10,3,0,11,10,12,7,9,11,4,3};

a2={8,8,11,9,4,0,6,9,3,5,12,6,1,4,1,1,3,6,7,0,4,6,2,12,8,4,5,7,5,5,2,4,9,0,7,4,10,8,1,7,12,9,12,12,10,7,6,0,9,7,11,1,5,9,8,6}。

令M=4,w=14，得到移位序列集H={E,G}，根據(jù)構(gòu)造1的步驟2得到移位序列集E和G，為

根據(jù)構(gòu)造1的步驟3，利用交織技術(shù)得到以下FHSSS：

?

?

根據(jù)漢明相關(guān)性的定義，得到最大漢明自相關(guān)和最大漢明互相關(guān)，如圖1所示。當(dāng)τ<3時(shí)，Hm=12，S是一個(168, 13, 48,2,12) FHSS。

注2：觀察圖1，S的最大漢明互相關(guān)最大為168，發(fā)生了移位等價(jià)的情況。

圖1　S的最大漢明相關(guān)函數(shù)

接下來消除移位等價(jià)。根據(jù)文獻(xiàn)[10]中的構(gòu)造3方法，替換E的最后2列，得到新的移位序列E′，根據(jù)文獻(xiàn)[11]中的構(gòu)造2，修改G中的最后2列，得到移位不等價(jià)序列集G′，其中E′和G′矩陣表示為：

交織后得到不等價(jià)的移位序列集

?

?

根據(jù)漢明相關(guān)性的定義，得到最大漢明自相關(guān)和最大漢明互相關(guān)，如圖2所示。當(dāng)τ<3時(shí)，Hm=12，S′是一個(168,13,48,2,12)FHSS，并且S′中所有序列是移位不等價(jià)的。

圖2　S′的最大漢明相關(guān)函數(shù)

注3：觀察圖2，S的最大漢明相關(guān)小于序列長度，說明移位等價(jià)的情況已經(jīng)被消除。

4　結(jié)論

基于交織技術(shù)，本文提出一種新的構(gòu)造方法，與文獻(xiàn)[12]和[13]相比，該方法所構(gòu)造出的序列集具有新的參數(shù)。本文構(gòu)造的序列集，其序列數(shù)目比已有文獻(xiàn)的序列數(shù)目更大，且所有序列都是移位不等價(jià)的。通過選擇一些已知的最優(yōu)FHSS，滿足特定條件可以構(gòu)造出最優(yōu)的LHZ FHSS。通過使用不同的移位序列，可以構(gòu)造出參數(shù)設(shè)置更靈活的LHZ FHSS。該FHSS可以應(yīng)用到準(zhǔn)同步的跳時(shí)/跳頻碼分多址系統(tǒng)中，用于消除多址干擾。

[1]梅文華,楊義先.跳頻通信編碼地址理論[M].北京：國防工業(yè)出版社,1996.

[2]趙寰, 全厚德, 崔佩璋. 抗跟蹤干擾的多序列跳頻無線通信系統(tǒng)[J]. 系統(tǒng)工程與電子技術(shù), 2015, 37(3):671.

[3]牛憲華,陳思利,王瑜. 跳頻序列研究綜述[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,35(2):259.

[4]梅文華,王淑波,邱永紅.跳頻通信[M].北京：國防工業(yè)出版社，2005.

[5]朱永松,張海勇,汲萬峰. 跳頻通信抗干擾性能分析[J]. 現(xiàn)代防御技術(shù), 2005, 33(5):37.

[6]苑雪, 曾興雯, 申振寧. 跳頻同步信號的干擾研究[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2004, 31(6):896.

[7]滕振宇,馮永新.差分跳頻通信抗干擾效能分析[J].火力與指揮控制, 2012, 37(1):11.

[8]牛憲華,曾柏森. 低碰撞區(qū)跳頻序列平均部分漢明相關(guān)理論界研究[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,33(3):1.

[9]YE W X, FAN P Z. Two class of frequency-hopping sequences with no-hit zone[C]//Proceedings of the Seventh International Symposium on Communications Theory and Applications (ISCTA’2003). Ambleside, UK:[s.n.], 2003:304-306.

[10]LIU X, PENG D. Frequency hopping sequences with optimal partial Hamming correlation by interleaving techniques[C]//International Workshop on Signal Design and ITS Applications in Communications. Tokyo, Japan：IEEE, 2014:158-161.

[11]XU Shanding,CAO Xiwang,XU Guangkui. Recursive construction of optimal frequency-hopping sequence sets[J]. IET Communications, 2016, 10(9):1080.

[12]NIU X H, PENG D Y, ZHOU Z C. New classes of optimal low hit zone frequency hopping sequence with new parameters by interleaving techniques [J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, 2012, E95-A (11):1835.

[13]NIU X H, ZHOU Z C. New classes of optimal low hit zone frequency hopping sequences with new parameters[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, 2014, E97-A (12): 2567.

[14]PENG D Y, FAN P Z. Lower bounds on the Hamming auto and cross correlations of frequency-hopping sequences [J]. IEEE Trans Inform Theory,2004, 50(9): 2149.

[15]WENPING M S. New designs of frequency hopping sequences with low hit zone[J]. Designs, Codes and Cryptography, 2011, 60(2): 145.

[16]HAN Y K, YANG K. New near-optimal frequency-Hopping sequences of length pq[C]//International Symposium on Information Theory. Toronto, ON, Canada:IEEE, 2008:2593-2597.

[17]CHUNG J H, GONG G, YANG K. New families of optimal frequency-hopping sequences of composite lengths[J]. IEEE Transactions on Information Theory, 2014, 60(6):3688.

[18]HAN H, PENG D, PARAMPALLI U. New sets of optimal low-hit-zone frequency-hopping sequences based on m-sequences[J]. Cryptography & Comm, 2016，9(4):1.

[19]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):208.

[20]GONG G. Theory and applications of q-ary interleaved sequences [J]. IEEE Trans Inform Theory,1995, 41(2):400.