黄 波 张小华

(成都东软学院 四川 成都 611844)

一类跳频序列集的最优构造

黄 波 张小华

(成都东软学院 四川 成都 611844)

跳频扩频是主要的扩频编码技术之一，跳频序列在跳频码分多址系统中的作用至关重要。分圆理论由于具有良好的特性，在组合设计、良好的二元随机序列设计中得到了广泛应用。基于分圆理论，构造了一类关于Peng-Fan界最优的跳频序列集，节省了一个频隙，丰富了跳频序列集的构造方法。结果表明，该构造方法简单易行，对跳频通信系统性能的提高具有一定的指导意义。

跳频序列集 彭-范界 分圆理论 周期汉明相关 码分多址

0 引 言

在无线通信系统中，跳频扩频和直接序列扩频是两种主要的扩频技术。跳频码分多址由于具有安全性、抗多址干扰等特性，其在蓝牙、军事无线电通信、移动通信以及现代雷达、声呐系统中得到了广泛应用[1]。通常情况下，如果两个或多个发送者在同一时隙发送相同的频隙，那么就产生了一次碰撞，相互之间的干扰就产生了。跳频序列用来指定在每个时隙被传输的频隙，所以，多个发送者之间的相互干扰与跳频序列之间的汉明相关是密切相关的，因而选择碰撞次数少的跳频序列(跳频序列集)有利于跳频通信系统性能的提高。好的跳频序列(跳频序列集)应具有以下特征：尽可能小的汉明相关特性；好的平衡性；尽可能长的周期；尽可能多的序列数目；尽可能大的复杂度；实现简单。

目前，一部分最优的跳频序列集已被学者们进行了广泛而深入的研究，例如：2011年，Zhou等[2]利用d型函数及线性方程组的解等相关知识构造了三类关于Peng-Fan界[3]最优的跳频序列集，并讨论了所构造序列集的线性复杂度；2010年，Ding等[4]提出了基于编码理论构造跳频序列集的方法，拓展了跳频序列集设计的方法，其他构造方法请参考相关文献。分圆类在组合设计，二元序列设计中得到了广泛的运用，学者们对利用分圆理论来构造最优跳频序列集进行了相应研究。对于有限域Fq，q是素数或素数方幂，令q-1=ef,2005年，Chu等[5]首次利用分圆理论构造出了两类关于Lempel-Greenberger 界[6]最优的跳频序列，其序列长度为q，频隙个数为e+1；之后，基于分圆理论的跳频序列集基本上是在Chu方法上的引申；2008年，基于分圆理论和离散对数函数,Ding等[7]提出了一种最优的跳频序列设计方法，构造的序列长度为q-1，频隙个数为e+1；2009年，Zhang等[8]利用分圆理论、离散对数函数以及中国剩余定理,构造出了一类最优的跳频序列以及跳频序列集，序列长度为2(q-1)频隙个数为e+1；对于素数p，2013年WenliRen[9]推广了Zhang和Ding的方法，构造出了一类最优的跳频序列集，序列的长度为p(q-1)，频隙个数为e+1。2013年Liu等[10]提出了一种关于平均周期汉明相关界最优的跳频序列集, 同时研究了所构造的跳频序列集的汉明相关分布。本文中，我们利用分圆理论，提出了一种关于Peng-Fan界[3]最优的跳频序列集，序列的长度为q，频隙个数为e，显然，我们的方法节省了一个频隙，构造简单易行，具有一定的参考价值。

1 基本概念

在本文中，我们用符号(N,M,q,λ)表示长度为N，具有M个跳频序列，频隙集中频隙个数为q，最大周期汉明相关为λ的跳频序列集。用符号(l,q,h)表示长度为l，频隙集中频隙个数为q，最大周期汉明自相关为h的跳频序列。

令F={f1,f2,…,fq}是一个具有q个频隙的频隙集,S是一个具有M个长度为N的跳频序列集,对于任意两个频隙f1、f2,令：

(1)

对于任意两个跳频序列x=(x0,x1,…,xN-1),y=(y0,y1,…,yN-1), 任意正整数τ，N0≤τ≤N，序列x和y在时延τ时的周期汉明相关定义如下：

(2)

这里，所有的下标运算都是在模N下进行的。

对于任意给定的跳频序列集S，最大周期汉明自相关Ha(S)和最大周期汉明互相关Hc(S)分别定义如下：

(3)

最大周期汉明相关Hm(S)定义如下：

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

(4)

1974年，LempelandGreenberger[6]建立了关于单个跳频序列汉明自相关的理论界。

引理1(Lempel-Greenberger界[6])：对于长度为N，定义在具有q个频隙的频隙集上的任意跳频序列，汉明自相关满足下面的界：

(5)

这里，r是N模q的最小非负剩余。显然，Lempel-Greenberger界没有涉及跳频序列的个数。

定义1 对于任意跳频序列(l,q,h)，若h-1使Lempel-Greenberger界(5)中的等号成立，则该序列关于Lempel-Greenberger界是渐进最优的。

2004年，PengandFan[3]引入跳频序列个数M，建立了在跳频序列集设计中广泛使用的关于最大周期汉明相关的理论界。

引理2(PengandFan界[3])：令S是一个长度为N，具有M个跳频序列，定义在具有q个频隙的频隙集上的跳频序列集，我们有：

(6)

和：

(7)

定义2 对于任意跳频序列集(N,M,q,λ)，若λ使PengandFan界(式(6)、式(7))中的等号成立，则该跳频序列集关于PengandFan界是最优的。

2 最优跳频序列集构造

该部分，我们利用分圆理论[11]构造了一类关于Peng-Fan界最优的跳频序列集。

令Fq是一个具有q个元素的有限域，同时设存在两个正整数e和f，满足ef=q-1,α是有限域Fq的一个本原元。C0=〈αe〉是由αe产生的Fq的乘法子群，有限域Fq的e阶分圆类定义如下：

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

(8)

对于0≤i≠j≤e-1,有：

(9)

对于任意正整数n，Ci+ne=Ci。进一步，关于有限域Fq的e阶分圆数定义如下：

(10)

显然，最多有e2个不同的e阶分圆数。

我们将会利用下面的引理来计算所设计的跳频序列集的汉明自相关和汉明互相关。

引理3 令q=ef+1是一个素数或素数方幂，Ci是有限域Fq的e阶分圆类，我们有：

(11)

本文构造最优跳频序列集的方法如下：

Step1 选择一个素数或素数方幂q，选择两个正整数e和f，满足q-1=ef，设Ci是有限域 Fq的e阶分圆类。

Step2 对于0≤i≤e-1，利用分圆类Ci得到如下的数集

显然下式成立：

(12)

(13)

其中：0≤k≤e-1。

定理1 根据Peng-Fan界，我们有：如果λ∈Ze,当f是偶数时,S是一个最优的跳频序列集，其参数为(q,e,e,f+1)。根据Lempel-Greenberger界：跳频序列集S中的每个跳频序列是渐进最优的。

=f-1+Δ

(14)

下面我们确定Δ的值。

1) 如果τ和-τ均属于分圆类Ci0。

Hsi(τ)=f+1

(15)

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

因为τ取遍{1,2,…,q-1}中的每个值，显然存在这样的τ，使这两种情况都成立，所以：

(16)

对于0≤u≤e-1，令si、si+u是跳频序列集S中的任意两个跳频序列，根据周期汉明互相关的定义，在时延τ时，我们有：

(17)

为了计算Hsi,si+u(τ)的值，我们分以下三种情况讨论。

1) 当τ跑遍{1,2,…,q-1}时，若存在τ，使τ∈Ci0+u，且-τ∈Ci0-u成立，则必有：

(18)

所以：

(19)

Hsi,si+u(τ)=f

(20)

2) 当τ跑遍{1,2,…,q-1}时，存在l≡i0+umode，使得τ∈Ci0+u。

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

(21)

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

(22)

基于以上分析，跳频序列集S的最大周期汉明相关为：

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

(23)

下面分析跳频序列集S关于Peng-Fan界是最优的。把相关参数代入Peng-Fan界有：

(24)

显然，达到了Peng-Fan界的下界，所以关于Peng-Fan界，S是最优的跳频序列集。

由于对于任意的q，均有q≡1mode，故r=1。把相关参数代入Lempel-Greenberger界有：

(25)

其中，Hm(S)-1使Lempel-Greenberger界中的等号成立，故S中的每个跳频序列是渐进最优的。

定理得证。

令S(19)=2，得到长度为19，个数为3，定义在有限域F19上的跳频序列集为:

对于时延τ，0≤τ≤18，汉明相关分别如下：

汉明自相关为：

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}

汉明互相关为：

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}

最大周期汉明相关为：

Hm(S)=7

可以验证，关于Peng-Fan界，S是最优的跳频序列集。关于Lempel-Greenberger界，S中每个跳频序列是渐进最优的。

3 结 语

基于分圆理论，提出了一种关于Peng-Fan界最优的跳频序列集的构造方法。本文所构造的跳频序列集与参考文献中所构造的跳频序列集的相关比较如表1所示。

表1 本文构造的跳频序列集与已知跳频序列集的比较

本文方法简单易行，丰富了跳频序列集的构造方法。利用分圆理论构造更多最优的其它类跳频序列集将是我们进一步研究的内容。

[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] 徐善顶,曹喜望,许广魁.一类周期为素数倍数的跳频序列集[J].电子学报,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。黄波，讲师，主研领域：网络通信，数字图像处理，软件工程。张小华，讲师。

TP393.04

A

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