Gray Code Compression

Darko Dimitrov, Tomáš Dvořák, Petr Gregor, and Riste Škrekovski— 2009

An n-bit (cyclic) Gray code is a (cyclic) sequence of all n-bit strings such that consecutive strings differ in a single bit. We describe an algorithm which for every positive integer n constructs an n-bit cyclic Gray code whose graph of transitions is the d-dimensional hypercube Qd if n = 2^d, or a subgraph of Qd if 2^d−1 < n < 2^d. This allows to compress sequences that follow this code so that only Theta (log log n) bits per n-bit string are needed.

TitelGray Code Compression
VerfasserDarko Dimitrov, Tomáš Dvořák, Petr Gregor, and Riste Škrekovski
VerlagFachbereich Mathematik und Informatik, Institut für Informatik, Freie Universität Berlin
OrtTakustraße 9, 14195 Berlin
BibTeX Code@TechReport{, author = { Darko Dimitrov and Tom\'a\v{s} Dvo\v{r}\'ak and Petr Gregor and and Riste \v{S}krekovski }, title = { Gray Code Compression }, journal = { TechReport }, year = { 2009 }, month = { March }, number = { B 09-02 }, institution = { Institut f{\"u}r Informatik }, address = { Freie Universit{\"a}t Berlin }, }