Arithemtic Circuits

Part I

Shift and Rotate Operations

1 Shift and Rotate Operations

2 Barrel Shifters
Logarithmic Barrel Shifters
Combining Rotate and Shift Operations
Bidirectional Shift and Rotate Operations
Arithemtic Circuits
Shift and Rotate Operations

Shift and Rotate Operations

SHL op, count CF operand 0

This can be implemented by a
SAL op, count Same as SHL
bi-directional shift register.
SHR op, count 0 operand CF
We have to add circuits to
operand CF choose the value and point of
SAR op, count
entry of new bits.
CF operand
ROL op, count This can be very slow for a
operand CF large number of shifts.
ROR op, count
CF operand
Ideally, we would like a shifter
RCL op, count which produces the result in a
operand CF single clock cycle.
RCR op, count
Arithemtic Circuits
Barrel Shifters

Shift/Rotate as Select Operations

No “computation” is being carried out during shift/rotate.
So why should we spend a large number of clock cycles for
it?
We can view Shift/Rotate as a selection operation.

B A
n bits n bits

n bits
Select n contiguous bits

We just have to choose B and A appropriately to implement a

particular shift or rotate operation.
Arithemtic Circuits
Barrel Shifters

Shift/Rotate as Select Operations

For all rotate operations,

B=A=data
B A
n bits n bits For Shift Left, B=data, A=0.
For Logical Shift Right, B=0,
n bits A=data.
Select n contiguous bits
For Arithmetic Shift Right,
B=replicated MSB of data,
A=data.
Of course we do not actually copy data bits to A/B.
Each output bit is produced by a mux which picks out the
correct input data bit.
Arithemtic Circuits
Barrel Shifters

Barrel Shifters

Shifters which produce outputs as select operations are

called barrel shifters.
The name comes from viewing the inputs as well as
outputs as a circular arrangement of bits.
The shifter then connects the input circle to the output
circle like the sections of a barrel.
A brute force implementation will require n multiplexers of n
bits each, where the control inputs for each multiplexer are
generated from the amount and type of shift/rotate.
This is quite complex and puts a heavy load on data bits.
Arithemtic Circuits
Barrel Shifters
Logarithmic Barrel Shifters

Logarithmic Barrel Shifters

The brute force barrel shifter places a heavy load on input

data lines because each input bit is a candidate for each
output position.
The control logic is complex because the amount of shift is
variable.
The loading on data lines and control logic complexity can
be reduced if we break up the shift process into parts.
We can carry out shifts in different stages, each stage
corresponding to a single bit of the binary representation of
the shift amount.
Thus a shift by 6 (binary: 110) will be carried out by first
doing a 4 bit shift and then a 2 bit shift.
Arithemtic Circuits
Barrel Shifters
Logarithmic Barrel Shifters

Logarithmic Barrel Shifters

We need n bits to represent a maximum shift amount of

2n − 1 places.
So the number of bits to express the shift amount (and
hence the number of shift stages required) is logarithmic in
the maximum shift desired.
That is why such shifters are called Logarithmic Barrel
Shifters.
We can optionally buffer the outputs after each stage.
Arithemtic Circuits
Barrel Shifters
Logarithmic Barrel Shifters

Logarithmic Barrel Shifter Stages

Bit i of the shift amount represents

no shift (if it is 0)
a constant shift by 2i places (if it is 1).
If the shift amount is fixed, we do not need any electronics.
The output can just be wired from the input bits.
Using a 2 way mux controlled by bit i of shift amount, we
can choose either the unshifted operand bit or the operand
bit 2i places away from it.
This can be done for all bits of the operand in parallel.
This constitutes one stage of the logarithmic shifter.
The output can then be shifted again in the next stage,
controlled by the next significant bit.
Arithemtic Circuits
Barrel Shifters
Logarithmic Barrel Shifters

Right Rotate for an 8 bit Operand

X7 X6 X5 X4 X3 X2 X1 X0
X3 X2 X1 X0 X7 X6 X5 X4

n2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Each input bit drives just two

muxes, each with just 2 inputs.
n1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
At each stage, the muxes
select either the unshifted bit
or a bit 2n places from it.
n0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 3 stages are required for 0 to 7
Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 bits of shift.
Arithemtic Circuits
Barrel Shifters
Logarithmic Barrel Shifters

8 bit Logical Shift Right

0 X7 X6 X5 X4 X3 X2 X1 X0
X7 X6 X5 X4

n2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
If we need a shift instead of a
rotate, we feed a 0 instead of
the corresponding bit.
n1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

This has to be done for 4

muxes in the first stage, 2 in
n0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
the second stage and 1 in the
Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
last stage.
Arithemtic Circuits
Barrel Shifters
Combining Rotate and Shift Operations

Combining Rotate and Shift

ASR
X3 X2 X1 X0
X7
0 1

0 We can combine the circuits

0 1 0 1 0 1 0 1 for rotate and shift functions by
Rotate
putting muxes where different
4 bit shift/rotate row
inputs need to be presented
for the two functions.
0 1 0 1
Rotate We can include the Arithmetic
2 bit shift/rotate row Shift function by choosing
between 0 or X7 as the bit to
0 1
Rotate be inserted.
1 bit shift/rotate row
Arithemtic Circuits
Barrel Shifters
Combining Rotate and Shift Operations

Rotate and Shift by Masking

We can also combine the rotate and shift functions by

masking.
We use the rotate function, which does not lose any
information.
Now we can mask n bits at the left to 0 if a right shift
operation was desired instead.
In case of an arithmetic shift, n bits on the left have to be
set to the same value as X7.
Shift/Rotate Left case is similar, except that the Logical and
Arithmetic shifts are the same.
Arithemtic Circuits
Barrel Shifters
Bidirectional Shift and Rotate Operations

Combining Left and Right Shift/Rotate

X7 X6 X5 X4 X3 X2 X1 X0
X0 X1 X2 X3 X4 X5 X6 X7 We can use the same
Left 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 hardware for left and right
shift/rotate operations.
This can be done by adding
Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 rows of muxes at the input and
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 output which reverse the order
of bits.
Arithemtic Circuits
Barrel Shifters
Bidirectional Shift and Rotate Operations

Combining Left and Right Shift/Rotate

We can also make use of the fact that a left rotate by n

places is the same as a right rotate by 2n − n places.
2n − n is just the 2’s complement of n.
By presenting the 2’s complement of n at the mux controls,
we can convert a right rotate to a left rotate.
This can be followed by a mask operation, if a shift
operation was required, rather than a rotate.