AT2-Optimal Galois Field Multiplier for VLSI

Finite or Galois field arithmetic is central in many encoding and decoding procedures for error detecting and error correcting codes. In this paper, VLSI designs for Galois field multipliers are presented. For every prime p, these designs (for GF(pn) multiplication in standard representation) are asymptotically optimal with respect to area A and time T. In fact, the lower bound AT2 = ω(n2) is matched for every computation time T in the range [ω(log n), O[formula omitted]]. Analogous results hold for variable primes p too. The designs are based on the DFT on a structure similar to Fermat rings. For p = 2 the DFT uses 3'th instead of 2'th roots of unity.