Given a {q} -ary frequency hopping sequence set of length {n} and size {M} with Hamming correlation {H}, one can obtain a {q} -ary (nonlinear) cyclic code of length {n} and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets [1]. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool-martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region.

Additional Metadata
Keywords Cyclic code, sequences
Persistent URL
Journal IEEE Transactions on Information Theory
Niu, X, Xing, C, & Yuan, C. (2020). Asymptotic Gilbert-Varshamov bound on frequency hopping sequences. IEEE Transactions on Information Theory, 66(2), 1213–1218. doi:10.1109/TIT.2019.2951383