## 2 Previous Work
### Hard Multiple Generators  
This subsection discusses the HMG for the modulo (\(2^{n}-1\)) [22], modulo (\(2^{n}\)) [23], and modulo (\(2^{n}+1\)) [24] multipliers in the literature. In the Booth encoder (BE), the radix-8 Booth-encoding operation, which can reduce the number of partial products to \(\lfloor n/3\rfloor+1\) items by means of a four-bit interpretation of the multiplier; multiplication by 1 (\(\times 1\)); multiplication by 2 (\(\times 2\)); multiplication by 3 (\(\times 3\)); multiplication by 4 (\(\times 4\)); and the sign signal is obtained after the operation. Multiplications by 1 (\(\times 1\)), 2 (\(\times 2\)), and 4 (\(\times 4\)) are easy to handle, as multiplications by 2 (\(\times 2\)) and 4 (\(\times 4\)) only need to shift one bit and two bits to the left, respectively. However, multiplication by 3 (\(\times 3\)) is difficult to handle and cannot be obtained directly from the multiplicand, so the HMG unit is used to operate the process. There are two processing methods; the first is \(\mid+X\mid_{m}+\mid+2X\mid_{m}\), and the second is \(\mid-X\mid_{m}+\mid+4X\mid_{m}\), where \(X\) is the multiplicand and \(\mid X\mid_{m}\) is defined as the modulo operation of \(X\). The first type is clearly better than the second type because the first one does not need to process the 1's compliment operation. The related derivation results of the reported HMG are as follows. The representation of multiplication by 3 (\(\times\)3) is as follows:  
\[ \begin{array}{l}\left|+3X\right|_{m}=\left|+X\right|_{m}+\left|+2X\right|_{m };\\ \left|+X\right|_{m}=\left(x_{n-1}x_{n-2}\ldots x_{0}\right);\\ \left|+2X\right|_{m}=\left\{\begin{array}{l}(x_{n-2}x_{n-3}\ldots x_{0}x_{n- 1}),\,if\,m=2^{n}-1\\ (x_{n-2}x_{n-3}\ldots x_{0}0),\,if\,m=2^{n}\end{array}\right.;\end{array}  \tag{6}\]  
The generated bit, propagated bit, half sum bit, and delay half (DH) sum bit are defined as \(g_{i},p_{i},h_{i}\), and \(dh_{i}\), respectively [22; 23; 24]:  
\[ \begin{array}{l}g_{i}=x_{i}\cdot\ x_{i-1}\\ p_{i}=x_{i}+x_{i-1}\\ h_{i}=x_{i}\oplus x_{i-1}\\ dh_{i}=x_{2i+1}\oplus x_{2i}h_{2i}\end{array}  \tag{7}\]  
The equation for the carry bit at the odd position is shown as [22; 23; 24]:  
\[c_{2i-1}={P_{2i-1}}^{*}{H_{2i-1}}^{**} \tag{8}\]  
where \(P_{2i-1}\)\({}^{*}\) is a modified propagated bit, and \(H_{2i-1}\)\({}^{**}\) is a modified Ling bit [22; 23; 24]. The general equation of the modified Ling bit \(H_{2i-1}\)\({}^{**}\) is represented as [22; 23; 24]:  
\[{H_{2i-1}}^{**}=({G_{2i-1}}^{**},{P_{2i-3}}^{**})\bullet({G_{2i-5}}^{**},{P_{2 i-7}}^{**})\bullet\ldots\bullet({G_{2i-9}}^{**},{P_{2i-11}}^{**})\bullet\ldots \tag{9}\]  
where \({G_{2i-1}}^{**}\) and \({P_{2i-1}}^{**}\) are modified \({G_{2i-1}}^{*}\) and modified \({P_{2i-1}}^{*}\) bits, respectively. \({H_{2i-1}}^{**}\) is used to produce odd carry bits in the HMG and perform HMG prefix operations between \({G_{2i-1}}^{**}\) and \({H_{2i-1}}^{**}\). \({G_{2i-1}}^{**}\) and \({P_{2i-1}}^{**}\) are used to perform the logic OR operation and logic AND operation for the modified generated bit (\({G_{2i-1}}^{*}\)) and modified propagated bit (\({P_{2i-1}}^{*}\)), respectively. The modified generated bit (\({G_{2i-1}}^{*}\)) and modified propagated bit (\({P_{2i-1}}^{*}\)) are calculated from the generated bit and propagated bit, respectively. \({H_{2i-1}}^{**}\), \({G_{2i-1}}^{**}\), and \({P_{2i-1}}^{**}\) are the intermediate processing units in the HMG operation and can be used to produce the hard multiple bit. The final equation for the sum of bits at the even and odd positions in the HMG is as follows [22; 23; 24]:  
\[ \begin{array}{l}s_{2i}=h_{i}\oplus({P_{2i-1}}^{*}{H_{2i-1}}^{**})\\ s_{2i+1}=dh_{i}\oplus({h_{2i}}\oplus({P_{2i-1}}^{*}{H_{2i-1}}^{**}))\end{array}  \tag{10}\]  
From the above derivation of Equations (6)-(10), the block diagram is HMG was presented [22; 23; 24].