黃 波 張小華

(成都東軟學(xué)院 四川 成都 611844)

一類跳頻序列集的最優(yōu)構(gòu)造

黃 波 張小華

(成都東軟學(xué)院 四川 成都 611844)

跳頻擴(kuò)頻是主要的擴(kuò)頻編碼技術(shù)之一，跳頻序列在跳頻碼分多址系統(tǒng)中的作用至關(guān)重要。分圓理論由于具有良好的特性，在組合設(shè)計(jì)、良好的二元隨機(jī)序列設(shè)計(jì)中得到了廣泛應(yīng)用?；诜謭A理論，構(gòu)造了一類關(guān)于Peng-Fan界最優(yōu)的跳頻序列集，節(jié)省了一個(gè)頻隙，豐富了跳頻序列集的構(gòu)造方法。結(jié)果表明，該構(gòu)造方法簡(jiǎn)單易行，對(duì)跳頻通信系統(tǒng)性能的提高具有一定的指導(dǎo)意義。

跳頻序列集 彭-范界 分圓理論 周期漢明相關(guān) 碼分多址

0 引 言

在無(wú)線通信系統(tǒng)中，跳頻擴(kuò)頻和直接序列擴(kuò)頻是兩種主要的擴(kuò)頻技術(shù)。跳頻碼分多址由于具有安全性、抗多址干擾等特性，其在藍(lán)牙、軍事無(wú)線電通信、移動(dòng)通信以及現(xiàn)代雷達(dá)、聲吶系統(tǒng)中得到了廣泛應(yīng)用[1]。通常情況下，如果兩個(gè)或多個(gè)發(fā)送者在同一時(shí)隙發(fā)送相同的頻隙，那么就產(chǎn)生了一次碰撞，相互之間的干擾就產(chǎn)生了。跳頻序列用來(lái)指定在每個(gè)時(shí)隙被傳輸?shù)念l隙，所以，多個(gè)發(fā)送者之間的相互干擾與跳頻序列之間的漢明相關(guān)是密切相關(guān)的，因而選擇碰撞次數(shù)少的跳頻序列(跳頻序列集)有利于跳頻通信系統(tǒng)性能的提高。好的跳頻序列(跳頻序列集)應(yīng)具有以下特征：盡可能小的漢明相關(guān)特性；好的平衡性；盡可能長(zhǎng)的周期；盡可能多的序列數(shù)目；盡可能大的復(fù)雜度；實(shí)現(xiàn)簡(jiǎn)單。

目前，一部分最優(yōu)的跳頻序列集已被學(xué)者們進(jìn)行了廣泛而深入的研究，例如：2011年，Zhou等[2]利用d型函數(shù)及線性方程組的解等相關(guān)知識(shí)構(gòu)造了三類關(guān)于Peng-Fan界[3]最優(yōu)的跳頻序列集，并討論了所構(gòu)造序列集的線性復(fù)雜度；2010年，Ding等[4]提出了基于編碼理論構(gòu)造跳頻序列集的方法，拓展了跳頻序列集設(shè)計(jì)的方法，其他構(gòu)造方法請(qǐng)參考相關(guān)文獻(xiàn)。分圓類在組合設(shè)計(jì)，二元序列設(shè)計(jì)中得到了廣泛的運(yùn)用，學(xué)者們對(duì)利用分圓理論來(lái)構(gòu)造最優(yōu)跳頻序列集進(jìn)行了相應(yīng)研究。對(duì)于有限域Fq，q是素?cái)?shù)或素?cái)?shù)方冪，令q-1=ef,2005年，Chu等[5]首次利用分圓理論構(gòu)造出了兩類關(guān)于Lempel-Greenberger 界[6]最優(yōu)的跳頻序列，其序列長(zhǎng)度為q，頻隙個(gè)數(shù)為e+1；之后，基于分圓理論的跳頻序列集基本上是在Chu方法上的引申；2008年，基于分圓理論和離散對(duì)數(shù)函數(shù),Ding等[7]提出了一種最優(yōu)的跳頻序列設(shè)計(jì)方法，構(gòu)造的序列長(zhǎng)度為q-1，頻隙個(gè)數(shù)為e+1；2009年，Zhang等[8]利用分圓理論、離散對(duì)數(shù)函數(shù)以及中國(guó)剩余定理,構(gòu)造出了一類最優(yōu)的跳頻序列以及跳頻序列集，序列長(zhǎng)度為2(q-1)頻隙個(gè)數(shù)為e+1；對(duì)于素?cái)?shù)p，2013年WenliRen[9]推廣了Zhang和Ding的方法，構(gòu)造出了一類最優(yōu)的跳頻序列集，序列的長(zhǎng)度為p(q-1)，頻隙個(gè)數(shù)為e+1。2013年Liu等[10]提出了一種關(guān)于平均周期漢明相關(guān)界最優(yōu)的跳頻序列集, 同時(shí)研究了所構(gòu)造的跳頻序列集的漢明相關(guān)分布。本文中，我們利用分圓理論，提出了一種關(guān)于Peng-Fan界[3]最優(yōu)的跳頻序列集，序列的長(zhǎng)度為q，頻隙個(gè)數(shù)為e，顯然，我們的方法節(jié)省了一個(gè)頻隙，構(gòu)造簡(jiǎn)單易行，具有一定的參考價(jià)值。

1 基本概念

在本文中，我們用符號(hào)(N,M,q,λ)表示長(zhǎng)度為N，具有M個(gè)跳頻序列，頻隙集中頻隙個(gè)數(shù)為q，最大周期漢明相關(guān)為λ的跳頻序列集。用符號(hào)(l,q,h)表示長(zhǎng)度為l，頻隙集中頻隙個(gè)數(shù)為q，最大周期漢明自相關(guān)為h的跳頻序列。

令F={f1,f2,…,fq}是一個(gè)具有q個(gè)頻隙的頻隙集,S是一個(gè)具有M個(gè)長(zhǎng)度為N的跳頻序列集,對(duì)于任意兩個(gè)頻隙f1、f2,令：

(1)

對(duì)于任意兩個(gè)跳頻序列x=(x0,x1,…,xN-1),y=(y0,y1,…,yN-1), 任意正整數(shù)τ，N0≤τ≤N，序列x和y在時(shí)延τ時(shí)的周期漢明相關(guān)定義如下：

(2)

這里，所有的下標(biāo)運(yùn)算都是在模N下進(jìn)行的。

對(duì)于任意給定的跳頻序列集S，最大周期漢明自相關(guān)Ha(S)和最大周期漢明互相關(guān)Hc(S)分別定義如下：

(3)

最大周期漢明相關(guān)Hm(S)定義如下：

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

(4)

1974年，LempelandGreenberger[6]建立了關(guān)于單個(gè)跳頻序列漢明自相關(guān)的理論界。

引理1(Lempel-Greenberger界[6])：對(duì)于長(zhǎng)度為N，定義在具有q個(gè)頻隙的頻隙集上的任意跳頻序列，漢明自相關(guān)滿足下面的界：

(5)

這里，r是N模q的最小非負(fù)剩余。顯然，Lempel-Greenberger界沒有涉及跳頻序列的個(gè)數(shù)。

定義1 對(duì)于任意跳頻序列(l,q,h)，若h-1使Lempel-Greenberger界(5)中的等號(hào)成立，則該序列關(guān)于Lempel-Greenberger界是漸進(jìn)最優(yōu)的。

2004年，PengandFan[3]引入跳頻序列個(gè)數(shù)M，建立了在跳頻序列集設(shè)計(jì)中廣泛使用的關(guān)于最大周期漢明相關(guān)的理論界。

引理2(PengandFan界[3])：令S是一個(gè)長(zhǎng)度為N，具有M個(gè)跳頻序列，定義在具有q個(gè)頻隙的頻隙集上的跳頻序列集，我們有：

(6)

和：

(7)

定義2 對(duì)于任意跳頻序列集(N,M,q,λ)，若λ使PengandFan界(式(6)、式(7))中的等號(hào)成立，則該跳頻序列集關(guān)于PengandFan界是最優(yōu)的。

2 最優(yōu)跳頻序列集構(gòu)造

該部分，我們利用分圓理論[11]構(gòu)造了一類關(guān)于Peng-Fan界最優(yōu)的跳頻序列集。

令Fq是一個(gè)具有q個(gè)元素的有限域，同時(shí)設(shè)存在兩個(gè)正整數(shù)e和f，滿足ef=q-1,α是有限域Fq的一個(gè)本原元。C0=〈αe〉是由αe產(chǎn)生的Fq的乘法子群，有限域Fq的e階分圓類定義如下：

Ci={αi+ks:i=0,…,e-1;k=0,…,f-1}

(8)

對(duì)于0≤i≠j≤e-1,有：

(9)

對(duì)于任意正整數(shù)n，Ci+ne=Ci。進(jìn)一步，關(guān)于有限域Fq的e階分圓數(shù)定義如下：

(10)

顯然，最多有e2個(gè)不同的e階分圓數(shù)。

我們將會(huì)利用下面的引理來(lái)計(jì)算所設(shè)計(jì)的跳頻序列集的漢明自相關(guān)和漢明互相關(guān)。

引理3 令q=ef+1是一個(gè)素?cái)?shù)或素?cái)?shù)方冪，Ci是有限域Fq的e階分圓類，我們有：

(11)

本文構(gòu)造最優(yōu)跳頻序列集的方法如下：

Step1 選擇一個(gè)素?cái)?shù)或素?cái)?shù)方冪q，選擇兩個(gè)正整數(shù)e和f，滿足q-1=ef，設(shè)Ci是有限域 Fq的e階分圓類。

Step2 對(duì)于0≤i≤e-1，利用分圓類Ci得到如下的數(shù)集

顯然下式成立：

(12)

(13)

其中：0≤k≤e-1。

定理1 根據(jù)Peng-Fan界，我們有：如果λ∈Ze,當(dāng)f是偶數(shù)時(shí),S是一個(gè)最優(yōu)的跳頻序列集，其參數(shù)為(q,e,e,f+1)。根據(jù)Lempel-Greenberger界：跳頻序列集S中的每個(gè)跳頻序列是漸進(jìn)最優(yōu)的。

=f-1+Δ

(14)

下面我們確定Δ的值。

1) 如果τ和-τ均屬于分圓類Ci0。

Hsi(τ)=f+1

(15)

2) τ和-τ之一屬于Ci0，或者τ和-τ均不屬于Ci0。

因?yàn)棣尤”閧1,2,…,q-1}中的每個(gè)值，顯然存在這樣的τ，使這兩種情況都成立，所以：

(16)

對(duì)于0≤u≤e-1，令si、si+u是跳頻序列集S中的任意兩個(gè)跳頻序列，根據(jù)周期漢明互相關(guān)的定義，在時(shí)延τ時(shí)，我們有：

(17)

為了計(jì)算Hsi,si+u(τ)的值，我們分以下三種情況討論。

1) 當(dāng)τ跑遍{1,2,…,q-1}時(shí)，若存在τ，使τ∈Ci0+u，且-τ∈Ci0-u成立，則必有：

(18)

所以：

(19)

Hsi,si+u(τ)=f

(20)

2) 當(dāng)τ跑遍{1,2,…,q-1}時(shí)，存在l≡i0+umode，使得τ∈Ci0+u。

Hsi,si+u(τ)=f+1

(21)

Hsi,si+u(τ)=f+1

(22)

基于以上分析，跳頻序列集S的最大周期漢明相關(guān)為：

Hm(S)=f+1 0≤τ≤q-1

(23)

下面分析跳頻序列集S關(guān)于Peng-Fan界是最優(yōu)的。把相關(guān)參數(shù)代入Peng-Fan界有：

(24)

顯然，達(dá)到了Peng-Fan界的下界，所以關(guān)于Peng-Fan界，S是最優(yōu)的跳頻序列集。

由于對(duì)于任意的q，均有q≡1mode，故r=1。把相關(guān)參數(shù)代入Lempel-Greenberger界有：

(25)

其中，Hm(S)-1使Lempel-Greenberger界中的等號(hào)成立，故S中的每個(gè)跳頻序列是漸進(jìn)最優(yōu)的。

定理得證。

令S(19)=2，得到長(zhǎng)度為19，個(gè)數(shù)為3，定義在有限域F19上的跳頻序列集為:

對(duì)于時(shí)延τ，0≤τ≤18，漢明相關(guān)分別如下：

漢明自相關(guān)為：

Hs1(τ)={5,5,5,7,5,7,5,5,7,7,5,5,7,5,7,5,5,5}

Hs2(τ)={7,5,5,5,5,5,7,7,5,5,7,7,5,5,5,5,5,7}

Hs3(τ)={5,7,7,5,7,5,5,5,5,5,5,5,5,7,5,7,7,5}

漢明互相關(guān)為：

Hs1,s2(τ)={7,6,6,7,6,7,7,7,7,7,7,7,7,6,7,6,6,7,1}

Hs1,s3(τ)={6,7,7,7,7,7,6,6,7,7,6,6,7,7,7,7,7,6,1}

Hs2,s1(τ)={7,6,6,7,6,7,7,7,7,7,7,7,7,6,7,6,6,7,1}

Hs2,s3(τ)={7,7,7,6,7,6,7,7,6,6,7,7,6,7,6,7,7,7,1}

Hs3,s1(τ)={7,7,7,6,7,6,7,7,6,6,7,7,6,7,6,7,7,7,1}

Hs3,s2(τ)={6,7,7,7,7,7,6,6,7,7,6,6,7,7,7,7,7,6,1}

最大周期漢明相關(guān)為：

Hm(S)=7

可以驗(yàn)證，關(guān)于Peng-Fan界，S是最優(yōu)的跳頻序列集。關(guān)于Lempel-Greenberger界，S中每個(gè)跳頻序列是漸進(jìn)最優(yōu)的。

3 結(jié) 語(yǔ)

基于分圓理論，提出了一種關(guān)于Peng-Fan界最優(yōu)的跳頻序列集的構(gòu)造方法。本文所構(gòu)造的跳頻序列集與參考文獻(xiàn)中所構(gòu)造的跳頻序列集的相關(guān)比較如表1所示。

表1 本文構(gòu)造的跳頻序列集與已知跳頻序列集的比較

本文方法簡(jiǎn)單易行，豐富了跳頻序列集的構(gòu)造方法。利用分圓理論構(gòu)造更多最優(yōu)的其它類跳頻序列集將是我們進(jìn)一步研究的內(nèi)容。

[1] Fan P Z,Darnell M.Sequence Design for Communications Applications[M].Research Studies Press (RSP),Wiley,London (1996).

[2] Zhengchun Zhou,Xiaohu Tang,Daiyuan Peng,et al.New constructions for optimal sets of frequency hopping sequences[J].IEEE Transactions On Inform.Theory,2011,57(6):3831-3840.

[3] Daiyuan Peng,Pingzhi Fan.Lower bounds on the Hamming auto-and cross correlations of frequency-hopping sequences[J].IEEE Transactions on Information Theory,2004,50(9):2149-2154.

[4] Cunsheng Ding,FujiHara,R Fujiwara,et al.Sets of frequency hopping sequences:bounds and optimal constructions[J].IEEE Trans Inform Theory,2009,55(7):3297-3304.

[5] Chu W,Colbourn C J.Optimal frequency-hopping sequences via Cyclotomy[J].IEEE Transactions on Information Theory,2005,51(3):1139-1141.

[6] Lempel A,Greenberger H.Families of sequences with optimal Hamming correlation properties[J].IEEE Transactions on Information Theory,1974,20(1):90-94.

[7] Cunsheng Ding,Jianxing Yin.Sets of optimal frequency-hopping sequences[J].IEEE Transactions on Information Theory,2008,54(8):3741-3745.

[8] Yun Zhang,Pinhui Ke,Shengyuan Zhang.Optimal frequency hopping sequences based on Cyclotomy[C]//First International Workshop on Education Technology and Computer Science,2009,1:1122-1126.

[9] Wenli Ren,Fangwei Fu,Zhengchun Zhou.New sets of frequency-hopping sequences with optimal Hamming correlation[J].Des.Codes Cryptogr,2014,72(2):423-434.

[10] Fang Liu,Daiyuan Peng,Zhengchun Zhou.A new frequency-hopping sequence set based upon generalized Cyclotomy[J].Des. Codes Cryptogr,2012,69(2):247-259.

[11] Storer T.Cyclotomy and Difference Sets[M].Chicago,IL:Markham,1967.

[12] 徐善頂,曹喜望,許廣魁.一類周期為素?cái)?shù)倍數(shù)的跳頻序列集[J].電子學(xué)報(bào),2015,43(10):1930-1935.

OPTIMAL CONSTRUCTION OF FREQUENCY-HOPPING SEQUENCE SETS

Huang Bo Zhang Xiaohua

(ChengduNeusoftUniversity,Chengdu611844,Sichuan,China)

Frequency-hopping (FH) spread spectrum is one of the main spread spectrum coding technologies. Furthermore, frequency-hopping sequences (FHS) play important roles in FH code division multiple access systems. Due to its good characteristics, the cyclotomy has been widely used in combinatorial designs and good designs of binary random sequences. Based on cyclotomy, a class of FHS set with Peng-Fan bounds is constructed, which can save a frequency gap and enrich the construction methods of FHS sets. The results show that this method is simple and easy to be implemented, and it has a certain guiding significance for improving the performance of FH communication system.

Frequency hopping sequence set Peng-Fan bound Cyclotomy Periodic hamming correlation Code division multiple access

2016-03-08。黃波，講師，主研領(lǐng)域：網(wǎng)絡(luò)通信，數(shù)字圖像處理，軟件工程。張小華，講師。

TP393.04

A

10.3969/j.issn.1000-386x.2017.03.022