An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of x/sup v/ mod m for arbitrary integers x, y, and m represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m<2/sup n/ and 0/spl les/Ix, y

An efficient initial approximation method for multiplicative division and square root is proposed. It is a modification of the piecewise linear approximation. The multiplication and the addition required for the linear approximation are replaced by only one multiplication with a slight modification of the operand. The same accuracy is achieved. The modification of the operand requires only a bit-wise inversion and a one-bit shift, and can be implemented by a very simple circuit. One clock cycle may be saved, because the addition is removed. The required table size is also reduced, because only one coefficient instead of two has to be stored.

An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of "x/sup y/ mod m" for arbitrary integers x, y and m. Represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m>

Efficient initial approximations and fast converging algorithms are important to achieve the desired precision faster at lower hardware cost in multiplicative division and square root. In this paper, a new initial approximation method for division, an accelerated higher order converging division algorithm, and a new square root algorithm are proposed. They are all suitable for implementation on an arithmetic unit where one multiply-accumulate operation, can be executed in one cycle. In the case of division, the combination of our initial approximation method and our converging algorithm, enables a single iteration of the converging algorithm to produce double-precision quotients. Our new square root algorithm can form, double-precision square roots faster using smaller look-up tables than the Newton-Raphson method.>

BDD-based approaches cannot handle some arithmetic functions such as multiplication efficiently, while Binary Moment Diagrams proposed by Bryant and Chen (1994) provide compact representations for those functions. They reported a BMD-based polynomial-time algorithm for verifying multipliers. This approach requires high-level information such as specifications to subcomponents. This paper presents a new technique called backward construction which can construct BMDs directly from circuit descriptions without any high-level information. The experiments show that the computation time for verifying for n-bit multipliers is approximately n/sup 4/. We have successfully verified 64-bit multipliers of several type in 3-6 hours with 46 Mbyte of memory on SPARCstation 10/51. This result outperforms previous BDD-based approaches for verifying multipliers.

We propose a fault simulation technique for multiple faults based on a deductive fault simulation method. The main difficulty in the development of a technique for multiple fault simulation is handling a very large number of multiple faults. Conventional deductive simulation using Linear lists to store fault sets is not appropriate for such large sets of multiple faults. Our approach to this problem is to represent sets of multiple faults by Boolean functions. We assign a distinct code word to each multiple fault and represent the fault by a minterm corresponding to its code word. Then, set operations in deductive simulation are replaced by logic operations. As an internal representation of fault sets, we use shared binary decision diagrams. The method of coding multiple faults is a key to efficient simulation. We propose a coding method called FNT coding. We also propose a fault dropping method, called prime fault dropping, which is used efficiently with our multiple fault simulation technique. Experimental results show that our technique effectively handles multiple faults at significantly lower computation cost.>

The paper presents an efficient method for manipulating very large shared binary decision diagrams (SBDDs) which are too large to be stored within main memory. In contrast that the conventional depth-first algorithm causes random access of memory, the proposed method is intended to cause sequential access of memory. The main idea of our method is level-by-level manipulation of shared quasi-reduced BDD's (SQBDD's) upon a breadth-first algorithm. A garbage collection algorithm based on sliding type compaction is also introduced in order to reduce page faults in succeeding manipulation. We implemented and evaluated the proposed method on the workstation Sun SPARC Station 10 and 64 Mbyte main memory and a 1 Gbyte hard disk drive. As a result it took only 5.6 h to obtain an SQBDD of more than 12 million nodes, which represents all the primary outputs of a 15-bit multiplier, from its circuit description. If we use the conventional SBDD manipulator instead, it is estimated that it would take about 1900 h.

Radix-2 and radix-4 modular multiplication hardware algorithms are proposed. Numbers are represented in a redundant representation and modular additions are performed without carry propagation. Serial-parallel modular multipliers based on them have a regular cellular array structure with a bit slice feature suitable for VLSI implementation. They are efficient especially in applications, such as an RSA cryptosystem, where modular multiplications are performed iteratively.>

Article Probabilistic CTSS: analysis of timing error probability in asynchronous logic circuits Share on Authors: Yutaka Deguchi Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile , Nagisa Ishiura Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile , Shuzo Yajima Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 650–655https://doi.org/10.1145/127601.127745Published:01 June 1991 7citation160DownloadsMetricsTotal Citations7Total Downloads160Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Boolean function manipulators based on Shared Binary Decision Diagrams (SBDD'S) =e utilized efficiently in various applications such as design verification.We propose a high-speed algorithm of manipulating SBDD'S, which can be used with a vector supercomputer effectively.This proposed algorithm is implement ed and evaluated on the vector supercomput er HI-TAC S-820/80.The vector acceleration ratio obtained is 14.3 in the best case. 1

The authors present a novel exact algorithm and gradual improvement methods for minimizing binary decision diagrams (BDDs). In the exact minimization algorithm, the optimum order is searched by the exchanges of variables of BDDs based on the framework of the algorithm of S.J. Friedman and K.J. Supowit (1990). The use of the BDD representation of a given function and intermediate functions makes it possible to produce pruning into the method, which drastically reduces the computation cost. The authors succeeded in minimizing a 17-variable function by the use of the BDD representation of intermediate functions and the introduction of pruning. They also propose a greedy method and a simulated annealing method based on exchanges of two arbitrary variables, and a greedy method based on exchanges of adjacent m variables for m=3 and 4.>

The authors propose a novel fault simulation technique for multiple faults. In order to handle a large number of multiple faults, sets of multiple faults are represented by Boolean functions, in which shared binary decision diagrams (BDDs) are used as an internal representation of Boolean functions. The authors also propose a fault dropping method, prime fault dropping, which is used efficiently to execute multiple fault simulation. The authors have succeeded in simulating 39 million double faults of a circuit of 2300 gates with about 20 Mbyte storage.>

Proposes two redundant CORDIC (coordinate rotation digital computer) methods with a constant scale factor for sine and cosine computation, called the double rotation method and the correcting rotation method. In both methods, the CORDIC is accelerated by the use of a redundant binary number representation, as in the previously proposed redundant CORDIC. In the proposed methods, since the number of rotation-extensions performed for each angle is a constant, the scale factor is a constant independent of the operand. Hence, one does not need to calculate the scale factor during the computation, and can make a more efficient sine and cosine generator than that based on the previous redundant CORDIC.>

In this paper we propose a new timing verification technique named coded time-symbolic simulation, CTSS. We are concerned with simulation of logic circuits consisting of gates whose delay is specified only by its minimum and maximum values. We encode the cases of possible delay values of each gate by binary values and simulate all the possible combinations of the delay values by means of symbolic simulation. This simulation technique can deal with logic circuits containing feedback loops as well as combinational circuits. We implemented an efficient simulator by using a shared binary decision diagram (SBDD) as an internal representation of Boolean functions. We also propose novel techniques of analyzing the results of CTSS.

This paper describes a new behavioral model of hardware, named NES (Nondeterministic Event Sequence) model, which was developed for the purpose of defining formal semantics of the gate level and the register transfer level hardware description languages. The NES model is a generalization of the event driven simulation, and can be a basis of synthesis and verification as well as simulation. We introduce basic concepts, formal definition, and a description method of the NES model.

The efficiency of Boolean function manipulation depends on the form of representation of Boolean functions. Binary Decision Diagrams (BDD's) are graph representations proposed by Akers and Bryant. BDD's have some properties which can be used to enable efficient Boolean function manipulation.

An approach to accelerating fault simulation using a vector super computer is described and the zero-delay, two-valued fault simulation of gate-level combinational circuits is discussed. As a vector processor oriented simulation technique, an algorithm was developed that is based on the parallel fault simulation technique. In the technique, fault simulation can be accelerated (given that enough vector lengths can be obtained) to a maximum of 20 times faster using vector operations of a currently available vector computer by extending the processing unit from one word to multiple words. However, when fault simulation to generate or to evaluate test patterns is performed, enough vector length is not obtained or the computation time increases if large vector length is attempted because detected faults are dropped. In order to address the problems, a dynamic, two-dimensional, parallel fault simulation technique is proposed. In this technique, large vector length is obtained by utilizing both fault and pattern parallelism, and fault dropping is efficiently used to adjusting the two parallelism factors complementarily from pass to pass. The computation time is further reduced by combining this technique with selective tracing under the notion of multiple fault propagation. The experiments on the FACOM vector processor show that the simulation speed is accelerated by 10 to about 15 times through vectorization.>

As a new approach for timing verification of logic circuits, we propose a new concept of time-symbolic simulation. While a conventional symbolic simulator treats signal values as logical expressions, a time-symbolic simulator treats time as algebraic expressions. In this paper, we describe algorithms for time-symbolic simulation, and its application to hazard detection and verification of asynchronous sequential circuits.

An on-line error-detectable high-speed multiplier is described. It is based on the multiplication algorithm which we have previously proposed. In the algorithm, the redundant binary representation each of whose digits is 0, 1, or -1 is used. The multiplier consists of an input encoder, a multiplication block, and an error checker. The input encoder encodes each primary input bit into the 1-out-of-2 code. The multiplication block is designed by means of the three-rail logic. The three-rail logic is a logic design technique in which three mutually exclusive conditions calculated in a circuit are encoded in 1-out-of-3 code and the circuit is designed to be inverter-free. The error checker is a totally self-checking two-rail checker and produces a bit pair as an error indicator. The multiplier can perform n-bit multiplication in a time proportional to log2n and has a regular cellular array structure suitable for VLSI implementation. Furthermore, we can detect any error caused by unidirectional stuck-at faults on gate output lines in normal operation by observing the error indicator. Many errors caused by other faults can be also detected. We can develop various on-line error-detectable high-speed arithmetic circuits using the redundant binary representation and the three-rail logic.

In this paper, we propose logic simulation techniques using vector processors, or supercomputers with pipeline architecture, as a new approach to accelerating simulation speed. In order to use vector processors efficiently, we have to tune up the coding scheme or the basic algorithms to be suitable for vector processing. We developed three types of new simulation techniques for vector processing, which are dedicated for (1) zero-delay simulation of combinational circuits, (2) zero-delay simulation of synchronous sequential circuits, and (3) simulation with delay consideration. The first two are based on the compiler-driven method and the last on the event-driven method. We implemented logic simulators based on the above techniques on the FACOM VP-100 and VP-200 at Kyoto University and on the HITAC S-810/20 at the University of Tokyo. The maximum performance is about 7.7 x 10 /sup 9/ gate-evaluations per second for combinational circuit simulation, 1.4 x 10 /sup 9/ gate-evaluations per second for sequential circuit simulation (on the VP-200), and 230 x 10 /sup 3/ events per second for timing simulation (on the S-810/20). These results are comparable to the performance of hardware simulation engines. Moreover, our techniques are so straightforward that we can implement them on most of the recent vector processors without serious modifications

A high-speed VLSI multiplication algorithm internally using redundant binary representation is proposed. In n bit binary integer multiplication, n partial products are first generated and then added up pairwise by means of a binary tree of redundant binary adders. Since parallel addition of two n-digit redundant binary numbers can be performed in a constant time independent of n without carry propagation, n bit multiplication can be performed in a time proportional to log2 n. The computation time is almost the same as that by a multiplier with a Wallace tree, in which three partial products will be converted into two, in contrast to our two-to-one conversion, and is much shorter than that by an array multiplier for longer operands. The number of computation elements of an n bit multiplier based on the algorithm is proportional to n2. It is almost the same as those of conventional ones. Furthermore, since the multiplier has a regular cellular array structure similar to an array multiplier, it is suitable for VLSI implementation. Thus, the multiplier is excellent in both computation speed and regularity in layout. It can be implemented on a VLSI chip with an area proportional to n2 log2 n. The algorithm can be directly applied to both unsigned and 2's complement binary integer multiplication.

An Interactive Simulation System (ISS) is presented. ISS is an integrated interactive CAD system for logic design, and is configurated “module oriented” to support structured logic design. An Interactive Simulator (IS) is used for design verification. A designer can control simulation steps interactively in IS, and he can find design errors early using a good interactive interface. A Structured Hardware Design Language (SHDL) is used to describe logic designs.

In distributed database systems, the cost to process a query is mainly determined by the amount of communication. Semi-join is a very useful tool to reduce the cost of joins in such systems. There are, however, queries called cyclic ones which cannot be processed by semi-joins only. In this paper the concept of generalized semi-joins is introduced to solve such a problem. To handle an arbitrary cyclic query, first a spanning tree is selected in the corresponding query graph and then generalized semi-joins are applied in the order determined by the tree. Processing of cyclic queries, however, requires more communication cost than processing of tree queries, since in the former case we need to transmit attribute values which are not required in the latter case. A procedure to reduce the communication cost of such additional data is developed, which will make the generalized semi-join based procedures practical.

We propose a new parallel sorting scheme, called the parallel enumeration sorting scheme, which is suitable for VLSI implementation. This scheme can be introduced to conventional computer systems without changing their architecture. In this scheme, sorting is divided into two stages, the ordering process and the rearranging one. The latter can be efficiently performed by central processing units or intelligent memory devices. For implementations of the ordering process by VLSI technology, we design a new hardware algorithm of parallel enumeration sorting circuits whose processing time is linearly proportional to the number of data for sorting. Data are serially transmitted between the sorting circuit and memory devices and the total communication between them is minimized. The basic structure used in the algorithm is called a bus connected cellular array structure with pipeline and parallel processing. The circuit consists of a linear array of one type of simple cell and two buses connecting all cells for efficient global communications in the circuit. The sorting circuit is simple, regular and small enough for realization by today's VLSI technology. We discuss several applications of the sorting circuit and evaluate its performance.

This correspondence describes new two-stage data compression algorithms of Kanji character patterns digitized on the hexagonal mesh. One third of the pattern elements are stored, and an additional small amount of data is used to correct effors in the recovered pattern. A data reduction of 60 percent has been achieved.

In this paper, we mainly discuss the semantic aspects of functional and multivalued dependencies in order to choose a better logical design of a relational database. We clarify the differences between a conceptual design and a logical design of a relational database. For example, a multivalued dependency does not always capture a conceptual dependency such that a data element semantically determines a set of other data elements. Moreover, some transitively specified multivalued dependencies are shown to often impose a semantically unnatural constraint. A sufficient condition for these multivalued dependencies to hold in a natural sense is provided. A mixed design approach of a conceptual and a logical designs is introduced, in which each design approach is compensated for its deficiency by the other one. Some generalization of a relational model is also suggested to handle some interface problems between a logical design and a conceptual design, such as a null value problem and an entity identification problem.

In the database field, the requirement of high level facilities for retrieval/update operations is now increasing rapidly. Our approach from the relational database point of view for contribution to this problem is to provide 1) efficient processing of relational retrieval/ update operations, and 2) a high level user interface. In order to achieve this goal, a new concept concerning "abstracted characteristics" is presented. Abstracted characteristics are defined to be characteristics abstracted from sets of tuples in relations stored in the database. A classification of abstracted characteristics is presented. Functional dependencies, which play an important role in relational database design, and time-dependent functional dependencies are pointed out to be useful in processing retrieval/update operations. Some important applications of abstracted characteristics are discussed. Among them: 1) efficient processing of retrieval/update operations, 2) powerful view update checking facilities, 3) providing some rough meanings of null responses and 4) a high level user interface.

As a method for greatly reducing power dissipation in logic networks, we propose some logic organization techniques for logic networks. By such techniques, their power dissipation is to be minimized under certain input conditions, or the average power dissipation in the whole network should be minimized. A logic network in which these problems are taken into account will be called a power minimized logic circuit (PML).

This paper shows that 1) there exist at least four types of binary-input binary-output maximum-memory n-state machines for any n; 2) there exist binary-input ternary-output maximum output -memory n-state machines for any n; and 3) there exists a binary- input binary-output maximum output-memory n-state machine for n≤5.

Abstract—As an approach to clarifying the basic properties of threshold logic, the completely monotonic function is investigated. Its testing procedure, functional form, etc., are discussed by using a new concept, mutual monotonicity.

Abstract—The concept of mutual monotonicity developed in the previous paper[1] is applied to the compound synthesis of an arbitrary logic function by a combination of completely monotonic functions or in most cases by threshold functions.

Abstract—A model of autonomous logic nets composed of n threshold elements is presented and several properties of a single threshold element are generalized to this model. The number of these nets is shown to be 2kn³(½≤k≤l) for completely specified machines. The capacity of the net is defined and conjectured to be 2, similar to the case of a single threshold element. P and NPN classifications of the machines are proposed and applied to the enumeration of all periodic sequences of length 2n(n≤4) realizable by this net. The state assignment problem of the net is also treated. The existence of transition diagrams which cannot be realized by this model for any state assignment, or of those that can be realized for any state assignment, is shown, and it turns out that almost all completely specified machines belong to the former class when n is sufficiently large. Considering the synthesis of a net, an application of learning procedure is also discussed and it is pointed out that only periodic sequences of length 2" can be learned automatically.

Threshold functions are a class of Boolean Functions which have been studied for several years under different names such as majority functions, linearly separable functions, and linear input functions.