On the Conversion between Binary Code and Binary Reflected Gray Code

• We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires ap proximately 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 to within a multiplicative factor of 4/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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Keyword

GRAY-TO-BINARY CONVERSION; BINARY CODE ENCODING; GRAY CODE ENCODING HYPERCUBES; PERMUTATION; ROUTING ALGORITHM; COMMUNICATION ALGORITHM; ALL-PORT COMMUNICATION

Publication and Content Type

ref (subject category)

art (subject category)