新的具有最優(yōu)平均漢明相關(guān)性的跳頻序列族

柯品惠，章海輝，張勝元

（福建師范大學 網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室，福建 福州 350007）

1 引言

跳頻碼分多址（FH-CDMA）擴頻系統(tǒng)具有抗干擾、抗截獲的能力，并能做到頻譜資源共享，所以在藍牙、超寬頻、雷達等當中都得到了廣泛的應(yīng)用[1,2]。

在跳頻多址擴頻系統(tǒng)中，當接收器解調(diào)來自發(fā)送器傳送的信號時，會受不明信號的干擾。為了防止相互干擾，采用的跳頻序列的漢明互相關(guān)值和非平凡的漢明自相關(guān)值應(yīng)盡可能小。

迄今已有的關(guān)于跳頻序列的漢明相關(guān)最優(yōu)性的判定方式有如下2種。

一種是最大的漢明相關(guān)值[3,4]，另外一種是平均漢明相關(guān)值[5]。近年來,跳頻序列的設(shè)計已成為人們關(guān)注的熱點，其中大部分都是針對最大的漢明相關(guān)值構(gòu)造出最優(yōu)的跳頻序列族[6～10]。而平均漢明相關(guān)值代表的是跳頻多址擴頻系統(tǒng)平均誤差，因此,設(shè)計出具有達到平均漢明相關(guān)界的跳頻序列族也是非常有意義的。基于模p的高次剩余及Whiteman廣義分圓類，文獻[11]和文獻[12]分別構(gòu)造了達到平均漢明相關(guān)界的跳頻序列族。然而，較之達到最大漢明相關(guān)界的跳頻序列，公開發(fā)表的達到平均漢明相關(guān)界的跳頻序列族的結(jié)果比較少。

Ding-Helleseth廣義分圓類及Whiteman廣義分圓類是2種重要的分圓類。人們對上述2種分圓類進行了各種推廣，并由此構(gòu)造了一系列性質(zhì)良好的序列。最近，Meidl在文獻[13]中給出了Ding-Helleseth廣義分圓的推廣，進而利用該推廣的分圓類構(gòu)造了多值序列，并分析了該序列的自相關(guān)值及錯綜復(fù)雜度等性質(zhì)。本文首先給出Whiteman廣義分圓類的一個推廣，然后應(yīng)用推廣的廣義分圓類構(gòu)造一類新的跳頻序列族，并計算了它們的平均漢明相關(guān)值。最后證明了新構(gòu)造的跳頻序列族關(guān)于平均漢明相關(guān)界是最優(yōu)的。注意到，當d=2n時，此時推廣的Whiteman廣義分圓類等同于Whiteman廣義分圓類，從而本文的結(jié)果推廣了文獻[12]的結(jié)論。

2 預(yù)備知識

設(shè)F={f0,f1,…,fv-1}為頻率集,令U是F上的周期為L，序列條數(shù)為M的跳頻序列族。U中的任意2條跳頻序列X={x0, x1,…,xL-1}, Y={y0,y1,…,yL-1}的周期漢明相關(guān)函數(shù)定義為

這里

其中，下標是模L運算。若X=Y, HX,X(τ)稱為X的漢明自相關(guān)函數(shù)，簡記為HX(τ)。X的最大漢明自相關(guān)以及X與Y(X≠Y)的最大漢明互相關(guān)分別定義為

Lempel和Greenberger在1974年給出了H( X)的一個下界。

引理1[3]設(shè)U是F上周期為L的跳頻序列，則

其中，|F|=v，b是L模v的非負整數(shù)，|x|表示為大于或等于x的最小整數(shù)。

對任意給出的一個跳頻序列族U，最大的漢明自相關(guān)Ha( U)和最大的漢明互相關(guān)Hc( U)分別定義為

關(guān)于跳頻序列族，Peng 和 Fan 在2004年給出了如下一個理論界。

引理2[4]設(shè)U是F上周期為L，序列條數(shù)為M的跳頻序列族，|F|=v，I =，則

跳頻序列族的另外2個重要參數(shù)平均漢明自相關(guān)函數(shù)和平均漢明互相關(guān)函數(shù)分別定義如下：

定義1[14]設(shè)U是F上周期為L，序列條數(shù)為M的跳頻序列族，則分別稱

為U的總漢明自相關(guān)和漢明互相關(guān)。同時分別稱

為U的平均漢明自相關(guān)和平均漢明互相關(guān)。為了簡便，本文約定

最近，Peng等人給出了Aa和Ac的如下理論界。

引理3[15]設(shè)U是F上的周期為L，序列條數(shù)為M的跳頻序列族，|F|=v,Aa和Ac分別為U的平均漢明自相關(guān)和平均漢明互相關(guān)，則

綜上所述，關(guān)于跳頻序列的最優(yōu)性，有如下幾種判定標準。

1) 對于單條跳頻序列X∈U，如果參數(shù)v、L和H( X)使得式(2)等式成立，則稱X是最優(yōu)的。

2) 對于跳頻序列族U，如果參數(shù)v、L、M、Hc和Hc使得式(3)中的任一等式成立，則稱U關(guān)于最大漢明相關(guān)界是最優(yōu)的。

3) 對于跳頻序列族U,如果參數(shù)v、L、M、Aa和Ac使得式(4)等式成立,則稱U關(guān)于平均漢明相關(guān)界是最優(yōu)的。

由式(3)和式(4)易知，如果一個跳頻序列集關(guān)于最大漢明相關(guān)界是最優(yōu)的，那么它關(guān)于平均漢明相關(guān)界一定是最優(yōu)的。但是，平均漢明相關(guān)界考慮的是一個序列集的全局性質(zhì)，此時對一個跳頻序列集，即使它關(guān)于最大漢明相關(guān)界不是最優(yōu)的,但如果能達到平均漢明界亦是很好的性質(zhì)[11]。更為重要的是，求平均漢明相關(guān)界的直接途徑是給出所考慮的序列集的漢明相關(guān)值的分布，而一個跳頻序列族的漢明相關(guān)分布和它對應(yīng)的循環(huán)碼的重量分布有密切聯(lián)系[8]，這是需要考慮這一問題的另一個主要原因。

3 廣義分圓類及其推廣

設(shè)p和q是不同的奇素數(shù)，gcd(p-1,q-1)，=2n，n為整數(shù),根據(jù)中國剩余定理，存在p和q的公共本原根，記為g。令x為滿足下列同余方程組的整數(shù)解：

令e=(p-1)(q-1)/2n, L=pq，則ZL中所有可逆元的集合可表示為

Whiteman廣義分圓類定義如下[16]：

定義

引理4[16]符號同上，則

其中，u是某個給定的整數(shù)，且0≤u≤e-1。

現(xiàn)在給出Whiteman廣義分圓類的一個推廣。

設(shè)d|2n，且d為奇素數(shù)。定義

注意到，如上提出的是基于Whiteman廣義分圓類的推廣，它不同于Meidl等在文獻[13]中提出的分圓類的推廣，因為后者是基于Ding-Helleseth廣義分圓類的推廣。對于新推廣的Whiteman廣義分圓有如下性質(zhì)。

性質(zhì)1 設(shè)D0及(i, j)分別表示如上所定義的推廣的Whiteman廣義分圓類和分圓數(shù)，則：

1) -1∈D0；

2) (i, j)=(j, i)；

3) (i, j)=(d-i, j-i)。

證明 1) 由d|2n，且d為奇素數(shù)，可知d| n，又由引理4可知，-1∈D0。

2)和3)易證。證畢。

性質(zhì)2 對任一給定的i，0≤i≤d-1，有：

根據(jù)上文所提到的在互聯(lián)網(wǎng)+視域下大數(shù)據(jù)對于管理會計所帶來的挑戰(zhàn)可知，當前要想全面發(fā)揮管理會計的積極作用，要求能夠把握機遇，規(guī)避挑戰(zhàn)。

證明 只證式(5)(式(6)可類似證明)。

1) 當ω∈Q時，結(jié)論顯然成立。

易知，有且只有一個s1∈Zq使得上述方程成立。因此，可設(shè)s=s1+k( q -1)，由0≤s≤e-1可知，，所以對于z=gsxdt+i+ω∈Q∪R總共有

注1 顯然有

性質(zhì)3

個元素。

1) 當i≡0(modd)時，Di+1中與L不互素的元素可分為如下3種情形。

① 元素能被L整除。 屬于該情形的元素個數(shù)為1。

② 元素能被p整除而不能被L整除。屬于該情形的元素個數(shù)為

③ 元素能被q整除而不能被L整除。屬于該情形的元素個數(shù)為。因此，Di+1中共有

個元素與L互素，即

2) 當i≠0(modd)時,Di+1中與L不互素的元素可分為如下3種情形。

① 元素能被L整除。屬于該情形的元素個數(shù)為0。

② 元素能被p整除而不能被L整除。屬于該情形的元素個數(shù)為

③ 元素能被q整除而不能被L整除。屬于該情形的元素個數(shù)為

因此，Di+1中共有

個元素與L互素，即

證畢。

性質(zhì)4

證明 由性質(zhì)1中3)可知,

再由性質(zhì)3，結(jié)論顯然成立。證畢。

證明 只證式(7)(式(8)可類似證明)。

當ω∈P時，元素z∈(Di+ω)∩Di，此時

以下分2種情形討論。

1) 當t1=t2時，由

可知，gs1+dt1+i=gs2+dt2+i(modp),即gs1=gs2(modp)。不妨設(shè)s1=s2+m1( p-1)，，則有

即gs2xdt2+i(gm1(p-1)-1)=ω(modpq )。又顯然有g(shù)m1(p-1)-1=0(modp)，因而,

由gs2xdt2+i=gs2(modq)， 設(shè)s2=s2′+h( q-1),，給定一個h,當s2遍歷{h( q-1),h( q-1)+1,…,h( q-1)+q-2}時,

包含P中每一元素的次數(shù)為

2) 當t1≠t2時，由

可知，gs1+dt1+i≡gs2+dt2+i(mod p ),即。假設(shè)

即s1=s2+d( t2-t1)+m2(p -1)，則有：

由gs2xdt2+i=gs2(mod q),設(shè)

給定一個h′,當s2遍歷{h′( q-1),h′( q -1)+1,…,h′( q-1)+q -2}時，gs2xdt2+i=gs2(mod q)對應(yīng)中每一個元素恰好均出現(xiàn)一次，也就是對應(yīng)P中的元素恰好出現(xiàn)一次，所以多重集

包含P中每一元素的次數(shù)為

綜合情形1)和情形2)，方程gs1xdt1+i=gs2xdt2+i(modpq)的解個數(shù)為

最后，當ω∈Dl，由定義ω-1Di=Di-l，有：

由性質(zhì)4可得結(jié)論。 證畢。

性質(zhì)6 對任一給定的i，0≤i≤d-1，有：

證明 1) 當ω∈Di時，ω-1Di=D0，由性質(zhì)1可知,-1∈D0，從而

|(Di+ω)∩R|=|(ω-1Di+1)∩R|=|(D0+1)∩R |=1當ω∈/Di時，結(jié)論顯然成立。

對2)及3)，注意到

由性質(zhì)2和性質(zhì)6可得結(jié)論。證畢。

注2 顯然有：

性質(zhì)7[12]

和

注3 1) 顯然有：

2) 類似地，容易驗證

4 新的跳頻序列族的構(gòu)造

本節(jié)將構(gòu)造一類新的跳頻序列族，并利用上一節(jié)給出的推廣的Whiteman廣義分圓類的性質(zhì)給出該跳頻序列族的漢明相關(guān)值的分布，證明了該類跳頻序列族關(guān)于平均漢明相關(guān)界是最優(yōu)的。

令

令X={x0, x1,…,xL-1}是在頻率集F={0,l,…,d-1}上的周期為L的跳頻序列，稱

為k∈F在序列X上的支撐集。

定義2 設(shè)L=pq，Ci,0≤i≤d-1定義同上。定義跳頻序列族U={X(i),i=0,1,…,d -1},其中，的支撐集為

這里，j+i是模d運算。

定理1 令p和q是不同的奇素數(shù)，gcd(p-1,q-1)=2n，令d|2n，d為奇素數(shù)，則如上定義的跳頻序列族U滿足如下性質(zhì)。

1) 序列族的大小為|U|=d，序列的周期為L=pq，頻率集大小為|F|=d。

2) U中任意一條跳頻序列(k)X的漢明相關(guān)函數(shù)值

3) U中任意2條不同的跳頻序列X(k),X(l)的漢明互相關(guān)函數(shù)值

證明 1) 顯然成立。

2) X(k)在ω移位的漢明自相關(guān)函數(shù)為

由性質(zhì)2、4、6、7可得結(jié)論。

3) 任意不同的2條跳頻序列X(k),X(l)∈U,0≤k≠l≤d-1，在ω移位的漢明互相關(guān)函數(shù)為

由d是奇素數(shù)可知，k-l≡/l-k(mod d )，令t=l-k

則由性質(zhì)2、5、6可得結(jié)論。證畢。

定理2 跳頻序列族U的平均漢明自相關(guān)和漢明互相關(guān)分別為

進一步地，跳頻序列族U關(guān)于平均漢明相關(guān)界是最優(yōu)的。

證明 由Sa( U)和Sc( U)的定義可知

由平均漢明自相關(guān)和平均漢明互相關(guān)的定義可得式(9)和式(10)。把式(9)和式(10)代入式(4)可得：

5 結(jié)束語

較之達到最大漢明相關(guān)界的跳頻序列族, 具有最優(yōu)平均漢明相關(guān)界的跳頻序列族的研究成果要少得多。在文獻[12]的基礎(chǔ)上，本文給出了Whiteman廣義分圓類的一個推廣，并且基于推廣的Whiteman廣義分圓類構(gòu)造了新的跳頻序列族，證明了新構(gòu)造的跳頻序列族關(guān)于平均漢明相關(guān)界是最優(yōu)的。

[1] FAN P Z, DAMELL M. Sequence Design for Communications Applications[M]. London: Research Studies Press, 1996.

[2] WIN M Z, SCHOLTZ R A. Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications[J]. IEEE Transactions on Communications, 2002,48(4):679-691.

[3] LEMPEL A, GREENBERGER H. Families of sequences with optimal Hamming correlation properties[J]. IEEE Transactions on Information Theory, 1974, 20(1): 90-94.

[4] PENG D Y, FAN P Z. Lower bounds on the hamming auto- and cross-correlations of frequency-hopping sequences[J]. IEEE Transac-tions on Information Theory, 2004, 50(9): 2149-2154.

[5] PENG D Y, et al. The average Hamming correlation for the cubic polynomial hopping sequences[A]. IEEE IWCMC 2008, International Conference on Wireless Communications and Mobile Computing[C].Crete, Greece, 2008. 464-469.

[6] CHU W S, COLBOURN C J. Optimal frequency-hopping sequences via cyclotomy[J]. IEEE Transactions on Information Theory, 2005,51(3):1139-1141.

[7] KE P H, ZHANG S Y. Frequency-hopping sequences based on d-form functions[J]. The Journal of China University of Posts and Telecommunications, 2010, 17(4): 58-62.

[8] DING C S, YANG Y, TANG X H. Optimal sets of frequency hopping sequences from linear cyclic codes[J]. IEEE Transactions on Information Theory, 2010, 56(7): 3605-3612.

[9] GE G N, MIAO Y, YAO Z X. Optimal frequency hopping sequences:auto- and cross-correlation properties[J]. IEEE Transactions on Information Theory, 2009, 55(2): 867-879.

[10] ZHANG Y, KE P H, ZHANG S Y. Optimal frequency-hopping sequences based on cyclotomy[A]. ETCS 2009, First International Workshop on Education Technology and Computer Science[C]. Wuhan, China, 2009.1122-1126.

[11] 劉方, 彭代淵.一類具有最優(yōu)平均漢明相關(guān)特性的跳頻序列族[J].電子與信息學報, 2010, 32(5): 1257-1261.LIU F, PENG D Y. A class of frequency-hopping sequence family with optimal average Hamming correlation property[J]. Journal of Electronics and Information Technology, 2010, 32(5): 1257-1261.

[12] LIU F, et al. Construction of frequency hopping sequence set based upon generalized cyclotomy[EB/OL]. http://arxiv.org/abs/1009.3602,2010.

[13] MEIDL W. Remarks on a cyclotomic sequence[J]. Designs, Codes,and Cryptography, 2009, 51: 33-43.

[14] PENG D Y, PENG T, FAN P Z. Generalized classof cubic frequency-hopping sequences with large family size[J]. IEEE Proceedings on Communications, 2005,152 (6): 897-902.

[15] PENG D Y, et al. A class of optimal frequency hopping sequences based upon the theory of power residues[A]. SETA 2008,Proceedings of the 5th International Conference on Sequences and Their Applications[C]. Lexington, KY, USA, 2008. 188-196.

[16] WHITEMAN A L. A family of difference sets[J]. Illinois Journal of Mathematics, 1962, 6: 107-121.