Hardware algorithms generated by GF-AMG

Galois-Field Arithmetic Module Generator (AMG) supports two types of hardware algorithms for parallel multipliers. In the following, we briefly describe the hardware algorithms that can be handled by GF-AMG.

• Multipliers
• Mastrovito multiplier
• Massey-Omura parallel multiplier
• References

Multipliers

Mastrovito multiplier

Mastrovito multiplier is a class of parallel multipliers over Galois fields based on polynomial basis representations. The polynomial basis of GF(p^m) is given as a vector (β^m-1,β^m-2, …, β⁰) . As an example, consider a Galois field GF(2⁸) obtained by an irreducible polynomial IP(x)=x⁸+x⁴+x³+x+1. When IP(β)=0, a vector (β⁷, β⁶, …, β⁰) is a polynomial basis. Figure 1 shows the architecture of Mastrovito multipliers handled in GF-ACG, which consists of Matrix generator and Matrix operator. The Matrix generator first generates a matrix determined by a reminder which is given by the division of multiplicand by polynomial basis. The Matrix operator then performs the multiplication of the multiplier (i.e., another input) and the generated matrix and finally produces the product. Such Mastrovito multipiler is known as a GF parallel multiplier with the minimal area cost.
> generate mastrovito multipliers

Massey-Omura parallel multiplier

Massey-Omura parallel multiplier is a class of parallel multipliers over Galois fields based on normal basis representations. The normal basis of GF(p^m) is given as a vector (α^pm-1, α^pm-2, …,α^p0), where α is the normal element of GF(p^m). As an example, consider a Galois field GF(2⁸) obtained by an irreducible polynomial IP(x)=x⁸+x⁴+x³+x+1. When IP(β)=0 and α=β⁵, a vector (α²⁷,α²⁶, …,α²⁰) is a normal basis. Figure 2 show the architecutre of Massey-Omura parallel multipliers handled in GF-ACG, which consist of Partial Product Generator (PPG) and Accumulator (ACC). The PPG stage first generates partial products from the multiplicand and multiplier in parallel. The ACC stage then performs multi-operand addition for all the generated partial products and produces the final product. Such GF multipliers based on normal basis representations are useful for constructing circuits including squaring operators such as exponentiation and inverse circuits.
> generate massey-omura parallel multipliers

References

1. A. Halbutogullari and C.K. Koc, "Mastrovito multiplier for general irreducible polynomials", IEEE Trans. Computers, Vol. 49, No. 5, pp. 503--518, May 2000.
2. A. Reyhani-Masoleh and M.A. Hasan, "A New Construction of Massey-Omura Parallel Multiplier over GF(2^m)", IEEE Trans. Computers, vol. 51, no. 5, pp. 511--520, May 2001.
3. R.C. Mullin, I.M. Onyszchuk, S.A, Vanstone, and R.M. Wilson, "Optimal Normal Basis in GF(pⁿ)", Discrete Applied Math, vol.~22, pp.~149--161, 1988/1989.