基于中國剩余定理的最優(yōu)低碰撞區(qū)跳頻序列集擴(kuò)展構(gòu)造

韓 璐，牛憲華，蔡紅斌

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

跳頻通信系統(tǒng)最早起源于軍事無線電通信，它具有良好的抗干擾性和多址組網(wǎng)性，能夠使軍事通信在惡劣電磁環(huán)境中實(shí)現(xiàn)無阻礙。由于跳頻通信具有的優(yōu)良特性，它在民用通信系統(tǒng)中也占據(jù)了廣泛的應(yīng)用市場[1-3]。

在跳頻擴(kuò)頻通信系統(tǒng)的通信過程中，信號(hào)發(fā)射機(jī)的載波頻率信號(hào)是按照某一無規(guī)律的變化規(guī)則進(jìn)行跳變發(fā)射，與之相對(duì)應(yīng)的信號(hào)接收機(jī)在接收對(duì)方信號(hào)時(shí)，為了正確得到相應(yīng)信息，就需要接收機(jī)按照相同的載波頻率的跳變規(guī)則接收來自發(fā)射機(jī)的信號(hào)。如何選擇載波頻率這種偽隨機(jī)變化序列，即跳頻序列(frequency hopping sequence，F(xiàn)HS)，是保證高質(zhì)量、高效率的跳頻通信的研究重點(diǎn)。跳頻通信系統(tǒng)用戶間的信號(hào)干擾程度取決于不同跳頻序列之間頻隙的重合次數(shù)，任意2條跳頻序列間頻隙的重合次數(shù)表示為序列間的漢明相關(guān)值(Hamming correlation value)，所以跳頻通信系統(tǒng)性能主要取決于跳頻序列集的漢明相關(guān)性的好壞[4-8]。

低/零碰撞區(qū)(LHZ/NHZ)跳頻序列的概念，是由Ye等[9]在2003年首次提出，即將跳頻序列的漢明相關(guān)值限制在零時(shí)延附近的一個(gè)較小的時(shí)延范圍內(nèi)，從而可以構(gòu)造出較多的漢明相關(guān)性能好、序列數(shù)目更多、序列長度更長的跳頻序列。近年來，國內(nèi)外關(guān)于LHZ跳頻序列集的構(gòu)造研究有了很大的突破，并且取得了一些成果[10-23]。

本文提出了一種新的最優(yōu)低碰撞區(qū)跳頻序列集的構(gòu)造方法。其構(gòu)造核心是基于中國剩余定理，將已有的最優(yōu)跳頻序列集作為基序列集，利用單次重合(one-coincidence，OC)跳頻序列集(OC-FHS Set)作為擴(kuò)展序列集，構(gòu)造出序列數(shù)目更大、頻點(diǎn)更多、序列更長且滿足Peng-Fan-Lee界的最優(yōu)低碰撞區(qū)跳頻序列集，并且結(jié)果序列集在低碰撞區(qū)內(nèi)的最大漢明相關(guān)值與基序列集的最大漢明相關(guān)值保持一致。

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

設(shè)F={f1，f2，…，fv}大小為v的頻隙集，X是由F上M個(gè)長度為N的跳頻序列組成的集合。對(duì)于任意的f1，f2∈F，令

對(duì)于任意2條跳頻序列x={x(0)，x(1)，…，x(N-1)}和y={y(0)，y(1)，…，y(N-1)}∈X，x和y在相對(duì)時(shí)延τ的周期漢明相關(guān)函數(shù)Hxy(τ)定義為

(1)

其中i+τ按模N運(yùn)算。當(dāng)x=y時(shí)，Hxx(τ)為周期漢明自相關(guān)函數(shù)；當(dāng)x≠y時(shí)，Hxy(τ)為周期漢明互相關(guān)函數(shù)。

對(duì)于已知的跳頻序列集X，序列集的最大周期漢明自相關(guān)Ha(X)、最大周期漢明互相關(guān)Hc(X)、最大周期漢明相關(guān)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)。

在異步跳頻通信系統(tǒng)中，期望每個(gè)跳頻序列在整個(gè)周期內(nèi)沒有碰撞，但是根據(jù)跳頻序列集漢明相關(guān)函數(shù)的理論界可知，滿足條件的跳頻序列的數(shù)目非常少，不能滿足大量用戶的需求。如果將跳頻序列的漢明相關(guān)值限制在零時(shí)延附近的一個(gè)較小的時(shí)延范圍內(nèi)，就能構(gòu)造出較多的漢明相關(guān)性能好、序列數(shù)目更多、序列長度更長的跳頻序列。

跳頻序列周期漢明相關(guān)函數(shù)低碰撞區(qū)的定義為：對(duì)于任意跳頻序列集X，令整數(shù)λa≥0，λc≥0，那么，X關(guān)于周期漢明相關(guān)函數(shù)的低碰撞區(qū)Z，自相關(guān)低碰撞區(qū)Za和互相關(guān)低碰撞區(qū)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}

當(dāng)Za=Zc=0時(shí)，Z稱為X的無碰撞區(qū)ZN。一個(gè)具有Z≥0或ZN≥0的跳頻序列集X稱為關(guān)于周期漢明相關(guān)的低碰撞區(qū)(LHZ)跳頻序列集或無碰撞區(qū)(NHZ)跳頻序列集。

在2004年，Peng等[7]推導(dǎo)了跳頻序列集的最大周期漢明相關(guān)理論界。

引理1(Peng-Fan界)令F是一個(gè)大小為v的頻隙集，X為F上M個(gè)長度為N的跳頻序列構(gòu)成的集合，有

(2)

如果跳頻序列集X的參數(shù)是不等式(2)的最小整數(shù)解，則稱序列集X是關(guān)于最大周期漢明相關(guān)的最優(yōu)跳頻序列集。

在2006年，Peng等[8]推導(dǎo)了LHZ跳頻序列集的周期漢明相關(guān)理論界。

引理2(Peng-Fan-Lee界)令F是一個(gè)大小為v的頻隙集，X為F上M個(gè)長度為N的跳頻序列構(gòu)成的集合，Z是序列集X關(guān)于周期漢明相關(guān)函數(shù)的低碰撞區(qū)。對(duì)于任意整數(shù)LH，0≤LH≤Z，有

(3)

如果跳頻序列集X的參數(shù)是不等式(3)的最小整數(shù)解，則跳頻序列集X是關(guān)于最大周期漢明相關(guān)的最優(yōu)低碰撞區(qū)跳頻序列集。

由于OC-FHS集的最大漢明自相關(guān)為0，互相關(guān)為1，可以最大限度地提高頻率的使用率，降低序列間的碰撞次數(shù)，因此被廣泛用于多址通信中。1984年，Shaar等[18]首先為跳頻碼分多址擴(kuò)頻系統(tǒng)引入OC-FHS集。

引理3 OC-FHS集C具有以下基本性質(zhì):

1)對(duì)于序列集C中任意序列的頻點(diǎn)只出現(xiàn)1次，即序列集的最大漢明自相關(guān)有Ha(C)=0；

2)對(duì)于序列集C中任意2條FHS的最大漢明互相關(guān)有Hc(C)=1。

引理4令F是一個(gè)大小為v的頻隙集，X為F上M個(gè)長度為N的跳頻序列構(gòu)成的集合。設(shè)μi={μi(0)，μi(1)，…，μi(N-1)}，0≤i

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

設(shè)li表示頻點(diǎn)在序列集X的第i條序列xi中出現(xiàn)的最大次數(shù)，即li=max{μi(t):0≤t

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

在本文中

〈z〉n：z模n的最小非負(fù)剩余。

Zn：模n的整數(shù)環(huán)。

(N，v，λ；M)：在大小為v的頻隙集上長度為N，序列個(gè)數(shù)為M，最大漢明相關(guān)值為λ的跳頻序列集。

(N，v，λ；M；Z)：在大小為v的頻隙集上長度為N，序列個(gè)數(shù)為M，低碰撞區(qū)Z內(nèi)最大漢明相關(guān)值為λ的低碰撞區(qū)跳頻序列集。

(N，v；M)：在大小為v的頻隙集上長度為N，序列個(gè)數(shù)為M，最大漢明自相關(guān)值為0，最大漢明互相關(guān)值為1的OC-FHS集。

2 最優(yōu)低碰撞區(qū)跳頻序列集構(gòu)造

由中國剩余定理(CRT)可知，當(dāng)正整數(shù)a與b滿足gcd(a，b)=1時(shí)，對(duì)于任意的整數(shù)t，0≤t

設(shè)F={f1，f2，…，fv}大小為v的頻隙集，低碰撞區(qū)跳頻序列集的構(gòu)造描述如下。

構(gòu)造1

步驟1：選擇一個(gè)滿足Peng-Fan界(N，v，λ；M)跳頻序列集X，作為基序列集，而

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

序列集X的相關(guān)參數(shù)μi，ωi，li和m(X)由引理4的定義可得。

步驟2：選擇(q，q；p-1)OC-FHS集C，其中q=pa(p是素?cái)?shù)且a是正整數(shù))，gcd(q，N)=1，p>m(X)+1，有

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

證明由構(gòu)造1可知，序列集S的頻隙集大小為qv，序列長度為qN，序列個(gè)數(shù)為qM。

(4)

情況1：i=j。

1)當(dāng)τ2=0，τ1=0，k1=k2時(shí)，根據(jù)式(4)，有

2)當(dāng)τ2=0，τ1=0，k1≠k2或τ2=0，τ1≠0，k1=k2時(shí)，根據(jù)引理3知，OC-FHS集C的最大漢明自相關(guān)Ha(C)=0。因此，通過式(4)可得

3)對(duì)于任意t2，0≤t2

①當(dāng)τ1≡μi(t2)·(k1-k2) modq，即τ1=μi(t2)·k1-q，μi(t2)k2≠0或τ1=q-μi(t2)·k2，μi(t2)k1≠0時(shí)，可知xi(t2)=xi(t2+τ2)，此時(shí)只需要研究cωi(t2)、cωi(t2+τ2)與它們分別移動(dòng)μi(t2)·k1，μi(t2+τ2)·k2位后構(gòu)成的新序列在時(shí)延為τ1時(shí)的漢明相關(guān)性。令ε(0<ε≤N)表示在式(4)中出現(xiàn)Hcωi(t2)cωi(t2)(0)的個(gè)數(shù)，則有

4)當(dāng)τ2≠0時(shí)，根據(jù)引理3知，OC-FHS集C的最大漢明自相關(guān)Ha(C)=0，最大漢明互相關(guān)Hc(C)=1。因此，通過式(4)可得

情況2：i≠j。根據(jù)引理3和引理4可知，cωi(t2)≠cωj(t2+τ2)，OC-FHS集C的最大漢明互相關(guān)Hc(C)=1。因此，通過式(4)有

綜合情況1和情況2，有

由此可得，當(dāng)0≤τ

綜上，序列集S是滿足參數(shù)(qN，qv，λ；qM；N)的低碰撞區(qū)跳頻序列集。

證畢。

定理2當(dāng)

成立時(shí)，序列集S(qN，qv，λ；qM；N)是滿足Peng-Fan-Lee界的最優(yōu)低碰撞區(qū)跳頻序列集。

證明根據(jù)定理1，序列集S在低碰撞區(qū)N內(nèi)的最大漢明相關(guān)值Hm(S)為

根據(jù)Peng-Fan-Lee界，跳頻序列集S在低碰撞區(qū)內(nèi)的最大漢明相關(guān)值Hmo(S)為

當(dāng)

成立時(shí)，在低碰撞區(qū)N內(nèi)，跳頻序列集S的最大漢明相關(guān)值Hm(S)=λ=Hmo(S)。

綜上，序列集S(qN，qv，λ；qM；N)是滿足Peng-Fan-Lee界的最優(yōu)低碰撞區(qū)跳頻序列集。

證畢。

選擇同一個(gè)(N，v，λ；M)最優(yōu)的跳頻序列集X作為基序列集，然后選擇參數(shù)不同的OC-FHS集C作為擴(kuò)展因子，可以根據(jù)構(gòu)造1中的方法得到更多滿足Peng-Fan-Lee界的最優(yōu)低碰撞區(qū)跳頻序列集。

推論的證明方法與定理1和定理2類似。

下面給出一個(gè)實(shí)例。

例選擇一個(gè)滿足Peng-Fan界的最優(yōu)(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}

根據(jù)引理4得l0=3，l1=3，l2=3，m(X)=9。當(dāng)0≤i<3時(shí)，序列xi中頻點(diǎn)出現(xiàn)的次數(shù)μ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}

當(dāng)q=p=11時(shí)，選擇一個(gè)(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}

根據(jù)構(gòu)造1中的步驟3，利用中國剩余定理得到低碰撞區(qū)跳頻序列集S，有

其中

?

?

?

根據(jù)漢明相關(guān)性的定義，可以計(jì)算得到序列集S最大漢明相關(guān)值，如圖1所示?？梢钥闯觯我?條序列在整個(gè)時(shí)延周期內(nèi)的最大漢明相關(guān)值的分布情況。

當(dāng)τ<8時(shí)，Hm(S)=3，所以，序列集S是一個(gè)滿足Peng-Fan-Lee界參數(shù)為(88，33，3；33；8)的最優(yōu)低碰撞區(qū)跳頻序列集，且低碰撞區(qū)Z=8。

3 結(jié)論

本文通過選擇已有最優(yōu)跳頻序列集X(N，v，λ；M)，作為基序列集，再選擇滿足特定條件的(q，q；p-1)OC序列集C，作為擴(kuò)展序列集，利用中國剩余定理(CRT)，構(gòu)造出滿足Peng-Fan-Lee界的最優(yōu)低碰撞區(qū)跳頻序列集S(qN，qv，λ；qM；N)。與現(xiàn)有文獻(xiàn)構(gòu)造出的低碰撞區(qū)跳頻序列集相比，利用本文構(gòu)造方法構(gòu)造出的LHZ FHS集S具有更加靈活的參數(shù)，序列集大小、序列長度和頻點(diǎn)個(gè)數(shù)相比于基序列集X均有所增加，并且序列集S在低碰撞區(qū)內(nèi)的最大漢明相關(guān)值與基序列集X的最大漢明相關(guān)值保持一致，如表1所示。該跳頻序列集可以更好地消除準(zhǔn)同步跳頻/跳時(shí)碼分多址系統(tǒng)中的多址干擾。

表1 與現(xiàn)有最優(yōu)低碰撞區(qū)跳頻序列集的參數(shù)對(duì)比

注：p是素?cái)?shù)，q是素?cái)?shù)冪；lpf(n)表示正整數(shù)n的最小素因子；l，m，w是正整數(shù)；文獻(xiàn)[11][13][17]以及本文構(gòu)造都是在參數(shù)為(N，v，λ；M)的序列集基礎(chǔ)上進(jìn)行擴(kuò)展