- Published: Tuesday, 03 April 2018 22:27
- Written by Timothy Chapman
Bit shifters shift the bits to the left or right and multiply or divide a number by a power of two. Shifting to the left is the equivalent of multiply by power of two, and shifting to the right is the equivalent of divide by power of two. There are two forms of shift right: Signed and Unsigned. The hardware for shift left, unsigned shift right and signed shift right can be built using exclusively NAND and NOT gates in a manner nearly identical to multiplexers and demultiplexers. The A input is the number being shifted while the B input is the number of bits that A is being shifted by. We want to use a decoder on the B input to convert the number into a power of two. This decoder can be built into the main part of the shifter in order to save on logic gates and reduce propagation delay.
I find it easier to build shifters when I think of the first level of AND gates (or NAND gates, which is what is used in this article) as having a specific value. AND gates of the same value will be ORed together to produce an output. Because we're only multiplying and dividing by powers of two, we don't need to worry about adding values together.
As mentioned above, shift left is a multiply by power of two operation. So the value of the output is going to be A·2B. Implementing this is quite easy though. Each of the first level NAND gates is going to have a value of An·2B, where n is the bit index of the A input going into that gate. Gates that will output the same value get grouped together. To save on space, we'll look at a 4-bit shifter. We will have 10 NAND gates on the first layer, and one NOT gate plus 3 NAND gates on the second layer. The shifter will look something like what is shown below.
Notice the patterns here. This shifter can be expanded almost indefinitely without increasing the time it takes to output the correct value. Any bits that are shifted beyond the highest value bit are discarded. And the maximum value of the B input is equal to the number of bits minus one. Shifting by any more than that would always result in an output of 0.
Right shifts are divisions by powers of two. The pattern for the NAND gates shown in the diagram above is flipped. In addition, the inputs to the first layer of NAND gates are going to be completely rewired from what is shown above, because each of the first level NAND gates are really the result of dividing A by B. An example of an unsigned shift right bit-shifter is shown below.
Just like with the shift left bit shifter, the shift right bit shifter can only shift by less than the number of bits that goes to the A input. Shifting by more than that will always result in a value of 0. Any bits that are shifted below a value of 1 are discarded. Also, unsigned shift right is also known as "logical shift right."
Signed shift right is also known as "arithmetic shift right." The idea behind signed right-shifts is that you preserve the sign of the number as you shift it to the right. Implementing such a device isn't that difficult. In fact, you can just forward the highest value A bit straight to the highest value output bit without any logic gates in between. The diagram below shows an example of a highly-optimized signed shift right bit shifter.
The shifter shown above has all of the "unsigned" shift logic on the top of the first level of NAND gates with the "signed" logic being done on the bottom 3 NAND gates on the first level. This circuit may need a bit of adjustment if you want to expand it, but like the previous two shifters shown, this one can be expanded fairly easily. Like with the previous shifter shown, the maximum shift is equal to the number of A bits minus 1. Any shift greater than that will always result in a value of 0 or -1 depending on the sign bit of the input (the highest value bit is always the sign bit for signed numbers). Also, any bits shifted beyond P0 are simply discarded.