Electronic – the correct way to implement left shift operations using multipliers

fpgavhdl

I require a left shift operation to be done in VHDL. Input is 24 bit and shift amount is by 16 bits maximum.

Left shift operations by n are synonymous with multiplication with 2^n which is to say that:

x << n = x*2^n.

Normally implementating a left shift operation in VHDL with variable shift amount shall implement a multiplexer e.g implementing a 16 bit shifter on a 24 bit input shall create a 16-to-1 multiplexer. The shift amount n will then select one of the 16 possible 24 bit outputs. This approach can create massive multiplexers that will later limit Fmax in the design.

I have found that alternative to this is to use a multiplier for the shift operation. Using a hard multiplier in place of a mux created from FPGA logic resources shall lead to better Fmax in the design. In this instance the 24 bit input shall be one operand and a 2^n where n has maximum value of 16 shall be the other operand. Here also, n is input to control the shift amount.

I have one confusion here; when using a multiplier we shall have to generate quantity 2^n from the shift amount n. This will require a look up table. In this case it shall become a 16-to-1 multiplxer where n selects the 16 bit mux output. Since we end up with a big multiplexer in this case as well, doesn't this defeat the purpose of using a multiplier?

Best Answer

If your input shift is 4 bits wide, you need 16 LUTs for the 16 inputs of the multiplier, and generate 00001, 00010, 00100 ... 

A<=INPUT;
OUTPUT <= A  * B;
B(0)<='1' WHEN SHIFT="0000" ELSE '0';
B(1)<='1' WHEN SHIFT="0001" ELSE '0';
B(2)<='1' WHEN SHIFT="0010" ELSE '0';
*etc...*

With "free" multipliers, it can be smaller than a barrel shifter.

Usually barrel shifters are made with cascaded multiplexers. Something like that :

X0 <= INPUT & '0' WHEN SHIFT(0)='1' ELSE '0' & INPUT;
X1 <= X0 & "00" WHEN SHIFT(1)='1' ELSE "00" & X0;
X2 <= X1 & "0000" WHEN SHIFT(2)='1' ELSE "0000" & X1;
OUTPUT <= X2 & "00000000" WHEN SHIFT(3)='1' ELSE "00000000" & X2;

You can also use VHDL standard libraries and let the synthesiser decide which implementation is the best :

OUTPUT <= ieee.numeric_std.shift_left(INPUT,to_integer(SHIFT));
Related Topic