Inversion encoding

Last updated June 28, 2024

Inversion encoding is an encoding technique used for 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 these transitions aids optimization of power dissipation. This is done introducing an additional signal line named INV to the bus lines. This signal determines whether the other lines should be inverted or not.

Overview

The bus-invert encoding technique uses an extra signal (INV) to indicate the "polarity" of the data. Having a bus-invert code word INV@x where @ is the concatenation operator and x denotes either the source word or its ones' complement, the bus-invert decoder takes the code word and produces the corresponding source word. If the INV signal is 1, the result is ones' complement of x, otherwise it is x.

Usage scenarios

High capacitance lines
High switching activity

Bus-invert method

The Hamming distance (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, invert is set to 1, and the next bus value is made equal to the inverted next data value.
Otherwise invert is set to 0, and 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 value of invert must be transmitted over the bus (the method increases the number of lines from n to n+1).^[1]

Example

Considering an example of a system which gets one of its data from a sensor, most of the time the sensor may be measuring some noise. For this example, the values being measured should 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 two's complement representation. The Hamming distance in this case is 32 (since all 32 bits are changing their state). The Hamming distance is much smaller using the sign bit representation. However, even using two's complement, inversion encoding reduces the activity necessary. In this case 0 would be represented as 0x00000000 with INV=0 and -1 would be represented as 0x00000000 with INV=1. Since INV=1, the receiver would invert the data before consuming it, thereby converting it to 0xFFFFFFFF internally. In this case, only 1 bit (INV bit) is changed in the bus, leading to an activity of factor 1, which is even better than sign bit representation.

Performance analysis

The bus-invert 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 bus-invert code is a time-dependent Markovian code.

While the maximum number of transitions is reduced by half, the average number has a smaller decrease. 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% of the number with an unencoded bus. This is because the invert line contributes some transitions and the distribution of the Hamming distances is not uniform.^[1]

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 bus 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 8 added invert signals. Because of the assumption that the data to be transferred over the wide bus is uniformly distributed, the statistics for the narrower subbuses will be independent and the sequence of data for each subbus will be 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.^[1]

Related Research Articles

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

Differential Manchester encoding (DM) is a line code in digital frequency modulation in which data and clock signals are combined to form a single two-level self-synchronizing data stream. Each data bit is encoded by a presence or absence of signal level transition in the middle of the bit period, followed by the mandatory level transition at the beginning. The code is insensitive to an inversion of polarity. In various specific applications, this method is also called by various other names, including biphase mark code (CC), F2F, Aiken biphase, and conditioned diphase.

<span class="mw-page-title-main">Line code</span> Pattern used within a communications system to represent digital data

In telecommunication, a line code is a pattern of voltage, current, or photons used to represent digital data transmitted down a communication channel or written to a storage medium. This repertoire of signals is usually called a constrained code in data storage systems. Some signals are more prone to error than others as the physics of the communication channel or storage medium constrains the repertoire of signals that can be used reliably.

In telecommunication and data storage, Manchester code is a line code in which the encoding of each data bit is either low then high, or high then low, for equal time. It is a self-clocking signal with no DC component. Consequently, electrical connections using a Manchester code are easily galvanically isolated.

Modified AMI codes are a digital telecommunications technique to maintain system synchronization. Alternate mark inversion (AMI) line codes are modified by deliberate insertion of bipolar violations. There are several types of modified AMI codes, used in various T-carrier and E-carrier systems.

<span class="mw-page-title-main">Non-return-to-zero</span> Telecommunication coding technique

In telecommunication, a non-return-to-zero (NRZ) line code is a binary code in which ones are represented by one significant condition, usually a positive voltage, while zeros are represented by some other significant condition, usually a negative voltage, with no other neutral or rest condition.

The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit.

<span class="mw-page-title-main">G.711</span> ITU-T recommendation

G.711 is a narrowband audio codec originally designed for use in telephony that provides toll-quality audio at 64 kbit/s. It is an ITU-T standard (Recommendation) for audio encoding, titled Pulse code modulation (PCM) of voice frequencies released for use in 1972.

Two's complement is the most common method of representing signed integers on computers, and more generally, fixed point binary values. Two's complement uses the binary digit with the greatest value as the sign to indicate whether the binary number is positive or negative; when the most significant bit is 1 the number is signed as negative and when the most significant bit is 0 the number is signed as positive. As a result, non-negative numbers are represented as themselves: 6 is 0110, zero is 0000, and -6 is 1010. Note that while the number of binary bits is fixed throughout a computation it is otherwise arbitrary.

Run-length limited or RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. RLL codes are defined by four main parameters: m, n, d, k. The first two, m/n, refer to the rate of the code, while the remaining two specify the minimal d and maximal k number of zeroes between consecutive ones. This is used in both telecommunication and storage systems that move a medium past a fixed recording head.

Excess-3, 3-excess or 10-excess-3 binary code, shifted binary or Stibitz code is a self-complementary binary-coded decimal (BCD) code and numeral system. It is a biased representation. Excess-3 code was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

In telecommunications, 8b/10b is a line code that maps 8-bit words to 10-bit symbols to achieve DC balance and bounded disparity, and at the same time provide enough state changes to allow reasonable clock recovery. This means that the difference between the counts of ones and zeros in a string of at least 20 bits is no more than two, and that there are not more than five ones or zeros in a row. This helps to reduce the demand for the lower bandwidth limit of the channel necessary to transfer the signal.

Transition-minimized differential signaling (TMDS) is a technology for transmitting high-speed serial data used by the DVI and HDMI video interfaces, as well as by other digital communication interfaces.

In telecommunication, bipolar encoding is a type of return-to-zero (RZ) line code, where two nonzero values are used, so that the three values are +, −, and zero. Such a signal is called a duobinary signal. Standard bipolar encodings are designed to be DC-balanced, spending equal amounts of time in the + and − states.

4B3T, which stands for 4 (four) binary 3 (three) ternary, is a line encoding scheme used for ISDN PRI interface. 4B3T represents four binary bits using three pulses.

IEEE Standard 1355-1995, IEC 14575, or ISO 14575 is a data communications standard for Heterogeneous Interconnect (HIC).

The Power Management Bus (PMBus) is a variant of the System Management Bus (SMBus) which is targeted at digital management of power supplies. Like SMBus, it is a relatively slow speed two wire communications protocol based on I²C. Unlike either of those standards, it defines a substantial number of domain-specific commands rather than just saying how to communicate using commands defined by the user.

The ones' complement of a binary number is the value obtained by inverting (flipping) all the bits in the binary representation of the number. The name "ones' complement" refers to the fact that such an inverted value, if added to the original, would always produce an "all ones" number. This mathematical operation is primarily of interest in computer science, where it has varying effects depending on how a specific computer represents numbers.

Bus encoding refers to converting/encoding a piece of data to another form before launching on the bus. While bus encoding can be used to serve various purposes like reducing the number of pins, compressing the data to be transmitted, reducing cross-talk between bit lines, etc., it is one of the popular techniques used in system design to reduce dynamic power consumed by the system bus. Bus encoding aims to reduce the Hamming distance between 2 consecutive values on the bus. Since the activity is directly proportional to the Hamming distance, bus encoding proves to be effective in reducing the overall activity factor thereby reducing the dynamic power consumption in the system.

State encoding assigns a unique pattern of ones and zeros to each defined state of a finite-state machine (FSM). Traditionally, design criteria for FSM synthesis were speed, area or both. Following Moore's law, with technology advancement, density and speed of integrated circuits have increased exponentially. With this, power dissipation per area has inevitably increased, which has forced designers for portable computing devices and high-speed processors to consider power dissipation as a critical parameter during design consideration.

References

1 2 3 Stan, Mircea R.; Burleson, Wayne P. (March 1995). "Bus-Invert Coding for Low-Power I/O". IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 3 (1): 49–58. CiteSeerX 10.1.1.89.2154 . doi:10.1109/92.365453. 1063-8210/95$04.00.