Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Conversion between Binary Code and Binary Reflected Gray Code
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1995 (English)In: I.E.E.E. transactions on computers (Print), ISSN 0018-9340, E-ISSN 1557-9956, Vol. 44, no 1, 47-53 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
1995. Vol. 44, no 1, 47-53 p.
Keyword [en]
GRAY-TO-BINARY CONVERSION; BINARY CODE ENCODING; GRAY CODE ENCODING HYPERCUBES; PERMUTATION; ROUTING ALGORITHM; COMMUNICATION ALGORITHM; ALL-PORT COMMUNICATION
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-90983OAI: oai:DiVA.org:kth-90983DiVA: diva2:507633
Note
NR 20140805Available from: 2012-03-05 Created: 2012-03-05 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
In the same journal
I.E.E.E. transactions on computers (Print)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf