On binary reflected Gray codes and functions

Authors

Martin W. Bunder, University of WollongongFollow
Keith P. Tognetti, University of WollongongFollow
Glen Wheeler, University of WollongongFollow

RIS ID

23071

Publication Details

Bunder, M. W., Tognetti, K. P. & Wheeler, G. (2008). On binary reflected Gray codes and functions. Discrete Mathematics, 308 (9), 1690-1700.

Abstract

The Binary Reflected Gray Code function b is defined as follows: If m is a nonnegative integer, then b(m) is the integer obtained when initial zeros are omitted from the binary reflected Gray code of length m. This paper examines this Gray code function and its inverse and gives simple algorithms to generate both. It also simplifies Conder’s result that the jth letter of the kth word of the binary reflected Gray code of length n, is

(2ⁿ − 2^n−j − 1

[2ⁿ − 2^n−j−1 − k/2]) mod 2,

by replacing the binomial coefficient by

[(k-1)/(2^n-j+1)+1/2].