Field of the Invention
This invention relates to an area efficient data shifter/rotator using barrel shifter.
Background of the Invention
Data bits shifting and rotation are common operations by which bits of a data word are shifted into lower order bit positions (shift right) or into higher order bit positions (shift left). On an integrated circuit, real estate is generally a scarce commodity as more and more functions are to be provided within a limited area. Therefore, it is desirable to have a universal shifter unit capable of handling both the shift and rotate operations, which can be implemented in an efficient manner that reduces the number of logic required.
Conventional circuits for performing left and right shifting of bits (the bits comprising a data word) and rotation have been implemented. However, such shifting circuits include two separate circuit branches: one for shifting the bits to the left; the other for shifting the bits to the right.
United States Patent number 6,304,956 entitled 'Using two barrel shifters to implement shift, rotate, rotate with carry, and shift double as specified by the X86 architecture' discloses a shifter unit having three major portions: a right shifter, a left shifter and control logic. For shifting operations, only one of the two shifters is used, while rotation functions require both left and right shifters.
The results of the two shifters are then provided to a merging logic for logic operations. Depending on the instruction type, the merging logic performs different logic operations on the two results. For example, in some instructions (rotation), the two results are ORed together. In some other instructions (shifting), only one result is needed from one of the two shifters, and the result of the other shifter is ignored The merging logic outputs the desired results as an output.
For rotation, both of the two shifters are provided with the source operand. Then, the first shifter shifts the source operand by a first number, where the first number is the count operand as defined in the instruction. The second shifter shifts the source

operand by a second number, where the first number in addition with the second number equal to the number of bits of the source operand. Due to the two branches, each using a Barrel Shifter, area consumed by this technique is very large.
The United States Patent number 5978822 entitled "Circuit for rotating, left shifting, or right shifting bits" uses a single branch of shifter unit which is capable of performing shifting and rotation operations. The circuit includes a set of series connected multiplexer stages, and circuitry for selectively inverting the order of the bits of the word input to and the word output from the set of multiplexer stages. Each of the multiplexer stages shifts the bits of the word it receives either by zero places (in response to a first condition of a control signal), or by a positive number of places (in response to a second condition of the control signal).
To execute a left shift, the circuitry for selectively inverting the input to the multiplexer stages does not invert the order of the bits of the input word. To execute a right shift, the circuitry for selectively inverting the input to the multiplexer stages does invert the order of the bits of the input word.
To enable the circuit to perform rotations (by a selectable number of bits to the left or right) of bits of the input word, a first one of the multiplexer stages includes bit selection circuitry for asserting appropriate bits needed for executing any such rotation to multiplexing circuitry in that multiplexer stage.
But for circuit of input digital data word containing 2n bits, shifting can be done from 0 to n - 1 places, while rotation can be done only up to (n/2) - 1 place. Thus it can rotate the input bits up to some places only of an input word (by two or more bits to the left or right) during a single cycle, by duplicating the input word to form an extended word, shifting bits of the extended word, and selecting a subset of the shifted bits of the extended word.
United Slates Patent number 5,844,825 entitled "Bidirectional Shifter Circuit" comprises of one shifter unit and two bit reversing circuits: one at the input of the shifter unit and one at the output of the shifter unit. This technique can handle two

operations and these two operations are based on the shifter unit, left or right. Further it can handle left rotation and right rotation.
In this technique, the bidirectional shifter has 3 components: First bit reversing circuit, a single direction shifter circuit and second bit reversing circuit. The first bit reversing circuit receives an input data word. In response to choosing a first shift direction, the first bit reversing circuit outputs the data word with the bits in their original order. In response to choosing the second shift direction, the first bit-reversing circuit outputs the data word with the bits in reverse order. A single-direction shifter circuit is provided which receives the data word outputted by the first bit-reversing circuit and shifts the received data word the chosen number of bit positions in the first direction. A second bit-reversing circuit is provided which receives the shifted data word and which, in response to choosing the first shift direction, outputs the data word with the bits in the same order as received and, in response to choosing the second shift direction, outputs the data word with the bits in reverse order.
If the shifter unit is left cyclic shifter, then the circuit can handle only left and right cyclic shifting i.e. ROL and ROR. This technique can handle only two types of the operation based on the shifter unit. Thus said circuit does not do all the expected operations.
Object & Summary of the Invention
It is an object of the present invention to obviate above and other drawbacks from the existing arts to provide an area efficient data shifter/rotator that can rotate entire input bits and is capable of doing expected operations.
Another object of the present invention is to produce the output for all operations in a single cycle.
To achieve the aforesaid objects the instant invention provides an area efficient shift / rotate system comprising:
- a series arrangement of multiplexer stages each stage having a plurality of multiplexer equal to the number of inputs bits ; characterized in that it includes:

an input reversal circuit receiving the inputs bits;
- an additional circuitry at the input to each stage of said series arrangement;
- an output reversal circuit connected to the output of the last stage of said series arrangement, and
- a right arithmetic control logic having its output connected to input of each stage of the additional circuitry.
For each stage, said Additional Circuitry has 2m-1 multiplexers where m is stage number, m = 1,2,3... n for 2n input data word.
Said input reversal circuit comprises of multiplexers.
Said output reversal circuit comprises of multiplexers.
Said right arithmetic control logic comprises:
a logic gate receiving two inputs; and
a multiplexer having its select line connected to the output of said logic
gate for selecting either most significant bit of input data word or zero.
Said logic gate is an AND gate.
Brief Description of the Accompanying Drawings
The invention will now be described with reference to the accompanying drawings.
Figure 1 is a block diagram showing the 2n bit shifter circuit.
Figure 2 shows a detailed layout of the 8 bit shifter unit.
Detailed Description of the Invention
Present invention can handle following six operations using one Barrel Shifter:
Shift arithmetic left (SAL)

Shift logic left (SHL) Shift Arithmetic Right (SAR) Shift Logic Right (SHR) Left Rotation (ROL) Right Rotation (ROR)
For performing above 6 operations, it uses three control signals in following manner:
(Table Removed)

Table 1
Shift Control Signals
Shift Arithmetic Left (SAL) and Shift Logical Left (SHL) instructions perform the same operation; they shift the bits to the left (toward more significant bit locations). For each shift count, the least significant bit is cleared.
The Shift Arithmetic Right (SAR) and Shift Logical Right (SHR) instruction shifts the bits to the right (toward less significant bit locations). For each shift count, the SHR instruction clears the most significant bit; the SAR instruction sets or clears the most significant bit to correspond to the sign (most significant bit) of the input word.
For each shift count, rotate left (ROL) instruction shifts all the bits toward more-significant bit positions, except for the most significant bit, which is rotated to the

least significant bit location. For each shift count, rotate right (ROR) instruction shifts all the bits towards less significant positions, except for the least significant bit, which is rotated to the most significant bit location.
Figure 1 has four major components: IP reversal circuit 10, Shifter Unit 11, OP reversal circuit 12 and Right Arithmetic Control Logic 13.
A digital data word having 2° bits is the input to the IP reversal circuit 10. For 2n-bit shifter circuit, IP reversal circuit 10 has 2" 2: 1 multiplexers. These multiplexers invert the data word if it is right shift or right rotation operation. For left shift or left rotation operation. IP multiplexers do not invert data words. Invert data word means inversion of the order of the bits of original data word. Most significant bit of original data word becomes the least significant bit of inverted data word. In general, for n bit data word, kth bit of the non-inverted word will be (n -k -1) th bit of the inverted data word.
Ip Reversal Circuit 10 sends non-inverted digital data word to the shifter unit 11, if it is left shift or left rotation and sends inverted digital data word to the shifter unit 11 if operation is right shift or right rotation.
Shifter Unit 11 performs the shifting/rotating operation on the inverted or non-inverted input digital data word based on the operation required.
For 2" bit Shifter Circuit, shifter unit 11 contains n stages. Each stage has one shifting stage 16. 18 and the like and an additional circuitry 15, 17 and the like. Additional circuitry selects data based on whether it is shift operation or rotation operation. Output of additional circuitry goes to the input of corresponding shift stage. Output of IP reversal circuit 10 goes to the first stage of shifter unit 11.
Additional circuitry 15 for stage 1 contains one 2: 1 multiplexer, for stage 2 contains two 2: 1 identical multiplexers, in general, for stage n, additional circuitry contains 2n-1 2:1 identical multiplexers.

Each shifter stage, 1 to n, contains 2° 2: 1 identical multiplexers for shifting the bits of word it receives or does not shift the input word, based on the selection line. Stage 1 either shifts the bits by one place or does not shift the bits, depending on the value of the selection line bit [0]. Stage 2 either shifts the bits by two places or does not shift the bits, depending on the value of the selection line bit [1]. And Stage n either shifts the bits by 2n~1places or does not shift the bits, depending on the value of selection line bit [n-1]. Output of shift stage k goes to the input of the stage k + 1. Output of last shift stage goes to the OP Reversal Circuit 12.
Shifter unit 11 gives the shifted/rotated output of the input digital data word (inverted or non inverted) and this output goes to the OP reversal circuit 12. The OP reversal circuit 12 contains 2" 2:1 identical multiplexers, which invert the output of the shifter unit 11 if it is right shift or right rotation operation and the inverted output is thus the final output for desired operation. If the operation is left shift or left rotation, output Reversal Circuit 12 does not invert the output of the shifter unit 11 and gives non-inverted output of the shifter unit 11 as the final output.
Right Arithmetic Control logic unit 13 comprises of one logic gate and one Multiplexer M. This logic gate is an AND gate with input as Right (R) and Arithmetic ( A) that are used to generate right arithmetic signal. Output of this AND gate is connected to the selection line of multiplexer M. Multiplexer M selects either most significant bit of input data word or zero based on whether it is right arithmetic shift operation or not.
In figure 2, data inputs are from 10 to 17, 10 is the least significant bit of input digital data word and 17 is the most significant bit. SO to S2 are the selection lines, SO is the least significant bit and S2 is the most significant bit of the selection line. For all 2:1 multiplexers, lower data input line is for selection line value 0 and upper data line is for selection line value 1.
Comparative analysis of the logic required by present invention and US Patent 6,304,956.
(Table Removed)
Table 2
In table [2], all multiplexers are 2:1 and OR gates are having 2 inputs.
If proposed shifter circuit and shifter by US Patent 6,304,956 is implemented in 4 Input LUT (Look up table) based FPGA (LUT can give only one Output), following table compares the number of LUTs required by these two techniques:
(Table Removed)

Table 3
Table |2) and [3| do not take into consideration logic / LUT required to generate control signals. The proposed technique requires only one two input AND gate and one 2:1 multiplexer or one LUT to generate right Arithmetic control logic.
Reduction in LUTs count with respect to US Patent 6,304,956 is 41.34 %.

Thus operations, where only shift and rotate without carry are required, proposed technique saves considerable area compared to the US patent 6,304,956.
Following are the some of the products/design where it would be advantageous to use proposed shifter circuit, since, proposed shifter circuit provides area-optimized solution.
1) Microprocessor
The present invention can be used in the microprocessor and more particularly, to the design of shifter units used in microprocessor.
Data bits shifting is a common operation in a microprocessor design and shifter unit is required to handle both the data word shifting and rotating functions. For example, in the Intel x86 instruction set, there are two groups of instructions (i.e. shift group, and rotate group instructions) that require either shifting or rotating function. Proposed dynamic shifter circuit can be used in the shifter unit of microprocessor, since it requires lesser area as compared to the conventional methods.
2) DSP
A conventional DSP includes data memory, Program Memory, Program Control Unit (PCU). Memory Management Unit (MMU), Arithmetic Computational Unit (ACU), and Input/Output Unit (10U).
ACU preferably includes two Multiply and Accumulate (MAC) units that operate in parallel (in response to control bits from PCU), and an arithmetic manipulation unit (AMU) which operates in parallel with the MAC units (in response to control bits from PCU)
The proposed shift circuit is preferably included within the AMU.
Since conventional AMU was using 2 separate circuit branches, area consumed by conventional circuit is more, while proposed circuit uses only one branch for all

shifting/rotation operation, area required by proposed circuit is very less as compared to the conventional shifter circuit. In addition, proposed shifter circuit is able of shifting or rotating any number of bits in one cycle. To add more, proposed shifter circuit can perform Arithmetic Left and Right Shift also in the same circuit.
3) Suppose user wants to implement a design where user selects one of the six operations (listed in Table 1) at a time based on the some control variable value.
Design's pseudo code is like this:
Case (sel)
3 "b000: a =a SHL b //Do Shift Logical Left Operation
3 "b00 1: a = a S AL b //Do Shift Arithmetic Left Operation
3' b0 1 x: a = a ROL b // Do Rotate Left Operation
3 b 100: a = a SHR b // Do Shift Logical Right Operation
3' b 101 a = a S AR b //Do Shift Arithmetic Right Operation
3' 11 x: a = a ROR b //Do Rotate Right Operation
endcase;
Above design performs the shift or rotate operation based on the sel value.
Please note that above design at a time requires only ONE shift/rotate operation to be performed based on the sel value.
Conventional Method:
If we have to implement above design in a circuit, conventionally, it would require following components:
1) Multiplexer to select the appropriate Shift/Rotate operation based on sel value
2) Logical Left Shift Circuit
3) Arithmetic Left Shift Circuit
4) Rotate Left Circuit
5) Logical Right Shift Circuit
6) Arithmetic Right Shift Circuit

7) Rotate Right Circuit
Proposed Method:
If we use proposed dynamic shifter, following components would be required:
1) Multiplexer to select the appropriate Shift/Rotate operation based on sel value
2) Dynamic Shifter Circuit, where sel bits would drive Right(R), Rotate (ROT), and Arithmetic (A) bits of Dynamic Shifter.
If the logic required by conventional method and logic required by proposed method is compared, it is quite obvious that proposed method takes very less chip area as compared to the conventional method because conventional circuit requires six separate circuits for doing shift/rotate operations while all these six shift/rotate operations can be done in a single circuit in proposed method.

We claim
1 An area efficient shift / rotate system comprising:
a series arrangement of multiplexer stages each stage having a plurality of multiplexers equal to the number of inputs bits ; characterized in that it includes:
an input reversal circuit receiving the inputs bits;
an additional circuitry at the input to each stage of said series
arrangement;
an output reversal circuit connected to the output of the last stage of
said series arrangement, and
a right arithmetic control logic having its output connected to input of
each stage of the additional circuitry
2. The area efficient shift / rotate system as claimed in claim 1 wherein for each stage of series arrangement said Additional Circuitry has 2m-1 multiplexers where m is the stage number of said series arrangement.
3. The area efficient shift / rotate system as claimed in claim 1 wherein said input reversal circuit comprises of multiplexers connected in parallel.
4. The area efficient shift / rotate system as claimed in claim 1 wherein said output reversal circuit comprises of multiplexers connected in parallel.
5. The area efficient shift / rotate system as claimed in claim 1 wherein said right arithmetic control logic comprises:
a logic gate receiving two inputs; and
a multiplexer having its select line connected to the output of said logic
gate for selecting either most significant bit of input data word or zero.
6. The area efficient shift / rotate system as claimed in claim 5 wherein said logic
gate is an AND gate.

7. An area efficient shift / rotate system substantially as herein described with reference to and as illustrated in the accompanying drawings.