一類具有較大線性復(fù)雜度的最優(yōu)跳頻序列集*

劉 方 ， 劉 捷

（1.網(wǎng)絡(luò)空間安全四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；2.中國電子科技網(wǎng)絡(luò)信息安全有限公司，四川 成都 610041；3.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610030）

0 引 言

跳頻（FH）多址擴(kuò)頻系統(tǒng)具有抗干擾、抗接入的能力，并能做到頻譜資源共享。所以，在現(xiàn)代電子戰(zhàn)中，跳頻通信已顯示出巨大的優(yōu)越性。在跳頻多址系統(tǒng)中，載波頻率跳變是由一個(gè)稱為跳頻序列的偽隨機(jī)序列控制頻率合成器產(chǎn)生的。跳頻序列設(shè)計(jì)理論目前有兩方面的內(nèi)容，一是尋找跳頻序列設(shè)計(jì)時(shí)所受到的理論限；二是設(shè)計(jì)出達(dá)到或接近理論限的跳頻序列。跳頻序列的線性復(fù)雜度可以表征跳頻序列被破譯的難易程度。線性復(fù)雜度越高，表明其抗破譯的能力越強(qiáng)。因此，尋找和設(shè)計(jì)具有低漢明相關(guān)、序列集合容量大及具有較大線性復(fù)雜度的跳頻序列集，是跳頻通信系統(tǒng)研究的重要課題之一。

目前，在跳頻序列設(shè)計(jì)的理論界方面，人們已經(jīng)得到了很多成果，如Lempel- Greenberger界[1]、Peng-Fan界[2]等。在最優(yōu)跳頻序列設(shè)計(jì)方面，基于組合和代數(shù)工具[3-9]，人們構(gòu)造了許多具有最優(yōu)漢明相關(guān)性能的跳頻序列集?；诶硐胱韵嚓P(guān)特性的p元偽隨機(jī)序列，構(gòu)造具有優(yōu)良漢明相關(guān)特性的跳頻序列是一種很重要的方法。劉元慧等人[10]基于m序列構(gòu)造了一類具有新參數(shù)的跳頻序列集和基于糾錯(cuò)碼構(gòu)造最優(yōu)跳頻序列集[11-13]。

1 基本概念

設(shè)一個(gè)跳頻通信系統(tǒng)具有q個(gè)頻點(diǎn)，頻點(diǎn)集合假設(shè)為F={ f1, f2,…, fq}。S是基于頻點(diǎn)集F上包含有M個(gè)跳頻序列的集合，其中每個(gè)序列長度為L。對(duì)于任意的頻點(diǎn)fi、 fj∈F，令：

對(duì)于跳頻序列集S中任意兩個(gè)序列X={x0,x1,…,xL-1}和Y={y0,y1,…,yL-1}，在相對(duì)時(shí)延為τ時(shí)的周期漢明相關(guān)函數(shù)定義為：

其中，下標(biāo)t+τ按模L運(yùn)算。當(dāng)X=Y時(shí)，HX,Y(τ)稱 為 漢 明 自 相 關(guān) 函 數(shù)， 簡 記 為 HX(τ)； 當(dāng)X≠Y時(shí)，HX,Y(τ)稱為漢明互相關(guān)函數(shù)。

針對(duì)跳頻序列集S，對(duì)任意的兩個(gè)序列X、Y∈S，下面將分別給出最大漢明自相關(guān)函數(shù)HX(τ)、最大漢明互相關(guān)函數(shù)HX,Y(τ)和最大漢明相關(guān)函數(shù)Hm的定義。

顯然，H(X)、H(X,Y)和Hm越小，跳頻通信系統(tǒng)的性能越好。因此，跳頻序列設(shè)計(jì)的一個(gè)基本要求是使H(X)、H(X,Y)和Hm的值盡可能小。跳頻序列設(shè)計(jì)主要涉及4個(gè)參數(shù)：頻點(diǎn)數(shù)目q、序列長度L、序列數(shù)目M以及最大漢明相關(guān)Hm，而這4個(gè)參數(shù)受到一些理論界的限制。

對(duì)于給定的頻點(diǎn)數(shù)目、序列長度，單個(gè)跳頻序列的最大漢明自相關(guān)滿足下面不等式。

引理1（Lempel-Greenberger界）[1]令X是頻點(diǎn)集F上的跳頻序列，序列長度為L，那么X的最大漢明自相關(guān)值滿足：

其中，|F|=q，b為L模q的最小非負(fù)余數(shù)。

在給定頻點(diǎn)數(shù)目、序列長度和序列個(gè)數(shù)的條件下，Peng和Fan[2]給出了S個(gè)序列集的最大漢明相關(guān)值滿足的理論界。

引理2（Peng-Fan界） 令S是一個(gè)在大小為q的頻點(diǎn)集F上的跳頻序列集，其序列數(shù)目為M，序列長度為L，令 I = [LM] /q ，則有：

在文獻(xiàn)[6]中，Ge、Miao和Yao證明了Peng-Fan界比Lempel-Greenberger界更好。當(dāng)M=1時(shí)，Lempel-Greenberger界是Peng-Fan界的特例；當(dāng)M=2時(shí)，關(guān)于H(X,Y)，Peng-Fan界要么比Lempel-Greenberger界緊，要么與Lempel-Greenberger界相同。

下面對(duì)單個(gè)序列和序列集的最優(yōu)性進(jìn)行定義。

定義1 如果一個(gè)序列X的參數(shù)使得式（6）的等式成立，則稱X是一個(gè)最優(yōu)的跳頻序列；如果一個(gè)序列集S的參數(shù)使得式（7）或式（8）的等式成立，則稱S是最優(yōu)的跳頻序列集。

本文中，使用如下的記號(hào)：

(L,q,λ)-FHS表示一個(gè)在大小為q的頻點(diǎn)集上長度為L、最大漢明自相關(guān)值為λ的跳頻序列；

(L,M,Λ;q)-FHSS表示在大小為q的頻點(diǎn)集上長度為L、序列個(gè)數(shù)為M、最大漢明相關(guān)值為Λ的一個(gè)跳頻序列集。

2 基于范函數(shù)構(gòu)造跳頻序列集

本節(jié)提出了一種新的構(gòu)造方法，所得到的跳頻序列集達(dá)到了理論界，并具有較大的線性復(fù)雜度。

令p是一個(gè)奇素?cái)?shù)，n、k為一正整數(shù)，且k|n，定義：表示從有限域F=Fpn到K=FP跡映射。

范函數(shù)NF/K(x)是從有限域F到K的一個(gè)映射函數(shù)，對(duì)任意的x∈F，有：

范函數(shù)NF/K(x)具有如下幾個(gè)特性[14-15]。

性質(zhì)1：對(duì)所有的x、y∈F，NF/K(xy)=NF/K(x)NF/K(y)。

性質(zhì)2：NF/K(x)是從F到K的滿射，F(xiàn)*到K*的滿射，其中F*和K*分別表示F和K中的非零元。

性質(zhì)3：對(duì)于任意的a∈K，NF/K(a)=an。

性質(zhì)4：對(duì)于任意的x∈F，NF/K(xp)=NF/K(x)。

令α為Fpn中的本原元，q=pk，n、m、k、s為正整數(shù)，且n=(2m+1)k，1≤s≤2m，gcd(s,2m+1)=1。定義 b0=1、bis=(-1)i、bi=b2m+1-i，其中 i=1,2,…,m。令u0=b0/2=(p+1)/2，ui=b2i，其中i=1,2,…,m。定義f(x)為：

容易驗(yàn)證 f(λx)=λf(x)，對(duì)任意的 λ∈ Fq。

定義如下跳頻序列集：

定理1 序列集C為一個(gè)(pn-1,p,pn-1;p)跳頻序列集。

證明：顯然，序列集C中有p個(gè)移位不等價(jià)序列，頻點(diǎn)數(shù)為p，序列長度為pn-1。下面證明該序列集的最大漢明相關(guān)值為pn-1。

令w表示一個(gè)p次單位根，即w=e2πj/p，其中j=。

對(duì)于C中任意兩個(gè)跳頻序列ca、cb，a,b∈Fp，其漢明相關(guān)函數(shù) Ha,b(τ)，0≤ τ＜pn-1計(jì)算如下：

（1）當(dāng) a=b=0，0＜τ＜pn-1 時(shí)，有：

將變量x替換為c-1x，因?yàn)椋?/p>

所以，Ha,b(τ)=pn-1。

（3）對(duì)于a≠0,b=0，0≤τ＜pn-1時(shí)，類似于情況 2，Ha,b(τ)=pn-1。

（4）對(duì)于a≠b且ab≠0,0≤τ＜pn-1時(shí)，有：

將變量x替換為c-1x，則有：

當(dāng)aNF/K(ατr)-b≠0時(shí)，同樣對(duì)c≠0時(shí)進(jìn)行變量替換x→c-1x，則有：

因此，最大漢明相關(guān)為pn-1。

（5）對(duì)于a=b≠0,0≤τ＜pn-1時(shí)，有：

當(dāng) 0＜τ＜pn-1 時(shí)，因?yàn)?gcd(r,p-1)，所以 NF/K(ατr)-1 ≠ 0。因此，有：

綜合以上結(jié)果，得到該序列集的最大漢明相關(guān)為pn-1。

證明完畢。

定理2 序列集C達(dá)到了Peng-Fan界，是一類最優(yōu)的跳頻序列集。

結(jié)論得證。

顯然序列集C中的序列線性復(fù)雜度大于等于(m+1)n。

例1：令q=5、m=1、k=1、n=3、s=2，則f(x)=3x-x13，那么得到序列集C={c0,c1,c2,c3,c4}為：

c0={1,1,4,1,0,1,0,0,4,2,4,2,2,4,1,1,3,1,2,2,0,1,3,4,1,1,0,2,3,1,0,2,2,3,2,0,2,0,0,3,4,3,4,4,3,2,2,1,2,4,4,0,2,1,3,2,2,0,4,1,2,0,4,4,1,4,0,4,0,0,1,3,1,3,3,1,4,4,2,4,3,3,0,4,2,1,4,4,0,3,2,4,0,3,3,2,3,0,3,0,0,2,1,2,1,1,2,3,3,4,3,1,1,0,3,4,2,3,3,0,1,4,3,0}；

c1={2,0,0,0,1,0,1,4,0,1,0,1,3,3,2,0,4,0,3,1,1,0,4,3,2,0,1,1,4,0,1,1,3,2,3,4,3,4,1,2,0,2,0,3,4,1,3,0,3,3,0,4,3,0,4,1,3,4,0,0,3,4,0,3,2,3,1,3,1,4,2,2,2,2,4,0,0,3,3,3,4,2,1,3,3,0,0,3,1,2,3,3,1,2,4,1,4,4,4,4,1,1,2,1,2,0,3,2,4,3,4,0,2,4,4,3,3,2,4,4,2,3,4,4}；

c2={3,4,1,4,2,4,2,3,1,0,1,0,4,2,3,4,0,4,4,0,2,4,0,2,3,4,2,0,0,4,2,0,4,1,4,3,4,3,2,1,1,1,1,2,0,0,4,4,4,2,1,3,4,4,0,0,4,3,1,4,4,3,1,2,3,2,2,2,2,3,3,1,3,1,0,4,1,2,4,2,0,1,2,2,4,4,1,2,2,1,4,2,2,1,0,0,0,3,0,3,2,0,3,0,3,4,4,1,0,2,0,4,3,3,0,2,4,1,0,3,3,2,0,3}；

c3={4,3,2,3,3,3,3,2,2,4,2,4,0,1,4,3,1,3,0,4,3,3,1,1,4,3,3,4,1,3,3,4,0,0，0,2,0,2,3,0,2,0,2,1,1,4,0,3,0,1,2,2,0,3,1,4,0,2,2,3,0,2,2,1,4,1,3,1,3,2,4,0,4,0,1,3,2,1,0,1,1,0,3,1,0,3,2,1,3,0,0,1,3,0,1,4,1,2,1,2,3,4,4,4,4,3,0,0,1,1,1,3,4,2,1,1,0,0,1,2,4,1,1,2}；

c4={0,2,3,2,4,2,4,1,3,3,3,3,1,0,0,2,2,2,1,3,4,2,2,0,0,2,4,3,2,2,4,3,1,4,1,1,1,1,4,4,3,4,3,0,2,3,1,2,1,0,3,1,1,2,2,3,1,1,3,2,1,1,3,0,0,0,4,0,4,1,0,4,0,4,2,2,3,0,1,0,2,4,4,0,1,2,3,0,4,4,1,0,4,4,2,3,2,1,2,1,4,3,0,3,0,2,1,4,2,0,2,2,0,1,2,0,1,4,2,1,0,0,2,1}。

可以計(jì)算得到H(c0)=24，H(ci)=25，其中1 ≤ i＜5。 針 對(duì) 0 ≤ i≠ j＜5，H(ci，cj)=25。 容 易 驗(yàn)證c0關(guān)于Lempel-Greenberger界是一個(gè)最優(yōu)的(124,5,24)-FHS；而對(duì)于i=1,2,3,4，ci關(guān)于Lempel-Greenberger界是幾乎最優(yōu)的(124,5,25)-FHS。通過簡單的驗(yàn)證，C關(guān)于Peng-Fan界是一個(gè)最優(yōu)的(124,5,25;5)-FHSS。c0的線性復(fù)雜度為6，其他4個(gè)序列的線性復(fù)雜度為7。

需要注意，當(dāng)f(x)=x時(shí)，序列集C即為參考文獻(xiàn)[8]第IV節(jié)所得到的序列集。C中的每個(gè)序列的線性復(fù)雜度為n。如果采用其他的f(x)函數(shù)，那么能得到具有更大線性復(fù)雜度的最優(yōu)跳頻序列集。

3 結(jié) 語

本文基于范函數(shù)構(gòu)造了一類跳頻序列集，通過計(jì)算證明了該類跳頻序列的漢明相關(guān)性能滿足Peng-Fan界，是一類具有最優(yōu)漢明特性的跳頻序列集。同時(shí)，本文得到的跳頻序列線性復(fù)雜度大于等于(m+1)n，相較已有序列具有較大的線性復(fù)雜度，因此這些跳頻序列在軍事通信系統(tǒng)中具有很好的應(yīng)用前景。