Transforms and algorithms for spectral techniques in binary and multiple-valued logic

Abstract

Spectral representations of discrete functions have allowed development of powerful tools for many applications in digital logic design and image and signal processing. Through the investigation of their properties, they can be used to effectively solve many problems that are difficult to solve in the original sum of product representation based on the truth table. This thesis focuses on the development of spectral transforms for binary and multiple-valued functions, investigation of their properties, and algorithms for their efficient computation. Algorithms for calculation and optimization of fixed polarity Reed-Muller expansions for five-valued functions are presented. New linearly independent transforms for binary functions are introduced. Efficient algorithms for obtaining fixed polarity arithmetic expansions are developed for ternary and quaternary functions. Representations of ternary functions with linearly independent basis functions are discussed. The hardware computations and implementations of some of the discussed transforms are shown.