Decomposition of Multi-Valued Functions,

MMath Thesis,

Department of Computer Science,

University of Waterloo, Waterloo, Ontario, Canada N2L 3G1,

August 1998.

(Supervised by J. A. Brzozowski)

Abstract

Decomposition of functions has been studied since the late 1950s; it was mainly

used in minimizing circuit designs for switching functions. Recently, decompositions

have been used in FPGA synthesis and other applications, and interest in this topic has

again increased. A commonly used method decomposes a function f(x_1,...,x_n) into

the form h(x_1,...,x_r,g(x_{r+1},...,x_n)), where both g and h are switching functions.

In this thesis, we study the decomposition of a very general form of functions,

called

functions where the outputs can take the value of any non-empty subset of an underlying

set E. We represent these functions in a compact cube notation using

set matrices

which are a generalization of partitions and set systems. We also give a survey of different decomposition methods, including the formalizations of some of these methods using blankets.