Implementing a shifter with only multiplexers

multiplexer

This is my homework question, I would appreciate any hints to help me get started.

A shifter is used to shift a string of 0's and 1's to the left or
right by a fixed number of positions. The vacated positions(s) is/are
filled by 0. For example, if 0011 is shifted left by one position the
result is 0110; if 0011 is shifted right by one position the result is
0001.

Two control signals, S1 and S0, are used to specify the various
actions, as given below.

S1 = 0 and S0 = 0: No change, that is, pass input string to output

S1 = 0 and S0 = 0: Shift right one bit position

S1 = 1 and S0 = 0: Shift right two bit positions

S1 = 1 and S0 = 1: Shift left one bit position

Using a number of appropriate multiplexers without any additional
logic gate, implement a shifter that accepts a 4-bit string ABCD, and
generates the required 4-bit string WXYZ depending on the control
signals S1 and S0. Complemented literals are not available. You must
label your multiplexers, inputs and outputs clearly.

I researched online about the shifting operation and found out that it actually coincide with arithmetic operations, i.e., so "shift right one bit position" is actually division by 2, and "shift left one bit position" is multiplication by 2. However, I have no idea what "shift right two bit" means, is it division by 5? I tested with 1111 binary code (15) and the result is 0011 (3).

So basically since the shifting operations is just arithmetic operations, should I use the multiplexers to implement the latter? Yet I don't know how to go about it with only two control signals S1 and S0. Do I need 4 multiplexers since the output is 4 bits?

Best Answer

This isn't a direct answer to your homework, but a response to your analysis of what shifting means numerically.

Yes, shifting a binary number left is a multiplication by 2. In general, shifting a number left by one digit multiplies it by the number base. That is because each digit to the left has a weight of the number base times higher. In decimal, shifting left one digit multiplies the number by ten, in binary by two.

No, shifting right by two does not divide by 5. By the same logic as above, shifting right one digit divides the number by the number base. In binary, this means it gets divided by 2. Shifting two bits right divides by 4. The reason you are not seeing this in you example is because you lost some of the digits.

You started with 1111 binary and shifted it right by two bits. This yields 11.11 binary. Add the weights from each of the digits and you get

  2**1 + 2**0 + 2**-1 + 2**-2
=    2 +    1 +    .5 +   .25
= 3.75

Which is exactly 15/4 as expected. The problem is that you ignored the fraction digits and were therefore only left with 3. In this case, that happened to look like the shift divided by 5.

If you do a integer shift, then shifting by one bit right really does

trunc(N / 2)

where N is the original number and TRUNC simply sets all fraction bits to 0 (truncates them). Note that trunc(15/2) does equal 3.

Related Topic