Bounds on Codes for the Bit-Shift Channel with (d,k)-Constrained Inputs

Abstract

This paper studies the error correction problem for bit-shift channels with the so-called (d,k) input constraints (where successive 1's are required to be separated by at least d and at most k zeros). Bounds on the size of optimal (d,k)-constrained codes correcting any given number of bit-shifts are derived, with a focus on their asymptotic form in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of (d,k)-constrained sequences that may be of independent interest are established as well; in particular, the exponential growth rate of the number of (d,k)-constrained constant-weight sequences is characterized.