Multiplication using Look Up Tables - Digital System Design

In the previous tutorials, many techniques are discussed for multiplication operation. An alternative way of computing multiplication is using look up tables. Multiplication using look up tables can be useful where serial multiplication is needed or memory devices are available like in FPGA device. This technique is based on the following popular algebraic equation

$A\times B = \{{(A+B)}^2 - {(A-B)}^2\}/4 = 4\times (A \times B)/4$

In the first step, two data elements $A$ and $B$ are added and subtracted. Then results of addition and subtraction are provided to two squaring tables as addresses. The squaring tables store the square of all the elements which are required to fetch. The output of the squaring tables are then subtracted to get the final multiplication result

Figure 1: A schematic for Multiplication using look up tables

The simplest parallel architecture of multiplication using look up tables is shown in Figure 1. Here, two $n$ bit adder and subtractors are placed in the first step. The results of these adder and subtractor blocks are of $(n+1)$ -bit. Thus size of the squaring tables will be $2^n\times (n+1)$ . At the final stage a subtractor is placed which is of $2n$ -bit size. The circuit is simpler and pipeline registers can be easily inserted.

One squaring table can also be used. The adder and subtractor blocks in the first stage is also can be shared. In this case, the architecture will be serial and the circuit will be more hardware efficient. The size of the table can be reduced as they only store the square numbers. The square numbers will be always even and also the two LSB bits will be shifted out at the final stage. Thus the new size of the tables will be $2^n\times (n-1)$ .

Verilog code for Multiplication using LUT (3656 downloads )

Related Posts