Inversion encoding

Last updated October 25, 2019

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.

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.

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 one's complement of x, otherwise it is x.

The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number. The ones' complement of the number then behaves like the negative of the original number in some arithmetic operations. To within a constant, the ones' complement behaves like the negative of the original number with binary addition. However, unlike two's complement, these numbers have not seen widespread use because of issues such as the offset of −1, that negating zero results in a distinct negative zero bit pattern, less simplicity with arithmetic borrowing, etc.

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.

Two's complement is a mathematical operation on binary numbers, and is an example of a radix complement. It is used in computing as a method of signed number 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 and thus the peak power dissipation for input/output (I/O) is reduced by half. From the coding theory point of view, the bus-invert code is a time-dependent Markovian code.

In computing, input/output or I/O is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals or data received by the system and outputs are the signals or data sent from it. The term can also be used as part of an action; to "perform I/O" is to perform an input or output operation.

Coding theory study of the properties of codes and their fitness for a specific application

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

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]

In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of symmetric probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by the two parameters, a and b, which are its minimum and maximum values. The distribution is often abbreviated U(a,b). It is the maximum entropy probability distribution for a random variable X under no constraint other than that it is contained in the distribution's support.

This is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes.

Related Research Articles

The Accelerated Graphics Port (AGP) was designed as a high-speed point-to-point channel for attaching a video card to a computer system, primarily to assist in the acceleration of 3D computer graphics. It was originally designed as a successor to PCI-type connections for video cards. Since 2004, AGP has been progressively phased out in favor of PCI Express (PCIe); by mid-2008, PCI Express cards dominated the market and only a few AGP models were available, with GPU manufacturers and add-in board partners eventually dropping support for the interface in favor of PCI Express.

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

Differential Manchester Encoding (DM) is a line code in which data and clock signals are combined to form a single 2-level self-synchronizing data stream. In various specific applications, this line code is also called by various other names, including Biphase Mark Code (CC), Frequency Modulation (FM), F2F , Aiken Biphase, and Conditioned diphase. DM is a differential encoding, using the presence or absence of transitions to indicate logical value. It is not necessary to know the polarity of the sent signal since the information is not represented by the absolute voltage levels but in their changes: in other words it does not matter which of the two voltage levels is received, but only whether it is the same or different from the previous one; this makes synchronization easier.

Line code code used within a communications system for baseband transmission purposes

In telecommunication, a line code is a pattern of voltage, current, or photons used to represent digital data transmitted down a transmission line. This repertoire of signals is usually called a constrained code in data storage systems. Some signals are more prone to error than others when conveyed over a communication channel as the physics of the communication 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. As a result, electrical connections using a Manchester code are easily galvanically isolated.

Non-return-to-zero line code in which the signal value does not return to zero after each pulse

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 pulses in NRZ have more energy than a return-to-zero (RZ) code, which also has an additional rest state beside the conditions for ones and zeros. NRZ is not inherently a self-clocking signal, so some additional synchronization technique must be used for avoiding bit slips; examples of such techniques are a run-length-limited constraint and a parallel synchronization signal.

G.711 is an ITU-T standard (Recommendation) for audio companding, titled Pulse code modulation (PCM) of voice frequencies. It is primarily used in telephony. The standard was released for use in 1972. Its formal name is Pulse code modulation (PCM) of voice frequencies. It is a required standard in many technologies, for example in H.320 and H.323 specifications. It can also be used for fax communication over IP networks. G.711 is a narrowband audio codec that provides toll-quality audio at 64 kbit/s. G.711 passes audio signals in the range of 300–3400 Hz and samples them at the rate of 8,000 samples per second, with the tolerance on that rate of 50 parts per million (ppm). Non-uniform (logarithmic) quantization with 8 bits is used to represent each sample, resulting in a 64 kbit/s bit rate. There are two slightly different versions: μ-law, which is used primarily in North America and Japan, and A-law, which is in use in most other countries outside North America.

Modified frequency modulation (MFM) is a run-length limited (RLL) coding scheme used to encode the actual data-bits on most floppy disks. It was first introduced in disk drives in 1970 with the IBM 3330 hard disk drive and then in floppy disk drives beginning with the "double density" IBM 53FD in 1976.

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 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 yet 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), a technology for transmitting high-speed serial data, is used by the DVI and HDMI video interfaces, as well as by other digital communication interfaces.

In computing, signed number representations are required to encode negative numbers in binary number systems.

A bit array is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.

Elias ω coding or Elias omega coding is a universal code encoding the positive integers developed by Peter Elias. Like Elias gamma coding and Elias delta coding, it works by prefixing the integer with a representation of its order of magnitude in a universal code. Unlike those other two codes, however, Elias omega recursively encodes that prefix; thus, they are sometimes known as recursive Elias codes.

Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.

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.