Booth’s algorithm provides a faster and simpler method that can be used to multiply two n-bits binary numbers that can be either positive or negative. The main instructions it uses are shifting an adding. However, Booth technique is preferred to other methods of multiplying numbers because it uses a smaller number of logic elements compared to the others. This report, therefore, focuses on how to use the Booth algorithm to design a multiplier that has the ability to multiply two 8-bits signed numbers to give an output result in 16-bits.
Its design has three main registers named A, P, and S that are 2N+1 in input size, multiplicand, multiplier, and the 2’s complement of the multiplicand respectively. The registers implement the Booth’s algorithm multiplier operation. When the input size is 8 bit wide, then the output ought to be as double as that, 16 bits wide. The logic used to implement the multiplier is shown in the diagram below.
Figure1. State Diagram of the Booth’s Algorithm Multiplier Design.
Figure1 above depicts the different states that are used when designing a multiplier. The initial state is ‘init’ and it can’t move to the next stage called ‘Load’ unless the ‘start count’ is increased. The Load state loads inputs into their respective registers whereby the two smallest significant bits, 2LSB of the register P determines the operations to be performed as appropriate. For instance, if the 2LSB of the register P is “01”, the state goes to “(P+A)&shift” which adds A to P and shifts by 1 bit to the right. If the 2LSB of the register P is increased to “10”, the state will go to “(P+S)&shift” which will add the values of P to the 2’complements of A and shift it 1 bit to the right. Other values of the 2LSB of the register P make the state to go to “Do_nothing&shift” state and shift it one bit to the right. The shift operation is, therefore, performed to result to either the 2LSB of register P equal or differ.
The states then transform from “(P+S)&shift”, “Do_nothing&shift”, or “(P+A)&shift” to “shift state”. On reaching “shift state,” there are two conditions involved; state to move to one of the following states determined by the 2LSB of register P, “(P+S)&shift” or “Do_nothing&shift”, or “(P+A)&shift,” or move to “Done” state which is determined by the Count signal. The Count signal is, however, required to be equal to the input size in order for the state to move to “Done.” At this point, note that if the two least significant bits of P are equal, then the shift constitutes to one count. But, when they are equal to logic “01”, it will result to both an addition and a shift to the right, thus making another count. When one complete process is over, the state reaches “Done” and in this case there should be an increased “start_count” should to start next process.
Figure1 which shows the state diagram of the Booth’s algorithm multiplier is used to design the code in VHDL. The code includes the following components; a state machine instantiation that performs the proper operation to be executed, an instantiation of the counter to keep track of the shifts and additions, an instantiation of the multiplier that performs the shifts or additions or 2’s complement in the registers, and a product output that shows how the process occurs and seven segment code to display the result in the seven segments display.
Furthermore, a test bench code is created to test the correct operation of the booth’s multiplier. The code reads from an input file that contains comma separated values, .csv. It evaluates these values to generate an output following the process discussed above.
ModelSim software is used to check and simulate the VHDL code in order to make sure that the results and process are correct. Quartus software would then compile the VHDL code in order to know the number of created logics and implement the design onto DE2 board, as well. The following figure shows the results obtained from the Modelsim.
Figure 2. Simulation results of Booth’s algorithm multiplier design(A).
From the figure above, initially it can be seen that the input 1 and input 2 are at unknown state. When start is increased, the next rising edge of the clock loads the multiplier into the product register. Since the 2LSB are logic 10, the expected operation takes the 2’s complement of the multiplicand, input1 and add to the product register and then perform a shift operation. The process continues until the data ready becomes 1 as shown in the figure below.
Figure 2. Simulation Results of Booth’s Algorithm Multiplier Design(B).
When data ready becomes high, the output is compared with the expected output from the test bench. If the results are identical, no error is generated unless the otherwise. The figure below shows the flow summery of the design after the code compiled in Quratus.
Figure 3. The Flow Summery of the Booth’s Algorithm Multiplier.
From the figure above it can be seen that the design consumes about 116 logic elements which constitute less than one percent of the total logic elements. The total number of register used is 50 registers, estimated to be about 9% of the overall number of registers.
With its two main functions of addition and shifting, Booth’s multiplier is an excellent technique to perform multiplication of both positive and negative numbers. When compared to other multipliers, Booth has fewer logic elements thus giving it the advantage of faster shifting and addition regardless of short timing.