On the Conversion between Binary Code and Binary-Reflected Gray Code on Boolean Cubes

Abstract

We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately (2K/3) element transfers in sequence for K elements per node, compared to K element transfers for previously known algorithms. For a binary cube of n = 2 dimensions the new algorithm degenerates to yield a complexity of (K/2)+1 element transfers, which is optimal. The new algorithm is optimal within a factor of 1/3 with respect to the best known lower bound for any routing strategy. We show that the minimum number of element transfers for minimum path length routing is K with concurrent communication on all channels of every node of a binary cube.