On Barrel Shifters.

There are two major points in the construction of Barrelshifters,
as given in the book, on page 197, fig.6-6.

1) The construction of the shifter for any one SA bit, [recall, SA stands
for Shift Amount]. Altogether since we might want to shift anywhere between
0 and 31 bits, we need log_2(32) = 5 bits to represent the shift amount.
Hence, altogether we have bits, SA_0,..., SA_4.

2) The second stage is, after the composition of a shifter for a particular
SA bit, to compose all of them together, that is, to cascade the shifters.
This stage is easier, once the composition of every individual shifter is
completed, because, this is what we have. Suppose there is a circuit C_1 
which shifts its input by 1 bit [for the sake of brevity, or exposition,
lets assume, things are being shifted to the right], and that there's 
another circuit C_2 which shifts its input by 2 bits to the right.
That is, an instance of the action of C_1 or C_2 on the input, 0111, 
would be : 
C_1(0111) = 0011
C_2(0111) = 0001

So when we cascade the two circuits one after the other, then we get, in 
effect, a three bit shift to the right, of the input. Cascading, by 
definition, means, that we take the output of one circuit and feed it 
as the input to the next. 

Now we can get down to the actual construction of the circuits.

The construction is rather simple, if one prepares not to get bogged down
by Fig.6-6 of the book. For step 1 above, all we need to do is to decide
what it is we have to do. 

For instance, say the inputs are given as b_0, b_1,.... [as in the book]
and the outputs are taken out as c_0,c_1,.... 
Consider the case for SA_0  :
We denote the ShiftRight line by SR.

Consider the single output, c_1. When SR = 1, we are meant to be shifting 
the input to the right, whereas if SR = 0, it means we are shifting things
to the left. On the other hand, if SA_0 = 0, we aren't supposed to be 
shifting anything at all, whereas, if SA_0 = 1, we are supposed to be 
doing a shift (by one bit) depending on the value of SR.

Now, we can draw up the following table : 

  SA_0       SR         c_1
----------------------------
   0         0          b_1
   0         1          b_1
   1         0          b_0
   1         1          b_2
----------------------------

Clearly, if SA_0 = 0, that is we are instructed not to shift stuff, 
then whatever be the value of SR, c_1 is just copied over from the 
value of b_1.

So, from this table, we can get an expression for c_1 in terms of 
SA_0, SR, and the b_i's.

c_1 = not(SA_0).b_1 + SA_0.not(SR).b_0 + SA_0.SR.b_2 .

Similarly, so also for c_2, c_3... and c_0 too. [Caveat : for c_0,
and c_31 we have to be a tad bit careful, these being the boundary 
cases. For instance, what happens, if we are shifting left, c_0 gets
the value 0 in that case.]

So, this when represented as an OR of ANDs gives us the circuit for 
SA_0.

SA_1 is somewhat similar. What does SA_1 signify? If its 1, then it means
shift the input (left or right, according as to the SR value) by two bits.
If its 0, don't do anything.

So, a similar table for c_2 (say) : 

  SA_1    SR     c_2
----------------------
   0      0      b_2
   0      1      b_2 
   1      0      b_0
   1      1      b_4
----------------------

So, again, 
c_2 = not(SA_1).b_2 + SA_1.not(SR).b_0 + SA_1.SR.b_4
(represent as OR of 3 ANDs)

So, up until now, we have described the barrel shifting process' stage 1.
Step 2 is easy, just cascade the various circuits for SA_4, SA_3 .. 
one after the other. 

I hope that helps to clarify Fig.6-6 of the book. Comments are welcome, 
and may be sent to samroy@paul.rutgers.edu.