Effective algorithms exist for synthesizing symmetric functions and for "ordinary" nonsymmetric functions. However, the existing methods have difficulties when the functions are not symmetric but are "close" to being symmetric. We formulate a set of operations to decompose a function so that symmetric components can be created and utilized to simplify the function. These operations are collectively called symmetry reexpression, and we present theoretical and practical work for performing such operations. The optimal decomposition has exponential complexities; therefore, we seek algorithms to approximate the optimum. The resulting software package applies to arbitrary multilevel Boolean networks. For experimental functions constructed by taking cubes from otherwise symmetric, multiple-output benchmark functions, symmetry reexpression is beneficial when up to 40% of the cubes are removed.

An algorithm is offered for generating minimum-cost, two-level expressions for totally symmetric, complete switching functions. The algorithms discussed were programmed in TurboPascal (and TurboC) and executed on an IBM PS/2-80. Many symmetric switching functions of from 7 to 15 variables were minimized and the results validated against the original specifications of the functions. Run times varied from a tenth to tens of seconds and were heavily dependent on the size of the input array and the literals of symmetry.>

The authors offer extended algebraic operations and strategies for se in algebraic approaches. A novel cube/array representation that directly shows some legal expressional variations from a minimal expression written in the conventional three symbol (0, 1, x) representation is defined, along with certain operations on those cube/arrays. Conversions between the new and conventional representations are explained. Division methods are presented that are based on expressions like those used to describe algebraic division but use more operations of Boolean algebra. Factoring on the new representations is explained. A multilevel logic synthesis algorithm with a control strategy is presented and compared with published systems.>

Designs of totally symmetric functions provided by logic synthesis systems have on average more than twice as many literals as best designs, while the designs of nonsymmetric functions have on average 20% more literals. A simple, but effective, heuristic method for synthesizing symmetric functions that detects and takes advantage of symmetry and is based on classic disjoint decomposition theory is fully developed from basic definitions. Functions are realized as Boolean networks with cost measured as the literal count of factored expressions. Programs based on the method almost always produce the best designs known to the authors. Two strategies for accepting decompositions are explored. They do produce different results in a few cases: examples are presented to show that neither always produces best designs. These programs are proposed as preprocessors for a comprehensive synthesis system.>

Wislan is a language for describing computer hardware at the gate and functional levels of abstraction. After converting a WISLAN description to a gate table data structure, users interactively apply local transformations to that network to transform the gate network to a technology, meet technology limits, and optimize the network. A number of extensions to WISLAN and new, less-local transforms are reported. The transforms are made efficient via operations on array representations of switching functions. Conversion between gate table and array data structures is also efficient.

Existing techniques for finding minimum state covers of an incompletely specified sequential machine are streamlined to yield a single minimum cover with significantly less computation. The factor by which computation is reduced is directly proportional to the complexity of the machine.

Armstrong et al.[1] have shown how critical races and function hazards can be suppressed in asynchronous sequential circuits by using gate delays to advantage rather than introducing explicit delay elements, if certain delay assumptions are satisfied. This paper shows that the same techniques may be used to design circuits which will respond reliably to simultaneous changes of several input variables.

Factoring techniques are incorporated in computer-oriented algorithms for the synthesis of fan-in limited NAND switching networks. Tree networks with reduced gate count or levels of logic are sought. While example FORTRAN programs emphasize computer execution of the algorithms, they are also efficient for hand execution.

A digital system design language, DDL, has been described and shown to provide a concise yet precise means of specifying the organization and operation of digital systems, regardless of timing mode or hardware types, at various levels of detail [2]. This paper defines a series of tasks that transform any DDL document to Boolean and next-state equations from which a system may be implemented. Each task of the transformation produces another DDL description of a system which uses fewer features of the language.

An algorithm which reduces the number of gates and connections (diodes) in two-level, multiple-output combinational logic networks is presented and compared with conventional minimization procedures.

Abstract—Repetitious activity is assumed in randomly interconnected networks of elements with spacial and temporal summation of input excitation and exponentially decaying threshold and stimulation. Bounds on the period of that oscillatory activity are theoretically established, and verified by computer simulation. The dependency of such bounds on threshold and stimulation decay rates, number of inputs to each element, maximum and return values of threshold, the presence of inhibitory elements in a network, and the profile of network activity is shown.

Abstract—Successful design and manufacture of future digital systems will depend upon the availability of a suitable design language. A precise, concise language is presented which facilitates the specification of complex digital systems. The language 1) is independent of any particular technology, design procedure, machine organization, etc., 2) allows specification at different levels of detail from architecture to detailed Boolean equations, and 3) may be com- piled into manufacturing information. Its syntax and semantics per- mit documents with an organization which parallels the block struc- ture of the systems they specify.

Abstract—A computer-oriented algorithm for synthesizing combinational logic circuits from a collection of functionally packaged circuits is developed. The algorithm uses a hierarchy of "goals" in an iterative decision process in a manner similar to that employed by theorem proving and gamne playing programs. With each iteration a set of "tasks" finds the circuit package which satisfies the highest level goal while meeting circuit constraints.

Functionally packaged logic can only be effectively utilized if the totality of switching functions that each package is capable of providing is recognized. Theorems concerning, and algorithms operating on, multiple output switching functions (possibly with don't care conditions) in cubical array notation are presented that 1) detect partial symmetry and redundancy sets of input varibles, 2) determine the function generated by a package with some of its inputs tied to logical 1 or 0 or tied together, and 3) rapidly show equivalence between two functions using symmetry information. While manual execution of the algorithms is possible, they are computer oriented. Results from actual computer experimentation show their efficiency.

Because transistor NOR gates allow only a liitmed number of inputs, NOR equations must be factored before they can be implemented. An easily programmed algorithm is developed which rapidly generates a subset of factors, selects optimum factors, and indicates a realization for the factored equation based on the relation A ↓ B ↓ C ↓ D = [(A ↓ B) ↓] ↓ C ↓ D. A method for preventing excessive fan-out is also presented.