Spectral Logic and Its Applications for the Design of Digital Devices

CHAPTER 5

ANALYSIS AND OPTIMIZATION OF LOGIC FUNCTIONS

In this chapter, we study spectral methods for solving the decision problems for some important classes of logical functions¹ and also develop spectral methods for solving optimization problems in the algebra of logic (including the linearization and approximation of systems of logical functions). We will also present in this chapter spectral methods for serial and parallel decomposition of combinatorial networks.

A special section will be devoted to the analysis of spectral complexity of Boolean functions, deriving bounds for the number of nonzero coefficients in their orthogonal expansions. The main tool throughout the chapter will be the Walsh transform, since this is a transform defined in terms of two-valued ±1 functions.

It is assumed that, when appropriate, the logic values 0 and 1 are also interpreted as the corresponding integers. In this sense, the Walsh transform is compatible with the switching functions to which it is applied.

5.1 SPECTRAL ANALYSIS OF BOOLEAN FUNCTIONS

The problem of the analysis of Boolean functions (BF), or switching functions, is to decide whether a given function belongs to some standard class (linear, self-dual, threshold, among other functions). In other words, we determine whether a given function possesses any of the properties characterizing these classes of switching functions. The reason for the importance of the corresponding decision problems is that standard methods of network synthesis ...