We demonstrate circuits that generate set and integer partitions on a set S of n objects at a rate of one per clock. Partitions are ways to group elements of a set together and have been extensively studied by researchers in algorithm design and theory. We offer two versions of a hardware set partition generator. In the first, partitions are produced in lexicographical order in response to successive clock pulses. In the second, an index input determines the set partition produced. Such circuits are useful in the hardware implementation of the optimum distribution of tasks to processors. We show circuits for integer partitions as well. Our circuits are combinational. For large n , they can have a large delay. However, one can easily pipeline them to produce one partition per clock period. We show (1) analytical and (2) experimental time/complexity results that quantify the efficiency of our designs. For example, our results show that a hardware set partition generator running on a 100MHz FPGA produces partitions at a rate that is approximately 10 times the rate of a software implementation on a processor running at 2.26GHz.

We show that there is significant benefit to using a reconfigurable computer to enumerate bent Boolean functions for cryptographic applications. Bent functions are rare, and the only known way to generate all bent functions is by a sieve technique in which many prospective functions are tested. The speed-up achieved depends on the number of variables n; for n = 8, we show that the reconfigurable computer achieves better than a 60,000× speed-up over a conventional computer. Further, we introduce the transeunt triangle as a means to reduce the number of functions that must be considered. For n = 6, this reduction is better than 500,000,000 to 1. Previously, the transeunt triangle had been used only in the design of exclusive OR logic circuits; it converts a truth table to the algebraic normal form. However, this fact has never been proven rigorously, and that shortcoming is removed in this paper. Our proof provides a practical benefit; it yields a new realization of the transeunt triangle that has less complexity and delay. Finally, we show computational results from a reconfigurable computer.

This paper proposes a design method and programmable architectures for numerical function generators (NFGs) of two-variable functions. To realize a two-variable function in hardware, we partition a given domain of the given function into segments, and approximate the function by a polynomial in each segment. This paper introduces two planar segmentation algorithms that efficiently partition a domain of a two-variable function. This paper also introduces two architectures that can realize a wide range of two-variable functions. Our architectures allow a systematic design of two-variable functions. FPGA implementation results show that, for a complicated function, our NFG achieves 58% of memory size and 39% of delay time of a circuit designed using one-variable NFGs.

Two-variable numerical functions are widely used in various applications, such as computer graphics and digital signal processing. Fast and compact hardware implementations are required. This paper introduces the bilinear interpolation method to produce fast and compact numerical function generators (NFGs) for two-variable functions. This paper also introduces a design method for symmetric two-variable functions. This method can reduce the memory size needed for symmetric functions by nearly half with small speed penalty. Experimental results show that the bilinear interpolation method can significantly reduce the memory size needed for two-variable functions, and the speed of NFGs based on the bilinear method is comparable to that of NFGs based on tangent plane approximation. For a complicated function, our NFG is faster and more compact than a circuit designed using a one-variable NFG.

In this paper, we introduce the edge-valued binary decision diagram (EVBDD) to reduce the memory and delay in numerical function generators (NFGs). An NFG realizes a function, such as a trigonometric, logarithmic, square root, or reciprocal function, in hardware. NFGs are important in, for example, digital signal applications, where high speed and accuracy are necessary. We use the EVBDD to produce a fast and compact segment index encoder (SIE) that is a key component in our NFG. We compare our approach with NFG designs based on multi-terminal BDDs (MTBDDs), and show that the EVBDD produces SIEs that have, on average, only 7% of the memory and 40% of the delay of those designed using MTBDDs. Therefore, our NFGs based on EVBDDs have, on average, only 38% of the memory and 59% of the delay of NFGs based on MTBDDs.

This paper focuses on numerical function generators (NFGs) based on k-th order polynomial approximations. We show that increasing the polynomial order k reduces significantly the NFG's memory size. However, larger k requires more logic elements and multipliers. To quantify this tradeoff, we introduce the FPGA utilization measure, and then determine the optimum polynomial order k. Experimental results show that: 1) for low accuracies (up to 17 bits), 1st order polynomial approximations produce the most efficient implementations; and 2) for higher accuracies (18 to 24 bits), 2nd-order polynomial approximations produce the most efficient implementations.

This paper proposes an architecture and a synthesis method for high-speed computation of fixed-point numerical functions such as trigonometric, logarithmic, sigmoidal, square root, and combinations of these functions. Our architecture is based on the lookup table (LUT) cascade, which results in a significant reduction in circuit complexity compared to traditional approaches. This is suitable for automatic synthesis and we show a synthesis method that converts a Matlab-like specification into an LUT cascade design. Experimental results show the efficiency of our approach as implemented on a field-programmable gate array (FPGA)

This paper presents architecture and a synthesis method for programmable numerical function generators (NFGs) for trigonometric, logarithmic, square root, and reciprocal functions. Our NFG partitions a given domain of the function into nonuniform segments using a LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Implementation results on an FPGA show that: 1) our NFGs require only 4% of the memory needed by NFGs based on the linear approximation with nonuniform segmentation; and 2) our NFGs require only 22% of the memory needed by NFGs based on the 5th-order approximation with uniform segmentation. Our automatic synthesis system generates such compact NFGs quickly.

This paper presents an architecture and a synthesis method for programmable numerical function generators of trigonometric functions, logarithm functions, square root, reciprocal, etc. Our architecture uses an LUT (look-up table) cascade as the segment index encoder, compactly realizes various numerical functions, and is suitable for automatic synthesis. We have developed a synthesis system that converts MATLAB-like specification into HDL code. We propose and compare three architectures implemented as a FPGA (field-programmable gate array). Experimental results show the efficiency of our architecture and synthesis system.

The traditional problem in binary decision diagrams (BDDs) has been to minimize the number of nodes since this reduces the memory needed to store the BDD. Recently, a new problem has emerged: minimizing the average path length (APL). APL is a measure of the time needed to evaluate the function by applying a sequence of variable values. It is of special significance when BDDs are used in simulation and design verification. A main result of this paper is that the APL for benchmark functions is typically much smaller than for random functions. That is, for the set of all functions, we show that the average APL is close to the maximum path length, whereas benchmark functions show a remarkably small APL. Surprisingly, however, typical functions do not achieve the absolute maximum APL. We show that the parity functions are unique in having that distinction. We show that the APL of a BDD can vary considerably with variable ordering. We derive the APL for various functions, including the AND, OR, threshold, Achilles' heel, and certain arithmetic functions. We show that the unate cascade functions uniquely achieve the absolute minimum APL.

A function f is AND bi-decomposable if it can be written as f (X1,X2) = h1(X1)h2(X2). In this case, a sum-of-products expression (SOP) for f is obtained from minimum SOPs (MSOP) for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for f. We show an incompletely specified function of n(n-1) variables that requires at most n products in an MSOP, while 2(n-1) products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for f . We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.

In an irredundant sum-of-products expression (ISOP), each product is a prime implicant (Pl) and no product can be deleted without changing the function. Among the ISOPs for some function f, a worst ISOP (WSOP) is an ISOP with the largest number of Pls and a minimum ISOP (MSOP) is one with the smallest number. We show a class of functions for which the Minato-Morreale ISOP algorithm produces WSOPs. Since the ratio of the size of the WSOP to the size of the MSOP is arbitrarily large when it, the number of variables, is unbounded, the Minato-Morreale algorithm can produce results that are very far from minimum. We present a class of multiple-output functions whose WSOP size is also much larger than its MSOP size. For a set of benchmark functions, we show the distribution of ISOPs to the number of Pls. Among this set are functions where the MSOPs have almost as many Pls as do the WSOPs. These functions are known to be easy to minimize. Also, there are benchmark functions where the fraction of ISOPs that are MSOPs is small and MSOPs have many fewer Pls than the WSOPs. Such functions are known to be hard to minimize. For one class of functions, we show that the fraction of ISOPs that are MSOPs approaches 0 as n approaches infinity, suggesting that such functions are hard to minimize.

The above paper finds an optimal fixed-polarity Reed-Muller expansion of an n-variable totally symmetric function using an OFDD-based algorithm that requires O(n/sup 7/) time and O(n/sup 6/) storage space. However, an algorithm based on Suprun's transient triangles requires only O(n/sup 3/) time and O(n/sup 2/) storage space. An implementation of this algorithm yields computation times lower by several orders of magnitude.

We derive the average and worst case number of nodes in decision diagrams of r-valued symmetric functions of n variables. We show that, for large n, both numbers approach n/sup r//rl. For binary decision diagrams (r=2), we compute the distribution of the number of functions on n variables with a specified number of nodes. Subclasses of symmetric functions appear as features in this distribution. For example, voting functions are noted as having an average of n/sup 2//6 nodes, for large n, compared to n/sup 2//2, for general binary symmetric functions.

We analyze the computational complexity of the cost-table approach to designing multiple-valued logic circuits that is applicable to I/sup 2/L, CCDs, current-mode CMOS, and RTDs. We show that this approach is NP-complete. An efficient algorithm is shown for finding the exact minimal realization of a given function by a given cost-table.

A heuristic is proposed for finding minimal cost-tables, for use in the design of multiple-valued logic circuits. It is an iterative approach, in which a good table of size t is composed of a good table of size t-1, etc. The authors analyze its performance, comparing it with three other heuristics. The importance of finding good cost-tables is demonstrated by an analysis that shows there is a wide variation in both cost-table performance and in the performance of heuristics for generating cost-tables. A study is made of linear cost, a general cost function of which two previously studied cost functions are special cases. It is shown that the minimal cost-table using one of the (infinitely many) linear cost functions is identical to a minimal cost-table using any other linear cost function. Two additional results on cost-table design are given.>

The performance of various heuristic algorithms for minimizing realizations of multiple-valued functions by the charge-coupled device (CCD) and CMOS programmable logic arrays (PLAs) of H.G. Kerkhoff and J.T. Butler (1986) and J.G. Samson (1988), respectively, is analyzed. The functions realized by the PLAs are in sum-of products form, where the sum is ordinary addition truncated to the highest logic value and the product represents the MIN operation of functions of the input variables that are the interval literal operations. Three heuristics, proposed by G. Pomper and J.A. Armstrong (1981), P.W. Besslich (1986), and G.W. Dueck and D.M. Miller (1987), are compared over sets of random and random-symmetric functions. An exact minimization method that is a tree search using backtracking is described. A reduction in the search space is achieved by considering constrained implicant sets and by eliminating some implicants altogether. Even with this improvement, the time required for exact minimization is extremely high when compared to all three heuristics. The case involving only prime implicants is considered, and it is shown that such implicants have marginal value compared to constrained implicant sets. The basis of comparison is the average number of product terms.>

In the cost-table approach to logic design, a function is realized as a combination of functions from a table. The objective of the synthesis is to find the least-cost realization, where realization cost is the sum of the costs of the functions used plus the cost of combining them. The costs of cost-table functions are defined by a cost function which represents chip area, speed, power dissipation, or a combination of these factors. It is shown that there is an arbitrarily large set S of cost functions which yield the same cost-table. This implies, for example, that every minimal realization of any function over a cost function in S is independent of the actual cost function used. With any cost function, if the cost of combining functions from a cost-table F is sufficiently large, the realizations behave as if the cost function belonged to S. That is, any minimal realization of a function f, using cost-table F, is one of the minimal realizations of f using F and a cost function in S. The interpretation of these results is that there are not as many distinct cost-tables as originally thought.>

A multiprocessing system is t/s-diagnosable if all faulty processors can be identified to within s processors, provided there are no more than t faulty processors. A characterization theorem of S. Karunanithi and A.D. Friedman (1979) for t/s-diagnosability in certain special cases of systems called designs is extended to the entire class of D/sub 1,t'/(n) designs. It is shown that for large t, s is approximately t/sup 2//4t'. Furthermore, the minimum number of processors needed to attain a given diagnosability is derived. A multiprocessor system is sequentially t-diagnosable if at least one faulty processor can be identified provided there are no more than t faulty processors. A theorem by F. Preparata, G. Metze, and R. Chien (1967), giving a sufficient condition for sequential t-diagnosability in the single-loop system (a special case of designs), is extended to the entire class of D/sub 1,t'/(n) designs. It is shown that, for large t, approximately t/sup 2//4t' nodes are needed for a D/sub 1,t'/(n) design to be sequentially t-diagnosable.>

Upper and lower bounds are shown for the average number of product terms required in the minimal realization, as a function of the number of nonzero output values. The variance, in addition to the bounds, allows conclusions to be drawn about how PLA size determines the set of realizable functions. Although the bounds are most accurate when there are few nonzero values, they are adequate for analyzing commercially available PLAs. The analysis shows that, for all but one commercially available PLA, the number of nonzero values is a statistically meaningful criterion for determining whether or not a given function is likely to be realized.>

An analysis of structured flowcharts is presented, where size is measured by the number, n , of decision nodes (IF-THEN-ELSE and DO-WHILE nodes). For all classes of structured flowcharts considered, the number of charts is approximately, cn -3/2 γ n , for large n , where c >and γ are parameters that depend on the class. It is also shown that most large flowcharts consist of a short sequence of basic charts (IF-THEN-ELSE and DO-WHILE charts). The average length of such sequences is 2.5.

Expressions are derived for the average number of steps. required (speed) and the average number of fault-free units replaced (efficiency) when universal diagnosis algorithms are applied to systems of various degrees of interconnection (complexity). Specifically, two algorithms proposed by Smith [4] are considered. It is shown, for example, that there is a clear tradeoff between the two algorithms; one is much faster, while the other is more efficient.

Art algorithm is presented for assigning functmns to gates in a fanout-free network so that a gwen function is reahzed Since the method is tabular, ~t IS easily programmed As long as the gates used are symmetric and positive the synthesis technique can be tadored to the particular set of gates available, for example, AND, OR, and majority gates It is shown that the functions realized by such networks are a proper subset of the set of unate functions but not of threshold functions Also, ~t is shown that the fanout-free functions that are threshold realizable are exactly those reahzed by the cascade, a special case of the fanout-free network KEY WORDS AND PHRASES swItchmg funcuons, fanout, fanout-free functions, fanout-free networks, unate funcUons, threshold funcUons, posmve symmetnc funcUons, Chow parameters CR CATEGORIES.

Expressions are derived for the approximate number of functions realized by various n-variable fanout-free networks. Six recently studied networks are considered. It is shown that the relative number of functions realized by two networks for small and large n is quite different in certain cases.

The tandem network, a row-like interconnection of cells is described. Such networks are more general than the widely studied irredundant cascade, but less general than a universal network based on, for example, the Shannon decomposition. The analysis is facilitated by the introduction of three cell-network interconnections, whose functions are characterized by certain attributes of the partition matrix of the realized function. Partition matrices have been used to significant advantage in characterizing disjunctive decompositions. They are also important in the analysis of nondisjunctive decompositions, but their application is cumbersome in such cases. It is shown that certain nondisjunctive decompositions can be handled easily as operations on partition matrices. A counting technique is developed which shows that the number of functions realized by tandem networks is significantly larger than that realized by cascades. In addition, a synthesis technique is shown for constructing a tandem network to realize a given function.

Networks of two input-one output cells are described in which the cells are restricted to realize a subset of the 16 two-variable functions. The restriction, if appropriately chosen, will result in a network whose function set is the same as that of a network of identical structure in which each cell realizes all 16 functions. A restricted network is demonstrated which realizes exactly those functions realized by an irredundant disjunctive network which are dependent on all inputs. In addition, a restriction on cell set size is shown which produces the same functions realized by a general network in which all cells realize 16 functions. From this latter result, it can be concluded that 16 · 7c-1is an upper bound on the number of functions realizable by any network of c cells.

In this paper, the number of functions realized by certain networks of two-input one-output gates are presented. Two networks are considered; one is the disjunctive network, which is characterized by the restriction that each gate output and each network input connect to exactly one gate input. The other network, the cascade, is the special case of the disjunctive networks in which each gate has at least one input which connects to a network input. For both networks, a recursion relation is derived for the number of realized switching functions dependent on exactly k variables. Both expressions have been solved by computer for k up to 15. Also, expressions are derived for the number of functions realized by cascades and disjunctive networks of two-input one-output cells, where each cell realizes any of the 16 functions on two variables.

In this paper, one-output n-input combinatorial nondegenerate networks of cells are analyzed. The networks consist of one-output two-input cells that are universal in that they realize all 16 functions of the two-input variables. Such networks have a number of interesting properties, among which is the fact that if network N realizes F(x), it also realizes the dual function Fd(x).