# American Institute of Mathematical Sciences

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

 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.
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., (). Google Scholar [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. doi: 10.1109/TIT.2009.2032742. Google Scholar [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. doi: 10.1109/TIT.2009.2021366. Google Scholar [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. doi: 10.1109/TIT.2010.2048504. Google Scholar [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. doi: 10.1109/TIT.2004.834792. Google Scholar [6] P. Z. Fan and M. Darnell, Sequence Design for Communications Applications,, Research Studies Press, (1996). Google Scholar [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. Google Scholar [8] G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties,, IEEE Trans. Inf. Theory, 55 (2009), 867. doi: 10.1109/TIT.2008.2009856. Google Scholar [9] S. W. Golomb, A mathematical theory of discrete classification,, in Proc. 4th London Symp. Inf. Theory, (1961), 404. Google Scholar [10] S. W. Golomb, Optimal frequency hopping sequences for multiple access,, Proc. Symp. Spread Spectrum Commun., 1 (1973), 33. Google Scholar [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. Google Scholar [12] S. W. Golomb, B. Gordon and L. R. Welch, Comma-free codes,, Canad. J. Math., 10 (1958), 202. doi: 10.4153/CJM-1958-023-9. Google Scholar [13] T. Helleseth and P. V. Kumar, Sequences with low correlation,, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), (1998), 1767. Google Scholar [14] A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties,, IEEE Trans. Inf. Theory, 20 (1974), 90. Google Scholar [15] R. Lidl and H. Niederreiter, Finite Fields,, Cambridge Univ. Press, (1997). Google Scholar [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. doi: 10.1007/s11432-012-4620-9. Google Scholar [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. doi: 10.1109/TIT.2004.833362. Google Scholar [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. doi: 10.1007/s11432-006-0208-6. Google Scholar [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. doi: 10.1007/978-3-540-85912-3_18. Google Scholar [20] I. S. Reed, $k$th-order near-orthogonal codes,, IEEE Trans. Inf. Theory, 17 (1971), 116. Google Scholar [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. doi: 10.1109/PROC.1970.7649. Google Scholar [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. doi: 10.1109/18.243465. Google Scholar [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. doi: 10.1109/18.681324. Google Scholar [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. doi: 10.1109/TIT.2011.2162571. Google Scholar [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. doi: 10.1109/TIT.2011.2167126. Google Scholar

show all references

##### References:
 [1] , Specification of the bluetooth system: core,, Bluetooth S. I. G. Inc., (). Google Scholar [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. doi: 10.1109/TIT.2009.2032742. Google Scholar [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. doi: 10.1109/TIT.2009.2021366. Google Scholar [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. doi: 10.1109/TIT.2010.2048504. Google Scholar [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. doi: 10.1109/TIT.2004.834792. Google Scholar [6] P. Z. Fan and M. Darnell, Sequence Design for Communications Applications,, Research Studies Press, (1996). Google Scholar [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. Google Scholar [8] G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties,, IEEE Trans. Inf. Theory, 55 (2009), 867. doi: 10.1109/TIT.2008.2009856. Google Scholar [9] S. W. Golomb, A mathematical theory of discrete classification,, in Proc. 4th London Symp. Inf. Theory, (1961), 404. Google Scholar [10] S. W. Golomb, Optimal frequency hopping sequences for multiple access,, Proc. Symp. Spread Spectrum Commun., 1 (1973), 33. Google Scholar [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. Google Scholar [12] S. W. Golomb, B. Gordon and L. R. Welch, Comma-free codes,, Canad. J. Math., 10 (1958), 202. doi: 10.4153/CJM-1958-023-9. Google Scholar [13] T. Helleseth and P. V. Kumar, Sequences with low correlation,, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), (1998), 1767. Google Scholar [14] A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties,, IEEE Trans. Inf. Theory, 20 (1974), 90. Google Scholar [15] R. Lidl and H. Niederreiter, Finite Fields,, Cambridge Univ. Press, (1997). Google Scholar [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. doi: 10.1007/s11432-012-4620-9. Google Scholar [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. doi: 10.1109/TIT.2004.833362. Google Scholar [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. doi: 10.1007/s11432-006-0208-6. Google Scholar [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. doi: 10.1007/978-3-540-85912-3_18. Google Scholar [20] I. S. Reed, $k$th-order near-orthogonal codes,, IEEE Trans. Inf. Theory, 17 (1971), 116. Google Scholar [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. doi: 10.1109/PROC.1970.7649. Google Scholar [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. doi: 10.1109/18.243465. Google Scholar [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. doi: 10.1109/18.681324. Google Scholar [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. doi: 10.1109/TIT.2011.2162571. Google Scholar [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. doi: 10.1109/TIT.2011.2167126. Google Scholar
 [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] Alain Miranville, Xiaoming Wang. Upper bound on the dimension of the attractor for nonhomogeneous Navier-Stokes equations. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 95-110. doi: 10.3934/dcds.1996.2.95 [11] Gang Meng. The optimal upper bound for the first eigenvalue of the fourth order equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6369-6382. doi: 10.3934/dcds.2017276 [12] 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 [13] S. E. Kuznetsov. An upper bound for positive solutions of the equation \Delta u=u^\alpha. Electronic Research Announcements, 2004, 10: 103-112. [14] Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029 [15] Mrinal Kanti Roychowdhury. Least upper bound of the exact formula for optimal quantization of some uniform Cantor distributions. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4555-4570. doi: 10.3934/dcds.2018199 [16] Frédéric Vanhove. A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q2$)$. Advances in Mathematics of Communications, 2011, 5 (2) : 157-160. doi: 10.3934/amc.2011.5.157 [17] Mourad Choulli. Local boundedness property for parabolic BVP's and the Gaussian upper bound for their Green functions. Evolution Equations & Control Theory, 2015, 4 (1) : 61-67. doi: 10.3934/eect.2015.4.61 [18] Lutz Recke, Anatoly Samoilenko, Alexey Teplinsky, Viktor Tkachenko, Serhiy Yanchuk. Frequency locking of modulated waves. Discrete & Continuous Dynamical Systems - A, 2011, 31 (3) : 847-875. doi: 10.3934/dcds.2011.31.847 [19] Shi Jin, Peng Qi. A hybrid Schrödinger/Gaussian beam solver for quantum barriers and surface hopping. Kinetic & Related Models, 2011, 4 (4) : 1097-1120. doi: 10.3934/krm.2011.4.1097 [20] Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199

2018 Impact Factor: 0.879