# Improved methods for generating quasi-Gray codes

### by Dana Jansens

This is the topic of my Thesis for my Master of Computer Science degree,
where I looked at efficient algorithms to generate Gray codes and
quasi-Gray codes. I looked at measuring efficiency in terms of the
worst-case number of bits
read and written to generate each string in the code, the average number of
bits read, and the space efficiency, or the ratio of
the number of bit strings generated to the dimension of the code.

## 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 give 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 on quasi-Gray codes
has required at least one extra bit for the algorithms, such that
at most *1/2*
of the possible bit strings are generated, while our results do not require
any extra bits. We show that when an algorithm is allowed to read all
*d* bits
in the worst case, it is possible to generate all *2*^{d}
bit strings of a
quasi-Gray code efficiently.
When a smaller worst-case bound is required, we generate a
factor of *1-O(d*^{-t}), for any constant *t > 0*,
of the possible bit strings.

## Thesis

My full thesis can be read here.

## Presentation

I gave a presentation on this topic for the
Carleton Algorithms Seminar
series on March 17, 2010.
My notes used for the talk can be viewed here.

An extended abstract paper version of my thesis will be appearing at the
SWAT 2010
(12th Scandinavian Symposium and Workshops on Algorithm Theory)
conference.