具有最優特性的一次碰撞跳頻序列集的新構造

謝 春， 陳 平， 王常遠， 彭代淵

(1. 成都工業學院 計算機工程學院 網絡空間安全研究所 四川 成都 611730； 2. 四川省宜賓市翠屏區 建設工程安全服務站 四川 宜賓 644000；3. 宜賓學院 計算機與信息工程學院 四川 宜賓 644007)

0 引言

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

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

1 跳頻序列漢明相關特性

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

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

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

1.1 最大周期漢明相關

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

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

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

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

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

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

定理2若跳頻序列集D的參數使Peng界_1中的等號成立，則稱D關于最大周期漢明相關是最優的；若Yang界中的等號成立，則稱D的序列數目達到最優；若N+1使Yang界中的等號成立，則稱D的序列數目是漸進最優的。

1.2 最大周期部分漢明相關

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

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

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

定理3若對于所有相關窗長，跳頻序列集D的參數使Zhou界中的等號成立，則稱D關于最大周期部分漢明相關是最優的；若Cai界中的等號成立，稱D的序列數目達到最優；若N+1使Cai界中的等號成立，則稱D的序列數目是漸進最優的。

1.3 最大非周期漢明相關

u與v在時延τ時的非周期漢明相關值定義為

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

定理4若跳頻序列集D的參數使Liu界_1中的等號成立，則稱D關于最大非周期漢明相關是最優的；若Liu界_2中的等號成立，則稱D關于序列個數是最優的；若N+1使Liu界_2中的等號成立，則稱D的序列數目是漸進最優的。

1.4 平均周期漢明相關

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

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

定理5若跳頻序列集D的參數使Peng界_2中的等號成立，則D關于平均周期漢明相關是最優的。

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

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

定理6若跳頻序列集D的參數使Ren界中的等號成立，則D關于平均周期漢明相關是最優的。

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

2 一次碰撞跳頻序列集的新構造

本節構造一類一次碰撞跳頻序列集，并對其漢明相關特性進行分析。

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

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

2.1 最大非周期漢明相關

定理8關于最大非周期漢明相關理論界—Liu界_1，跳頻序列集Sa是最優的。

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

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

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

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

AH(Sa)=1，

Sa的最大周期漢明互相關值為

非周期漢明相關值可表示為

最大非周期漢明相關值為

則

因為

所以

進一步地

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

定理9針對最大非周期漢明相關，關于Liu界_2，跳頻序列集Sa的序列個數是漸進最優的。

證明把相關參數代入Liu界_2中，右邊的值為

所以，結論成立。

2.2 平均周期漢明相關

定理10關于平均周期漢明相關理論界—Peng界_2，跳頻序列集Sa是最優的。

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

則

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

把相關參數代入Peng界_2的左邊，可得

把相關參數代入Peng界_2的右邊，可得

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

定理11關于平均周期部分漢明相關理論界—Ren界，跳頻序列集Sa是最優的。

2.3 最大周期漢明相關

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

定理12跳頻序列集Sa中每個跳頻序列關于最大周期漢明自相關是漸進最優的。

證明把相關參數代入L-G界，右邊的值為

顯然，結論成立。

定理13針對最大周期漢明相關，跳頻序列集Sa的序列個數是最優的。

證明把相關參數代入Yang界，右邊為

顯然，結論成立。

2.4 最大周期部分漢明相關

定理14關于最大周期部分漢明相關理論界—Zhou界，跳頻序列集Sa是最優的。

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

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

對于任意相關窗長w，把相關參數代入Zhou界，右邊的值為

所以結論成立。

定理15針對最大周期部分漢明相關，跳頻序列集Sa的序列個數是最優的。

證明根據Cai界，對于任意相關窗長w，Cai界右邊的值為

所以結論成立。

例根據本文的構造，可以得到有限域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 結束語

本文在有限域內，利用多項式構造一類一次碰撞跳頻序列集，新序列集關于平均周期漢明相關、最大周期漢明相關、周期部分漢明相關是最優的，同時，針對特定漢明相關，序列個數達到最優。進一步構造具有最優漢明相關特性的跳頻序列是下一步研究的重點內容。