Implementation complexity of algorithms for optimization of galois field expressions for multiple-valued functions

Abstract

This paper discusses methods for efficient implementation of algorithms for determination of Fixed-polarity Galois field (FPGF) expressions for q-valued logic functions (q-prime). Calculations of coefficients in FPGF expressions can be most efficiently performed in terms of space and time, if conversion of an expression for a given polarity into the expression for another polarity is done along the so-called extended dual polarity route. However, there are many possible extended dual polarity routes which differ in the associated processing rules. The complexity of whatever software or hardware resources required for calculations of FPGF expressions depends on the number of different processing rules required along a route. In this paper, we introduce the notion of homogeneous extended dual polarity routes and show that calculations along these routes can be performed with a reduced number of processing rules required. Due to that, both hardware and software implementation of the procedure for determination of all possible FPGF expressions for a given function is considerably simplified.