## 2 Background
### Schoolbook Strategy
Moreover, the \(clk\), \(rst\), and \(start\) inputs are one bit, while the remaining input pins (i.e., \(a\) and \(b\)) are \(m\) bits for \(m\)-bit operand lengths. The output pin \(c\)'s size is \(2m\) bits. The \(m\)-bit operand size ensures that our accelerator is parameterized and flexible. Depending on the user's choice, it can take different operand sizes as inputs and generate the multiplication result accordingly. We let the reader know that the Booth accelerator only multiplies polynomials without considering polynomial reduction. Therefore, the internal architecture of our proposed Booth accelerator depends on several elements such as three \(m\)-bit registers, i.e., \(Reg\)-\(A\), \(Reg\)-\(a\), \(Reg\)-\(b\), and one \(2m\)-bit register, named \(Reg\)-\(c\). Moreover, it contains one \(m\)-bit adder and subtractor, one \(4\times 1\) multiplexer, one _shift-right-add_ block, and a control unit. We describe these components one after another in the following text. ### Registers (or Buffers)

As shown in Algorithm 2, the required storage elements are \(A\), \(\overline{b}\), and \(c\). It can be seen that lines five and eight of Algorithm 2 require input of polynomial \(a\) for completion of the addition and subtraction operations. This is why the proposed accelerator contains four registers: three \(m\) bits and one \(2m\) bit. These registers are reused throughout the multiplication process, which allows us to obtain minimum hardware resource utilization. In addition, these four registers are temporary storage elements in our design. We discuss more specific details below. \(Reg\)-\(A\) is an accumulator buffer that initializes with \(0\) at reset, and then, in each clock cycle during the multiplication process, it updates values with the new ones. We preserve

Figure 1: Proposed Booth accelerator architecture. The red and blue dotted lines are the control signals. the input polynomial \(a\) in _Reg-a_ for the corresponding addition and subtraction executions of Algorithm 2. It can be observed that the input polynomial \(a\) is only needed for the addition and subtraction operations, and it never updates the corresponding _Reg-a_ during the entire multiplication execution. Therefore, _Reg-a_ can be avoided, but on the other hand, the design faces synchronization issues. Thus, we must hold the input polynomial \(a\) in _Reg-a_ to eliminate such problems. The \(\overline{\mathsf{b}}\) storage element of Algorithm 2 is shown with simple _Reg-b_ in Figure 1. Thus, from now on in the manuscript, _Reg-b_ means that it has a value of \(\overline{\mathsf{b}}\). _Reg-b_ contains a polynomial \(b\) with an additional 0-bit next to the least significant bit (LSB) of the multiplier for Booth encoding. Moreover, this _Reg-b_ is a part of the control block that shifts two bits (i.e., \(b_{j+1}\) and \(b_{j}\)) towards the right in each clock cycle to conduct the multiplication operation. Finally, _Reg-c_ keeps the resultant polynomial of \(2m\)-bit size. ### Adder and Subtractor

The adder and subtractor circuits require two inputs. The first input is from the accumulator, and the other is the polynomial \(a\), which is a multiplicand. We remind the reader that the accumulator is _Reg-A_ and the multiplicand is preserved in _Reg-a_. Figure 1 confirms the input connections to the adder and subtractor, which are from registers _Reg-A_ and _Reg-a_. Depending on the values of \(b_{j+1}\) and \(b_{j}\) in each clock cycle, the adder accumulates the multiplicand into _Reg-A_. If we delve more into it, the adder operates when the inspected bits for \(b_{j+1}\) and \(b_{j}\) are 01. Similarly, the subtractor is responsible for subtracting the multiplicand from the accumulated value preserved in _Reg-A_. In other words, the subtractor operates when the inspected bits for \(b_{j+1}\) and \(b_{j}\) are 10. There are several choices or possibilities for implementing the logic for the adder and subtractor.