On the Conversion Between Binary Code and Binary-Reflected Gray Code on Binary Cubes

Abstract

We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately [Formula Omitted] 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 [Formula Omitted] element transfers, which is optimal. The new algorithm is optimal to within a multiplicative factor of [Formula Omitted] 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 A″ with concurrent communication on all channels of every node of a binary cube. © 1995 IEEE