Using complementation and resequencing to minimize transitions
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This paper addresses the problem of finding the optimal transmission sequence for a set of data words on a bus—where word order is initially irrelevant—to minimize the total number of transitions.
- Problem
- The authors prove that finding this optimal sequence while allowing word inversion, a challenge termed the Data Ordering Problem with Inversion (DOPI), is NP-complete.
- Method
- The paper combines data reordering with the existing bus-invert coding scheme, allowing words to be complemented, reordered, and then transmitted to minimize transitions.
- Results
- Experimental results show that the proposed polynomial-time approximation algorithm generates solutions that are, on average, within 4.4% of the optimum.
- Contributions
- The authors introduce the combined DOPI problem, prove its computational complexity, present a 1.5-approximation algorithm, and demonstrate its performance empirically.
- Limitations
- Not specified in the abstract.
- Takeaways
- Combining resequencing with word complementation achieves a significant 34.4% reduction in switching activity.
- Applications
- Not specified in the abstract.
- Topics
- Not specified in the abstract.
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Recently, in [3], the following problem was addressed: Given a set of data words or messages to be transmitted over a bus such that the sequence (order) in which they are transmitted is irrelevant, determine the optimum sequence that minimizes the total number of transitions on the bus. In 1994, Stan and Burleson [5] presented the bus-invert method as a means of encoding words for reducing I/O power, in which a word may be inverted and then transmitted if doing so reduces the number of transitions. In this paper, we combine the two paradigms into one — that of sequencing words under the bus-invert scheme for the minimum transitions, i.e., words can be complemented, reordered and then transmitted. We prove that this problem DOPI — Data Ordering Problem with Inversion — is NP-complete. We present a polynomial-time approximation algorithm to solve DOPI that comes within a factor of 1.5 from the optimum. Experimental results show that, on average, the solutions generated by our algorithm were within 4.4% of the optimum, and that resequencing along with complementation leads to 34.4% reduction in switching activity.