Johnsson, S. LennartHo, Ching-Tien2016-03-111991Johnsson, S. Lennart and Ching-Tien Ho. 1991. On the Conversion between Binary Code and Binary-Reflected Gray Code on Boolean Cubes. Harvard Computer Science Group Technical Report TR-20-91.http://nrs.harvard.edu/urn-3:HUL.InstRepos:25811007We 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.en-USResearch Paper or Report2016-03-11