New families of strictly optimal frequency hopping sequence sets

Jingjun Bao

doi:10.3934/amc.2018024

Article Contents

2018, Volume 12, Issue 2: 387-413. Doi: 10.3934/amc.2018024

This issue Previous Article The weight distribution of quasi-quadratic residue codes Next Article On some classes of codes with a few weights

New families of strictly optimal frequency hopping sequence sets

Jingjun Bao

Department of Mathematics, Ningbo University, Ningbo 315211, China

Received: May 31, 2017

Revised: October 31, 2017

Published: April 2018

The first author is supported by the NSFC under Grants 11701303, and K.C.Wong Magna Fund in Ningbo University

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

Frequency hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, we investigate constructions of FHS sets with optimal partial Hamming correlation. We present several direct constructions for balanced nested cyclic difference packings (BNCDPs) and balanced nested cyclic relative difference packings (BNCRDPs) by using trace functions and discrete logarithm. We also show three recursive constructions for FHS sets with partial Hamming correlation, which are based on cyclic difference matrices and discrete logarithm. Combing these BNCDPs, BNCRDPs and three recursive constructions, we obtain infinitely many new strictly optimal FHS sets with respect to the Peng-Fan bounds.

Keywords:

Mathematics Subject Classification: Primary: 94A55, 94A05; Secondary: 05B40.

Citation:

Full Text(HTML)

Table Ⅰ. SOME KNOWN FHS SETS WITH OPTIMA HAMMING CORRELATION

Length	Number of sequences	$H_{max}$	Alphabet size	Constraints	Reference
$p(q-1)$	$\left\lfloor \frac{c}{p}\right\rfloor$	$pd$	$c+1$	$q-1=cd$, $c\geq p(d+1)$, gcd$(p, q-1)=1$	[25]
$q^m-1$	$q^u$	$q^{m-u}$	$q^u$	$m > u \geq 1$	[31]
$\frac{q^m-1}{d}$	$d$	$\frac{q^{m-u}-1}{d}$	$q^u$	$d\|q-1$, $ m > u \geq 1$, gcd$(d, m)=1$	[31]
$\frac{q+1}{d}$	$d(q-1)$	$1$	$q$	$q+1\equiv d \pmod {2d}$	[15]
$2^{2u}+1$	$2^{2u}-1$	$2^u+1$	$2^u$		[13]
$up^2$	$\left\lfloor \frac{p}{u}\right\rfloor$	$up$	$p$	$ p>u\geq 2$	[9]
$u\frac{q^m-1}{d}$	$\left\lfloor \frac{d}{u}\right\rfloor$	$u\frac{q^{m-1}-1}{d}$	$q$	$ d\geq u \geq 2$, $d\|q-1$, gcd$(m, d)=1$	[9]
$v$	$f$	$e$	$\frac{v-1}{e}+1$	$v$ is not a prime or $v$ is a prime with $f\geq e >1$	[30]
$\frac{w(q^m-1)}{d}$	$d$	$\frac{q^{m-u}-1}{d}$	$wq^u$	$d\|q-1$, gcd$(d, m)=1$, $q_1>q^{m-u}$, $m > u \geq 1$	[2]
$vw$	$f$	$e$	$\frac{v-1}{e}w+\frac{w-1}{e^{'}}+1$	$e\geq e'\geq 2$, $v\geq e^2$, $q_1\geq p_1> 2e$	[2]
$vwu(q-1)$	$\lfloor \frac{c}{u}\rfloor$	$ud$	$cvw+\frac{(v-1)w}{e}+\frac{w-1}{e^{'}}+1$	$q-1=cd$, $c\geq u(d+1)$, $d\geq e\geq e'\geq 2$, gcd$(u, q-1)=1$, $q_1 \geq p_1> q-1$	[2]
$vu(q-1)$	$\lfloor\frac{f}{u}\rfloor$	$eu$	$\frac{vq-q}{e}+c+1$	$q-1=cd$, $c \geq u(d+1)$, gcd$(u, q-1)=1$, $q\geq \max\{p_1-1, 4ue\}$, $e\geq d$, $p_1> 2ue$, $v \geq 4e^2u$	[2]
$m, u, c$ and $d$ are positive integers; $p$ is a prime and $q$ is a prime power; $v$ is an integer with prime factor decomposition $v=p_1^{m_1}p_2^{m_2}\cdots p_s^{m_s}$ with $p_1 <p_2<\ldots<p_s$; $e$ is an integer such that $e\|gcd(p_1-1, p_2-1, \ldots, p_s-1)$, and $f=\frac{p_1-1}{e}$; $w$ is an integer with prime factor decomposition $w=q_1^{n_1}q_2^{n_2}\cdots q_t^{n_t}$ with $q_1<q_2<\ldots<q_t$; $e'$ is an integer such that $e'\|gcd(q_1-1, q_2-1, \ldots, q_t-1)$

| Show Table

DownLoad: CSV

Table Ⅱ. SOME KNOWN FHS SETS WITH OPTIMAL PARTIAL HAMMING CORRELATION

Length	Alphabet size	$H_{max}$ over correlation window of length L	Number of sequences	Constraints	Source
$\frac{q^m-1}{d}$	$q^{m-1}$	$\left\lceil \frac{L(q-1)}{q^m-1}\right\rceil$	$d$	$d\|(q-1)$, gcd$(d, m)=1$	[32]
$ev$	$v$	$\left\lceil \frac{L}{v}\right\rceil$	$f$		[4]
$ p(p^m-1)$	$p^{m}$	$\left\lceil\frac{L}{p^{m}-1}\right\rceil$	$p^{m-1}$	$m\geq 2$	[5]
$evw$	$(v-1)w+\frac{ew}{r}$	$\left\lceil \frac{L}{vw}\right\rceil$	$f$	$q_1\geq p_1>2e$, $r\|e$ $v\geq \frac{p_1e}{r}$ and $gcd(w, e)=1$	[1]
$v\frac{q^m-1}{d}$	$vq^{m-1} $	$\left\lceil \frac{(q-1)L}{v(q^{m}-1)}\right\rceil$	$d$	$m>1, $ $q^m \leq p_1$ and $gcd(d, m)=1, $ $d\|q-1$, $\frac{q^m-1}{d}\|p_i-1$ for $1\leq i \leq s$	[1]
$q$ is a prime power and $p$ is a prime; $v$ is an integer with prime factor decomposition $v=p_1^{m_1}p_2^{m_2}\cdots p_s^{m_s}$ with $p_1 < p_2<\cdots <p_s$; $e, f$ are integers such that $e>1$ and $e\|gcd(p_1-1, p_2-1, \ldots, p_s-1)$, and $f=\frac{p_1-1}{e}$; $w$ is an integer with prime factor decomposition $w=q_1^{n_1}q_2^{n_2}\cdots q_t^{n_t}$ with $q_1<q_2<\cdots <q_t$; $r$ is an integer such that $r>1$ and $r\|gcd(q_1-1, q_2-1, \ldots, q_t-1)$; $d, m$ are positive integers.

| Show Table

DownLoad: CSV

Table Ⅲ. NEW FHS SETS WITH OPTIMAL PARTIAL HAMMING CORRELATION

Length	Alphabet size	$H_{max}$	Number of sequences	Constraints	Reference
$\frac{w(q^m-1)}{d}$	$(q^{m-1}-1+\frac{q-1}{d})w$	$\frac{q-1}{d}$	$d$	$m\geq 3$, $d\|q-1$, gcd$(m, d)=1$, $q_1>q, $	Corollary 6
$wp(p^m-1)$	$p^{m}w$	$p$	$p^{m-1}$	$m>1, \ $ and $q_1>p^m, $	Corollary 7
$ewv$	$(v-1+e)w$	$e$	$f$	$q_1>p_1-1$, If $v$ is not a prime with $f>1$ or $v$ is a prime with $f\geq e$,	Corollary 8
$pv(p^m-1)$	$vp^m$	$p$	$f_1$	$p\|p_i-1$, $f_1=\frac{p_1-1}{p}\geq 2$, $p^m >p_1-1$, $p^m>2(1+p)$	Corollary 9
$(q'-1)\frac{q^m-1}{d}$	$(q^{m-1}-1+\frac{q-1}{d})q'$	$\frac{q-1}{d}$	$d$	$d\|q-1$, gcd$(m, d)=1$, $d\geq 2$ $gcd(q'-1, \frac{q-1}{d})=1$, $q'>q+1$	Corollary 10
$(q-1)p(p^m-1)$	$p^{m}q$	$p$	$p^{m-1}$	$p^{m}-3p\geq 1$, $q\geq p^m$, $gcd(q-1, p)=1$, $m>1$	Corollary 11
$ev(q-1)$	$(v-1+e)q$	$e$	$f$	$q> p_1-1$, $v\geq e^3f^2$, $q\geq 2e+5$, $gcd(q-1, e)=1$, $f>1$	Corollary 12
$q, q'$ are prime powers and $p$ is a prime; $v$ is an integer with prime factor decomposition $v=p_1^{m_1}p_2^{m_2}\cdots p_s^{m_s}$ with $p_1 < p_2<\ldots<p_s$; $e$ is an integer such that $e\| gcd(p_1-1, p_2-1, \ldots, p_s-1)$, and $f=\frac{p_1-1}{e}$; $w$ is any an integer with prime factor decomposition $w=q_1^{n_1}q_2^{n_2}\cdots q_t^{n_t}$ with $q_1<q_2<\ldots<q_t$; $d, m$ are positive integers.

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	J. Bao and L. Ji , Frequency hopping sequences with optimal partial hamming correlation, IEEE Trans. Inf. Theory, 62 (2016) , 3768-3783. doi: 10.1109/TIT.2016.2551225.
	J. Bao and L. Ji , New families of optimal frequency hopping sequence sets, IEEE Trans. Inf. Theory, 62 (2016) , 5209-5224. doi: 10.1109/TIT.2016.2589258.
	Bluetooth Special Interest Group (SIG), Washington, DC, USA. (2003, Nov.). Specification of the Bluetooth Systems-Core [Online]. Available: http://www.bluetooth.org
	H. Cai , Z. Zhou , Y. Yang and X. Tang , A new construction of frequency hopping sequences with optimal partial Hamming correlation, IEEE Trans. Inf. Theory, 60 (2014) , 5782-5790. doi: 10.1109/TIT.2014.2332996.
	H. Cai , Y. Yang , Z. Zhou and X. Tang , Strictly optimal frequency-hopping sequence sets with optimal family sizes, IEEE Trans. Inf. Theory, 62 (2016) , 1087-1093. doi: 10.1109/TIT.2015.2512859.
	B. Chen , L. Lin , S. Ling and H. Liu , Three new classes of optimal frequency-hopping sequence sets, Des. Codes Cryptogr., 83 (2017) , 219-232. doi: 10.1007/s10623-016-0220-9.
	W. Chu and C. J. Colbourn , Optimal frequency-hopping sequences via cyclotomy, IEEE Trans. Inf. Theory, 51 (2005) , 1139-1141. doi: 10.1109/TIT.2004.842708.
	J.-H. Chung , G. Gong and K. Yang , New families of optimal frequency-hopping sequences by composite lengths, IEEE Trans. Inf. Theory, 60 (2014) , 3688-3697. doi: 10.1109/TIT.2014.2315207.
	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.
	J.-H. Chung and K. Yang , $k$ -fold cyclotomy and its application to frequency-hopping sequences, IEEE Trans. Inf. Theory, 57 (2011) , 2306-2317. doi: 10.1109/TIT.2011.2112235.
	J.-H. Chung and K. Yang , Optimal frequency-hopping sequences with new parameters, IEEE Trans. Inf. Theory, 56 (2010) , 1685-1693. doi: 10.1109/TIT.2010.2040888.
	C. J. Colbourn, The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 2010. doi: 10. 1201/9781420049954.
	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.
	C. Ding , M. J. Moisio and J. Yuan , Algebraic constructions of optimal frequency-hopping sequences, IEEE Trans. Inf. Theory, 53 (2007) , 2606-2610. doi: 10.1109/TIT.2007.899545.
	C. Ding , Y. Yang and X. Tang , Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 56 (2010) , 3605-3612. doi: 10.1109/TIT.2010.2048504.
	C. Ding and J. Yin , Sets of optimal frequency-hopping sequences, IEEE Trans. Inf. Theory, 54 (2008) , 3741-3745. doi: 10.1109/TIT.2008.926410.
	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.
	C. Fan , H. Cai and X. Tang , A combinatorial construction for strictly optimal frequency-hopping sequences, IEEE Trans. Inf. Theory, 62 (2016) , 4769-4774. doi: 10.1109/TIT.2016.2556710.
	P. Fan and M. Darnell, Sequence Design for Communications Applications, London, U. K. : Wiley, 1996.
	R. Fuji-Hara , Y. Miao and M. Mishima , Optimal frequency hopping sequences: A combinatorial approach, IEEE Trans. Inf. Theory, 50 (2004) , 2408-2420. doi: 10.1109/TIT.2004.834783.
	G. Ge , R. Fuji-Hara and Y. Miao , Further combinatorial constructions for optimal frequency-hopping sequences, J. Combin. Theory Ser. A, 113 (2006) , 1699-1718. doi: 10.1016/j.jcta.2006.03.019.
	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.
	A. Lempel and H. Greenberger , Families of sequences with optimal Hamming-correlation properties, IEEE Trans. Inf. Theory, 20 (1974) , 90-94.
	D. Peng and P. 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.
	W. Ren , F. Fu and Z. Zhou , New sets of frequency-hopping sequences with optimal Hamming correlation, Des. Codes Cryptogr., 72 (2014) , 423-434. doi: 10.1007/s10623-012-9774-3.
	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.
	L. Yang and G. B. Giannakis , Ultra-wideband communications: An idea whose time has come, IEEE Signal Process. Mag., 21 (2004) , 26-54.
	Y. Yang , X. Tang , P. Udaya and D. 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.
	X. Zeng , H. Cai , X. Tang and Y. Yang , A class of optimal frequency hopping sequences with new parameters, IEEE Trans. Inf. Theory, 58 (2012) , 4899-4907. doi: 10.1109/TIT.2012.2195771.
	X. Zeng , H. Cai , X. Tang and Y. Yang , Optimal frequency hopping sequences of odd length, IEEE Trans. Inf. Theory, 59 (2013) , 3237-3248. doi: 10.1109/TIT.2013.2237754.
	Z. Zhou , X. Tang , D. Peng and U. Parampalli , New constructions for optimal sets of frequency-hopping sequences, IEEE Trans. Inf. Theory, 57 (2011) , 3831-3840. doi: 10.1109/TIT.2011.2137290.
	Z. Zhou , X. Tang , X. Niu and U. Parampalli , New classes of frequency hopping sequences with optimal partial correlation, IEEE Trans. Inf. Theory, 58 (2012) , 453-458. doi: 10.1109/TIT.2011.2167126.