時頻二維低/無碰撞區跳頻序列集構造

許成謙, 曹　琦

(燕山大學信息科學與工程學院, 河北 秦皇島 066004)

0　引　言

基于低/無碰撞區(low hit zone/ no hit zone,LHZ/NHZ)跳頻序列的準同步組網的跳頻碼分多址系統是一種性能優越的跳頻通信方式,與傳統的跳頻通信方式相比,具有更低的多址干擾以及抗多徑干擾能力。LHZ/NHZ跳頻序列的優劣對跳頻碼分多址系統的性能有著決定性的影響,所以,設計出性能良好的LHZ/NHZ跳頻序列一直是研究跳頻碼分多址系統的重要方向之一。近年來,學者們分別在構造NHZ跳頻序列[1-3]與LHZ跳頻序列[4-9]方面取得了大量的研究成果。

在實際系統中,跳頻信號除存在傳輸時延外,還可能發生頻率偏移。特別是像雷達等系統在高速運動的情況下,傳輸信號的頻率可能發生偏移,跳頻序列的頻隙可能移位至其他頻隙,導致與其他跳頻序列發生碰撞,影響通信質量。所以,有必要將只考慮時延的一維碰撞區擴展到同時考慮時延頻移的二維碰撞區。文獻[10]首先考慮了跳頻序列包含頻移的漢明相關性,用Reed-Solomon (RS)跳頻序列作為實例進行分析。文獻[11]設計出了基于Costas序列的跳頻序列,根據實際系統可能出現的最大多普勒頻移,利用循環移位法獲得含有一個間隙列和一個間隙行的序列族來設計正交頻分復用系統的跳頻序列。文獻[12]提出了時頻二維無碰撞區跳頻序列的概念,并推導出了此類跳頻序列的理論界,設計出了時頻二維無碰撞區跳頻序列集。文獻[13]給出了跳頻序列由時頻低碰撞區邊長值、時頻二維移位漢明相關值、頻隙個數、序列的長度、序列的個數構成的理論界。文獻[14]分別基于Welch Costas陣列和Golomb Costas陣列構造出了兩種滿足理論界的時頻二維低碰撞區跳頻序列集。文獻[15]研究了跳頻序列集時頻最大周期漢明相關值的理論界,分析了Cai跳頻序列集和多項式同余法構造的跳頻序列集的時頻二維周期漢明相關性。

本文首先證明了RS碼的時頻二維周期漢明自相關函數的上界,為后續的構造提供了理論基礎;此后,提出了兩種時頻二維低/無碰撞區跳頻序列集的構造方法。第一種方法基于RS碼來構造時頻二維周期低碰撞區跳頻序列集,同時,構造出的跳頻序列集也為時頻二維非周期低碰撞區跳頻序列集。第二種方法利用矩陣來構造時頻二維非周期無碰撞區跳頻序列集。

1　基本概念

(1)

式中

當s1=s2時,Hs1s1(τ,v)稱為s1的時頻二維周期漢明自相關函數,當s1≠s2時,Hs1s2(τ,v)稱為s1和s2的時頻二維周期漢明互相關函數。

下面給出時頻二維非周期漢明相關函數的概念。

(2)

式中

文獻[1]和文獻[4]分別給出了一維漢明相關函數下具有無碰撞區和低碰撞區的跳頻序列概念。下面給出時頻二維漢明相關函數下具有無碰撞區和低碰撞區的跳頻序列概念。

0≤τ≤TA,0≤v≤VA,(τ,v)≠(0,0)}}

(3)

0≤τ≤TA,0≤v≤VA,(τ,v)≠(0,0)}}

(4)

0≤τ≤TC,0≤v≤VC,k≠l}}

(5)

0≤τ≤TC,0≤v≤VC,k≠l}}

(6)

Lt=min{LAt,LCt},Lf=min{LAf,LCf}

(7)

若(Lt,Lf)≠(0,0),則稱區間[0,LAt]×[0,LAf]為S的時頻二維周期自相關低碰撞區,稱區間[0,LCt]×[0,LCf]為S的時頻二維周期互相關低碰撞區,稱區間[0,Lt]×[0,Lf]為S的時頻二維周期低碰撞區,稱S為(q,L,M,Lt,Lf,Ha(S),Hc(S))時頻二維周期低碰撞區跳頻序列集。

為簡化起見,在下面的討論中,令Ha=Ha(S),Hc=Hc(S),Hm=max{Ha,Hc}。

特殊地,當Ha=Hc=0時,稱S的低碰撞區為S的無碰撞區,用符號Z表示。此時,稱區間[0,ZAt]×[0,ZAf]為S的時頻二維周期自相關無碰撞區,稱區間[0,ZCt]×[0,ZCf]為S的時頻二維周期互相關無碰撞區,稱[0,Zt]×[0,Zf]為S的時頻二維周期無碰撞區,稱S為(q,L,M,Zt,Zf)時頻二維周期無碰撞區跳頻序列集。

0≤τ≤TA,0≤v≤VA,(τ,v)≠(0,0)}}

(8)

0≤τ≤TA,0≤v≤VA,(τ,v)≠(0,0)}}

(9)

0≤τ≤TC,0≤v≤VC,k≠l}}

(10)

0≤τ≤TC,0≤v≤VC,k≠l}}

(11)

(12)

設GF(q)為q階有限域,q=pm,p為素數,m為正整數,α是GF(q)的本原元,以多項式g(x)=(x-α)(x-α2)…(x-α2t)(t>0)生成多項式的循環碼稱為GF(q)上的RS碼。RS碼的碼長為q-1,信息位數為q-2t-1。

2　性質

定理1給出了RS碼碼字時頻二維周期漢明自相關函數的上界,即RS碼碼字與其時頻二維移位碼字碰撞次數的上界。

定理1設s為GF(q)上信息位數為b的RS碼的碼字,則s的時頻二維周期漢明自相關函數不大于b-1,即Hss(τ,v)≤b-1。

證明

設s=(n(1),n(α),n(α2),…,n(αq-2)),則

(13)

令αi=x,根據漢明相關函數的特點知,式(13)的值等于式(14)根的個數。

n(x)-n(ατx)-v=0

(14)

因為n(x)是b-1次多項式,所以式(14)在GF(q)上最多有b-1個根,因此

Hss(τ,v)≤b-1

(15)

證畢

定理1指出RS碼碼字的二維漢明相關函數的上界是RS碼的信息位數減1,因此為了使得碼子二維漢明相關函數性小，需要采用信息位數小的RS碼。

證明從S中任意選取序列sk和sl,k,l=0,1,…,M-1,其時頻二維非周期漢明相關函數為

(16)

(17)

(18)

即

(19)

證畢

定理2給出了形成跳頻序列集時頻二維非周期無碰撞區的充分條件,從該條件可以得到判斷跳頻序列集時頻二維非周期無碰撞區大小的有效方法。

3　構造

3.1　時頻二維周期低碰撞區跳頻序列集的構造方法

構造方法具體如下:

步驟1從C中選取M個碼字sk,k=0,1,…,M-1,其中sk的信息向量為

nk=(1+k(Lf+1),α1+k(Lt+1))

(20)

式中,α是GF(q)的本原元。

步驟2將選取的每個碼字看作一個跳頻序列,構成跳頻序列集S={sk}。其中,k=0,1,…,M-1。

定理3構造方法1所構造出的序列集S為(q,q-1,M,Lt,Lf,1,1)時頻二維周期低碰撞區跳頻序列集。

證明由構造方法1構造的跳頻序列集頻隙個數為q,序列長度為q-1,序列數目為M且M≥2,下面證明低碰撞區為[0,Lt]×[0,Lf]。

(1) 討論自相關性

對于?sk∈S,由構造方法1知,sk是RS碼中的碼字,由定理1知,對(τ,v)≠(0,0),有

Hsksk(τ,v)≤1

(21)

即S中序列的時頻二維周期漢明自相關函數皆小于等于1。

(2) 討論互相關性

設sk,sl分別是信息向量nk,nl對應的RS碼碼字, 其中nk=(1+k(Lf+1),α1+k(Lt+1));nl=(1+l(Lf+1),α1+l(Lt+1))(k≠l),則sk=(nk(1),nk(α),nk(α2),…,nk(αq-2)),sl=(nl(1),nl(α),nl(α2),…,nl(αq-2))∈S。

sk和sl的時頻二維周期漢明互相關函數為

(22)

根據漢明相關函數的特點知,式(22)的值等于式(23)根的個數。

nk(αi)-nl(αi+τ)-v=0

(23)

令αi=x,由式(20)知式(23)為

1+k(Lf+1)+α1+k(Lt+1)x-

[1+l(Lf+1)+α1+l(Lt+1)+τx+v]=0

(24)

即

(α1+k(Lt+1)-α1+l(Lt+1)+τ)x+(k-l)(Lf+1)-v=0

(25)

當(τ,v)∈[0,Lt]×[0,Lf]時,因為1+k(Lt+1)-[1+l(Lt+1)+τ]=(k-l)(Lt+1)-τ≠0,所以α1+k(Lt+1)-α1+l(Lt+1)+τ≠0,此時式(25)為一次多項式,即式(25)在GF(q)上最多有1個根,因此

Hsksl(τ,v)≤1((τ,v)∈[0,Lt]×[0,Lf])

(26)

證畢

3.2　時頻二維非周期無碰撞區跳頻序列集構造

構造方法2取頻隙集合F={0,1,…,q-1},其中

(27)

構造方法具體如下:

(28)

(29)

(30)

式中,T表示轉置。

(31)

式中,T表示轉置。

證明

(1) 證明頻隙總數,序列長度的值

由式(27)和i、j、k的取值范圍知,構造的跳頻序列的元素取自F,因此頻隙總數為

證畢

4　構造實例

4.1　構造方法1實例

設C為有限域GF(11)上的RS碼,C的信息位數b=2,碼長L=10,令Lt=1,Lf=1,則M1=4,M2=4,M=4。2為GF(11)上的一個本原元。從C中選取4個碼字sk(k=0,1,2,3),其中，sk(k=0,1,2,3)的信息向量分別為n0=(1,2),n1=(3,23),n2=(5,25),n3=(7,27),則

s0=(3,5,9,6,0,10,8,4,7,2)

s1=(0,8,2,1,10,6,9,4,5,7)

s2=(4,3,1,8,0,6,7,9,2,10)

s3=(3,10,2,8,9,0,4,1,6,5)

將選取的每個碼字sk(k=0,1,2,3)看作一個跳頻序列,這4個跳頻序列構成的集合S={sk}是參數為(11,10,4,1,1,1,1)的時頻二維周期低碰撞區跳頻序列集。

S中跳頻序列的時頻二維周期漢明自相關函數和互相關函數分別取值為

式中,k≠l且k,l=0,1,2,3;λ為不小于0的整數。可以看出相關函數的峰值為10,時頻二維周期低碰撞區為[0,1]×[0,1]。

4.2　構造方法2實例

式中,i=0,1;k=0,1,2。

(2) 構造3×3階矩陣A0、A1,表示為

(3) 構造3×3階矩陣A2，表示為

(4) 將矩陣A0、A1、A2拼接得到矩陣A，表示為

A=[A0A1A2]=

(5) 取A矩陣每一行對應一個跳頻序列sk(k=0,1,2),則所有跳頻序列構成的跳頻序列集S={sk}即為(19,9,3,2,1)時頻二維非周期無碰撞區跳頻序列集。

集合中跳頻序列的時頻二維非周期漢明自相關函數和互相關函數分別取值為

Hsksk(τ,v)=

Hsksl(τ,v)=

式中,k≠l且k,l=0,1,2;λ為不小于0的整數。可以看出相關函數的峰值為9,時頻二維非周期無碰撞區為[0,2]×[0,1]。

5　結　論

文獻[10]以RS碼為實例,分析了跳頻序列在同時考慮時延和頻移時的漢明相關性,但是沒有給出基于RS碼的低碰撞區跳頻序列時頻二維漢明相關函數取值的理論證明結果。本文證明了以RS碼碼字形成的跳頻序列的時頻二維周期漢明自相關函數的上界為RS碼的信息位數減1。構造方法1利用RS碼中一些特殊信息向量對應的碼字構造出了時頻二維周期(非周期)低碰撞區跳頻序列集。構造方法2通過將頻隙分組構成行向量,再將向量轉置后拼接形成矩陣,取矩陣的行作為跳頻序列,這些跳頻序列構成的跳頻序列集即為時頻二維非周期無碰撞區跳頻序列集。本文對構造方法1和構造方法2構造出的跳頻序列的時頻二維漢明相關性進行了嚴格證明,從理論上保證了這些構造方法的正確性。

參考文獻：

[1] YE W X, FAN P Z. Construction of non-repeating frequency-hopping sequences with no-hit-zone[J].Electronics Letters, 2006, 42(12): 681-682.

[2] ZENG Q, PENG D, WANG X. Performance of a novel MFSK/FHMA system employing no-hit zone sequence set over rayleigh fading channel[J].IEICE Trans.on Communications,2011,94-B(2):526-532

[3] CHUNG J, HAN Y K, YANG K. No-hit-zone frequency-hopping sequence sets with optimal hamming autocorrelation[J]. IEICE Trans.on Fundamentals of Electronics, Communications and Computer Sciences, 2010, E93-A (11):2239-2244.

[4] MA W P, SUN S H. New designs of frequency hopping sequences with low hit zone[J]. Designs Codes and Cryptography, 2011,60 ( 2) :145-153.

[5] CHUNG J,YANG K. New Classes of optimal low-hit-zone frequency-hopping sequence sets by cartesian product[J]. IEEE Trans.on Information Theory, 2013, 59(1):726-732.

[6] HAN H, PENG D, PARAMPALLI U, et al. Construction of low-hit-zone frequency hopping sequences with optimal partial Hamming correlation by interleaving techniques[J]. Designs Codes and Cryptography, 2017,84(3): 401-414.

[7] LIU X, PENG D, HAN H. Low-hit-zone frequency hopping sequence sets with optimal partial Hamming correlation properties[J]. Designs, Codes and Cryptography, 2014, 73(1): 167-176.

[8] WANG C Y, PENG D Y, HAN H Y, et al. New sets of low-hit-zone frequency-hopping sequence with optimal maximum periodic partial Hamming correlation[J]. Science China Information Sciences, 2015, 36(2): 1-15.

[9] WANG C Y, PENG D Y, ZHOU L M N. New constructions of optimal frequency-hopping sequence sets with low-hit-zone[J]. International Journal of Foundations of Computer Science, 2016, 27(1): 53-66.

[10] MERSEREAU R M, SEAY T S. Multiple access frequency hopping patterns with low ambiguity[J]. IEEE Trans.on Aerospace and Electronic Systems, 1981, 17(4): 571-578.

[11] 姚建國, 王玉峰, 衡偉. Golomb Costas序列 的結構及其在OFDM系統中的應用[J]. 通信學報, 2013, 34(7): 1-13.

YAO J G, WANG Y F, HENG W. Constructions of Golomb Costas arrays and their applications in OFDM systems[J]. Journal on Communications, 2013, 34(7): 1-13.

[12] 葉文霞.無碰撞區跳頻序列與準同步/消息驅動跳頻通信系統研究[D].成都:西南交通大學,2011:31-40.

YE W X. Investigation of no hit zone FH sequences,quasi-synchronous and message diven FH systems[D]. Chengdu: Southwest Jiaotong University, 2011: 31-40.

[13] 許成謙,馬雅楠. 時頻低碰撞區跳頻序列理論界的研究[J].燕山大學學報, 2017, 41(1): 68-73.

XU C Q, MA Y N. Theoretical bounds on low hit zone of time-frequency frequency hopping sequences[J].Journal of Yanshan University, 2017,41(1):68-73.

[14] 許成謙,馬雅楠. 二維時頻低碰撞區跳頻序列集的構造[J].系統工程與電子技術,2017,39(4): 905-909.

XU C Q, MA Y N. Construction of frequency hopping sequence set with two-dimensional time-frequency low hit zone[J]. Systems Engineering and Electronics,2017, 39(4): 905-909.

[15] 劉元慧,許成謙. 兩類跳頻序列集時頻二維漢明相關性的分析[J].系統工程與電子技術,2017,39(9):2132-2136.

LIU Y H, XU C Q. Analysis of time-frequency two-dimensional Hamming correlation of two frequency hopping sequence sets[J].Systems Engineering and Electronics,2017,39(9):2132-2136.