About Arithmetic Module Generator (AMG)
High-level Design Methodology for Integer/Galois-field Arithmetic Circuits for Embedded Systems
This project aims to establish a high-level design methodology for arithmetic circuits frequently used in embedded systems. We are studying a dedicated graph-based description for computer arithmetic algorithms, which is called Arithmetic Circuit Graph (ACG). The use of ACG allows us to perform (i) formal description of arithmetic algorithms including those using unconventional number systems (e.g., non-binary, redundant and Galois-field arithmetic), (ii) formal verification of described arithmetic algorithms by algebraic computations based on Groebner bases and polynomial reduction techniques, and (iii) translation of arithmetic algorithms to equivalent HDL (Hardware Description Language) codes.
Our project applys ACG to the development of a new type of arithmetic module generators consisting of I-AMG and GF-AMG. I-AMG can generate a variety of integer arithmetic circuits including two-operand adders, multi-operand adders, multipliers, constant-coefficient multipliers and multiply accumulators. GF-AMG can generate Matrovito and Massey-Omura multipliers based on a variety of Galois fields, using an extended version of ACG nameed GF-ACG. Each arithmetic module generated by both I-AMG and GF-AMG performs its function that are completely verified at the algorithm level.
This project inherited the ARITH project which was performed at Computer Structures Laboratory (Aoki Laboratory) in Tohoku University according to the transfer of researchers from 2019.
- Integer Arithmetic Module Generator based on ACG
- Galois-Field Arithmetic Module Generator based on GF-ACG
N. Homma et. al., "Formal design of arithmetic circuits based on arithmetic description language," IEICE Trans. on Fundamentals., Vol. E89-A, No. 12, pp. 3500-3509, December 2006.
Y. Watanabe et. al., "Arithmetic Circuit Verification Based on Symbolic Computer Algebra," IEICE Trans. on Fundamentals., Vol. E91-A, No. 10, pp. 3038-3046, October 2008.
N. Homma et. al., "A Formal Approach to Designing Cryptographic Processors Based on GF(2^m) Arithmetic Circuits," IEEE Trans. on IFS, Vol. 7, No. 1, pp. 3-13, February 2012.
R. Ueno et. al., "Automatic Generation System for Multiple-Valued Galois-Field Parallel Multipliers," IEICE Trans. on Information and Systems, Vol.E100-D, No.8, pp.1603-1610, August 2017.
This work has been supported by JSPS KAKENHI Grant No. 17H00729.