Counting sequences, Gray codes and lexicodes

A counting sequence of length n is a list of all 2^n binary n-tuples (binary codewords of length n). The number of bit positions where two codewords differ is called the Hamming distance of these two codewords. The average Hamming distance of a counting sequence of length n is defined as the average Hamming distance between the 2^n pairs of successive codewords, including the pair of the last and the first codeword. A counting sequence of length n which has average Hamming distance equal to n-1/2 is called a maximum counting sequence. The number of bit changes in bit position i, in a counting sequence of length n is called the transition count of bit position i. If a counting sequence of length n has the property that the difference between any two bit positions is at most 2, the sequence is called balanced. We introduce a construction for balanced maximum counting sequences for every codeword length n>0, n not equal 4, which implies a proof of a longstanding conjecture of Robinson and Cohn in [IEEE Trans. Computers, vol. C-30, pp. 17-23, 1981]. A counting sequence of length n which has the property that any two successive codewords in the list have the same Hamming distance is called uniform. We introduce a heuristic construction how to construct uniform sequences. This construction occasionally produces balanced sequences, and so gives a partial answer to another conjecture of Robinson and Cohn dealing with the existence of balanced uniform counting sequences [IEEE Trans. Computers, vol. C-30, pp. 17-23, 1981]. A cyclic Gray code of length n is a uniform sequence of length n with Hamming distance exactly one between any two successive codewords. We introduce a construction of Gray codes satisfying the property that either all transition counts are equal to the same power of two, or are all equal to two consecutive powers of two, which proves the conjecture of Wagner and West in [Congressus Numerantium, vol. 80, pp. 217-223, 1991]. Furthermore, we also introduce a construction of Gray codes of length n>0, n not equal 3, inducing the complete graph K_n, thus providing the complete answer for an open problem suggested by Wilmer and Ernst in [Discrete Mathematics, vol. 257, pp. 585-598, 2002]. Moreover, we derive the separability function of the reflected N-ary Gray codes. We also introduce a simple method for the construction of cyclic N-ary Gray codes, and for the construction of constant weight N-ary Gray codes. The separability functions of these codes are derived as well. In the remaining part of the thesis we present a greedy algorithm for the construction of a large class of linear q-ary lexicodes which generalizes the algorithms in several other papers. By applying this method, one can produce linear lexicodes which cannot be constructed by previous algorithms. Especially, we discuss some interesting properties of self-orthogonal ternary lexicodes