High-Level Synthesis of Finite-Field Arithmetic Circuits Using Abstract Algebra
Date Issued
2011
Date
2011
Author(s)
Chen, Bing-Yuan
Abstract
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%.
Subjects
finite field
arithmetic circuit
fixed-point datapath
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-R98943148-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):5cbcc1218de0f2449d967c78cc1666a0