Sökning: onr:"swepub:oai:DiVA.org:kth-90983" >
On the Conversion b...
On the Conversion between Binary Code and Binary Reflected Gray Code
-
- Johnsson, Lennart (författare)
- KTH,Parallelldatorcentrum, PDC
-
Ho, Ching-Tien (författare)
-
(creator_code:org_t)
- 1995
- 1995
- Engelska.
-
Ingår i: IEEE Transactions on Computers. - 0018-9340 .- 1557-9956. ; 44:1, s. 47-53
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- GRAY-TO-BINARY CONVERSION; BINARY CODE ENCODING; GRAY CODE ENCODING HYPERCUBES; PERMUTATION; ROUTING ALGORITHM; COMMUNICATION ALGORITHM; ALL-PORT COMMUNICATION
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas