A survey on the orthogonal expansion of threshold functions.

Abstract

The classification and study of the structure of switching functions and their realizations/have received considerable attention in the past ten years. They were studied under various names such as the coordinate representation (13), the discrete Fourier transform (3), the Rademacher - Walsh expansion (7, 16) and the orthogonal expansion (2) of the functions. A concise survey on this field is presented in the first part of this work. The last part of the work is to apply these theories for the testing and realizing method of threshold functions. The (n+1) Chow parameters can uniquely characterize a threshold function of n variables. If we extend the number of Chow parameters to 2n with each representing the number of vertices in certain subcube, which is represented by a Boolean product of uncomplemented variables only, and if we arrange them in groups with each group having subcubes of the same dimension, then an augmented vector can be constructed. Such a vector will uniquely characterize the corresponding function and this can be developed for testing and realization of threshold functions. Without loss of generalities, we confine us to positive prime functions. A set of positive weights is first assigned to the variables. Their magnitudes will be in descending order. The components in the second group of the augmented vector corresponding to the number of vertices in the (n-2) - subcubes are listed in a table. In the t