Spectral Logic and Its Applications for the Design of Digital Devices

CHAPTER 3

CALCULATION OF SPECTRAL TRANSFORMS

Efficient calculations of spectral transforms are very important for their practical applications. The efficiency is expressed in terms of

1. Space required to store functions that will be transformed, results of intermediate calculations, and their spectra, and
2. Time to perform the calculations, which is usually expressed through the number of required arithmetical operations, often reduced to the number of additions and multiplications, while the time for some auxiliary manipulations with data, as for instance various reordering, is neglected.

This chapter discusses methods for calculation of spectra and autocorrelations for different transforms and uses different data structures to represent the functions processed.

Methods presented in this chapter have been developed for calculations with a single processor.

Efficient techniques for calcuation of spectral transforms with multiprocessors and interconnection networks can be found in References (295, 304, and 475).

3.1 CALCULATION OF WALSH SPECTRA

Henceforth, Walsh spectra will be used extensively as a working tool in solution of analysis and synthesis problems for network implementations of Boolean functions. We shall, therefore, devote some attention to methods for their efficient computation in terms of space and time.

We first consider an effective algorithm for construction of the Walsh spectrum and estimate its complexity. This algorithm is similar to the analogous algorithm used ...