## 2 Related Work  
This section reviews radix-4 Booth-encoding-based modulo (\(2^{n}+1\)) and modified Booth-encoding-based modulo (\(2^{n}-1\)) multipliers, as well as multifunction modulo (\(2^{n}\pm 1\)) multipliers based on the modified Booth encoding scheme [8]. Unlike the traditional Booth encoder, which uses double-code interpretation, the modified Booth encoder,also called radix-4 Booth encoding, adopts a three-code interpretation. First, 0 is added after the least significant bit of the multiplier and 0 is also added in front of the most significant bit of the multiplier. This three-code interpretation method substantially reduces the partial product, which almost halves the hardware area. As a result, the significant reduction in the use of the full adder facilitates faster calculations. The modulo (\(2^{n}+1\)) multipliers and modulo (\(2^{n}-1\)) multipliers are the two most commonly used in the RNS, and these will be reviewed in the following paragraphs. The operating range of the modified Booth-coded \(1^{\prime}\)s complement modulo (\(2^{n}-1\)) multiplier [1] is [0, \(2^{n}-1\)]. The block diagram of _modulo multiplication_ using modified Booth encoding is shown in Figure 1. Multiplier B first performs improved Booth encoding (BE) and multiplicand A operates a Booth selector (BS) according to the encoded value. Subsequently, the addition array of partial products is generated and these partial products are summed by the full and half adders. Finally, the result is obtained by performing end-around-carry. The relative formula found using the modified Booth-encoder-based \(1\)'s complement modulo (\(2^{n}-1\)) multiplier is given by  
\[B=\sum_{i=0}^{n-1}2^{2i}(b_{2i-1}+b_{2i}-2b_{2i+1}) \tag{1}\]  
\[A\times B=\sum_{i=0}^{n-1}A\times[2^{2i}(b_{2i-1}+b_{2i}-2b_{2i+1})]=\sum_{i=0 }^{n-1}PP_{i} \tag{2}\]  
The system block of modified Booth-coded \(1^{\prime}\)s complement modulo (\(2^{n}-1\)) multipliers is shown in Figure 2, where \(n\) is set to 8; therefore, it is the block diagram of the modified Booth-encoding-based modulo 63 multiplier [1]. In Figure 2b,c, the \(\times 1\) and \(\times 2\) of the Booth encoder and Booth selector are used to multiply by 1 and 2, respectively. The sign signal is used to determine positive or negative based on the modified Booth encoding regulation. Multiplier B adopts a three-code interpretation in operation, so the logic circuit diagram of BE in Figure 2b can be deduced from the operation in Equation (1). When three numbers, b\({}_{2i-1}\), b\({}_{2i}\), and b\({}_{2i+1}\), are inputted, the output can be obtained from the signals multiplied by 1 (\(\times 1\)), multiplied by 2 (\(\times 2\)), and the sign signal. The sign signal is used to  
Figure 1: Block diagram of modulo multiplication using modified Booth encoding [1]. determine whether the multiplication output of multiplicand will be positive or negative. When the value of sign is 0, the output of the multiplicand is a positive value; when it is 1, the output of the multiplicand is a negative value. According to Equation (1), multiplier B multiplied by multiplicand A will provide Equation (2), where \(\rm{PP_{i}}\) is its partial product and \(\rm{PP_{i}}=A\times 2^{2i}(b_{2i-1}+b_{2i}-2b_{2i+1})\). For modulo (\(2^{n}+1\)) multiplication using modified Booth encoding, a modified Booth-encoding-based modulo (\(2^{n}+1\)) multiplier was proposed [2]. This work adopted weighted architecture and did not require additional subtraction and addition operations, such as the diminished-1 architecture as well as additional conversion circuits and a zero detection circuit. However, an additional weighting circuit is required to obtain the final result. Even so, the performance of this method is still better than that of modified Booth-encoding-based modulo multiplication using the diminished-1 architecture.