跳頻序列部分漢明相關理論界及其最優構造

周正春

(西南交通大學 數學學院, 四川 成都 610031)

1 前言

跳頻多址技術目前廣泛應用于超寬帶(UWB)、軍事通信和藍牙等現代通信系統中.跳頻序列是跳頻多址通信系統的一個組成部分[1].例如,在多接入跳頻分組無線網絡中,每個發送器被分配一個唯一的簽名序列,以控制無線電在一幀內為連續的分組使用的頻率.在幀異步和包同步的假設下,當2個或多個無線電以相同的頻率同時發送它們的包時,碰撞的包有可能互相破壞.這些碰撞可以通過數字簽名序列的漢明相關來測量.為了減小頻率沖突引起的多址干擾,必須減小所采用的跳頻序列的漢明相關.

一般來說,跳頻序列的漢明相關大致可分為3種類型[2]:周期漢明相關、非周期漢明相關和部分漢明相關.跳頻序列的周期漢明自相關的研究可以追溯到著名的Lempel-Greenberger界[3].在2004年,Peng和Fan[4]推導了跳頻序列集的周期漢明相關的界.文獻[5-6]報道了關于周期漢明相關的跳頻序列集的編碼理論界.在過去的40 a中,已經有許多文獻(如文獻[3,6-15])達到了這些界的跳頻序列的構造.

在實際應用中,跳頻序列集的周期相關性決定了系統中可適應用戶的數量和容錯率[16],而它的非周期性和部分周期相關性影響它在接收端的同步和捕獲性能[16-17].如上所述,關于跳頻序列集的周期漢明相關性已有大量的研究,但是對于非周期相關和部分相關卻知之甚少,而這些性質在理論意義和實際應用中都很重要.特別地,在同步時間有限或硬件復雜的許多應用程序場景中[17],相關窗口的長度應該比選定的跳頻序列的周期短得多[4,17].同時,根據信道條件,窗口長度可能會隨時間變化而變化.因此,我們希望所采用的跳頻序列應具有良好的部分漢明相關性.

已有的跳頻序列(集)部分漢明相關的理論界主要分為2種:

一是給定頻率數目和序列長度條件下的部分漢明相關理論界.2004年,Eun等[17]建立了單個跳頻序列的最大部分漢明自相關的下界.2012年,Zhou等[2]將Peng-Fan界推廣到了部分漢明相關的情形,得到了跳頻序列集最大部分漢明相關的下界.2014年,Cai等[18]改進了上述理論界,分別給出了單個跳頻序列和跳頻序列集的最大部分漢明相關的下界.

二是限定部分漢明相關條件下的序列數目的理論界.2016年,Cai等[19]從糾錯編碼的一些經典界出發,得到了在限定部分漢明相關條件下的序列數目的2個上界.此外,2010年,Niu等[20]發現了低碰撞跳頻序列集的最大部分漢明相關的理論界.

下面介紹跳頻序列部分漢明相關的研究進展.2004年,Eun等[17]提出一類具有最優部分漢明自相關的跳頻序列的構造.Udaya等[12]基于多項式剩余類環上的m序列和Gordon-Mills-Welch序列提出了一類具有最優部分漢明自相關的跳頻序列的構造.2012年,Zhou等[2]基于陣列結構提出一類具有嚴格最優部分漢明自相關的單個跳頻序列和一類具有嚴格最優部分漢明相關的跳頻序列集的構造.2012年,Niu等[21]基于廣義m序列和廣義Gordon-Mills-Welch序列提出了一類最優部分漢明相關的跳頻/跳時序列集的構造.2014年,Cai等[18]基于廣義分圓提出了一類強最優部分漢明相關的跳頻序列(集)的構造.2016年,Cai等[19]提出一類具有最優序列集大小的強最優部分漢明相關跳頻序列集的構造.2016年,Fan等[22]基于不相交循環完美Mendelsohn差族提出一類強最優部分漢明相關跳頻序列的構造.2016年,Bao等[23]基于多重可劃分平衡嵌套循環差填充提出幾類強最優部分漢明相關跳頻序列(集)的構造.2019年,Liu等[24]基于可劃分差填充提出幾類強最優部分漢明相關跳頻序列(集)的構造.此外,2018年,Liu等[25]提出2類具有嚴格最優部分漢明相關的低碰撞區跳頻序列集的構造.2019年,Han等[26]利用交織技術提出一類具有嚴格最優部分漢明相關的低碰撞區跳頻序列集的構造.

2 基本概念

S={X1,X2,…,XM}.

τ=0,1,…,N-1,

其中〈x〉n是x模N的最小非負余數,

當X=Y時,稱HXY(τ)為周期漢明自相關;當X≠Y時,稱HXY(τ)為周期漢明互相關.

對于任意給定的跳頻序列集S,最大漢明自相關Ha(S)、最大漢明互相關Hc(S)和最大漢明相關Hm(S)分別定義為:

Ha(S)=max{HXX(τ)|X∈S,0<τ

Hc(S)=max{HXY(τ)|X,Y∈S,X≠Y,

0≤τ

Hm(S)=max{Ha(S),Hc(S)}.

為簡單起見,本文用(N,q,Ha)表示定義在大小為q的頻隙集F上、長度為N的、最大漢明自相關為Ha的跳頻序列,其中

Ha={HXX(τ):1≤τ

用(N,M,q,Hm)表示一個大小為q的頻隙集上長度為N的M個跳頻序列組成的集合,其最大漢明相關為Hm=Hm(S).

2.2 部分漢明相關函數

(1)

其中,0≤τ,j≤N-1,1≤L≤N.

特別地,如果L=N,j=0,(1)式就是周期漢明相關;如果L=N-τ,j=0,則(1)式就是非周期漢明相關函數.

當X=Y時,HX,X(τ;j|L)稱為X的部分漢明自相關函數;當X≠Y時,HX,Y(τ;j|L)稱為X和Y的部分漢明互相關函數.

定義 2.3對于F上任意2個不同的序列X和Y,任給整數L(1≤L≤N),它們的最大部分漢明自相關函數Pa(L)和最大部分漢明互相關函數Pc(L)分別定義為

和

設S是F上長度為N的M個跳頻序列組成的集合,對于任給的相關窗長L,序列集S的最大部分漢明相關函數Pm(L)定義為

3 部分漢明相關理論界

跳頻序列的參數(長度、頻隙集大小、最大相關值、序列集合大小)相互制約,本節主要介紹這些參數的理論界.

3.1 給定頻率數目和序列長度條件下的部分漢明相關理論界在2004年,Eun等[17]發現跳頻序列的最大部分漢明自相關下界.

定理 3.1(Eun-Jin-Hong-Song界[17]) 設X是大小為q的字母集F上的一條長度為N的跳頻序列,那么對于任意的相關窗長L(1≤L≤N),有

(2)

其中，r是N模q的最小非負余數.

當L=N時,(2)界恰好是Lempel-Greenberger界[3].

2014年,Cai等[18]改進(2)界,得到了如下結果.

推論 3.1(Cai-Zhou-Yang-Tang界[18]) 設X是大小為q的頻隙集F上的一條長度為N的跳頻序列,則對于任意的相關窗長L(1≤L≤N),有

(3)

其中，r是N模q的最小非負余數.

在實際系統中,相關窗口長度可能會根據信道條件的不同而變化.因此,希望跳頻序列對任何窗口長度都具有最佳的部分漢明相關性.

定義 3.1令X是F上長度為N的跳頻序列,如果對于任意相關窗長L(1≤L≤N),(3)界等號成立,則稱X為強最優的.

當L=N時,(2)和(3)界恰好是Lempel-Greenberger界.顯然,任何強最優跳頻序列關于Lempel-Greenberger界也是最優的,但反之不然.

2012年,Zhou等[2]將Peng-Fan界推廣到部分漢明相關的情形,得到如下結論.

(4)

和

(5)

2014年,Cai等[18]改進了(4)和(5)界,得到下面的推論.

(6)

和

(7)

顯然,當L=N時,定理3.2和推論3.2中的界恰好是Peng-Fan界[4].這就表明,強最優跳頻序列集關于Peng-Fan界也是最優的;反之不然.

雖然“每日優鮮”承諾兩小時送達，現在甚至90%的訂單都能在1小時內送達，但對于距離前置倉較遠的的訂單，不少顧客反映自己下單的產品在次日都未能送達。

3.2 限定部分漢明相關條件下的序列數目上界2009年,Ding等[5]基于經典的編碼理論界,得到跳頻序列集的周期漢明相關理論界.受Ding等[5]思想的啟發,Cai等[19]提出在限定部分漢明相關條件下的序列數目的上界.

設S是F上長度為N的M個跳頻序列組成的集合.Pm(L)表示S在所有長度為L的相關窗上的最大部分漢明相關函數.對于任意給定的L(1≤L≤N),將S中所有長度為L的子序列放在一起,得到一個F上參數為(L,NM,L-Pm(L);l)糾錯碼CS(L),其中

CS(L)={(ai,a〈i+1〉N,…,a〈i+L-1〉N):

{a0,a1,…,aN-1}∈S,0≤i≤N-1}.

(8)

將Plotkin界和Singleton界[27]應用到(8)式的糾錯碼CS(L)中,可得定理3.3.

定理 3.3[19]設S是由大小為q的頻隙集上的長度為N的M個跳頻序列組成的集合,則有

L>q·Pm(L)}

(9)

和

(10)

一個很自然的問題是,已知的強最優跳頻序列集對于(9)或(10)界是否也有最優的序列族大小?下面的定理給出了肯定答案.

定理3.5表示,當r≥2時,文獻[2]中的強最優跳頻序列集關于(9)界是緊的;當r=2時,關于(10)界也是緊的.

定義 3.2[17]如果對于任意的相關窗長L(1≤L≤N),(2)界等號成立,則跳頻序列X∈F稱為嚴格最優的.

當L=N時,(2)界恰好是Lempel-Greenberger界.因此,任何嚴格最優的跳頻序列,關于Lempel-Greenberger界也是最優的;反之不然.文獻[17]的跳頻序列關于Lempel-Greenberger界最優,但不是嚴格最優的.

類似于3.2中嚴格最優跳頻序列的定義,嚴格最優跳頻序列集定義如下.

定義 3.3[4]如果對于任意的相關窗長L(1≤L≤N),(4)或者(5)界等號成立,則跳頻序列集S是嚴格最優的.

當L=N時,(4)和(5)界正好是Peng-Fan界.因此,任何嚴格最優跳頻序列集關于Peng-Fan界也是最優的;反之不然.

4 基于廣義m序列和廣義GMW序列的嚴格最優跳頻序列集

vb(t)=(Trqn/q(b0αt),Trqn/q(b1αt),…,Trqn/q(bk-1αt)).

(11)

當n=2時,定理4.1給出了文獻[17]相同的參數;當n>2時,定理4.1的參數是新的.

ub(t)=(Trqn/q(b0βt),Trqn/q(b1βt),…

(12)

定義序列集

(13)

4.2 第二類最優部分漢明相關跳頻序列集設p是素數,且q=pm,r、k是正整數且滿足k|r,f(x)是GF(q)上的r次本原多項式,α是f(x)的根.設l是一正整數,且滿足l|(qr-1)和gcd(r,l)=1.定義

3) 構造跳頻序列集S={su,0≤u≤l-1}.

定理 4.3[21]由構造4.1生成的跳頻序列集S具有以下性質:

5 基于廣義分圓的強最優部分漢明相關跳頻序列(集)

本節先回顧一下廣義分圓的基本理論,然后介紹一類基于廣義分圓的強最優部分漢明相關跳頻序列(集)[18].

pi-1=efi,

且集合

對于任意的Iv1=(i1,i2,…,iπ(v1))∈Ψv1,定義

(14)

(15)

定義集合

且Iv1∈Ψv1}∪{{0}}.

(16)

Δ(x)=〈i〉e,

(17)

(18)

ii)S關于(6)和(7)界是強最優的;

iii)S中的每一條序列Si關于(3)界都是強最優的.

6 具有最優序列集大小的強最優部分漢明相關跳頻序列集設計

構造 6.1[19]令m和n是2個正整數且滿足gcd(m,n)=1.

(19)

(20)

t1=〈t〉n,t2=〈t〉m.

基于構造6.1,可以得到如下結論.

定理 6.1[19]定義序列集

(21)

1)S是由Fpr上長度為p(pr-1)的pr-1個跳頻序列組成的集合;

3) 集合S關于(6)和(10)界都是最優的.

7 基于不相交循環完美Mendelsohn差族的強最優跳頻序列設計

CPMDF[30-31]由Fuji-Hara和Miao在構造最優光正交碼時首次提出.首先,回顧CPMDF的定義.

基于不相交CPMDF,可得如下結論.

(22)

其中,0≤t1<(v-1)/k,0≤t2

下面利用循環群中的差分矩陣提出一個不相交(v,k,1)-CPMDF的遞歸構造.

定理 7.2[22]設u和v是2個正整數.如果存在一個不相交的(u,k,1)-CPMDF、一個不相交的(v,k,1)-CPMDF以及一個(v,k+1,1)-CDM,則存在一個不相交的(uv,k,1)-CPMDF.

定理 7.3[22]設v和k是2個正整數.如果v和k滿足以下條件之一:

根據定理7.1中給出的強最優跳頻序列與不相交CPMDF之間的聯系,可以得到如下結論.

推論 7.1[22]設v和k是2個正整數,當v和k滿足定理7.3的3個條件之一時,則存在定義在大小為v的頻隙集上的長度為kv的強最優跳頻序列.

8 基于多重可劃分平衡嵌套循環差填充的強最優跳頻序列集設計

8.1 一類強最優跳頻序列2004年,Fuji-Hara等[33]指出跳頻序列與可劃分循環差填充(CDP)之間的聯系.基于此,文獻[23]給出幾類強最優跳頻序列的構造.

使得

其中

K={|Br|:0≤r≤l-1}.

如果n=8a+1,則

B0={0,4a+1,8a},B1={4a-1,4a},

B1+r={r,2a-2+2r}, 1≤r≤a,

Ba+1+r={a+r,2a-1+2r}, 1≤r≤a-1,

B2a+r≡B1+r+4a+1(mod n),

1≤r≤2a-1.

如果n=8a+3,則

B0={0,4a+1,4a+2},B1={2a,6a+3},

B2={2a+1,6a+1},

B3={6a+2,6a+4},

B3+r={r,4a+1-r}, 1≤r≤2a-1,

B2a+2+r≡B3+r+4a+2(mod n),

1≤r≤2a-2.

如果n=8a+5,則

B0={0,4a+2,4a+3},

B1={2a+1,6a+5},

B2={2a+2,6a+3},B3={1,6a+4},

B3+r={2a+2+r,6a+3-r},

1≤r≤2a-1,

B2a+2+r≡B3+r+4a+3(mod n),

1≤r≤2a-1.

如果n=8a+7,則

B0={0,4a+3,4a+4},

Br={r,2a+2r}, 1≤r≤a+1,

Ba+r={a+1+r,2a+1+2r}, 1≤r≤a,

B2a+r≡Br+4a+4(modn),

1≤r≤2a+1.

利用分圓類構造可分解的CRDFs,可以得到強最優的跳頻序列.

5) 存在一個強最優的(6p,2;2p+1)跳頻序列,其中p≡5(mod 8)是素數.

8.2 強最優跳頻序列集的組合構造2009年,Ge等[34]給出跳頻序列集與可劃分平衡嵌套循環差填充(BNCDP)之間的聯系.基于上述用于設計強最優跳頻序列的組合方法,文獻[23]給出強最優跳頻序列集的組合構造.

下面利用分圓類得到一類具有特殊性質的可劃分BNCDPs,并由此得到一類新的強最優跳頻序列集的構造.

K0=…=Kf-1={e}.

推論 8.1[18]設參數v、e、f與引理8.1中的假設相同,則存在一個強最優的(ev,f,e;v)跳頻序列集S,其部分漢明相關為

8.3 強最優跳頻序列集的兩類遞歸構造第一個遞歸構造是基于循環差分矩陣(CDM)[23]的.

下面是第二類遞歸結構.

9 基于可劃分差填充的強最優跳頻序列集設計

本節介紹一類強最優跳頻序列集的構造方法[24].

1≤τ≤N-1,

其中,Bi+τ={b+τ(mod N):b∈Bi}.

Γ(B,τ)={(x,y):x-y≡τ(mod N),x,y∈B},1≤τ≤N-1.

(23)

i=0,1,…,q-1},

(24)

下面構造幾類PDPs.

B0={0,q+1,q-2},

Bj={j,2q+2-j},

B0={0,q+2,q},

B1={q+3,q+4},B2={1,2,2q+2},

B6={2q-2,6,2q+3},

Bq-4={q-4,q+8,q+1},

j≠q-4.

B0={0,q+4,q+2},

B1={q+5,q+6},

B2={1,2,2q+6},

B3={q,q+8},

B6={6,2q+2,2q+7},

B12={12,2q-4,3},

B14={14,2q-6,2q+5},

Bq-10={q+18,q-10,q+1},

Bq-8={q+16,q-8,q+7},

Bq-2={q+10,q-2,q+3},

Bi={i,2q+8-i}, 4≤i≤q-1,

i≠6,12,14,q-10,q-8,q-2.

Bi0,i1,…,im-2={i:Tr(αi)=i0,Tr(αi+1)=i1,…,

Tr(αi+m-2)=im-2,i=0,1,…,qm-2}. (25)

(26)

(27)

χ(x1,x2)=x,

B0,0={χ(0,k)f+m:k=0,1,…,e-1,m=0,1,…,f-1}

(28)

和

Bi,j={χ(ihmgk,j+k)f+m:

k=0,1,…,e-1,m=0,1,…,f-1}.

(29)

B={pm-1(pm-1)u+v:u=0,1,…,p-1,

v=0,1,…,pm-1-1},

0≤b≤pm(pm-1)-1,b?B},i∈GF(pm).

9.1 強最優跳頻序列的設計本節給出了一類強最優跳頻序列的構造.

s=(s0,s1,…,s(ξ-1)N-1),

其中

0≤i≤q-1, 0≤j≤ei-1,

0≤v≤ξ-2.

對于構造9.10生成的跳頻序列,有以下結果.

定理 9.10[24]當l=1時,由構造9.10生成的跳頻序列s是一個((ξ-1)N,qξ,Ha)跳頻序列,且最大部分漢明自相關為

其中k=1,2,…,Ha.

定理 9.11[24]通過選擇不同的PDPs,可以得到下列強最優跳頻序列:

2) 在構造9.4中選擇一個大小為q的[2q+4,{2,3},2]PDP,由構造9.10可以得到一個

((ξ-1)(2q+2),qξ,2)

3) 在構造9.5中選擇一個大小為q的[2q+8,{2,3},2]PDP,由構造9.10可以得到一個

((ξ-1)(2q+8),qξ,2)

9.2 無限類強最優跳頻序列的設計在本節中,基于構造9.10,下面給出強最優跳頻序列的遞歸構造.

定理 9.13[24]對于l=1,如果

(30)

那么,由構造生成的跳頻序列s,s1,s2,…,su都是強最優的.

根據構造9.12,得到以下結果.

定理 9.14[24]通過選擇不同的PDPs,可以得到以下強最優跳頻序列集:

3) 在構造9.8中選擇一個大小為pm的[pm(pm-1),{pm-1},p]PDP,由構造9.10可以生成一個大小為pmξ的[pm(pm-1)(ξ-1),▽′,p]PDP.那么,由構造9.12生成一個

(p(pm-1)(ξ-1),pm-1,pmξ,p)

ξ≥2m-1(2m-1),

且m≥3,則S4是強最優的.

10 結束語

跳頻序列一直是擴頻通信領域的基礎理論研究課題.跳頻序列理論包括理論界與序列設計2個方面.長期以來,跳頻序列的研究成果很豐富,但部分跳頻序列的研究結果不多.本文系統地闡述部分漢明相關跳頻序列(集)的研究成果.

表1中列出了具有最優部分漢明相關的跳頻序列(集)的參數.

表 1 具有最優部分漢明相關的跳頻序列(集)

r>1是整數,且r|gcd(e,q1-1,q2-1,…,qt-1);

d和n是正整數,p是一素數,ξ和ξ′是一素數冪;