Methods for detection of some properties of multiple-valued functions

Abstract

In the paper, methods are given for some symmetry properties: detection and functional decomposition of multiple-valued functions. Both methods are formulated using a matrix notation which enables the fast algorithms for their implementation to be disclosed. The problem of optimisation in logic design can be considered with respect to a number of different criteria. However, in general, all of them finally can be reduced to the minimisation of the cost and to the minimisation of the time. In a classical setting, these criteria are usually expressed by the number of components, or by the number of inputs in logical elements, and by the delay of signals in a logical network, i.e. by the number of levels in the network. The reduced price of electronic components, together with the advent of different ways of realisation of discrete functions (PLA, universal logic modules, ROM-realisation etc.) provide us with hardware capabilities of low cost and high performance. This implies a change in the optimisation criteria which now can be replaced by the requirements for reducing the size of the silicon area and for efficient testability. Also, these days, the optimisation problems in logic design are closely related to the minimisation of time and efforts, and hence the cost, needed for the implementation of the synthesis procedure, rather than with reducing the cost of hardware components. The parameters mentioned can be greatly reduced in cases where the realised discrete function possesses some characteristic properties. Therefore, the development of efficient methods for analysis of discrete functions is a very important task. In this paper we propose a method for symmetry detection and a method for functional decomposition of multiple-valued functions including Boolean functions as a particular example.