Constructing snake-in-the-box codes and families of such codes covering the hypercube

Constructing snake-in-the-box codes and families of such codes covering the hypercube

Haryanto, L.

van Zanten, A.J. (promotor)

Electrical Engineering, Mathematics and Computer Science

2007-01-15

A snake-in-the-box code (or snake) is a list of binary words of length n such that each word differs from its successor in the list in precisely one bit position. Moreover, any two words in the list differ in at least two positions, unless they are neighbours in the list. The list is considered to be a cyclic list which implies that the \verb+'+first word\verb+'+ is the successor of the \verb+'+last word\verb+'+. The two defining rules mentioned above have to be interpreted in cylic sense. There are some methods known to construct such codes. These are all of a recursive nature, i.e. snakes of a certain length $n$ are constructed from snakes of length $m < n.$ These snakes of length $m$ are already known in some way, either by similar recursive methods, or by computer search, or just by accident. In this thesis a new method is developed to construct snakes in a straightforward, i.e. non-recursive, way. Since this method uses a linear algebraic code, the constructed snakes have an additional kind of structure apart from their \verb+'+snake structure\verb+'+, More precisely, every fourth word of the snake is a word of the applied linear code, and hence, part of the snake (its 'backbone') has the structure of a linear space. Due to this linearity, we are able to give a partial answer to an old problem posed by Erdos \verb+:+ how many disjoint snakes of the same length contain all binary words of length $n$ (known as \verb+'+a cover of the hypercube $Q_n$\verb+'+)? For $n = 2,$ this number is equal to 1, and for < n \leq 4,$ it is equal to 2. We found that 4 snakes suffice for < n \leq 8,$ and so do 8 snakes for < n \leq 16.$ For < n \leq 32$ we found a cover of 16 symmetric snakes. All these results are better than the results known in the literature. Moreover, for all $n > 2,$ our method delivers concrete covers of $Q_n$ with a large symmetry group.

standard gray codes
symmetric transition sequence
snake-in-the-box codes (snakes
minimum-weight basis
fixed-position property
ordered basis of linear code
reed-muller codes
p-cover of hypercube qn by disjoint snakes
invariance translation group

http://resolver.tudelft.nl/uuid:eb9462c4-078b-40ae-9a14-ae61ba46dfa6

90-8559-265-8

Institutional Repository

doctoral thesis

(c) 2007 L. Haryanto