具有最優(yōu)特性的一次碰撞跳頻序列集的新構(gòu)造

謝 春， 陳 平， 王常遠(yuǎn)， 彭代淵

(1. 成都工業(yè)學(xué)院 計算機(jī)工程學(xué)院 網(wǎng)絡(luò)空間安全研究所 四川 成都 611730； 2. 四川省宜賓市翠屏區(qū) 建設(shè)工程安全服務(wù)站 四川 宜賓 644000；3. 宜賓學(xué)院 計算機(jī)與信息工程學(xué)院 四川 宜賓 644007)

0 引言

當(dāng)前，信息技術(shù)在各行各業(yè)得到廣泛應(yīng)用，產(chǎn)生的信息安全問題日益突出，網(wǎng)絡(luò)攻防[1-2]、密碼學(xué)[3-4]、保密通信[5-6]等相關(guān)內(nèi)容得到深入研究。跳頻通信作為一種重要的保密通信方式，得到了廣泛關(guān)注。在通信中，當(dāng)多個用戶在同一頻隙同時通信時，便產(chǎn)生了影響通信性能的主要干擾，減小或消除通信中的各種干擾，實(shí)現(xiàn)保密、安全、可靠通信是十分必要的，跳頻通信應(yīng)運(yùn)而生。跳頻通信在藍(lán)牙、軍事通信以及移動通信中得到了廣泛應(yīng)用[5-7]，跳頻通信中主要使用跳頻序列來消除相關(guān)干擾，設(shè)計最優(yōu)漢明相關(guān)特性的跳頻序列具有重要的理論與應(yīng)用價值。

一次碰撞跳頻序列在全周期內(nèi)具有最小的漢明相關(guān)值，其理論界以及最優(yōu)跳頻序列的設(shè)計得到了廣泛研究。如：一次碰撞跳頻序列理論界的建立以及序列構(gòu)造[8-10]；基于笛卡爾積理論的構(gòu)造[11]；一次碰撞跳頻序列組合特征研究以及最優(yōu)構(gòu)造[12]；有限域上的構(gòu)造[13-18]。本文利用有限域上的多項式理論，關(guān)于最大漢明相關(guān)值、平均漢明相關(guān)值、部分漢明相關(guān)值，構(gòu)造一類具有新參數(shù)的一次碰撞跳頻序列集，新跳頻序列集在多個指標(biāo)上均達(dá)到最優(yōu)。

1 跳頻序列漢明相關(guān)特性

本文中，將用到下面兩個記號。

(N,M,q)-FHSS：由長度為N的M個序列組成的跳頻序列集，其頻隙個數(shù)為q。

(N,M,q,h) -FHSS：由長度為N的M個序列組成的、最大周期漢明相關(guān)值為h的跳頻序列集，其頻隙個數(shù)為q。

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

令D為定義在具有q個頻隙的頻隙集F上的跳頻序列集(L,M,q)-FHSS。設(shè)u=(u0,u1,…,uL-1)與v=(v0,v1,…,vL-1)為D中的兩個跳頻序列，在時延τ時，u與v之間的周期漢明相關(guān)值PHu,v(τ)定義為

其中：如果uk≠v(k+τ)mod L，ph(uk,v(k+τ)mod L)=0；否則，ph(uk,v(k+τ)mod L)=1。

D的最大周期漢明相關(guān)值MH(D)定義為

針對單個跳頻序列，Lempel和Greenberger[19]建立了最大周期漢明自相關(guān)值的理論界(L-G界)。

定理1若跳頻序列的參數(shù)使L-G界中的等號成立，則該序列關(guān)于最大周期漢明自相關(guān)是最優(yōu)的，若AH(s)-1使等號成立，則該序列關(guān)于最大周期漢明自相關(guān)是漸進(jìn)最優(yōu)的。

Peng等[7]建立了關(guān)于最大周期漢明相關(guān)值的理論界(Peng界_1)。針對最大周期漢明相關(guān)，Yang等[20]得到跳頻序列集序列個數(shù)的理論上界(Yang界)。

定理2若跳頻序列集D的參數(shù)使Peng界_1中的等號成立，則稱D關(guān)于最大周期漢明相關(guān)是最優(yōu)的；若Yang界中的等號成立，則稱D的序列數(shù)目達(dá)到最優(yōu)；若N+1使Yang界中的等號成立，則稱D的序列數(shù)目是漸進(jìn)最優(yōu)的。

1.2 最大周期部分漢明相關(guān)

u與v在起點(diǎn)為j0、相關(guān)窗長度為w、時延為τ時的周期部分漢明相關(guān)值定義為

D的最大周期部分漢明相關(guān)值MPD(w)定義為

Zhou等[21]得到最大周期部分漢明相關(guān)值的理論界(Zhou界)。進(jìn)一步地，Cai等[22]得到跳頻序列集序列個數(shù)的上界(Cai界)。

定理3若對于所有相關(guān)窗長，跳頻序列集D的參數(shù)使Zhou界中的等號成立，則稱D關(guān)于最大周期部分漢明相關(guān)是最優(yōu)的；若Cai界中的等號成立，稱D的序列數(shù)目達(dá)到最優(yōu)；若N+1使Cai界中的等號成立，則稱D的序列數(shù)目是漸進(jìn)最優(yōu)的。

1.3 最大非周期漢明相關(guān)

u與v在時延τ時的非周期漢明相關(guān)值定義為

Liu等[23]建立了最大非周期漢明相關(guān)值的理論界(Liu界_1)。同時，Liu等[24]建立了跳頻序列集序列數(shù)目的理論上界(Liu界_2)。

定理4若跳頻序列集D的參數(shù)使Liu界_1中的等號成立，則稱D關(guān)于最大非周期漢明相關(guān)是最優(yōu)的；若Liu界_2中的等號成立，則稱D關(guān)于序列個數(shù)是最優(yōu)的；若N+1使Liu界_2中的等號成立，則稱D的序列數(shù)目是漸進(jìn)最優(yōu)的。

1.4 平均周期漢明相關(guān)

跳頻序列集D的平均周期漢明自相關(guān)值以及平均周期漢明互相關(guān)值分別定義為

對于跳頻序列集D的參數(shù)L、N、AA(D)以及CA(D)，Peng等[25]建立了平均周期漢明相關(guān)值的理論界(Peng界_2)。

定理5若跳頻序列集D的參數(shù)使Peng界_2中的等號成立，則D關(guān)于平均周期漢明相關(guān)是最優(yōu)的。

跳頻序列集D的平均周期部分漢明自相關(guān)值以及平均周期部分漢明互相關(guān)值分別定義為

Ren等[26]得到了跳頻序列集平均周期部分漢明相關(guān)值的理論界(Ren界)。

定理6若跳頻序列集D的參數(shù)使Ren界中的等號成立，則D關(guān)于平均周期漢明相關(guān)是最優(yōu)的。

定理7若跳頻序列集D關(guān)于平均周期漢明相關(guān)是最優(yōu)的，則D關(guān)于平均周期部分漢明相關(guān)也是最優(yōu)的，反之亦然。

2 一次碰撞跳頻序列集的新構(gòu)造

本節(jié)構(gòu)造一類一次碰撞跳頻序列集，并對其漢明相關(guān)特性進(jìn)行分析。

令p為素數(shù)，有限域GF(p)上的一個跳頻序列集Sa定義為

其中：k∈GF(p)。顯然，跳頻序列集的序列個數(shù)、序列長度以及頻隙集大小均為p。接下來，將從最大非周期漢明相關(guān)、平均周期漢明相關(guān)、最大周期漢明相關(guān)、最大周期部分漢明相關(guān)4個角度分析Sa的特性。

2.1 最大非周期漢明相關(guān)

定理8關(guān)于最大非周期漢明相關(guān)理論界—Liu界_1，跳頻序列集Sa是最優(yōu)的。

證明令F(x)表示有限域GF(p)上的多項式，N(F)=N(F(x)≡0 modp)表示方程F(n)≡0 modp在有限域GF(p)內(nèi)解的個數(shù)。對于Sa中的任意兩個跳頻序列u(i)、u(j)，其周期漢明相關(guān)值可表示為

其中：F(n)=2nτ+τ+τ2+j-i。

1) 當(dāng)i≠j，τ取遍{0,1,2,…,p-1}中的數(shù)時，方程F(n)≡0 modp在有限域GF(p)內(nèi)有唯一解n=(2τ)-1(i-j-τ-τ2)modp。

2) 當(dāng)i=j，τ取遍{1,2,…,p-1}中的數(shù)時，方程F(n)≡0 modp在有限域GF(p)內(nèi)有唯一解n=(2τ)-1(-τ-τ2)modp。當(dāng)i=j，τ=0時，方程在有限域GF(p)內(nèi)有p個解。所以

AH(Sa)=1，

Sa的最大周期漢明互相關(guān)值為

非周期漢明相關(guān)值可表示為

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

則

因?yàn)?/p>

所以

進(jìn)一步地

高血壓合并心房顫動是心律失常最常見的類型之一，血壓升高可增加房顫的發(fā)生風(fēng)險，血壓上升可增加左心室與左心房后負(fù)荷，導(dǎo)致心肌細(xì)胞肥大及間質(zhì)纖維化，進(jìn)而可導(dǎo)致心房電生理活動異常。由此可以看出，高血壓與房顫的發(fā)生、發(fā)展及預(yù)后具有密切聯(lián)系[3] 。

定理9針對最大非周期漢明相關(guān)，關(guān)于Liu界_2，跳頻序列集Sa的序列個數(shù)是漸進(jìn)最優(yōu)的。

證明把相關(guān)參數(shù)代入Liu界_2中，右邊的值為

所以，結(jié)論成立。

2.2 平均周期漢明相關(guān)

定理10關(guān)于平均周期漢明相關(guān)理論界—Peng界_2，跳頻序列集Sa是最優(yōu)的。

證明根據(jù)定理8的證明，對于任意i和j，有

則

AS(Sa)=p(p-1)；2CS(Sa)=p(p-1)2；

把相關(guān)參數(shù)代入Peng界_2的左邊，可得

把相關(guān)參數(shù)代入Peng界_2的右邊，可得

故結(jié)論成立。由定理7，可以得到定理11。

定理11關(guān)于平均周期部分漢明相關(guān)理論界—Ren界，跳頻序列集Sa是最優(yōu)的。

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

由定理8的證明可知，Sa的最大周期漢明相關(guān)值MH(Sa)=1。容易驗(yàn)證，關(guān)于最大周期漢明相關(guān)，Sa是最優(yōu)的。

定理12跳頻序列集Sa中每個跳頻序列關(guān)于最大周期漢明自相關(guān)是漸進(jìn)最優(yōu)的。

證明把相關(guān)參數(shù)代入L-G界，右邊的值為

顯然，結(jié)論成立。

定理13針對最大周期漢明相關(guān)，跳頻序列集Sa的序列個數(shù)是最優(yōu)的。

證明把相關(guān)參數(shù)代入Yang界，右邊為

顯然，結(jié)論成立。

2.4 最大周期部分漢明相關(guān)

定理14關(guān)于最大周期部分漢明相關(guān)理論界—Zhou界，跳頻序列集Sa是最優(yōu)的。

證明設(shè)相關(guān)窗長為w，1≤w≤p，對于Sa中的任意兩個跳頻序列u(i)、u(j)，在起點(diǎn)為l的相關(guān)窗內(nèi)的最大漢明相關(guān)值為

問題等價于n∈{l,l+1,l+2,…,l+w-1}，方程2nτ+τ+τ2+j-i≡0 modp解的個數(shù)。跳頻序列集Sa的最大周期部分漢明相關(guān)值可表示為

對于任意相關(guān)窗長w，把相關(guān)參數(shù)代入Zhou界，右邊的值為

所以結(jié)論成立。

定理15針對最大周期部分漢明相關(guān)，跳頻序列集Sa的序列個數(shù)是最優(yōu)的。

證明根據(jù)Cai界，對于任意相關(guān)窗長w，Cai界右邊的值為

所以結(jié)論成立。

例根據(jù)本文的構(gòu)造，可以得到有限域GF(13)上的跳頻序列集，

y={y0={0,2,6,12,7,4,3,4,7,12,6,2,0};y1={1,3,7,0,8,5,4,5,8,0,7,3,1};

y2={2,4,8,1,9,6,5,6,9,1,8,4,2};y3={3,5,9,2,10,7,6,7,10,2,9,5,3};

y4={4,6,10,3,11,8,7,8,11,3,10,6,4};y5={5,7,11,4,12,9,8,9,12,4,11,7,5};

y6={6,8,12,5,0,10,9,10,0,5,12,8,6};y7={7,9,0,6,1,11,10,11,1,6,0,9,7};

y8={8,10,1,7,2,12,11,12,2,7,1,10,8};y9={9,11,2,8,3,0,12,0,3,8,2,11,9};

y10={10,12,3,9,4,1,0,1,4,9,3,12,10};y11={11,0,4,10,5,2,1,2,5,10,4,0,11};

y12={12,1,5,11,6,3,2,3,6,11,5,1,12}}。

3 結(jié)束語

本文在有限域內(nèi)，利用多項式構(gòu)造一類一次碰撞跳頻序列集，新序列集關(guān)于平均周期漢明相關(guān)、最大周期漢明相關(guān)、周期部分漢明相關(guān)是最優(yōu)的，同時，針對特定漢明相關(guān)，序列個數(shù)達(dá)到最優(yōu)。進(jìn)一步構(gòu)造具有最優(yōu)漢明相關(guān)特性的跳頻序列是下一步研究的重點(diǎn)內(nèi)容。