Visualizza wikitesto di No more secrets Part E: Shift to Multiply and Divide

This is a left shift circuit for three bits:

[[File:leftshift_v2.jpg]]

and the jumper table:

<pre>
in3 -> A
in2 -> BD
in1 -> EG
in0 -> JH
SL -> BEH
NSL -> ADGJ
A -> C
B -> C
C -> out3
D -> F
E -> F
F -> out2
G -> I
H -> I
I -> out1
J -> KK
K -> out0
</pre>

To test this circuit exactly one of the inputs SL or NSL must be set to
one. When NSL is one the 4 input bits are copied to the outputs.
When SL is one in0 is copied to out1, in1 to out2, in2 to out3 and out0 is
zero. If we give to the four input bits the meaning of the binary
representation of a number, when SL is one the result is the input times
two. The result is correct both for signed and unsigned numbers provided
the result can be stored in four bits.

For esample:
<pre>
leftshift(3) = leftshift(0011) = 0110 = 6 (both for unsigned and signed numbers)

leftshift(5) = leftshift(0101) = 1010 = 10 (unsigned only!)

leftshift(-3) = leftshift(1101) = 1010 = -6 (signed)
</pre>

It is possible to test the circuit in this way: plug four leds on the
output and connect NSL to one (positive rail). Now set a random input
configuration, you'll see the same configuration in the pattern of
leds. Moving the jumper from NSL to SL the led pattern will move (left) and the
least significant bit will be zero.

A right shift circuit can divide values by two in a similar manner.
Unfortunately, in this case signed and unsigned numbers must be processed
in a different way.

This is the circuit:

[[File:rightshift_v2.jpg]]

and the jumper table:
<pre>
in3 -> AC
in2 -> DF
in1 -> GI
in0 -> J
SR -> CFI
NSR -> DGJ
copy3 -> A
A -> BB
B -> out3
C -> E
D -> E
E -> out2
F -> H
G -> H
H -> out1
I -> K
J -> K
K -> out0
</pre>

Now the valid configurations for SR, NSR and copy3 are the following ones:
<pre>
SR NSR copy3
0   1   1     copy all the inputs in the corrisponding outputs
1   0   0     shift right for unsigned (the MSB is zero)
              (also known as logical shift)
1   0   1     shift right for signed (the MSB is copied)
              (A.K.A. arithmetic shift)
</pre>

The difference between a logical shift and an arithmetic shift is the
management of the Most Significant Bit (MSB, i.e. out3):
a logical shift resets it to zero while an arithmetic shift copies the
former value of the MSB, out2 and out3 has always the same value in
an arithmetic shift.
In other words, an arithmetic shift keeps the sign bit unchanged.

A logical right shift is a division by two operation for unsigned integers.
An arithmentic right shift is a division by two only for positive integers
and for even negative numbers. For odd negative numbers the result is
rounded downwards, so incorrect.

<pre>
(any kind of right shift, logical or arithmetic).
rightshift(3) = leftshift(0110) = 0011 = 3
(both for unsigned and signed numbers)

logical_rightshift(10) = logical_rightshift(1010) =
    = 101 = 5 (unsigned only!)

arithmetic_rightshift(-6) = arithmetic_rightshift(1010) =
    = 1101 = -3 (signed)

arithmetic_rightshift(-3) = arithmetic_rightshift(1101) =
    = 1110 = -2 (signed)
</pre>

A complete and flexible shifter can be implemented using three breadboards.

[[File:completeshifter.jpg]]

The shift control circuit has two control bits sh0 and sh1 supporting
the following configurations:
<pre>
sh1 sh0
0   0   do not shift
0   1   left shift
1   0   (logical) right shift
1   1   arithmetic right shift
</pre>

This is the circuit and the map for the jumpers:

[[File:shiftcontrol.jpg]]

<pre>
sh1 -> AABC outSR
sh0 -> BD
A -> outNSR
B -> CD
C -> outcopy3
D -> EE outNSL
E -> outSL
</pre>