基于中国剩余定理的最优低碰撞区跳频序列集扩展构造

韩 璐，牛宪华，蔡红斌

(西华大学计算机与软件工程学院，四川 成都 610039)

跳频通信系统最早起源于军事无线电通信，它具有良好的抗干扰性和多址组网性，能够使军事通信在恶劣电磁环境中实现无阻碍。由于跳频通信具有的优良特性，它在民用通信系统中也占据了广泛的应用市场[1-3]。

在跳频扩频通信系统的通信过程中，信号发射机的载波频率信号是按照某一无规律的变化规则进行跳变发射，与之相对应的信号接收机在接收对方信号时，为了正确得到相应信息，就需要接收机按照相同的载波频率的跳变规则接收来自发射机的信号。如何选择载波频率这种伪随机变化序列，即跳频序列(frequency hopping sequence，FHS)，是保证高质量、高效率的跳频通信的研究重点。跳频通信系统用户间的信号干扰程度取决于不同跳频序列之间频隙的重合次数，任意2条跳频序列间频隙的重合次数表示为序列间的汉明相关值(Hamming correlation value)，所以跳频通信系统性能主要取决于跳频序列集的汉明相关性的好坏[4-8]。

低/零碰撞区(LHZ/NHZ)跳频序列的概念，是由Ye等[9]在2003年首次提出，即将跳频序列的汉明相关值限制在零时延附近的一个较小的时延范围内，从而可以构造出较多的汉明相关性能好、序列数目更多、序列长度更长的跳频序列。近年来，国内外关于LHZ跳频序列集的构造研究有了很大的突破，并且取得了一些成果[10-23]。

本文提出了一种新的最优低碰撞区跳频序列集的构造方法。其构造核心是基于中国剩余定理，将已有的最优跳频序列集作为基序列集，利用单次重合(one-coincidence，OC)跳频序列集(OC-FHS Set)作为扩展序列集，构造出序列数目更大、频点更多、序列更长且满足Peng-Fan-Lee界的最优低碰撞区跳频序列集，并且结果序列集在低碰撞区内的最大汉明相关值与基序列集的最大汉明相关值保持一致。

1 预备知识

设F={f1，f2，…，fv}大小为v的频隙集，X是由F上M个长度为N的跳频序列组成的集合。对于任意的f1，f2∈F，令

对于任意2条跳频序列x={x(0)，x(1)，…，x(N-1)}和y={y(0)，y(1)，…，y(N-1)}∈X，x和y在相对时延τ的周期汉明相关函数Hxy(τ)定义为

(1)

其中i+τ按模N运算。当x=y时，Hxx(τ)为周期汉明自相关函数；当x≠y时，Hxy(τ)为周期汉明互相关函数。

对于已知的跳频序列集X，序列集的最大周期汉明自相关Ha(X)、最大周期汉明互相关Hc(X)、最大周期汉明相关Hm(X)分别定义为

Ha(X)=max{Hxx(τ) |x∈X，τ=1，…，N-1}

Hc(X)=max{Hxy(τ) |x，y∈X，x≠y，τ=0，1，…，N-1}

Hm(X)=max{Ha(X)，Hc(X)}

为了方便，令λa=Ha(X)，λc=Hc(X)，λ=Hm(X)。

在异步跳频通信系统中，期望每个跳频序列在整个周期内没有碰撞，但是根据跳频序列集汉明相关函数的理论界可知，满足条件的跳频序列的数目非常少，不能满足大量用户的需求。如果将跳频序列的汉明相关值限制在零时延附近的一个较小的时延范围内，就能构造出较多的汉明相关性能好、序列数目更多、序列长度更长的跳频序列。

跳频序列周期汉明相关函数低碰撞区的定义为：对于任意跳频序列集X，令整数λa≥0，λc≥0，那么，X关于周期汉明相关函数的低碰撞区Z，自相关低碰撞区Za和互相关低碰撞区Zc，分别为

Za=max{T|Hxx(τ)≤λa，x∈X，τ=1，…，T}

Zc=max{T|Hxy(τ)≤λc，x，y∈X，x≠y，τ=0，1，…，T}

Z=min{Za，Zc}

当Za=Zc=0时，Z称为X的无碰撞区ZN。一个具有Z≥0或ZN≥0的跳频序列集X称为关于周期汉明相关的低碰撞区(LHZ)跳频序列集或无碰撞区(NHZ)跳频序列集。

在2004年，Peng等[7]推导了跳频序列集的最大周期汉明相关理论界。

引理1(Peng-Fan界)令F是一个大小为v的频隙集，X为F上M个长度为N的跳频序列构成的集合，有

(2)

如果跳频序列集X的参数是不等式(2)的最小整数解，则称序列集X是关于最大周期汉明相关的最优跳频序列集。

在2006年，Peng等[8]推导了LHZ跳频序列集的周期汉明相关理论界。

引理2(Peng-Fan-Lee界)令F是一个大小为v的频隙集，X为F上M个长度为N的跳频序列构成的集合，Z是序列集X关于周期汉明相关函数的低碰撞区。对于任意整数LH，0≤LH≤Z，有

(3)

如果跳频序列集X的参数是不等式(3)的最小整数解，则跳频序列集X是关于最大周期汉明相关的最优低碰撞区跳频序列集。

由于OC-FHS集的最大汉明自相关为0，互相关为1，可以最大限度地提高频率的使用率，降低序列间的碰撞次数，因此被广泛用于多址通信中。1984年，Shaar等[18]首先为跳频码分多址扩频系统引入OC-FHS集。

引理3 OC-FHS集C具有以下基本性质:

1)对于序列集C中任意序列的频点只出现1次，即序列集的最大汉明自相关有Ha(C)=0；

2)对于序列集C中任意2条FHS的最大汉明互相关有Hc(C)=1。

引理4令F是一个大小为v的频隙集，X为F上M个长度为N的跳频序列构成的集合。设μi={μi(0)，μi(1)，…，μi(N-1)}，0≤i

μi(t)=|(i，θ):xi(θ)=xi(t)，0≤i≤t|

设li表示频点在序列集X的第i条序列xi中出现的最大次数，即li=max{μi(t):0≤t

设ωi={ωi(0)，ωi(1)，…，ωi(N-1)}，任意t，0≤t

在本文中

〈z〉n：z模n的最小非负剩余。

Zn：模n的整数环。

(N，v，λ；M)：在大小为v的频隙集上长度为N，序列个数为M，最大汉明相关值为λ的跳频序列集。

(N，v，λ；M；Z)：在大小为v的频隙集上长度为N，序列个数为M，低碰撞区Z内最大汉明相关值为λ的低碰撞区跳频序列集。

(N，v；M)：在大小为v的频隙集上长度为N，序列个数为M，最大汉明自相关值为0，最大汉明互相关值为1的OC-FHS集。

2 最优低碰撞区跳频序列集构造

由中国剩余定理(CRT)可知，当正整数a与b满足gcd(a，b)=1时，对于任意的整数t，0≤t

设F={f1，f2，…，fv}大小为v的频隙集，低碰撞区跳频序列集的构造描述如下。

构造1

步骤1：选择一个满足Peng-Fan界(N，v，λ；M)跳频序列集X，作为基序列集，而

X={xi={xi(0)，xi(1)，…，xi(N-1)}:0≤i

序列集X的相关参数μi，ωi，li和m(X)由引理4的定义可得。

步骤2：选择(q，q；p-1)OC-FHS集C，其中q=pa(p是素数且a是正整数)，gcd(q，N)=1，p>m(X)+1，有

C={cδ={cδ(0)，cδ(1)，…，cδ(q-1)}:0≤δ

证明由构造1可知，序列集S的频隙集大小为qv，序列长度为qN，序列个数为qM。

(4)

情况1：i=j。

1)当τ2=0，τ1=0，k1=k2时，根据式(4)，有

2)当τ2=0，τ1=0，k1≠k2或τ2=0，τ1≠0，k1=k2时，根据引理3知，OC-FHS集C的最大汉明自相关Ha(C)=0。因此，通过式(4)可得

3)对于任意t2，0≤t2

①当τ1≡μi(t2)·(k1-k2) modq，即τ1=μi(t2)·k1-q，μi(t2)k2≠0或τ1=q-μi(t2)·k2，μi(t2)k1≠0时，可知xi(t2)=xi(t2+τ2)，此时只需要研究cωi(t2)、cωi(t2+τ2)与它们分别移动μi(t2)·k1，μi(t2+τ2)·k2位后构成的新序列在时延为τ1时的汉明相关性。令ε(0<ε≤N)表示在式(4)中出现Hcωi(t2)cωi(t2)(0)的个数，则有

4)当τ2≠0时，根据引理3知，OC-FHS集C的最大汉明自相关Ha(C)=0，最大汉明互相关Hc(C)=1。因此，通过式(4)可得

情况2：i≠j。根据引理3和引理4可知，cωi(t2)≠cωj(t2+τ2)，OC-FHS集C的最大汉明互相关Hc(C)=1。因此，通过式(4)有

综合情况1和情况2，有

由此可得，当0≤τ

综上，序列集S是满足参数(qN，qv，λ；qM；N)的低碰撞区跳频序列集。

证毕。

定理2当

成立时，序列集S(qN，qv，λ；qM；N)是满足Peng-Fan-Lee界的最优低碰撞区跳频序列集。

证明根据定理1，序列集S在低碰撞区N内的最大汉明相关值Hm(S)为

根据Peng-Fan-Lee界，跳频序列集S在低碰撞区内的最大汉明相关值Hmo(S)为

当

成立时，在低碰撞区N内，跳频序列集S的最大汉明相关值Hm(S)=λ=Hmo(S)。

综上，序列集S(qN，qv，λ；qM；N)是满足Peng-Fan-Lee界的最优低碰撞区跳频序列集。

证毕。

选择同一个(N，v，λ；M)最优的跳频序列集X作为基序列集，然后选择参数不同的OC-FHS集C作为扩展因子，可以根据构造1中的方法得到更多满足Peng-Fan-Lee界的最优低碰撞区跳频序列集。

推论的证明方法与定理1和定理2类似。

下面给出一个实例。

例选择一个满足Peng-Fan界的最优(8，3，3；3)跳频序列集X={x0，x1，x2}，其中

x0={0，2，2，1，0，1，1，2}
x1={1，0，0，2，1，2，2，0}
x2={2，1，1，0，2，0，0，1}

根据引理4得l0=3，l1=3，l2=3，m(X)=9。当0≤i<3时，序列xi中频点出现的次数μi取值为

μ0={1，1，2，1，2，2，3，3}
μ1={1，1，2，1，2，2，3，3}
μ2={1，1，2，1，2，2，3，3}

ωi取值情况为

ω0= {1，1，2，1，2，2，3，3}
ω1= {4，4，5，4，5，5，6，6}
ω2= {7，7，8，7，8，8，9，9}

当q=p=11时，选择一个(11，11；10)OC-FHS集C={c0，c1，…，c9}，为

c0={0，1，2，3，4，5，6，7，8，9，10}
c1={0，2，4，6，8，10，1，3，5，7，9}
⋮
c9={0，10，9，8，7，6，5，4，3，2，1}

根据构造1中的步骤3，利用中国剩余定理得到低碰撞区跳频序列集S，有

其中

⋮

⋮

⋮

根据汉明相关性的定义，可以计算得到序列集S最大汉明相关值，如图1所示。可以看出，任意2条序列在整个时延周期内的最大汉明相关值的分布情况。

当τ<8时，Hm(S)=3，所以，序列集S是一个满足Peng-Fan-Lee界参数为(88，33，3；33；8)的最优低碰撞区跳频序列集，且低碰撞区Z=8。

3 结论

本文通过选择已有最优跳频序列集X(N，v，λ；M)，作为基序列集，再选择满足特定条件的(q，q；p-1)OC序列集C，作为扩展序列集，利用中国剩余定理(CRT)，构造出满足Peng-Fan-Lee界的最优低碰撞区跳频序列集S(qN，qv，λ；qM；N)。与现有文献构造出的低碰撞区跳频序列集相比，利用本文构造方法构造出的LHZ FHS集S具有更加灵活的参数，序列集大小、序列长度和频点个数相比于基序列集X均有所增加，并且序列集S在低碰撞区内的最大汉明相关值与基序列集X的最大汉明相关值保持一致，如表1所示。该跳频序列集可以更好地消除准同步跳频/跳时码分多址系统中的多址干扰。

表1 与现有最优低碰撞区跳频序列集的参数对比

注：p是素数，q是素数幂；lpf(n)表示正整数n的最小素因子；l，m，w是正整数；文献[11][13][17]以及本文构造都是在参数为(N，v，λ；M)的序列集基础上进行扩展