基于分圓理論和中國剩余定理的最優(yōu)平均漢明相關(guān)跳頻序列集構(gòu)造

蔡紅斌，牛憲華，張秀杰

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039）

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

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

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

本文基于分圓理論和中國剩余定理，構(gòu)造了一類具有新參數(shù)的最優(yōu)平均漢明相關(guān)跳頻序列集，即根據(jù)中國剩余定理在文獻(xiàn)[11]的基礎(chǔ)上，得到一類序列長度更長且滿足Peng-Liu-Tang 界的最優(yōu)平均漢明相關(guān)跳頻序列集。

1 預(yù)備知識(shí)

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

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

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

3)v：，pi為素?cái)?shù)，其中2 ＜p1＜p2＜ ··· ＜pk，mi是任意正整數(shù)。

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

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

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

7)q：q=pn，p為任意奇素?cái)?shù)。

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

9)Fq：q元有限域。

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

1.1 跳頻序列基本概念

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

其中當(dāng)a=b時(shí)，h(a,b)=1，否則，h(a,b)=0。下標(biāo)r+τ 按模N運(yùn)算。

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

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

理論界是評價(jià)跳頻序列（集）優(yōu)劣性的一個(gè)重要指標(biāo)，對序列設(shè)計(jì)起指導(dǎo)作用。

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

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

其中ε是N模l的最小非負(fù)剩余。

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

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

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

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

作為衡量跳頻序列集性能的重要參數(shù)，跳頻序列平均漢明自相關(guān)和平均漢明互相關(guān)的定義在2010 年P(guān)eng 等[4]給出。

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

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

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

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

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

推論1 的結(jié)果可以由文獻(xiàn)[2]中引理4 得出。

1.2 有限域上的分圓

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

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

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

引理4定義的e階分圓數(shù)具有如下基本性質(zhì)：

1.3 環(huán)上的分圓

2013 年，Zeng 等[11]給出了環(huán)上的分圓。

根據(jù)中國剩余定理可得：

對于模v剩余類環(huán)Zv={0,1,2,···,v-1}，令A(yù)是Zv的一個(gè)子集，b是Zv中的一個(gè)元素，則有：

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

下面定義集合Ωv，為

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

2 跳頻序列集的構(gòu)造

本節(jié)基于環(huán)上的分圓理論和中國剩余定理給出了一類跳頻序列集的構(gòu)造，并證明了所構(gòu)造的跳頻序列集滿足平均漢明相關(guān)理論界最優(yōu)。

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

基于環(huán)上分圓的性質(zhì)，可以給出新的跳頻序列集的構(gòu)造方法。

定理1根據(jù)構(gòu)造方法構(gòu)造的跳頻序列集有如下性質(zhì)。

1）構(gòu)造得到跳頻序列集的序列長度為n(v-1)，頻隙點(diǎn)個(gè)數(shù)為，跳頻序列集S平均自相關(guān)和互相關(guān)總和分別是：

2）由構(gòu)造得到的跳頻序列集S滿足平均漢明相關(guān)理論界最優(yōu)。

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

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

情況1，當(dāng)τ1=0，τ2=0 時(shí)，由g是二元單射,得到

情況2，當(dāng)τ1≠ 0，τ2=0 時(shí)，由g是二元單射,得到

情況3，當(dāng)τ1=0，τ2≠ 0 時(shí)，由g是二元單射,得到

情況4，當(dāng)τ1≠ 0，τ2≠ 0 時(shí)，由g是二元單射，得到

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

2) 根據(jù)分圓的性質(zhì)，漢明自（互）相關(guān)的總和是在所有時(shí)延下各頻點(diǎn)碰撞次數(shù)的總和。結(jié)合構(gòu)造得到的跳頻序列集頻點(diǎn)個(gè)數(shù)為，由性質(zhì)1)可得，漢明自相關(guān)總和互相關(guān)總和分別為：

故平均漢明自（互）相關(guān)為：

接下來證明跳頻序列集S關(guān)于平均漢明相關(guān)理論界是最優(yōu)的。

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

故可得結(jié)論

充分發(fā)揮訴前程序作用。牢牢把握“訴訟不是目的、維護(hù)公益才是目的”的價(jià)值目標(biāo)，將工作的重點(diǎn)放在訴前督促整改環(huán)節(jié)，督促行政機(jī)關(guān)履職。通過發(fā)出檢察建議、約談、走訪、訴前圓桌會(huì)議、訴訟風(fēng)險(xiǎn)提示等方式，督促行政機(jī)關(guān)整改糾錯(cuò)，全面履行法定職責(zé)。三年來，全省檢察機(jī)關(guān)共向行政機(jī)關(guān)發(fā)出督促履職檢察建議6577件，各地政府職能部門積極整改、主動(dòng)履職，訴前整改率從2016年的69%上升到目前的93.4%。

構(gòu)造中結(jié)果可使等號成立，故滿足理論界要求，因此跳頻序列集關(guān)于平均相關(guān)理論界是最優(yōu)的。證畢。

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

根據(jù)構(gòu)造，可以給出集合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}

經(jīng)計(jì)算，例構(gòu)造的長度為492，頻點(diǎn)個(gè)數(shù)為123，序列大小為3 的跳頻序列集的平均漢明自相關(guān)值和平均漢明互相關(guān)值分別是3.006 109 979 63和4，代入平均漢明相關(guān)理論界，滿足理論界最優(yōu)。故跳頻序列集S是一個(gè)滿足平均漢明相關(guān)理論界最優(yōu)的跳頻序列集。

3 結(jié)論

表1 分圓法構(gòu)造跳頻序列集的參數(shù)比較