A Simple Proof for the Existence of Exponentially Balanced Gray Codes

Abstract

A Gray code of length $n$ is a circular list of all $2^n$ bitstrings or binary codewords of length $n$ such that successive codewords differ in only one bit position. The frequencies of the positions where these differences occur are called transition counts. An exponentially balanced Gray code is a Gray code the transition counts of which are all the same power of two, or are two successive powers of two. A proof for the existence of exponentially balanced Gray codes is derived. The proof is much simpler than an earlier proof presented by van Zanten and Suparta (Discrete Analysis and Operation Research, 11 (2004) 81-98 (Russian Journal)).