Barrel shifter
Encyclopedia
A barrel shifter is a digital circuit
that can shift a data word by a specified number of bit
s in one clock cycle. It can be implemented as a sequence of multiplexer
s (mux.), and in such an implementation the output of one mux is connected to the input of the next mux in a way that depends on the shift distance.
For example, take a 4-bit barrel shifter, with inputs A, B, C and D. The shifter can cycle the order of the bits ABCD as DABC, CDAB, or BCDA; in this case, no bits are lost. That is, it can shift all of the outputs up to three positions to the right (and thus make any cyclic combination of A, B, C and D). The barrel shifter has a variety of applications, including being a useful component in microprocessor
s (alongside the ALU
).
im = IN, if S[1] 0
1
OUT = im, if S[0] 0
1
Larger barrel shifters have additional stages.
. Five common word sizes and the number of multiplexers needed are listed below:
Cost of critical path in FO4
(estimated, without wire delay):
of the two numbers must be aligned, which requires shifting the smaller number to the right, increasing its exponent, until it matches the exponent of the larger number. This is done by subtracting the exponents, and using the barrel shifter to shift the smaller number to the right by the difference, in one cycle. If a simple shifter were used, shifting by n bit positions would require n clock cycles.
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
that can shift a data word by a specified number of bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s in one clock cycle. It can be implemented as a sequence of multiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...
s (mux.), and in such an implementation the output of one mux is connected to the input of the next mux in a way that depends on the shift distance.
For example, take a 4-bit barrel shifter, with inputs A, B, C and D. The shifter can cycle the order of the bits ABCD as DABC, CDAB, or BCDA; in this case, no bits are lost. That is, it can shift all of the outputs up to three positions to the right (and thus make any cyclic combination of A, B, C and D). The barrel shifter has a variety of applications, including being a useful component in microprocessor
Microprocessor
A microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...
s (alongside the ALU
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
).
Implementation
A barrel shifter is often implemented as a cascade of parallel 2×1 multiplexers. For a 4-bit barrel shifter, an intermediate signal is used which shifts by two bits, or passes the same data, based on the value of S[1]. This signal is then shifted by another multiplexer, which is controlled by S[0]:im = IN, if S[1]
0
= IN << 2, if S[1]
1OUT = im, if S[0]
0
= im << 1, if S[0]
1Larger barrel shifters have additional stages.
Cost
The number of multiplexers required for an n-bit word is. Five common word sizes and the number of multiplexers needed are listed below:- 128-bit —
- 64-bit —
- 32-bit —
- 16-bit —
- 8-bit —
Cost of critical path in FO4
FO4
Fan-out of 4 is a process independent delay metric used in digital CMOS technologies.Fan out = Cload / CinCload = total MOS gate capacitance driven by the logic gate under considerationCin = the MOS gate capacitance of the logic gate under consideration...
(estimated, without wire delay):
- 32-bit: from 18 FO4 to 14 FO4
Uses
A common usage of a barrel shifter is in the hardware implementation of floating-point arithmetic. For a floating-point add or subtract operation, the significandSignificand
The significand is part of a floating-point number, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent an integer or a fraction.-Examples:...
of the two numbers must be aligned, which requires shifting the smaller number to the right, increasing its exponent, until it matches the exponent of the larger number. This is done by subtracting the exponents, and using the barrel shifter to shift the smaller number to the right by the difference, in one cycle. If a simple shifter were used, shifting by n bit positions would require n clock cycles.
External links
- Google Answers has a good explanation, and collection of links
- University of Hamburg for a useful Java Barrel shifter.
- Xilinx Application Note Implementation of Barrel shifter using Xilinx FPGAs.