基于分圓理論和中國剩余定理的最優平均漢明相關跳頻序列集構造

蔡紅斌，牛憲華，張秀杰

（西華大學計算機與軟件工程學院，四川 成都 610039）

跳頻通信系統的收發雙方利用載波跳變實現頻譜擴展。跳頻系統因具有抗干擾能力優異、截獲率低、抗衰落能力強等優點被廣泛應用于無線電通信、現代雷達、聲納等電子系統[1]。在跳頻通信系統中，控制載波頻率跳變的偽隨機碼稱為跳頻序列。跳頻序列的優劣對跳頻系統的性能有著決定性的影響。跳頻序列包含一些重要參數，如跳頻序列集的頻隙個數、周期長度、序列數目、序列的平均（最大）漢明自（互）相關值。通常要求跳頻序列集具有如下特點：1)平均（最大）漢明自（互）相關值要盡可能低；2)序列數目盡可能多；3)各個頻隙點出現的次數盡可能均勻；4)具有良好的隨機性和較大的線性復雜度；5)易于實現。

跳頻序列集的各參數之間相互約束，跳頻序列理論界給出了不同參數之間應滿足的約束關系。目前關于跳頻序列理論界的研究已經取得了豐富的成果[2-5]。Lempel 等[2]給出單條跳頻序列最大漢明自相關理論界；Peng 等[3]推導了跳頻序列集最大漢明相關理論界。上述2 個理論界為構造最大漢明相關最優的跳頻序列設計提供了理論基礎。Peng 等[4]指出跳頻序列的平均漢明相關可以衡量跳頻通信系統的平均誤差，更利于評價系統性能，并推導了平均漢明相關的理論界，然后基于多項式方法構造了一類滿足平均漢明相關理論界的最優跳頻序列集。Han 等[6]利用交織技術構造了一類滿足平均相關理論界最優的跳頻序列集。

分圓理論是構造最優跳頻序列的有效工具。Chu 等[7]基于有限域Fp上的分圓理論得到了一類滿足Peng-Fan 界最優的跳頻序列集。Ding 等[8]基于有限域Fpn上的分圓，得到了一類具有新參數的最優跳頻序列集。劉方等[9]基于廣義分圓理論構造了一類滿足平均漢明相關理論界最優的跳頻序列集?？缕坊莸萚10]推廣了廣義分圓理論并構造了一類滿足平均漢明相關理論界最優的跳頻序列集。Zeng 等[11]基于環上的分圓，給出了一類具有靈活參數的跳頻序列集。Xu 等[12]在文獻[11]的基礎上給出了一類最優跳頻序列集的擴展構造。

本文基于分圓理論和中國剩余定理，構造了一類具有新參數的最優平均漢明相關跳頻序列集，即根據中國剩余定理在文獻[11]的基礎上，得到一類序列長度更長且滿足Peng-Liu-Tang 界的最優平均漢明相關跳頻序列集。

1 預備知識

首先介紹本文中主要用到的一些符號。

1) 「a」：不大于a的最大整數。

2) 「a」：不小于a的最小整數。

3)v：，pi為素數，其中2 ＜p1＜p2＜ ··· ＜pk，mi是任意正整數。

4) (N,l,λ)：在大小為l的頻隙集F上，序列長度為N且最大漢明自相關值是λ的跳頻序列。

5) (N,l,λ;M)：在大小為l的頻隙集F上，序列長度為N，序列數目為M，且最大漢明互相關值是λ的跳頻序列集。

6)Zv={0,1,2,···,v-1}：一個有v個元素的模v剩余類環。

7)q：q=pn，p為任意奇素數。

8) ＜t＞n：t模n的最小非負剩余。

9)Fq：q元有限域。

10)Fq*：Fq中所有非零元的集合。

1.1 跳頻序列基本概念

令F是一個大小為l的頻隙集，S是定義在頻隙集F上，長度為N的M條跳頻序列構成的跳頻序列集。對于S內任意2 條跳頻序列xi={xi(0),xi(1),···,xi(N-1)}和xj={xj(0),xj(0),···,xj(N-1)}，0 ≤i，j≤M-1，在時延為τ時，其周期漢明相關函數定義為

其中當a=b時，h(a,b)=1，否則，h(a,b)=0。下標r+τ 按模N運算。

對所有0 ≤r＜N，若=，則xi=xj，否則xi≠xj；若xi=xj，這種情況下稱Hxixj(τ)為序列的漢明自相關函數；若xi≠xj，則稱Hxixj(τ)為序列集S的漢明互相關函數。跳頻序列集S的最大漢明自相關Ha(S)、最大漢明互相關Hc(S)和最大漢明相關H(S)定義為：

簡記：λa=Ha(S)，λc=Hc(S)，λ=H(S)。

理論界是評價跳頻序列（集）優劣性的一個重要指標，對序列設計起指導作用。

1974 年，Lempel 和Greenberger 給出了跳頻序列周期漢明自相關理論界。

引理1[2] (Lempel-Greenberger 界)對于一個定義在大小為l頻隙集F上，長度為N的跳頻序列X，其最大漢明自相關滿足

其中ε是N模l的最小非負剩余。

如果一個(N,l,λ)跳頻序列X的最大漢明自相關滿足不等式(1)的最小整數解，則稱其為最優跳頻序列。

2004 年，Peng 和Fan 給出了跳頻序列集最大漢明相關理論界。

引理2[3] (Peng-Fan 界)設F是一個大小為l的頻隙集，對于一個定義在頻隙集F上的M個長度為N的跳頻序列構成的跳頻序列集S，其最大漢明相關滿足

如果跳頻序列集S的最大漢明相關是不等式(2)的最小整數解，則該跳頻序列集可以被稱作最優跳頻序列集。

作為衡量跳頻序列集性能的重要參數，跳頻序列平均漢明自相關和平均漢明互相關的定義在2010 年Peng 等[4]給出。

定義1[6]設F是一個大小為l的頻隙集，對于一個定義在頻隙集F上的M個長度為N的跳頻序列構成的跳頻序列集S有

它們分別是序列集S的漢明自相關的總和、漢明互相關的總和。序列集S的平均漢明自相關和互相關分別是：

引理3[4]設F是一個大小為l的頻隙集，對于一個定義在頻隙集F上的M個長度為N的跳頻序列構成的跳頻序列集S，則有不等式

式中Aa和Ac分別是序列集S的平均漢明自相關和平均漢明互相關。如果跳頻序列集S的平均漢明相關值滿足不等式(3)的等號成立，則該跳頻序列集可以被稱為滿足平均最優的跳頻序列集。

推論1設F是一個大小為l的頻隙集，對于一個定義在頻隙集F上的長度為N的跳頻序列X，有

推論1 的結果可以由文獻[2]中引理4 得出。

1.2 有限域上的分圓

2008 年Ding 等[8]給出了有限域Fq上的分圓，本節將簡單介紹有限域上的分圓理論。設q=pn=ef+1，其中p是一個素數，n是一個正整數，e＞ 1。設α是Fq的一個本原根，則Fq*可劃分為一個e階分圓類，該分圓類定義為

設對于正整數N，模N剩余類環ZN={0,1,2,···,N-1}。對于a∈ZN，令D為ZN的一個子集，定義

對于任意點x∈Ci，y∈Cj，0 ≤i≠j＜e，定義方程x-y=1 的解是e階分圓類的e階分圓數，對于任意i和j，也可將e階分圓數表示為

引理4定義的e階分圓數具有如下基本性質：

1.3 環上的分圓

2013 年，Zeng 等[11]給出了環上的分圓。

根據中國剩余定理可得：

對于模v剩余類環Zv={0,1,2,···,v-1}，令A是Zv的一個子集，b是Zv中的一個元素，則有：

設v1表示v的一個因子，根據中國剩余定理，存在一個整數 ωv1滿足模v1乘法階是e1。定義D(v1)={|0 ≤d≤e1-1}，故可知D(v1)是的一個循環子群且階為e1。

下面定義集合Ωv，為

引理5對于任意的v1,v1是v的一個因子，可知

2 跳頻序列集的構造

本節基于環上的分圓理論和中國剩余定理給出了一類跳頻序列集的構造，并證明了所構造的跳頻序列集滿足平均漢明相關理論界最優。

設n是一個正整數且n小于v。由中國剩余定理可知，當n不能被v整除時，Znv中任意一元素h,都可寫成Zn×Zv中的一個元素(h1,h2),其中h1=＜h＞n,h2=＜h＞v。

基于環上分圓的性質，可以給出新的跳頻序列集的構造方法。

定理1根據構造方法構造的跳頻序列集有如下性質。

1）構造得到跳頻序列集的序列長度為n(v-1)，頻隙點個數為，跳頻序列集S平均自相關和互相關總和分別是：

2）由構造得到的跳頻序列集S滿足平均漢明相關理論界最優。

證明1) 定義＜τ1＞n,＜τ2＞v-1，xs，xr是跳頻序列集S里任意2 條序列

為求2 條序列的漢明相關性，將上面討論的結果τ1,τ2的取值分成4 種情況考慮。

情況1，當τ1=0，τ2=0 時，由g是二元單射,得到

情況2，當τ1≠ 0，τ2=0 時，由g是二元單射,得到

情況3，當τ1=0，τ2≠ 0 時，由g是二元單射,得到

情況4，當τ1≠ 0，τ2≠ 0 時，由g是二元單射，得到

上面討論的是序列集的漢明互相關總和，即s≠r的情況。當s=r時，在τ1=0，τ2≠ 0 的情況下。其余情況下和互相關結果相同。故綜合上面各種情況，可以得到：

2) 根據分圓的性質，漢明自（互）相關的總和是在所有時延下各頻點碰撞次數的總和。結合構造得到的跳頻序列集頻點個數為，由性質1)可得，漢明自相關總和互相關總和分別為：

故平均漢明自（互）相關為：

接下來證明跳頻序列集S關于平均漢明相關理論界是最優的。

將式(4)、式(5)代入平均漢明相關理論界不等式（3）中，可得

故可得結論

充分發揮訴前程序作用。牢牢把握“訴訟不是目的、維護公益才是目的”的價值目標，將工作的重點放在訴前督促整改環節，督促行政機關履職。通過發出檢察建議、約談、走訪、訴前圓桌會議、訴訟風險提示等方式，督促行政機關整改糾錯，全面履行法定職責。三年來，全省檢察機關共向行政機關發出督促履職檢察建議6577件，各地政府職能部門積極整改、主動履職，訴前整改率從2016年的69%上升到目前的93.4%。

構造中結果可使等號成立，故滿足理論界要求，因此跳頻序列集關于平均相關理論界是最優的。證畢。

例當v=247=13×19 時，v1∈{13，19，247}，e1是12 與18 的公因子，取e1=2 故f1=6，又可知2 是13，19 的公共本原根。

根據構造，可以給出集合A為

x1={107,19,85,38,61,85,105,57,53,61,2,6,116,7,29,76,27,53,122,80,55,40,64,25,94,109,3,26,70,29,60,95,···,95,60,29,70,26,3,109,94,25,64,40,55,80,122,53,27,76,29,7,116,6,2,61,53,57,105,85,61,38,85,19,107}

x2={69,107,47,0,23,47,67,19,15,23,72,76,114,77,99,38,97,15,120,42,35,2,26,95,56,116,73,96,32,99,22,···,22,99,32,96,73,116,56,95,26,2,35,42,120,15,97,38,99,77,114,76,72,23,15,19,67,47,23,0,47,107,69}

x3={31,69,9,88,93,9,29,107,85,93,52,38,112,39,61,0,59,85,118,4,105,72,96,57,18,114,53,58,102,61,92,···，92,61,102,58,53,114,18,57,96,72,105,4,118,85,59,0,61,39,112,38,52,93,85,107,29,9,93,88,9,69,31}

經計算，例構造的長度為492，頻點個數為123，序列大小為3 的跳頻序列集的平均漢明自相關值和平均漢明互相關值分別是3.006 109 979 63和4，代入平均漢明相關理論界，滿足理論界最優。故跳頻序列集S是一個滿足平均漢明相關理論界最優的跳頻序列集。

3 結論

表1 分圓法構造跳頻序列集的參數比較