徐善頂曹喜望許廣魁

?

基于分圓法的一類素?cái)?shù)平方周期跳頻序列族

徐善頂*①②曹喜望②③許廣魁②④

①(南京工程學(xué)院數(shù)理部 南京 211167)②(南京航空航天大學(xué)數(shù)學(xué)系 南京 211106)③(中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室 北京 100093)④(淮南師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系 淮南 232038)

最大漢明相關(guān)與平均漢明相關(guān)是評(píng)價(jià)跳頻序列族性能的兩個(gè)重要參數(shù)。該文首先給出了源于Fermat商的廣義分圓類的性質(zhì)；其次，基于此廣義分圓法構(gòu)造了一類上的長度為，序列族的大小為的跳頻序列族；最后證明了該跳頻序列族關(guān)于最大漢明相關(guān)界與平均漢明相關(guān)界都是最優(yōu)的。

跳頻序列；Fermat商；分圓；最大漢明相關(guān)界；平均漢明相關(guān)界

1 引言

跳頻技術(shù)被廣泛應(yīng)用于現(xiàn)代通信系統(tǒng)，比如超寬頻、藍(lán)牙、軍事及雷達(dá)等。其中，用于控制載波頻率跳變的地址碼序列稱為跳頻序列(Frequency- Hopping Sequence, FHS)，它的性能對(duì)跳頻系統(tǒng)有重大影響。在實(shí)際應(yīng)用中，我們盡可能使用非平凡漢明自相關(guān)值和漢明互相關(guān)值較小的跳頻序列以減少信號(hào)之間的彼此干擾，同時(shí)還要求序列的數(shù)目比較多以容納盡可能多用戶。但是，跳頻序列族的參數(shù)受限于一些理論界，因此構(gòu)造關(guān)于這些界的最優(yōu)跳頻序列族成了設(shè)計(jì)的熱點(diǎn)。目前關(guān)于跳頻序列族的漢明相關(guān)最優(yōu)性的評(píng)價(jià)指標(biāo)主要有如下兩種：一種是最大漢明相關(guān)[1,2](MHC)，代表的是跳頻系統(tǒng)的最壞情形，目前大多數(shù)跳頻序列的設(shè)計(jì)主要是針對(duì)它的最優(yōu)構(gòu)造。另一種是平均漢明相關(guān)[3](AHC)，代表的是跳頻系統(tǒng)的平均干擾狀況，所以設(shè)計(jì)出達(dá)到平均漢明相關(guān)界的跳頻序列族也意義重大。然而，公開發(fā)表的能同時(shí)達(dá)到最大漢明相關(guān)界與平均漢明相關(guān)界的跳頻序列族[1,13,14]卻比較少，這也成了序列設(shè)計(jì)中的一個(gè)重要課題。

分圓是一個(gè)很古老的數(shù)論問題，分圓數(shù)和廣義分圓數(shù)被廣泛應(yīng)用于數(shù)論問題、組合數(shù)學(xué)、序列設(shè)計(jì)、編碼理論以及密碼學(xué)等。近年來，許多編碼學(xué)者陸續(xù)利用Gauss經(jīng)典分圓、Whiteman廣義分圓、Ding-Helleseth廣義分圓及其推廣構(gòu)造了一系列性能良好的序列。本文基于Fermat商[15]導(dǎo)出的廣義分圓法[16]構(gòu)造了一類長度為的跳頻序列族，同時(shí)給出了各類漢明相關(guān)值的計(jì)算公式輔以驗(yàn)證其最優(yōu)性。隨后證明所構(gòu)造的序列族不僅關(guān)于最大漢明相關(guān)界與平均漢明相關(guān)界都是最優(yōu)的，而且序列族中的每個(gè)序列關(guān)于L-G界(見引理1)也是最優(yōu)的。

2 基本概念

Lempel和Greenberger[1]于1974年給出了跳頻序列的最大漢明自相關(guān)的一個(gè)下界：

引理1 (L-G 界[1]) 設(shè)是大小為的字符集上的長度為的任意跳頻序列，則

引理2[2]設(shè)是大小為的字符集上的長度為的個(gè)跳頻序列構(gòu)成的序列族，則

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

定義1[17]設(shè)是上的長度為的個(gè)跳頻序列的集合且=，則分別稱為

2008年，Peng等人[18]給出了跳頻序列族的和的如下理論界：

引理3[18]設(shè)是上的長度為的個(gè)跳頻序列的集合且=，則

今后我們將使用以下定義:

注1：上面定義的關(guān)于環(huán)的階廣義分圓既不同于Whiteman廣義分圓，又不同于Ding- Helleseth廣義分圓中環(huán)的二階廣義分圓，是一種全新的分圓形式。

如上定義的廣義分圓類與廣義分圓數(shù)有以下性質(zhì)：

性質(zhì)1[16]若,，那么=,。

(3)易證。 證畢

綜合(1)與(2)得結(jié)論。 證畢

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

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

本節(jié)將構(gòu)造一類新的跳頻序列族，并利用上節(jié)的性質(zhì)給出該跳頻序列族的漢明相關(guān)值的分布，隨后證明了所構(gòu)造的序列族不僅具有最優(yōu)MHC與最優(yōu)AHC，而且序列族中的每個(gè)序列關(guān)于L-G界也是最優(yōu)的。

證明 (1) 顯然成立；

由性質(zhì)5，性質(zhì)6，性質(zhì)7可得結(jié)論。

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

注2：本節(jié)與文獻(xiàn)[13]構(gòu)造的相似與不同之處：

(1)相似：與文獻(xiàn)[13]所構(gòu)造的跳頻序列族相比，本節(jié)構(gòu)造的序列族不僅具有與其相同的序列周期、序列個(gè)數(shù)和字符集大小，而且具有相同的最優(yōu)漢明相關(guān)特性，即：所構(gòu)造的序列族具有最優(yōu)MHC和最優(yōu)AHC，其中每個(gè)序列關(guān)于L-G界也是最優(yōu)的(見表1)。

(2)不同：首先，本文與文獻(xiàn)[13]所構(gòu)造的跳頻序列形式完全不同；其次，文獻(xiàn)[13]中的構(gòu)造主要利用廣義bent函數(shù)，其序列族定義形式和最優(yōu)性證明過程相對(duì)復(fù)雜。而本節(jié)中的構(gòu)造主要采用的是廣義分圓法，不僅定義字符集更加簡潔，而且序列族構(gòu)造方法簡單可行，從而具有更強(qiáng)的應(yīng)用背景。

表1幾類相關(guān)跳頻序列族的比較(其中為奇素?cái)?shù))

跳頻序列族L|U|L-G界MHCAHC 文獻(xiàn)[9]最優(yōu)非最優(yōu)最優(yōu) 文獻(xiàn)[13]最優(yōu)最優(yōu)最優(yōu) 文獻(xiàn)[14]最優(yōu)最優(yōu)最優(yōu) 本文最優(yōu)最優(yōu)最優(yōu)

5 結(jié)束語

[1] Lempel A and Greenberger H. Families of sequences with optimal Hamming correlation properties[J]., 1974, 20(1): 90-94.

[2] Peng D Y and Fan P Z. Lower bounds on the Hamming auto-and cross-correlations of frequency-hopping sequences[J]., 2004, 50(9): 2149-2154.

[3] Peng D Y, Niu X H, Tang X H,.. The average Hamming correlation for the cubic polynomial hopping sequences[C]. International Conference on Wireless Communications and Mobile Computing, Crete, Greece, 2008: 464-469.

[4] Ding C S and Yin J X. Sets of optimal frequency-hopping sequences[J]., 2008, 54(8): 3741-3745.

[5] Zhang Y, Ke P H, and Zhang S Y. Optimal frequency-hopping sequences based on cyclotomy[C]. First International Workshop on Education Technology and Computer Science, Wuhan, China, 2009: 1122-1126.

[6] Zhou Z C, Tang X H, Peng D Y,..New constructions for optimal sets of frequency-hopping sequences[J]., 2011, 57(6): 3831-3840.

[7] Zeng X Y, Cai H, Tang X H,.. Optimal frequency hopping sequences of odd length[J]., 2013, 59(5): 3237-3248.

[8] Ren W L, Fu F W, and Zhou Z C. New sets of frequency-hopping sequences with optimal Hamming correlation[J]., 2014, 72(2): 423-434.

[9] 劉方, 彭代淵. 一類具有最優(yōu)平均漢明相關(guān)特性的跳頻序列族[J]. 電子與信息學(xué)報(bào), 2010, 32(5): 1257-1261.

Liu F and Peng D Y. A class of frequency-hopping sequence family with optimal average Hamming correlation property[J].&, 2010, 32(5): 1257-1261.

[10] Liu F, Peng D Y, and Zhou Z C. A new frequency-hopping sequence set based upon generalized cyclotomy[J]., 2013, 69(2): 247-259.

[11] 柯品惠, 章海輝, 張勝元. 新的具有最優(yōu)平均漢明相關(guān)性的跳頻序列族[J]. 通信學(xué)報(bào), 2012, 33(9): 168-175.

Ke P H, Zhang H H, and Zhang S Y. New class of frequency-hopping sequence set with optimal average Hamming correlation property[J]., 2012, 33(9): 168-175.

[12] Zhang A X, Zhou Z C, and Feng K Q. A lower bound on the average Hamming correlation of frequency-hopping sequence sets[J]., 2015, 9(1): 55-62.

[13] Kumar P V. Frequency-hopping code sequence designs having large linear span[J]., 1988, 34(1): 146-151.

[14] Chung J H and Yang K. A new class of balanced near-perfect nonlinear mappings and its application to sequence design[J]., 2013, 59(2): 1090-1097.

[15] Agoh T, Dilcher K, and Skula L. Fermat quotients for composite moduli[J].1997, 66(1): 29-50.

[16] Chen Z X. Trace representation and linear complexity of binary sequences derived from Fermat quotients[J]., 2014, 57(11): 1-10.

[17] Peng D Y, Peng T, and Fan P Y. Generalised class of cubic frequency-hopping sequences with large family size[J]., 2005, 152(6): 897-902.

[18] Peng D Y, Peng T, Tang X H,..A class of optimal frequency hopping sequences based upon the theory of power residues[C]. Sequences and Their Applications (SETA 2008), Lexington, KY, USA, 2008: 188-196.

Class of Optimal Frequency-hopping Sequences Set with the Square of Prime Length Based on Cyclotomy

Xu Shan-ding①②Cao Xi-wang②③Xu Guang-kui②④

①(,,211167,)②(,,211106,)③(,,,100093,)④(,,232038,)

The Maximum Hamming Correlation (MHC) and the Average Hamming Correlation (AHC) are two important performance measures of the frequency-hopping sequences. Firstly, some properties of generalized cyclotomy are derived from Fermat quotient. Secondly, based on the generalized cyclotomy, a class of optimal frequency-hoppingsequences set with length of sequencesand size beingdefined onis constructed. Finally, it is proved that the proposed frequency-hopping sequences set is optimal with respect to the maximum Hamming correlation bound and the average Hamming correlation bound.

Frequency-hopping sequence; Fermat quotient;Cyclotomy; Maximum Hamming correlation bound; Average Hamming correlation bound

TN914.41

A

1009-5896(2015)10-2460-06

10.11999/JEIT150168

2015-01-29；改回日期：2015-05-29；

2015-07-06

徐善頂 sdxzx11@163.com

國家自然科學(xué)基金(11371011)和南京工程學(xué)院校級(jí)科研基金(QKJA201307)

The National Natural Science Foundation of China (11371011); The Foundation of Nanjing Institute of Technology (QKJA201307)

徐善頂： 男，1979年生，講師，主要研究方向?yàn)樘l序列分析與設(shè)計(jì).

曹喜望： 男，1965年生，教授，主要研究方向?yàn)榇鷶?shù)組合論與代數(shù)密碼學(xué).

許廣魁： 男，1981年生，講師，主要研究方向?yàn)榇鷶?shù)組合論與代數(shù)密碼學(xué).