ANALYSIS OF SYNTHESIS OF MULTI-THRESHOLD LOGIC.
Abstract
The thesis treats a generalization of the concept of linearly-separable (single-threshold) Boolean functions, multi-threshold functions. Some invariance operations peculiar to the multi-threshold functions are shown to exist. Necessary and sufficient conditions of self-dual and self-complementary dual functions are obtained in terms of the multi-threshold weight threshold vector. In particular, self-dual and self-complementary dual functions are shown to be realizable by odd and even number of effective thresholds only. It is shown that an n + 1 variable self-dual and self-complementary dual can be generated from an n variable Boolean function. Such generation of self-dual and self-complementary dual functions are shown to correspond to the functional forms of self-dualization and self-complementary dualization of an n-variable Boolean function. An algorithm for the synthesis of multi-threshold threshold elements is presented. Instead of solving the set of linear inequalities, where the unknowns are the weights corresponding to the input variables, incremental weights are sought. The procedure reduces to that of resolving contradicting pairs of vertices by the incremental weights. The procedure is valid for linearly separable and non-linearly separable Boolean functions. For the synthesis of arbitrary Boolean functions with a network of single threshold elements, compound and cascade threshold element syntheses from the multi-threshold weight threshold vector are discussed. Finally, an improved tabulation of the multi-threshold weight threshold vectors on the 221 equivalence classes of four-variable Boolean functions under the NPN operation is included. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1967
- Accession Number
- AD0654193
Entities
People
- King Sun Fu
- W. C. W. Mow
Organizations
- Purdue University