6
\$\begingroup\$

A left shift by n bits is the same thing as multiplication by 2^n. This means that left shift can be done without barrel shifter by using a hardware multiplier block. There are plenty of DSP blocks in modern FPGAs. This question is about using hardware multipliers.

That being said, what about right shift? A right shift could be implemented as division by 2^n. However, division hardware is basically out of question. So if we can't use divider, can right shift still be implemented using just a hardware multiplier somehow?

EDIT:

I have to shift 32 bit word by n bits and then concatenate with another 32 bits. The original input is 32 bits but the actual number of valid bits is usually less than 32 and that is why a left shift and OR to concatenate is possible.

So the thing being designed here is a concatenation module. When the word is large enough after conatenation, it shall be pushed into a FIFO.

\$\endgroup\$
12
  • 7
    \$\begingroup\$ All you need to implement shifts in an FPGA is some routing resources and muxes. There is no need to use multipliers at all. Is there a reason you insist on using multipliers? It really depends on the architecture of the FPGA whether the multiplier-based solution will be faster than conditionally moving some bits around, especially with wide LUTs where 2 or even 3 levels of shifting can be accommodated in one level of logic. \$\endgroup\$
    – Kuba hasn't forgotten Monica
    Commented Aug 7 at 22:51
  • 2
    \$\begingroup\$ I will explain the reason for multipliers. Having a large massive mux that shifts the data data does not let me reach the 100MHz that I need. I get stuck at 86MHz. But using hard multipliers, I am able to reach a higher FMax. That is the basic reason. \$\endgroup\$
    – gyuunyuu
    Commented Aug 7 at 22:56
  • 1
    \$\begingroup\$ Division by 2^n is equivalent to Multiplication with 2^-n, so yeah, multiplication works. \$\endgroup\$
    – tobalt
    Commented Aug 8 at 6:59
  • 1
    \$\begingroup\$ The basic idea is like this: I get two pieces of data that has a length of between 1 and 16 bits, and 1 and 12 bits. I need to concatenate them together. When I concatenate, I need to combine this variable size data with what was already present from last concatenation. If I use multiplier, I can do this in few clock cycles. If I use mux, it will be a lot of logic and not meet timing, or take a lot more latency. I am actually going to use both approaches and compare the result eventually. \$\endgroup\$
    – gyuunyuu
    Commented Aug 8 at 13:04
  • 1
    \$\begingroup\$ @PavanKumar, that gets the clock rate up but doesn't bring the circuit's latency down, it increases it. That may not matter for this OP's problem but, as a general solution, it's not improving performance, just attainable clock frequency. So that wouldn't be a solution for a CPU where performance matters, for example. The multiplier is the age-old and simple FPGA solution, if they're in your part which most have for a long time. \$\endgroup\$
    – TonyM
    Commented Aug 8 at 13:22

5 Answers 5

Reset to default
8
\$\begingroup\$

Here is the basic idea. We are talking about shifting by variable number of bits. I should have made that very clear.

x << n can be implemented as x*2^n
x >> n can be implemented as x/2^n

Now the / operator cannot be implemented in hardware without much trouble. However, there is still a way around this.

If we want to shift right rather than shift left, we first flip the bit order i.e x[m..0] to x[0..m] which causes MSb to go to the right end and LSb to goto the left end. Now if we shift left, we are actually going to drop the LSb of the original data so effectively are doing right shift on the original data!

Then multiply with 2^n with this x[0..m] where n in this case is the number of bits to shift to the right. Now, flip the result from multiplication back so that the x[0..m] becomes x[m..0] again.

This is how we can implement right shift on data by doing a left shift on the mirror image of data and then doing mirror of the result again.

\$\endgroup\$
4
  • \$\begingroup\$ Yes, this is the correct answer! If our previous conversation had gone further, I would have pointed this out to you. I'm glad you were able to realize it on your own. \$\endgroup\$
    – Dave Tweed
    Commented Aug 7 at 22:06
  • \$\begingroup\$ Edt your question to make this clearer. I just tried one edit. \$\endgroup\$
    – smci
    Commented Aug 8 at 5:10
  • 1
    \$\begingroup\$ Is bitswapping-multiplying-bitswapping somehow preferable to just multiplying and taking the MSBs you want? \$\endgroup\$
    – Justme
    Commented Aug 8 at 6:56
  • 1
    \$\begingroup\$ @Justme, yes, much. Besides being clearer to follow, it gives a greater output bit range as no multiplier bits were discarded. \$\endgroup\$
    – TonyM
    Commented Aug 8 at 10:30
6
\$\begingroup\$

Yes, you can do this. The trick is to just combine a variable left shift (implemented by a hardware multiplier) with a fixed right shift by selecting off the high bits of the result. For instance, to shift by quantities up to 16, you can do:

x >> n == (x * 2^(16-n)) >> 16

You have to make sure that the intermediate result doesn't overflow. However, most FPGAs I have worked with have multipliers with output large enough to avoid this problem.

\$\endgroup\$
3
\$\begingroup\$

If the implementation is on an FPGA, why bother shifting bits at all? Keep the input bits as they are and add new LSBs or MSBs that are zeroes to the original bit pattern. No shifting required.

If you need arbitrary left and right shifts, multiply input by some value and take the output bits you want from the MSB part. For example if you have an 8-bit input, multiply it by 128 and ignore 8 LSBs of the result and take the next 8 bits as the output - the output is 128/256 i.e. multiplied by 0.5 or divided by 2 i.e. shifted right by 1 position.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ If the implementation is on an FPGA, why bother shifting bits at all? Keep the input bits as they are and add new LSBs or MSBs that are zeroes to the original bit pattern. No shifting required. You're imagining just a fixed shift but OP states by n bits. Shifting by a variable number of bits is one of the slower operations in digital logic and FPGAs, especially with a larger number of bit positions. Using hardware multipliers for variable left shifts is a well-known and valuable way of speeding these up. Hence wanting to use the same to shift right. Downvoting as a result, I'm afraid. \$\endgroup\$
    – TonyM
    Commented Aug 7 at 20:17
  • 1
    \$\begingroup\$ @TonyM But I did mention how to use a hardware multiplier for right shift if really needed. \$\endgroup\$
    – Justme
    Commented Aug 7 at 20:33
  • \$\begingroup\$ Going on to say something contrary in the second paragraph doesn't alter the first, very declarative and free-standing paragraph. Or it sending out the message that you hadn't read the question, I'm afraid. (As a friendly observation of your answers over time, I don't think you read your answers as if you're another person reading it cold, I think you see them just from the pov you meant them. When people comment they're confusing, you often reply you don't see it. Just something to think about that may help. Here, I even quoted the paragraph in full so you knew what to look into.) \$\endgroup\$
    – TonyM
    Commented Aug 8 at 10:48
2
\$\begingroup\$

If you consider fixed point arithmetic instead of integer arithmetic, then you have access to a multiplicand that can perform a right shift.

Working in binary, a multiplication by 10.00 (ie decimal 2) is a left shift by 1, multiplication by 01.00 is no change and multiplication by 00.10 (ie decimal 1/2) is a right shift by 1.

Another way of looking at this is how the result is chosen from the available output bits.

If OP has a 32bit x 32bit multiplier, then the result would have to be 64bit to handle all input values without overflowing. Taking the low 32bits means that only left shifts can occur, while taking the high 32bits means that only right shifts can occur (assuming a single bit is set).

So inputs of 0x8000000 and 0x00000002 will give a 64bit result of 0x00000001 00000000. ie the upper 32bits is the second input shifted right by 1 bit.

\$\endgroup\$
0
\$\begingroup\$

Don't use multipliers if you don't have to, they are expensive in the amount of gates they use. This is why you should use shifting by 2 which requires very little Asic/FPGA resources, right divides and left multiplies (easy to see, if you pad 10b with 0 you get 100b which is 4 and conversely if you drop a digit of 1000b you get 4 which is 8/2=4)

You could do this with a hardware multiplier and get it to divide, if you truncate the output which can be done with most DSP blocks, but its more likely that it sends it to a shift register and shifts the value in a different instruction. There might be some DSP's that can do this in one operation, but I am not aware of any. (I know of a few that do muliply-adds in one operation)

\$\endgroup\$
1
  • 3
    \$\begingroup\$ You've not read the question correctly: OP states a hardware multiplier, not FPGA gates. So practically no FPGA gates used. Downvoting as a result, I'm afraid. \$\endgroup\$
    – TonyM
    Commented Aug 7 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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