Best Paper Award

  A multivariable function from a finite field to itself is called a multi-valued logic function, which has long been used for logic circuit design and switching theory. Here, "multi-valued" implies that the size of the finite field is larger than two. If the finite field consists of two elements of 0 and 1, that is a classical one called a ‘Boolean function.’ As an example of a multi-valued logic function, there is a multivariable polynomial with coefficients in the finite field. Actually, it is known that these two agree. This fact is usually called ‘algebraic normal form’ or ‘Reed-Muller expansion.’ It is also known that correspondence between multi-valued logic functions and multivariable polynomials makes the product of two functions correspond to the product of two polynomials. This fact is usually called the ‘convolution theorem of logic functions’ and is analogous to that of discrete or continuous functions with Fourier transforms.
   In this paper, we have generalized the above results to multivariable functions from a Cartesian product of semigroups in the finite field to the finite field. We have shown a new convolution theorem as an isomorphism of a quotient ring in the theory of abstract algebra. Moreover, we have applied this generalized convolution theorem to speedup of the product of two multivariable polynomials. This is done by transforming the polynomials to the functions, multiplying them, and inversely transforming the multiplied function to the polynomial. In order to prove that this method which seems to be a detour route is speeding up, it is necessary to estimate the computational complexity of transforms in both directions. In this paper, we convert it to the case of one variable, find the complexity by mathematical induction, and prove that the order of the complexity is reduced. Furthermore, we have shown the relation with the tensor product and that with the Kronecker product of the matrix, as well as the topic of being linked to the error-correcting code through matrix transposition, with numerical examples.
   Although this paper deals with the problem of classical logical functions, the result obtained is the most generalized one to date and it has value in the sense that we expanded the class of functions which can be handled. Several methods in this paper, including simple formulation, proofs, and evaluation of computational complexity, cannot be found elsewhere and are highly original. It is also an accomplishment that we connected these facts which were regarded as independent, such as the convolution theorem, the quotient ring, and the high speed multiplication. Based on the above description, this paper deserves an IEICE Best Paper Award.