# Decimal Multiplication in FPGA with a Novel Decimal Adder/Subtractor
## 2 Related Work  
Processors with dedicated decimal hardware multipliers implement them with iterative algorithms [16,17] to reduce the size of the arithmetic unit. However, iterative algorithms are slow compared to parallel implementations due to its iterative nature. for fast execution, parallel decimal multiplication consists of partial product generation for each multiplier digit followed by partial product addition. Partial product generation of a \(N\times N\) multiplication can be implemented with \(N\times N\) small digit by digit multipliers or \(N\) digit by multiplicand multipliers. A digit by digit multiplier can be implemented with logic or with look-up tables [18, 19, 20]), for fast and compact design. However, given the quadratic number of digit by digit multipliers necessary to implement a multiplication, these solutions are viable only for small operand sizes. The proposal in [21] considered recoding of operands to simplify digit by digit multiplication for partial product generation. However, the performance and area of the decimal multiplier based on digit by digit multiplication is still worst than a multiplier with a partial product for each multiplier digit. The approach followed to implement a \(1\times N\) multiplier is to determine the decimal multiples of the multiplier. A direct approach to a design a decimal multiplier based on multiples generates all multiples of the multiplicand. Then, selects the required multiples according to the multiplier digits. The generated multiples are then shifted and added to generate the final product. While simple, the method requires a large multiplexer with all multiplies for each multiplier digit and the generation of all multiples from A to 9A. Knowing that the generation of some multiples are not carry-free, this solution degrades the performance of the multiplier. Therefore, authors started to consider only a limited set of multiples. In [22] only multiples A, 2A, 4A, 5A are used, since they can be generated without carry propagation (multiple 4A is generated from 2A in sequence as 2\(\times\) 2A). The other multiples are obtained by adding two of these multiples. Since multiple 4A cannot be generated in a single carry-free step, it has been removed from the set of base multiples in [23]. The other multiples are obtained by adding a multiple from the set {0, 5X, 10X} and a multiple from the set {-2X, -X, 0, X, 2X}. For fast selection of multiples, digits of the multiplier are first recoded, but the solution requires a large multiplexer for each multiplier digit. Since then, other sets of multiples and encodings were considered. In [24] two different decimal encodings (4221 and 5211) are used to generate and reduce the partial products with two different architectures. In one the architectures the multiplier is recoded into a signed-digit (SD) set \([-5,5]\), while in the other the multiplier is encoded as \(A=Y^{U}S+Y^{L}\) like in [23], where \(Y^{U}\in\{0,1,2\}\) and \(Y^{L}\in\{-2,-1,0,1,2\}\). Signed-digit (SD) recoding of the multiplier in the set \([-5,5]\) was adopted by several authors for the implementation of a decimal multiplier [25; 26]. The base architecture generates multiples {0, X, 2X, 3X, 4X, 5X}. These are selected for each partial product and the output is complemented to obtain the negative of the multiple. The partial products are then reduced with a partial product reduction module. Different representations are used to improve the generation of complements and the decimal addition. The radix-5 algorithm proposed in [24] was followed by [27] but using an hybrid 8421-5421 representation. In [28] a decimal multiplier is proposed using a redundant decimal addition algorithm based on a weighted bit-set encoding. The method generates double BCD (Binary-Coded Decimal) numbers using decimal multiples 2X, 4X, and 5X. The redundant decimal adder is used to reduce the generated 2\(n\) BCD partial products to a redundant number in the range of [0, 15]. The final redundant product is then converted to BCD encoding.