0
\$\begingroup\$

I am trying to under stand how to build a barrel shifter using multiplexers. I understand how the barrel shifter works but I don't get how you decide the number of multiplexers to use, and how the shifting is done with the multiplexer basically.

So far wikipedia doen't help much. And the best I have so far is https://tams-www.informatik.uni-hamburg.de/applets/hades/webdemos/10-gates/60-barrel/shifter8.html

But it does not really answer my question.

\$\endgroup\$
1
\$\begingroup\$

The number of multiplexer stages equals the binary logarithm of the number of bits to be shifted.

Each stage passes the value either unchanged or shifts it by 2^n where n is the number of the stage starting with 0. The first stage shifts by one (2^0) bit, the second by two (2^1), the third by four (2^2) and so on.

If all stages are in shift mode then a total shift of 2^n + 2^(n-1) + ... 1 = 2^(n+1) - 1 is obtained. For three stages that would be 2^3 - 1 = 7 bits, what is exactly the required maximum, since a shift of 8 bits would equal to no shift at all.

Assuming the data width is 8 bits, 3 stages are required because 2^3 = 8.

The total number of multiplexers is given by the number of multiplexers per stage times the number of stages. In this case 8*3 = 24 multiplexers (with two inputs and one output).

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot.. Please Just for confirmation. Let's suppose we have 8 bits inputs. I want to make a shift of 4 bits to the left. It means the number of stages is 2. The total number of multiplexers will then mean 8^2=16 multiplexers. Does that means that there is a multiplexer for each input bit? why not one mux with 8 inputs and 3 control signals? \$\endgroup\$ – eskoba Jul 3 '16 at 13:21
  • \$\begingroup\$ The main idea is that you are able to set the number of bits dynamically. If you want to chose between 0, 1, 2, 3 or 4 bits, you have 5 possibilities. The next power of two larger than or equal to five is eight. Since 2^3 = 8 you again need three stages. \$\endgroup\$ – Mario Jul 3 '16 at 13:51
  • \$\begingroup\$ Ok. This means that the number of stage is 3 but the 24 is the maximum number of mux. Meaning it is actually possible to use fewer multiplexers but the number of stages is fixed. \$\endgroup\$ – eskoba Jul 3 '16 at 13:58
  • \$\begingroup\$ It's like in the link you provided. Three stages and eight muxes per stage. \$\endgroup\$ – Mario Jul 3 '16 at 14:13
  • \$\begingroup\$ alright, that means the number of Muxes is also fixed. Thanks again for the clarification \$\endgroup\$ – eskoba Jul 3 '16 at 14:18
1
\$\begingroup\$

Each multiplexer produces one output bit, so the number of multiplexers you need is equal to the width of the output bus.

The number of inputs on each multiplexer is equal to the number of different shifts you want to create. A fully-general barrel shifter would use multiplexers that have an input for each bit of the input bus.

Here's a simple example for a 4-bit input and output buses:

schematic

simulate this circuit – Schematic created using CircuitLab

This kind of barrel shifter has the minimum delay from any Dn input to any Yn output (2 levels of logic). The delay from any Sn input to any Yn output is slightly greater (3 levels of logic).

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the answer. Please what do mean when you say that " The number of inputs on each multiplexer is equal to the number of different shifts you want to create"? if I have 8 bits input, and want to make a 4 bits shift without lost of data. It will mean that I will have 7 multiplexers. But then will have 1 input for each multiplexer, right? how do I keep track of initial data? \$\endgroup\$ – eskoba Jul 3 '16 at 12:06
  • \$\begingroup\$ See edit above for an example. But I have no idea what you mean by "initial data". \$\endgroup\$ – Dave Tweed Jul 3 '16 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.