TR-09-08: Improved Methods For Generating Quasi-Gray Codes

Abstract

Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits, and the same holds for the first and last strings in the sequence. We call this sequence a cyclic quasi-Gray code. We examine the problem of efficiently generating such codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results show a trade-off between these four constraints, and present algorithms which do less work on average than previous results, while also increasing the number of strings generated. Previous work has required at least one extra bit in the algorithms, such that at most 1/2 of the possible bit strings are generated. Our results do not require an extra bit, and generate a factor of 1-O(d^{-t}), for a constant t, of the possible bit strings.

TR-09-08.pdf