American Institute of Mathematical Sciences

Advanced
August  2014, 8(3): 359-373. doi: 10.3934/amc.2014.8.359

Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions

Xing Liu 1, and  Daiyuan Peng 1,

1. 

Provincial Key Laboratory of Information Coding and Transmission, Institute of Mobile Communications, Southwest Jiaotong University, Chengdu, Sichuan 610031, China, China

Received  January 2014 Revised  April 2014 Published  August 2014

In order to evaluate the goodness of frequency hopping (FH) sequence design, the periodic Hamming correlation function is used as an important measure. Aperiodic Hamming correlation of FH sequences matters in real applications, while it received little attraction in the literature compared with periodic Hamming correlation. In this paper, an upper bound on the family size of FH sequences, with respect to the size of the frequency slot set, the sequence length, the maximum aperiodic Hamming correlation is established. Further, a construction of optimal FH sequence sets under aperiodic Hamming correlation from Reed-Solomon codes is presented, whose parameters meet the upper bound with equality. From generalized $m$ sequences (GM sequences) and generalized Gordon-Mills-Welch sequences (GGMW sequences), two classes of optimal FH sequence sets under aperiodic Hamming correlation are also presented, whose parameters meet the upper bound with equality.
Keywords: frequency hopping spread spectrum, aperiodic Hamming correlation, the Peng-Fan bound, Frequency hopping sequences, upper bound..
Mathematics Subject Classification: Primary: 94A55; Secondary: 94B0.
Citation: Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359
References:
[1]

, Specification of the bluetooth system: core, Bluetooth S. I. G. Inc., available from: http://www.bluetooth.com

[2]

J. H. Chung, Y. K. Han and K. Yang, New classes of optimal frequency-hopping sequences by interleaving techniques, IEEE Trans. Inf. Theory, 55 (2009), 5783-5791. doi: 10.1109/TIT.2009.2032742.

[3]

C. Ding, R. Fuji-Hara, Y. Fujiwara, M. Jimbo and M. Mishima, Sets of frequency hopping sequences: bounds and optimal constructions, IEEE Trans. Inf. Theory, 55 (2009), 3297-3304. doi: 10.1109/TIT.2009.2021366.

[4]

C. Ding, Y. Yang and X. H. Tang, Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 55 (2010), 3605-3612. doi: 10.1109/TIT.2010.2048504.

[5]

Y. C. Eun, S. Y. Jin, Y. P. Hong and H. Y. Song, Frequency hopping sequences with optimal partial autocorrelation properties, IEEE Trans. Inf. Theory, 50 (2004), 2438-2442. doi: 10.1109/TIT.2004.834792.

[6]

P. Z. Fan and M. Darnell, Sequence Design for Communications Applications, Research Studies Press, London, 1996.

[7]

P. Z. Fan, M. H. Lee and D. Y. Peng, New family of hopping sequences for time/frequency-hopping CDMA systems, IEEE Trans. Wireless Commun., 4 (2005), 2836-2842.

[8]

G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties, IEEE Trans. Inf. Theory, 55 (2009), 867-879. doi: 10.1109/TIT.2008.2009856.

[9]

S. W. Golomb, A mathematical theory of discrete classification, in Proc. 4th London Symp. Inf. Theory, 1961, 404-425.

[10]

S. W. Golomb, Optimal frequency hopping sequences for multiple access, Proc. Symp. Spread Spectrum Commun., 1 (1973), 33-35.

[11]

S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge Univ. Press, 2005. doi: 10.1017/CBO9780511546907.

[12]

S. W. Golomb, B. Gordon and L. R. Welch, Comma-free codes, Canad. J. Math., 10 (1958), 202-209. doi: 10.4153/CJM-1958-023-9.

[13]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier, 1998, 1767-1853.

[14]

A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inf. Theory, 20 (1974), 90-94.

[15]

R. Lidl and H. Niederreiter, Finite Fields, Cambridge Univ. Press, 1997.

[16]

X. H. Niu, D. Y. Peng and Z. C. Zhou, Frequency/time hopping sequence sets with optimal partial Hamming correlation properties, Sci. China Ser. F, 55 (2012), 2207-2215. doi: 10.1007/s11432-012-4620-9.

[17]

D. Y. Peng and P. Z. Fan, Lower bounds on the Hamming auto- and cross-correlations of frequency-hopping sequences, IEEE Trans. Inf. Theory, 50 (2004), 2149-2154. doi: 10.1109/TIT.2004.833362.

[18]

D. Y. Peng, P. Z. Fan and M. H. Lee, Lower bounds on the periodic Hamming correlations of frequency hopping sequences with low hit zone, Sci. China Ser. F, 49 (2006), 208-218. doi: 10.1007/s11432-006-0208-6.

[19]

D. Y. Peng, T. Peng, X. H. Tang and X. H. Niu, A class of optimal frequency hopping sequences based upon the theory of power residues, in Proc. 5th Int. Conf. Sequences Appl., 2008, 188-196. doi: 10.1007/978-3-540-85912-3_18.

[20]

I. S. Reed, $k$th-order near-orthogonal codes, IEEE Trans. Inf. Theory, 17 (1971), 116-117.

[21]

I. S. Reed and H. Blasbalg, Multipath tolerant ranging and data transfer techniques for air-to-ground and ground-to-air links, Proc. IEEE, 58 (1970), 422-429. doi: 10.1109/PROC.1970.7649.

[22]

H. Y. Song, I. S. Reed and S. W. Golomb, On the nonperiodic cyclic equivalent classes of Reed-Solomon codes, IEEE Trans. Inf. Theory, 39 (1993), 1431-1434. doi: 10.1109/18.243465.

[23]

P. Udaya and M. U. Siddiqi, Optimal large linear complexity frequency hopping patterns derived from polynomial residue class rings, IEEE Trans. Inf. Theory, 44 (1998), 1492-1503. doi: 10.1109/18.681324.

[24]

Y. Yang, X. H. Tang, P. Udaya and D. Y. Peng, New bound on frequency hopping sequence sets and its optimal constructions, IEEE Trans. Inf. Theory, 57 (2011), 7605-7613. doi: 10.1109/TIT.2011.2162571.

[25]

Z. C. Zhou, X. H. Tang, X. H. Niu and P. Udaya, New classes of frequency-hopping sequences with optimal partial correlation, IEEE Trans. Inf. Theory, 58 (2012), 453-458. doi: 10.1109/TIT.2011.2167126.

show all references

References:
[1]

, Specification of the bluetooth system: core, Bluetooth S. I. G. Inc., available from: http://www.bluetooth.com

[2]

J. H. Chung, Y. K. Han and K. Yang, New classes of optimal frequency-hopping sequences by interleaving techniques, IEEE Trans. Inf. Theory, 55 (2009), 5783-5791. doi: 10.1109/TIT.2009.2032742.

[3]

C. Ding, R. Fuji-Hara, Y. Fujiwara, M. Jimbo and M. Mishima, Sets of frequency hopping sequences: bounds and optimal constructions, IEEE Trans. Inf. Theory, 55 (2009), 3297-3304. doi: 10.1109/TIT.2009.2021366.

[4]

C. Ding, Y. Yang and X. H. Tang, Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 55 (2010), 3605-3612. doi: 10.1109/TIT.2010.2048504.

[5]

Y. C. Eun, S. Y. Jin, Y. P. Hong and H. Y. Song, Frequency hopping sequences with optimal partial autocorrelation properties, IEEE Trans. Inf. Theory, 50 (2004), 2438-2442. doi: 10.1109/TIT.2004.834792.

[6]

P. Z. Fan and M. Darnell, Sequence Design for Communications Applications, Research Studies Press, London, 1996.

[7]

P. Z. Fan, M. H. Lee and D. Y. Peng, New family of hopping sequences for time/frequency-hopping CDMA systems, IEEE Trans. Wireless Commun., 4 (2005), 2836-2842.

[8]

G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties, IEEE Trans. Inf. Theory, 55 (2009), 867-879. doi: 10.1109/TIT.2008.2009856.

[9]

S. W. Golomb, A mathematical theory of discrete classification, in Proc. 4th London Symp. Inf. Theory, 1961, 404-425.

[10]

S. W. Golomb, Optimal frequency hopping sequences for multiple access, Proc. Symp. Spread Spectrum Commun., 1 (1973), 33-35.

[11]

S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge Univ. Press, 2005. doi: 10.1017/CBO9780511546907.

[12]

S. W. Golomb, B. Gordon and L. R. Welch, Comma-free codes, Canad. J. Math., 10 (1958), 202-209. doi: 10.4153/CJM-1958-023-9.

[13]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier, 1998, 1767-1853.

[14]

A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inf. Theory, 20 (1974), 90-94.

[15]

R. Lidl and H. Niederreiter, Finite Fields, Cambridge Univ. Press, 1997.

[16]

X. H. Niu, D. Y. Peng and Z. C. Zhou, Frequency/time hopping sequence sets with optimal partial Hamming correlation properties, Sci. China Ser. F, 55 (2012), 2207-2215. doi: 10.1007/s11432-012-4620-9.

[17]

D. Y. Peng and P. Z. Fan, Lower bounds on the Hamming auto- and cross-correlations of frequency-hopping sequences, IEEE Trans. Inf. Theory, 50 (2004), 2149-2154. doi: 10.1109/TIT.2004.833362.

[18]

D. Y. Peng, P. Z. Fan and M. H. Lee, Lower bounds on the periodic Hamming correlations of frequency hopping sequences with low hit zone, Sci. China Ser. F, 49 (2006), 208-218. doi: 10.1007/s11432-006-0208-6.

[19]

D. Y. Peng, T. Peng, X. H. Tang and X. H. Niu, A class of optimal frequency hopping sequences based upon the theory of power residues, in Proc. 5th Int. Conf. Sequences Appl., 2008, 188-196. doi: 10.1007/978-3-540-85912-3_18.

[20]

I. S. Reed, $k$th-order near-orthogonal codes, IEEE Trans. Inf. Theory, 17 (1971), 116-117.

[21]

I. S. Reed and H. Blasbalg, Multipath tolerant ranging and data transfer techniques for air-to-ground and ground-to-air links, Proc. IEEE, 58 (1970), 422-429. doi: 10.1109/PROC.1970.7649.

[22]

H. Y. Song, I. S. Reed and S. W. Golomb, On the nonperiodic cyclic equivalent classes of Reed-Solomon codes, IEEE Trans. Inf. Theory, 39 (1993), 1431-1434. doi: 10.1109/18.243465.

[23]

P. Udaya and M. U. Siddiqi, Optimal large linear complexity frequency hopping patterns derived from polynomial residue class rings, IEEE Trans. Inf. Theory, 44 (1998), 1492-1503. doi: 10.1109/18.681324.

[24]

Y. Yang, X. H. Tang, P. Udaya and D. Y. Peng, New bound on frequency hopping sequence sets and its optimal constructions, IEEE Trans. Inf. Theory, 57 (2011), 7605-7613. doi: 10.1109/TIT.2011.2162571.

[25]

Z. C. Zhou, X. H. Tang, X. H. Niu and P. Udaya, New classes of frequency-hopping sequences with optimal partial correlation, IEEE Trans. Inf. Theory, 58 (2012), 453-458. doi: 10.1109/TIT.2011.2167126.

[1]

Xing Liu, Daiyuan Peng. Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques. Advances in Mathematics of Communications, 2017, 11 (1) : 151-159. doi: 10.3934/amc.2017009
[2]

Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55
[3]

Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004
[4]

Fang Liu, Daiyuan Peng, Zhengchun Zhou, Xiaohu Tang. New constructions of optimal frequency hopping sequences with new parameters. Advances in Mathematics of Communications, 2013, 7 (1) : 91-101. doi: 10.3934/amc.2013.7.91
[5]

Xianhua Niu, Daiyuan Peng, Zhengchun Zhou. New classes of optimal frequency hopping sequences with low hit zone. Advances in Mathematics of Communications, 2013, 7 (3) : 293-310. doi: 10.3934/amc.2013.7.293
[6]

Shanding Xu, Xiwang Cao, Jiafu Mi, Chunming Tang. More cyclotomic constructions of optimal frequency-hopping sequences. Advances in Mathematics of Communications, 2019, 13 (3) : 373-391. doi: 10.3934/amc.2019024
[7]

Lenny Fukshansky, Ahmad A. Shaar. A new family of one-coincidence sets of sequences with dispersed elements for frequency hopping cdma systems. Advances in Mathematics of Communications, 2018, 12 (1) : 181-188. doi: 10.3934/amc.2018012
[8]

Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209
[9]

Jingjun Bao. New families of strictly optimal frequency hopping sequence sets. Advances in Mathematics of Communications, 2018, 12 (2) : 387-413. doi: 10.3934/amc.2018024
[10]

Xianhong Xie, Yi Ouyang, Honggang Hu, Ming Mao. Construction of three classes of strictly optimal frequency-hopping sequence sets. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022024
[11]

Wenli Ren, Feng Wang. A new class of optimal wide-gap one-coincidence frequency-hopping sequence sets. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020131
[12]

Hongyu Han, Sheng Zhang. New classes of strictly optimal low hit zone frequency hopping sequence sets. Advances in Mathematics of Communications, 2020, 14 (4) : 579-589. doi: 10.3934/amc.2020031
[13]

Xiujie Zhang, Xianhua Niu, Xin Tan. Constructions of optimal low hit zone frequency hopping sequence sets with large family size. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021071
[14]

Wenjuan Yin, Can Xiang, Fang-Wei Fu. Two constructions of low-hit-zone frequency-hopping sequence sets. Advances in Mathematics of Communications, 2022, 16 (2) : 249-267. doi: 10.3934/amc.2020110
[15]

Mohammed Mesk, Ali Moussaoui. On an upper bound for the spreading speed. Discrete and Continuous Dynamical Systems - B, 2022, 27 (7) : 3897-3912. doi: 10.3934/dcdsb.2021210
[16]

Yuntao Zang. An upper bound of the measure-theoretical entropy. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022052
[17]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems and Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[18]

Alain Miranville, Xiaoming Wang. Upper bound on the dimension of the attractor for nonhomogeneous Navier-Stokes equations. Discrete and Continuous Dynamical Systems, 1996, 2 (1) : 95-110. doi: 10.3934/dcds.1996.2.95
[19]

Gang Meng. The optimal upper bound for the first eigenvalue of the fourth order equation. Discrete and Continuous Dynamical Systems, 2017, 37 (12) : 6369-6382. doi: 10.3934/dcds.2017276
[20]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (166)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy