On the conversion between binary code and binary-reflected Gray code on binary cubes

1 January 1995

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 44 (1) , 47-53
https://doi.org/10.1109/12.368010

Abstract

We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately 2 K/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 2 K/+1 element a transfers, which is optimal. The new algorithm is optimal to within a multiplicative factor of 4/3 with respect to the best known 3 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

Keywords

This publication has 0 references indexed in Scilit: