High-Level Synthesis of Finite-Field Arithmetic Circuits Using Abstract Algebra

In high-level hardware synthesis, circuit datapaths are often expressed by polynomials in fixed-point arithmetic. Interestingly the intrinsic boundedness of hardware
resources, rather than a limitation, is exploitable for circuit optimization. The data overflow (out-of-bounds) problems can be handled in different ways, for example,
treating them using exceptions, congruences (modulo some positive integer), etc.
Congruences under di erent moduli impose different algebraic structures. When the modulus is in the form of 2^n for some positive integer n, a polynomial can be
seen as a ring. On the other hand, when the modulus is a prime number, a polynomial can be seen as a finite field. While the former received recent attention and progress, the later was relatively not well explored. This thesis is concerned with datapath optimization in the latter algebraic structure, and intends to compare the optimalities under the two di erent algebraic structures for possible design space exploration. The main results include
(1) A simplification algorithm for single-output polynomials using unity polynomials.
(2) An optimization algorithm for multiple-output polynomials based on common expression extraction.
(3) A bracketing method to reduce the number of multiplication operations.
Experimental results show that the area generated by our method is averagely 34.2% smaller than the Horner Form. Regarding the comparison with [1], the area is improved by 29.8%.