{'fraction_non_alphanumeric': 0.03724630475071193, 'fraction_numerical': 0.015956244632283144, 'mean_word_length': 4.884042553191489, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Area- Efficient VLSI Implementation of Serial-In Parallel-Out Multiplier Using Polynomial Representation in Finite Field GF(2m)

Finite field multiplier is mainly used in error-correcting codes and signal processing. Finite field multiplier is regarded as the bottleneck arithmetic unit for such applications and it is the most complicated operation over finite field GF(2m) which requires a huge amount of logic resources. In this paper, a new modified serial-in parallel-out multiplication algorithm with interleaved modular reduction is suggested. The proposed method offers efficient area architecture as compared to proposed algorithms in the literature. The reduced finite field multiplier complexity is achieved by means of utilizing logic NAND gate in a particular architecture. The efficiency of the proposed architecture is evaluated based on criteria such as time (latency, critical path) and space (gate-latch number) complexity. A detailed comparative analysis indicates that, the proposed finite field multiplier based on logic NAND gate outperforms previously known results


Introduction
The finite field arithmetic has recently gained considerable attention in many important areas such as coding theory, the implementation of error correcting codes (ECC), computer algebra, and digital signal processing. The performance of these applications can be improved by an efficient hardware implementation of finite field GF(2 m ) arithmetic operations. A finite field GF(2 m ) is an algebraic set structure which contains 2 m elements which can be completely constructed by an m th degree monic polynomial over GF (2) called as an irreducible polynomial of the field GF(2 m ). A polynomial over GF(p) of degree m is irreducible if it is not divisible by any polynomial over GF(p) of degree less than m [13]. Diverse arithmetic operations such as addition, multiplication, inversion, and squares can be performed in the field GF (2 ) and the result of these operations is modulo the irreducible polynomial. While the addition is simpler than other finite field operations as there is no carry propagation, and it can be readily carried out with two-input XOR gates, multiplication is the most demanding and time-consuming operation which is frequently used in exponentiation, division, and multiplicative inversion. Hence, multiplication plays a pivotal role in performing finite field arithmetic operations, and it is crucial to employ efficient design in the implementation of finite field multiplier to meet the need of performance challenges of state-of-the-art applications based on finite field arithmetic. In the literature, the elements of a finite field GF(2 m ) can be represented using various basis including dual basis (DB) [8], normal basis (NB) [8], [21] and redundant basis (RB) [25], [18], polynomial basis (PB) [2], [10], [22], which each one has its own distinct features [1]. The efficiency of finite field multiplication highly depends on the representation of the elements. While DB bases multipliers require less chip area for VLSI implementation, they usually employ additional modules for basis conversions [7]. NB basis multiplier is favored in performing squaring in finite field that makes it more suitable in performing division, multiplicative inversion, and exponentiation operations. RB bases not only suggests free squaring operation but also eliminates the modulo reduction, however, it requires more bits to represent field elements that can result in more hardware complexity [18]. The PB multiplier is the most well-known one which does not require basis conversion. Moreover, considering its regularity and simplicity, it has gained more attention for hardware implementation. Furthermore, PB multiplication can be developed based on the two different categories: parallel and serial computations. All output bits of the multiplication in parallel implementation is generated in a single clock which leads to high throughput. However, for achieving low space complexity, bit-level serial computations are used. In bit-level serial multiplication schemes, space complexity is reduced at the expense of increasing the number of clock cycles required for generating the m output bits (computational latency) to m clock cycles. The proposed architecture in this work targets resource-constrained applications, and it is for a bit-level PB multiplier. In the bit-level category, the architectures can be bit-serial or bit-parallel. While in bitserial architectures, input/output enters/generates either in parallel, or serially, in bitparallel architectures, all inputs and outputs are parallel. Moreover, different types of implementations such as sequential [15], [19], parallel [1], [5], [24], [18], systolic [4], [26], [12], [23] and semi-systolic [10] have been proposed in the literature. Since the output of a sequential structure is available after m clock cycles for GF(2 m ) multiplication, it has longer execution time at the advantage of less hardware complexity. While parallel structures concurrently generate output in a single clock cycle, they consume excessive hardware. The outstanding features of systolic structures are regularity, modularity, concurrency and local interconnections which are more suitable for VLSI implementation. Systolic structures increase throughput, although their area and latency are usually very large. A group of bits called a digit can be processed at a time in digit-level [18] architectures. Digit-level architectures can achieve better area and time complexity and thus are practical for resource-constrained devices such as smartphones.
Numerous techniques for polynomial basis (PB) multiplication over GF (2 m ) have been proposed to reduce area overhead and speed up computations. [7] proposed a novel scalable serial multiplier architecture for PB multiplication over GF(2 m ) using progressive product reduction (PPR) technique. This architecture was extracted by converting the GF(2 m ) multiplication into an iterative algorithm using the systematic nonlinear technique that combines affine and nonlinear processing element (PE) scheduling and assignment of computations to processors. In [2], a new class of pentanomials over F2 was presented in which the standard Karatsuba algorithm has been used in the multiplication process, and shown that in the reduction process no ANDs are required. In [11] a serial-output bit-serial multiplier structure for general irreducible polynomials has been proposed which required m clock cycles for the latency, the proposed serial-output bit-serial multiplier has the latency of one clock cycle. By connecting the output of the proposed multiplier to the serialinput of the LSB-first multiplier, one can obtain a hybrid structure which performs two multiplications together. [5] presented a new non-pipelined bit-parallel-shifted polynomial basis multiplier for GF (2 m  for certain irreducible trinomials. In [9] was proposed the architecture of a polynomial basis multiplier which supported polynomial basis multiplication based on irreducible polynomials with m ≥ kt + 4. In terms of timing performance, the proposed architecture had a latency of m/4. In [27] was proposed a versatile polynomial basis multiplier which utilized a row of tri-state buffers and some control signals along with the (MSB)-first multiplier with a lower power dissipation property in a particular architecture. In [17] has been presented three small classes of irreducible polynomials for low-complexity bit-parallel multipliers. It has been shown that the proposed multiplier has lower complexities than the ones based on pentanomials.
[15] presented a sequential polynomial basis multiplier for generic irreducible polynomials with a latency of m clock cycles. This architecture is designed to take one operand in parallel and another operand serially during computation. It is a versatile multiplier in the view that it is applicable to any irreducible polynomial over GF(2 m ). In [19] was proposed a modified algorithm with interleaved modular reduction multiplication approach. The modification involved formulating the algorithm employing more efficient logical relations which uses logical NAND and XNOR gates in multiplier design. Motivated by the modified algorithm in [19], in this paper, we propose a new modified algorithm based on the method of serial interleaved multiplication [14] that is available in the literature. For more area-efficient implementation, the proposed formulated algorithm eliminates the logical XOR (XNOR) gates using a well-known logical relation. Since NAND gate has a lower area and time complexities as compared to other gates complexities such as AND or XOR/XNOR, employing this efficient logical relation can lead to hardware efficiency [16], [18]. We have also developed the bit-serial sequential architectures for the proposed algorithms and compared the performance of these architectures with that of architectures available in the literature. The analysis shows that the proposed multiplier achieves low-area compared to the majority of similar multipliers available in the literature and it is comparable with the best existing area-efficient multiplier, for m = 163. Hence, our multiplier would be preferable in situations where space complexity and saving energy are more relevant than time complexity such as parallel image watermarking in image sensors, a scenario which has area limitations [20], or a typical domestic application that needs a handful of IoT edge-devices [3] The organization of this paper is described as follows: In Section 2, we provide notations and preliminaries of finite field multiplication in GF(2 m ) using the polynomial basis. In Section 3, we derive formulations for the proposed polynomial basis multiplier structure. The architectural complexity and the performance comparison are discussed in Section 4 followed by the details of VLSI implementations of five practical field size multipliers. FPGA implementation results of the proposed multiplier are presented in Section 5. Finally, the conclusion remarks are given in Section 6.

NOTATIONS AND PRELIMINARIES
As it is noted before, this paper deals with finite field elements represented in polynomial (or standard or canonical) basis. An extension Galois field can be completely constructed by an m th degree monic polynomial of the form, (2 m ) of degree less than m [13]. All elements of the extension field GF(2 m ) in polynomial basis can be represented as polynomials over GF (2) of degree less than m [13]. Let be a root be of the irreducible polynomial for GF (2 m be two field elements and Then the finite field multiplication .
The product need to be first calculated, resulting in a polynomial of degree at most 2m -2. In a second stage, the modular reduction is performed which resulting in the polynomial C(x) of degree at most m -1.

GF(2 m )
The each in equation (3) can be performed recursively as follow: (4) It is obvious from the equation (4) that the summation is performed in m iterations for i = 0, 1, …,m-1. It should be also noted that xA(x) is calculated by the modular reduction step and then would be multiplied by bi . So by interleaving f(x) throughout the equation (4) it can be expressed as follow: According to equation (5) the term of should be carried out (m-1) times. If it is considered as P k-1 (x), module reduction will be performed on is a partial-product polynomial that generated in The equation (6) can be evaluated for each m k  , as follows, where k is the iteration count, , at the first, the product polynomial From equation (7) it can be seen that the modular reduction is reduced to the summation of Due to the left-most term equation (4) the product term should be added to equation (5). The result of summation can be represented by x P for the next iteration. So it is obvious that the equation should be repeated m times to be carried out the final multiplication result of equation (4). It is worth pointing out that the summation is computed using XOR operation. So the equation (8) can be written as follow: For more efficient implementation, the logical XOR operation can be converted to an equivalent circuit that only uses NAND, since for any two logic variables a and b, we can find that (a XOR b) = ((a NAND (a NAND b)) NAND ((a NAND b) NAND b)) as explained below: Where  denotes logical NAND operation. This equation reveals that to compute desired multiplication result, the logical NAND operation can be used instead of logical XOR operation. Compared to the conventional equation, this method can significantly improve hardware complexity. Figure 4(b) describes the details of the proposed formula as a flowchart.

Proposed bit-serial PB Multiplier Design
The architecture of proposed sequential PB multiplier in Figure 2 consists of two main blocks G and H, two m-bit registers, and a shift left (SL) block. Assume that the field polynomials to be multiplied are A and B, and field irreducible polynomial is f. All these three polynomials A; B, and f, using their vector representations. So the operands are considered as a m-bit vector for multiplier architecture. Block G computes the module reduction of equation (5) and block H performs a summation of partial products that can be seen in equation (5). The left-side m-bit register (Reg1) is initially loaded with operand A, and the left-side m-bit register (Reg2) is initialized to zero which stores the summation of previous reduction and m-bit partial product P K during K th cycle. At the first clock, the most significant bit of the operand B (bm-1) enters block H to be multiplied with operand A, likewise the remaining bits of B will enter serially in order to the accumulation of partial products result can be carried out. SL block computes the term P (k-1) x i which is the left shift P (k-1) , i times which just consists of hardware-free re-wiring. The final multiplication result is given by Reg2 after m clock cycles. Figure 3 shows the hardware details for the proposed design. Both blocks are composed of four levels of logic gates which is made of an array of m NAND gates to implement the NAND operations suggested in equation (10).

Hardware and Time Complexities Comparison
In this section, we obtain the space and time complexities of the proposed parallel output bit-serial (POBS) PB multiplier. The area and delay complexities of the proposed design can be readily calculated from Figure 1. Table 1 compares the proposed design with some of its competitors [4], [6], [9], [12], [15], [19] in terms of area (AND gates, NAND gates, XOR gates, multiplexers, and flip-flops), latency, and critical path delay.

Proposition1:
For the finite field GF(2 m ) generated by the general irreducible f(x), the proposed POBS PB multiplier (Figure 2) requires 2m register, 2m AND gates and 8m NAND gates. Figure 2) contains three levels of an array of m-NAND gates and one level of an array of m-AND gates. Moreover, the proposed architecture needs 2 registers to keeps m-bit operand A and the final m-bit product result respectively. Hence, the proposed multiplier architecture requires 8m NAND gates, 2m AND gates and 2m registers. 10

Author Names
The time complexities of the multiplier are determined by three factors: latency, the number of clock cycles required for whole multiplication, and the critical path delay. Let us define the latency as the number of clock cycles needed that the first bit of the output is available. Based on this definition, it is clear that the latency of the proposed SOBS multiplier is m clock cycles. The critical path delay, which is the longest path from the registers to the output C; determines the maximum operating frequency.

Proof:
The critical path delay of each block is determined by the maximum delay from input to output. As it can be observed from Figure 1 each block has three levels that consist of 3-input NAND gates, 2-input NAND gates and 2-input AND gates. So the delay of each block is max(TA , TN)+ 2TN . Therefore, the total delay to generate C is equal to 2TA + 4TN. Besides the multiplication of two m-bit elements is computed over m iterations. Therefore, the resultant latency is m clock cycles and the proof is complete.
From the results shown in Table 1, we cannot claim that our proposed multiplier is the best available sequential multiplier, but it has comparable results with the best sequential one [19]. Although the overall structure of the two architectures might seem similar, there is one important difference between them which is the implementation of the proposed PB multiplier without utilizing XOR gates. In other words, in terms of hardware complexity, the proposed architecture came in the second place which is around %11.53 more than [19]. It can be observed from Table 1 that multipliers [4], [6] have more number of registers and long latency compared to the proposed multiplier. It may also be observed that the multipliers [9], [12] require less latency and more hardware compared to the proposed multiplier. Moreover, the multiplier [15] has more hardware at the advantage of less critical path in comparison to our proposed architecture. Table 1. Comparison of space and time complexities between different finite field multipliers To enable a better comparison, the area and delay complexities of the multipliers listed in Table 1 have been calculated and tabulated in Table 2 as a case study. National Institute of Standards and Technology (NIST) has recommended five binary fields for Elliptic curve cryptographic applications: (GF 163 ), (GF 233 ), (GF 283 ), (GF 409 ), and (GF 571 ) (Hsu et al., 1998). In all the calculations made for Table 2, the field size was selected as m = 163. It should be noted that CMOS065LP CMOS VLSI technology-based standard cell library from STMicroelectronics is used to estimate area and time complexities of the gates. The area complexities in terms of the number of transistors for a 2-input NAND gate, a 3-input NAND gate, a 2-input AND gate, a 2-input XOR gate, a 2-input XNOR gate, a 2-1 MUX and a D flip-flop with set/reset capabilities are 4, 8, 6, 12, 12, 12, and 30 transistors, respectively. Moreover, the delays of a 2-input NAND gate, a 2-input AND gate, a 2-input XOR gate, a 2-input XNOR gate, a 2-1 MUX and a D flip flop with set/reset are 0.02, 0.03, 0.04, 0.04, 0.03, and 0.08 ns, respectively. It is observed that the proposed multiplier requires the least number of transistors as compared to the majority of multipliers available in the literature. In the design of digit-level finite field multipliers, there is always a tradeoff between delay and area costs as two important design factors and reducing one of them generally results in an increase in the other one. To achieve a fair comparison, the areadelay product of the multipliers has been calculated and listed in the rightmost column of Table 2. As can be seen, the proposed architecture shows much lower transistor counts than all the existing multipliers listed in Table 2 except the multiplier [19]. The space complexity of proposed multiplier is 99.91%, 97.97%, 75.50%, 21.25% and 17.46% lower than the multipliers [12], [4], [9], [6], [15] respectively. Furthermore, in comparison with multipliers [12, [4], [9] the proposed architecture offers 99.89%, and 96.02%, 82.26% areadelay improvement (ADP). As seen from this table, the proposed SOBS multiplier has the lowest hardware complexity at the expense of longer critical path and more delay.   [19]. On the other hand, the total transistor requirements for circuit implementations of the architectures in [12], [4] would grow exponentially when the order of the irreducible polynomial increase. For better understanding, Figure 4 depicts the result of this

FPGA Implementation Results
The proposed multiplier and the multipliers in [6] and [9] are modelled using VHDL for ) 2 ( 163 GF and then simulated and synthesized using Xilinx ISE 14.7 to verify the functionality. The synthesized netlist is implemented on a Xilinx Virtex-7 (XC7VX1140TFLG1930-1) FPGA prototype board. The delay, area, power consumption, ADP (area-delay product) and PDP (power-delay product), (at 66.67MHz frequency) obtained from the synthesis results are tabulated in Table 4. In this table, the power consumption is estimated using the X power Xilinx ISE 14.7. It can be seen that the proposed design involves nearly 93% less area-delay product (ADP) and 69.25% less power-delay product (PDP) compared with the existing structure of [9]. It can also be observed from implementation results that the proposed multiplier implementation achieves 76.66% reduction in area-delay product (ADP) and 69.61% reduction in powerdelay product (PDP) compared to the sequential multiplier [6]. Hence, the FPGA implementation results obtained from the proposed multiplier validate hardware complexity, area-delay product (ADP) and power-delay product (PDP) complexity advantage over the multipliers listed in Table 4 which can be useful in situations where space complexity and saving energy are more relevant than time complexity such as image sensors and IoT edge-devices.

Conclusion
We proposed a low complexity serial-in parallel-out multiplication scheme over generic field polynomials for the elements of ) 2 ( m GF , based on the PB representation. With combining the applied recursive formula of [14] and this study, an area-efficient architecture has been obtained that shows it is possible to design SPB bit parallel multipliers with logical NAND gate for the five binary fields recommended by NIST which can lead to regularity and modularity of VLSI implementation of finite field multipliers. It should also be noted that in our implementation no XOR gates are required. The proved complexity analysis of the proposed multiplier in this paper, suggests that its space complexity is as good as or possibly better to other existing well known techniques in the literature which is desirable in constrained applications, such as smart cards, IoT devices, and implantable medical devices.