Generalized Snake-in-the-Box Codes

Abstract

A snake-in-the-box (SIB) code of order k is defined to be an ordered sequence of binary code words in which adjacent words differ in only one bit, and pairs of code words that are k or more apart in the ordered sequence differ in at least k bit positions. In this paper, constructions for SIB codes of arbitrary order are given, as well as upper bounds on the maximum code sequence length for given order and word size. These codes are potentially useful for binary encoding of analog data. Gray codes are SIB codes of order one, and Kautz has investigated SIB codes of order two. The SIB codes of a given order contain as a subset all SIB codes of higher order.