HARMONIC ANALYSIS OF SWITCHING FUNCTIONS

摘要: ABSTRACT This chapter is a self-contained development of abstract harmonic analysis applied to single-output combinational logic functions; linear algebra and elementary group theory are the only mathematical prerequisites. New synthesis techniques developed, groundwork laid for future extensions multiple output logic, sequential machines, real- or complex-valued functions binary arguments. Harmonic adds novel conceptual insights unifying principles, improved computational techniques, new measures complexity traditional approach switching theory. The first section summary chapter. Section II surveys classical Fourier transform properties introduces canonical expansion function as an n-dimensional over finite two-element field. two most important convolution theorem, which leads tests prime implicants disjunctive decompositions, spectrum invariance basic further theoretical developments technique called encoded input logic. III develops algorithm concurrently extracts detects decompositions function. Implicants both its complement detected simultaneously, “core” can be identified. not sensitive functional has been programmed commercial time-sharing system. IV restricted affine (RAG) whose elements, prototype transformations, encode arguments outputs functions. partitions space F all two-valued on Zn into 3, 8, 48 equivalence classes respectively n=3, 4, 5. Unique representatives identified each class when n=3 4 46 5-argument V applies tools problem large truth tables (many-input logic). A general multilevel approach, introduced compatible with large-scale-integrated circuit technology. Both conventional macrocellular newer microcellular array included special cases. Prototype encoding transformations used reduce imbedded normal form realization. Practical algorithms based analysis. realistic 6-argument example treated in detail. concludes list fundamental problems solutions would extend research presented herein.