A generalized architecture is presented for reconfigurable m-ary tree structures, where m is any integer >1. The approach is based on a generalized multistage interconnection network (MIN), which is a generalization of the augmented shuffle-exchange MIN introduce by the authors previously (1990) for obtaining reconfigurable binary tree structures. The generalized architecture with m/sup k/ processing elements or nodes (where k is any integer >1) is implemented with a k-stage MIN. A single control code issued to the MIN establishes a distinct m-ary tree configuration among the nodes. The favorable features of the architecture include fast reconfiguration, simplified hardware in the nodes and the MIN, and simple routing control. The reconfigurability of the architecture is proved, and the results of the analysis are utilized to provide a procedure to synthesize the m-ary tree configuration that is generated for any given control code. Considerations for implementing the switching elements of the MIN are discussed.>

A novel approach to the design of a reconfigurable tree architecture is presented. The architecture is implemented with an augmented shuffle-exchange multistage interconnection network and is capable of assuming N distinct binary tree configurations, where N is the number of processing elements (PEs) in the system. The novel features of the architecture include fast switching from one configuration to another, simplified hardware in the PEs and the switching network, and simple routing control.>

In recent correspondence, L. Ye-Wei and J. Wei (see ibid., vol.C-35, p.930-1 (1986)) have shown two counterexamples that contradict theorems four and five of a paper by J.E. Smith (see ibid., vol.C-28, p.845-53 (1979)). In his reply, Smith (see ibid., vol.C-35, p.931 (1986)) stated an additional condition under which the theorems hold good. The commenters provide a counterexample that contradicts Smith's modified theorem five. They provide another counterexample that contradicts theorem three of Smith's original paper. In his reply, Smith corrects an error in his treatment.>

The computer-aided minimization procedure (CAMP) algorithm is a minterm-based computer-aided procedure for the minimization of single Boolean functions. Major modifications of the algorithm are presented. They allow it always to obtain the minimum cover covering all the uncovered minterms, both adjacent and distant, in the normal mode. In the branch mode, the solution may not be minimum in many cases. However, a new theorem introduced in the algorithm allows it to switch to the branch mode only when it is inevitable. The improved algorithm also has a mechanism which ensures the largest possible dimension for each cube of the solution.>

A computer-aided design procedure for the minimization of multiple-output Boolean functions as encountered in the synthesis of VLSI logic circuits is presented. A fast technique for the determination of essential prime cubes without generating all the prime cubes is among the salient features of the algorithm. A new class of selective prime cubes called valid selective prime cubes is described. This class of prime cubes has proved to be a very powerful tool inasmuch as it guides the algorithm to the minimal set of selective prime cubes while encountering either an independent chain or an interconnected chain of cyclic prime cubes. In many cases, this avoids branching, which is computationally an expensive operation. The algorithm does not generate either the complement or all the prime cubes of the functions. Therefore, it is well suited to minimizing functions with a large complement size and/or a very high number of prime cubes. The algorithm has been implemented in Pascal and evaluated using a large number of programmable logic arrays (PLAs) including those of the Berkeley PLA test set. Results of comparison with ESPRESSO II and McBOOLE indicate that the program produces absolute minimal solutions in most of the cases and near-minimal solutions in a few others.>

The problem of determining a minimal number of control inputs for converting a programmable logic array (PLA) with undetectable faults to crosspoint-irredundant PLA for testing has been formulated as a nonstandard set covering problem. By representing subsets of sets as cubes, this problem has been reformulated as familiar problems. It is noted that this result has significance because a crosspoint-irredundant PLA can be converted to a completely testable PLA in a straightforward fashion, thus achieving very good fault coverage and easy testability.>

In a reconfigurable binary tree structure controlled by a shift register with variable bias (SRVB), the root of a particular configuration is a function of the bias applied to the structure. This letter proves two new theorems for the derivation of formulas for the calculation of the root for a given bias. These are simpler than those obtained by Kartashev and Kartashev [1]. Consequently, both the software and hardware implementations are achieved in minimal time and hardware. The letter also presents these implementations in the form of a program and two circuits, one acting as a serial, and the other as a parallel, bias-to-root converter.

This paper describes the salient features of CAMP, a Computer Aided Minimization Procedure for single Boolean functions. The procedure is a divide and conquer algorithm, in which the essential prime implicants are first found, and then the best cover among the selective prime implicants are chosen. A significant feature of the algorithm is that the selection of the most suitable selective prime implicant to cover a minterm is based upon the information associated with the degree and direction of adjacency of the minterm itself. The generation of the complement of the function is not a requirement of the algorithm. The procedure has been implemented in a 250 line Fortran program. For shallow functions consisting mainly of essential prime implicants (EPI's) and a few selective prime implicants (SPI's), CAMP produces the exact or near minimal sum of product form. For dense functions consisting of a large number of interconnected cyclic SPI chains, a good minimal solution is obtained by minimizing the complementary function.

This paper describes two logic minimization algorithms. CAMP (Computer Aided Minimization Procedure) minimizes single functions. The minterms are covered either by essential prime implicants or by selective prime implicants. The two types of prime implicants are determined one at a time thus completely avoiding the computationally expensive covering problem. The adjacency of a minterm, that depends upon the proximity of this minterm with respect to other minterms on the Karnaugh map, guides the determination of prime implicants. This procedure is nonheuristic and has proved to be very efficient for large number of input variables. The multiple output minimization (MOM) algorithm generates the product terms with maximum sharing between the output functions. In addition to using adjacency, this procedure is also guided by the frequency with which a minterm is used by the functions. Examples show the performance of this algorithm to be equal or better than many other minimization procedures.

The microcommands constituting the microprogram of the control memory of a microprogrammed processor can be partitioned into a number of disjoint sets. Some of these sets are then encoded to minimize the word width of the ROM storing the microprogram. A further reduction in the width of the ROM words can be achieved by a technique known as bit steering where one or more bits are shared by two or more sets of microcommands. These sets are called the steerable sets. This correspondence presents a simple method for the detection and encoding of steerable sets. It has been shown that the concurrency matrix of two steerable sets exhibits definite patterns of clusters which can be easily recognized. A relation "connection" has been defined which helps in the detection of three-set steerability. Once steerable sets are identified, their encoding becomes a straightforward procedure following the location of the identifying clusters on the concurrency matrix or matrices.

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the algorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

In this paper, the validity of single fault assumption in deriving diagnostic test sets is examined with respect to crosspoint faults in programmable logic arrays (PLA's). The control input procedure developed here can be used to convert PLA's having undetectable crosspoint faults to crosspoint-irredundant PLA's for testing purposes. All crosspoints will be testable in crosspoint-irredundant PLA's. The control inputs are used as extra variables during testing. They are maintained at logic 1 during normal operation. A useful heuristic for obtaining a near-minimal number of control inputs is suggested. Expressions for calculating bounds on the number of control inputs have also been obtained.

This paper describes a new method for reducing the wordwidth in the control memory of a microprogrammed digital computer. The method requires the computation of maximal compatibility classes (MCC's) of only a subset of subcommands unlike the existing methods in which MCCs of the entire set of subcommands are used. An algorithm has been given to obtain a near minimal solution by appropriate grouping of the MCC's. The necessary modification of the algorithm has also been presented to deal with large size microprograms.

Presents an algorithm for microprogram control memory width minimization with the bit steering technique. The necessary and sufficient conditions to detect the steerability of two mutually exclusive sets of microcommands are established. The algorithm encodes the microcommands of the sets with a bit steering common part and also extends the theory to multiple (more than two) sets of microcommands.

This paper recasts the multiple data path assignment problem solved by Torng and Wilhelm by the dynamic programming method [1] into a minimal covering problem following a switching theoretic approach. The concept of bus compatibility for the data transfers is used to obtain the various ways of interconnecting the circuit modules with the minimum number of buses that allow concurrent data transfers. These have been called the feasible solutions of the problem. The minimal cost solutions are obtained by assigning weights to the bus-compatible sets present in the feasible solutions. Minimization of the cost of the solution by increasing the number of buses is also discussed.

A relationship between 2-monotonicity and 2-asummability has been established and thereby a fast method for testing 2-asummability of switching functions derived. The approach is based on the fact that only a particular type of 2-sums need be examined for 2-asummability testing of 2-monotonic switching functions. These 2-sums are those which contain more than five 1's. 2-asummability testing for these 2-sums can be easily done by using the authors' technique.

Simple algorithms have been developed to generate pairs of minterms forming a given 2-sum and thereby to test 2-asummability of switching functions. The 2-asummability testing procedure can be easily implemented on the computer. Since 2-asummability is a necessary and sufficient condition for a switching function of upto eight variables to be linearly separable (LS), it can be used for testing LS switching functions of upto eight variables.

In the above paper1Yang has expounded a concept of supersession and has claimed that superseded compatibles can be ignored in the process of minimizing incompletely specified sequential machines (ISSM). In this correspondence, we present a counterexample whose minimal solution must include a superseded compatible and not the superseding compatible. As a consequence of this it is evident that Yang's theory lacks generality.

A simple yet efficient method for the minimization of incompletely specified sequential machines (ISSM's) is proposed. Precise theorems are developed, as a consequence of which several compatibles can be deleted from consideration at the very first stage in the search for a minimal closed cover. Thus, the computational work is significantly reduced. Initial cardinality of the minimal closed cover is further reduced by a consideration of the maximal compatibles (MC's) only; as a result the method converges to the solution faster than the existing procedures. "Rank" of a compatible is defined. It is shown that ordering the compatibles, in accordance with their rank, reduces the number of comparisons to be made in the search for exclusion of compatibles. The new method is simple, systematic, and programmable. It does not involve any heuristics or intuitive procedures. For small- and medium-sized machines, it can be used for hand computation as well. For one of the illustrative examples used in this paper, 30 out of 40 compatibles can be ignored in accordance with the proposed rules and the remaining 10 compatibles only need be considered for obtaining a minimal solution.

A simple procedure for the state minimization of an incompletely specified sequential machine whose number of internal states is not very large is presented. It introduces the concept of a compatibility graph from which the set of maximal compatibles of the machine can be very conveniently derived. Primary and secondary implication trees associated with each maximal compatible are then constructed. The minimal state machine covering the incompletely specified machine is then obtained from these implication trees.

A modification in the algorithm for the detection of totally symmetric functions as expounded by the author in an earlier note1is presented here. The modified algorithm takes care of a limited number of functions that escape detection by the previous method.

The Quine–McCluskey method of minimizing a Boolean function gives all the prime implicants, from which the essential terms are selected by one or more cover tables known as the prime implicant tables. This note describes a tabular method where the essential prime implicants are selected during the process of forming the combination tables, and other essential terms are selected from what have been described in the note as chains of selective prime implicants. Consequently, the need for successive prime implicant tables is eliminated.

This paper shows how a "unity-ratio" totally sym-metric function can be identified without any further decomposition. The identification is carried out by writing the given function in its ordered partitioned tabular form. The method is general, straightforward, and programmable on a digital computer.