Inversion encoding: Difference between revisions

Revision as of 14:26, 3 June 2015

Latest revision as of 18:57, 27 June 2024

(19 intermediate revisions by 12 users not shown)

Line 1:

{{Use dmy dates|date=August 2019|cs1-dates=y}}

'''Inversion Encodingencoding''' is an encoding technique used for [[Bus encoding|encoding bus transmissions]] for low power systems. It is based on the fact that a large amount of power is wasted because of transitions, especially in external buses, and thus reducing thethese transitions willaids helpoptimization inof [[power optimizationsdissipation]]. This is done introducing an additional signal line named INV to the bus lines. This linesignal determines whether the other lines should be inverted or not.

== Overview ==

The Busbus-Invertinvert encoding technique uses an extra signal (INV) to indicate the “polarity”"polarity" of the data. SupposeHaving we have ana bus-invert code word INV@x where @ is the concatenation operator, and x denotes either the source word or its [[ones' complement]]., Thethe bus-invert decoder takes the code word and produces the corresponding source word. If the INV signal is 1, the result is one’sones' complement of x, otherwise it is x.

=== Usage Situationsscenarios===

* High capacitance lines

* High switching activitiesactivity

=== Bus-Invertinvert method ===

# Compute theThe [[Hamming Distancedistance]] (the number of bits in which they differ) between the present bus value (also counting the present invert line) and the next data value is computed.

# If the Hamming distance is larger than n/2, set ''invert'' =is set to 1, and make the next bus value is made equal to the inverted next data value.

# Otherwise let ''invert'' =is set to 0, and let the next bus value is equal to the next data value.

# At the receiver side the contents of the bus must be conditionally inverted according to the invert line, unless the data is not stored encoded as it is (e.g., in a RAM). In any case, the vauevalue of invert must be transmitted over the bus (the method increases the number of lines from n to n+1).<ref name="r1Stan_1995" />

== Example ==

Let us considerConsidering an example of a system which gets one of its data from a sensor., Mostmost of the times,time the sensor may be measuring some noise. and forFor this example, let us consider that the values being measured areshould be assumed to be (0) and (-1) alternatively. For a 32-bit data bus, value 0 translates to 0x00000000 (0000 0000 0000 0000 0000 0000 0000 0000) while (-1) translates to 0xFFFFFFFF (1111 1111 1111 1111 1111 1111 1111 1111) in a 2’s[[two's complement]] representation. WeThe see that the hammingHamming distance in this case is 32 (since all 32- bits are changing their state). UsingThe theHamming signeddistance bitis representation,much smaller using the hamming[[signed distancenumber isrepresentation|sign significantlybit minimizedrepresentation]]. However, even using 2’stwo's complement, weinversion canencoding achievereduces the same activity reductionnecessary. usingIn inversionthis encoding. So,case 0 willwould be represented as 0x00000000 with INV=0 and -1 willwould be represented as 0x00000000 with INV=1. Since INV=1, the receiver willwould invert the data before consuming it, thereby converting it to 0xFFFFFFFF internally. In this case, only 1 bit (INV bit) is changed overin the bus, leading to an activity of factor 1, which is even better than signedsign bit representation.

[[File:Overviewbusencoding.png|thumb|Overview for Performance Analysis: inversion encoding]]

== Performance Analysisanalysis ==

The Busbus-Invertinvert method generates a code that has the property that the maximum number of transitions per time-slot is reduced from n to n/2+1 and thus the peak power dissipation for [[input/output]] (I/O) is reduced by nearly the half. From the [[coding theory]] point of view, the Busbus-Invertinvert code is a time-dependent Markovian code.

While the maximum numHamming distancebernumber of transitions is reduced by half, the average number ofhas transitionsa is not thatsmaller gooddecrease. For an 8-bit bus for example, the average number of transitions, using bus-invert coding becomes 3.27 (instead of 4), or 0.41 (instead of 0.5) transitions per bus-line per time-slot. This means that the average number of transitions is 81.8% asof comparedthe number with an unencoded bus. ThereThis areis twobecause reasonsthe whyinvert theline performancecontributes ofsome thetransitions Bus-Invertand codingthe fordistribution decreasingof the averageHamming number of transitionsdistances is not asuniform.<ref good as for decreasing the maximum number of transitions:name="Stan_1995"/>

== Partitioned Inversioninversion Encodingencoding ==

* The invert line contributes itself with some transitions.

In order to decrease the average I/O power dissipation for wide buses the observation that the Busbus-Invertinvert method performs better for small nbus sizes can be used to partition the bus into several narrower subbuses. Each of these subbuses can then be coded independently with its own invert signal. For example, a 64-bit bus could be partitioned into eight 8-bit subbuses with a total of eight n order to decrease the average I/O power dissipation for wide buses the observation that the Bus-Invert method performs better for small n can be used to partition the bus into several narrower subbuses. Each of these subbuses can then be coded independently with its own invert signal. For example a 64-bit bus could be partitioned into eight 8-bit subbuses with a total of eightadded invert signals. Because of the assumption that the data to be transferred over the wide bus is random[[uniform distribution (continuous)|uniformly distributed]], the statistics for the narrower subbuses will be [[Independence (probability theory)|independent]] and the sequence of data for each subbus will be random uniformly distributed. For example, for a 64-bit bus partitioned into eight 8-bit subbuses the average number of transitions per time-slot will be 26.16 (8 times 3.27, the average for one 8-bit subbus) and the average number of transitions per bus-line per time-slot will be 0.41 (as for an 8-bit bus with one invert line). The maximum number of transitions is not improved by partitioning the bus and remains the same at n/2. However, there is always an extra overhead of using more lines, but computationally, it has been found that the inversion bus encoding works well for most purposes.<ref name="r1Stan_1995">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.2154&rep=rep1&type=pdf</ref>

* The distribution of the Hamming distances for the next data values is not uniform.<ref>M. R. Stan and W. P. Burleson, “Bus-invert coding for low-power I/O,” IEEE Transactions On VLSI Systems, Vol.3, No.1, pp.49-58, 1995</ref>

== Partitioned Inversion Encoding ==

In order to decrease the average I/O power dissipation for wide buses the observation that the Bus-Invert method performs better for small n can be used to partition the bus into several narrower subbuses. Each of these subbuses can then be coded independently with its own invert signal. For example a 64-bit bus could be partitioned into eight 8-bit subbuses with a total of eight n order to decrease the average I/O power dissipation for wide buses the observation that the Bus-Invert method performs better for small n can be used to partition the bus into several narrower subbuses. Each of these subbuses can then be coded independently with its own invert signal. For example a 64-bit bus could be partitioned into eight 8-bit subbuses with a total of eight invert signals. Because of the assumption that the data to be transferred over the wide bus is random uniformly distributed, the statistics for the narrower subbuses will be independent and the sequence of data for each subbus will be random uniformly distributed. For example for a 64-bit bus partitioned into eight 8-bit subbuses the average number of transitions per time-slot will be 26.16 (8 times 3.27, the average for one 8-bit subbus) and the average number of transitions per bus-line per time-slot will be .41 (as for an 8-bit bus with one invert line). The maximum number of transitions is not improved by partitioning the bus and remains the same n/2. However, there is always an extra overhead of using more lines, but computationally, it has been found that the inversion bus encoding works well for most purposes.<ref name="r1">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.2154&rep=rep1&type=pdf</ref>

== See also ==

* [[Bus Encodingencoding]]

* [[Two's Complementcomplement]]

* [[Low-power electronics]]

* [[CPU power dissipation|Power Dissipation]]

== References ==

{{Reflist}}|refs=

<ref name="Stan_1995">{{cite journal |author-first1=Mircea R. |author-last1=Stan |author-first2=Wayne P. |author-last2=Burleson |title=Bus-Invert Coding for Low-Power I/O |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |volume=3 |number=1 |pages=49–58 |date=March 1995 |id=1063-8210/95$04.00 |citeseerx=10.1.1.89.2154 |doi=10.1109/92.365453 }}</ref>

}}

==Further reading==

* {{cite book |author-first=Vincent C. |author-last=Gaudet |chapter=Chapter 4.1. Low-Power Design Techniques for State-of-the-Art CMOS Technologies |editor-first=Bernd |editor-last=Steinbach |editor-link=:de:Bernd Steinbach |title=Recent Progress in the Boolean Domain |publisher=[[Cambridge Scholars Publishing]] |publication-place=Newcastle upon Tyne, UK |___location=Freiberg, Germany |edition=1 |date=2014-04-01 |orig-date=2013-09-25 |isbn=978-1-4438-5638-6 |pages=187–212 |url=https://books.google.com/books?id=_pwxBwAAQBAJ |access-date=2019-08-04}} [https://web.archive.org/web/20210228020207/https://www.tau.ac.il/~ilia1/publications/rpbd_book.pdf<!-- https://m.tau.ac.il/~ilia1/publications/rpbd_book.pdf draft version 2013-09-25 -->] (xxx+428 pages)

[[Category:Electronics optimization]]

{{Uncategorized|date=May 2015}}