Linear Programming Bound on Frequency Hopping Sequences

There are several theoretical bounds on frequency hopping (FH) sequences. Each bound is tight in most cases while not tight in some other cases. Besides, the linear programming bound on FH sequences directly converted from that on error correcting codes can be made to be tighter due to the special structure of FH sequences. In this paper, we first give some properties of FH sequences and derive an inequality relationship between FH sequences and Krawtchouk polynomials. By utilizing those properties of FH sequences and the inequality relationship, we establish a linear programming bound on FH sequences. It is actually a nonlinear programming bound for gcd (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H_m</i>+1,<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>)1 and Σ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">^Hm</i><italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_j=0</i> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A_j</i> ≥ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q^H_m</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+1</sup>–<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H_m</i>+1/gcd(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H_m</i>+1,<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>)–1, but not difficult to be solved. It is showed that the linear programming bound is tighter than the Peng-Fan bound (Plotkin bound), the sphere-packing bound, the Singleton bound, and the improved Singleton bound in some cases.