Petrify is a tool for (1) manipulating concurrent specifications and (2) synthesis and optimization of asynchronous control circuits. Given a Petri Net (PN), a Signal Transition Graph (STG), or a Transition System (TS) it (1) generates another PN or STG which is simpler than the original description and (2) produces an optimized net-list of an asynchronous controller in the target gate library while preserving the specified input-output behavior. An ability of back-annotating to the specification level helps the designer to control the design process. For transforming a specification petrify performs a token flow analysis of the initial PN and produces a transition system (TS). In the initial TS, all transitions with the same label are considered as one event. The TS is then transformed and transitions relabeled to fulfill the conditions required to obtain a safe irredundant PN. For synthesis of an asynchronous circuit petrify performs state assignment by solving the Complete State Coding problem. State assignment is coupled with logic minimization and speed-independent technology mapping to a target library. The final net-list is guaranteed to be speed-independent, i.e., hazard-free under any distribution of gate delays and multiple input changes satisfying the initial specification. The tool has been used for synthesis of PNs and PNs composition, synthesis and re-synthesis of asynchronous controllers and can be also applied in areas related with the analysis of concurrent programs. This paper provides an overview of petrify and the theory behind its main functions.

The currying of term rewriting systems (TRSs) is a transformation of TRSs from a functional form to an applicative form. We have already introduced an order-sorted version of currying and proved that the compatibility and confluence of order-sorted TRSs were preserved by currying. In this paper, we focus on a key property of TRSs, completeness. We first show some proofs omitted in Ref. [3]. Then, we prove that the SN (strongly normalizing) property, which corresponds to termination of a program, is preserved by currying. Finally, we prove that the completeness of compatible order-sorted TRSs is preserved by currying.

Regenerative Pass-transistor Logic (RPL), a modular dual-rail circuit technique for high speed logic design that gives reasonably low power consumption, was discussed in previous work [1]. RPL combines advantages of both the compact size of CPL and the full voltage-swing of DPL, and gives reasonably high performance concerning both speed and power consumption. In this paper, the application and design technique of RPL on larger logic circuits and systems are reported. Parallel adders and Booth multipliers with different sizes and structures are used as examples to evaluate the functionality of the RPL gates and full adder. In addition, there is less signal skew in RPL circuits than in conventional CPL circuits when an arrangement of single-rail to dual-rail signal conversion is performed. And, RPL is found to be useful in design of high speed and high density parallel adders and multipliers.

In this paper, a novel completion prediction adder is proposed. The basic concept is to predict the completion of an adder by investigating the inputs and generate completion signal for synchronization according to the completion prediction signal. This scheme greatly enhances the performance of an adder in both aspects of delay and hardware cost. Furthermore, the relative performance enhancement compared with representative synchronous adders increases as the word length of an adder becomes longer. For example, the delay-hardware product of SCPA for a 64-bit adder is 45.1% and 42.7% of those of binary carry look-ahead adder (BCLA) and binary tree carry look-ahead adder (BTCLA), respectively.

In the data path circuits of asynchronous systems, logical faults may first manifest as undetectable, transient wrong codewords, in spite of encoding the inputs and the outputs and proper organization which enables the faults to be propagated to the primary outputs in the form of non-codewords. Due to this, the conventional methods of concurrent error detection (CED) using the logic (voltage) monitoring is not effective. In this paper, we suggest a mixed-signal approach to achieve CED for a class of asynchronous circuits, known as self-timed circuits. First, we show that it is impossible to guarantee the CED using logic monitoring of the primary outputs in spite of proper encoding and organization of self-timed circuits. Then, we discuss different manifestations of single stuck-at faults occurring during normal operation in these circuits. Finally, we present the feasibility of achieving CED using a built-in current sensor (BICS) along with encoding techniques.

An ultra low voltage CMOS pass-gate logic using body-bias controlled SOI MOSFETs has been developed. The logic is composed of gate-body connected SOI pass-gates and a CMOS buffer with the body-bias controlled by the complementary double-rail input. The full-adder using the proposed logic improved the lowest operation voltage by 27%, compared with the SOI CPL (Complementary Pass-Gate Logic). For a 16 16 bit multiplier, the power-delay product achieved 70 pJ (including 50 pF I/O) at 0.5 V power supply, which was more than 1 order of magnitude improvement over the bulk CPL.

In this paper we describe the implementation of complex architectures using a general design approach for two-phase asynchronous systems. This fundamental approach, called Event Controlled Systems, can be used to widely extend the utility of two phase systems. We describe solutions that we have developed that dramatically improve the performance of static and dynamic-logic asynchronous pipelines, and briefly describe a complex microprocessor designed using ECS.

We are working on an algorithm to optimize the logic circuits that can be realized on the super fine-grain parallel processing architecture. As a part of this work, we have developed an inverter reduction algorithm. This algorithm is based on modeling logic circuits as dynamical systems. We implement the algorithm in the PARTHENON system, which is the high level synthesis system developed in NTT's laboratories, and evaluate it using ISCAS85 benchmarks. We also compare the results with both the existing algorithm of PARTHENON and the algorithm of Jain and Bryant.

We apply a novel methodology, based on statecharts, to the design of large scale asynchronous systems. The design is specified at multiple levels, simulated, animated, and compiled into synthesizable VHDL code by using the ExpressV-HDL CAD tool. We add a validation sub-system to chech correct operation. ExpressV-HDL is originally synchronous, but we employ it for asynchronous design by avoiding any design dependence on the clock, and simulating with fast clock and on-line delays. The tool is demonstrated through a simple FSM. The synthesized synchronous circuit can be converted into an asynchronous one. Some results of a post-synthesis conversion example are given.

The reallocation problem is defined as determining whether products can be moved from their current storehouses to their target storehouses in a number of moves that is less than or equal to a given number. This problem is defined simply and has many practical applications. We previously presented necessary and sufficient conditions whether an instance of the reallocation problem is feasible, as well as a linear-time algorithm that determines whether aall products can be moved, when the volume of the products is restricted to one. However, a linear-time algorithm that generates the order of moving the products has not been reported yet. Such an algorithm is proposed in this paper. We have also previously proved that the reallocation problem is NP-complete in the strong sense when the volume of the products is not restricted and the products have evacuation storehouses show that the reallocation problem is NP-complete in the strong sense even when none of the products has evacuation storehouses.

An overview of known completion-detection methods is given and their advantages and drawbacks are briefly discussed. A relatively new class of single-rail completion-detection techniques is considered in more detail and dimulation results based on adder implementations are presented. A variant of a single-rail technique, which has the advantage of glitch-suppression and robust operation, is introduced. Simulation results are provided, based on a physical layout of the circuit with extracted parasitics.

We developed a 1200 dots-per-inch light emitting diode array (1200 dpi LED array) chip using a GaAs0.8 P0.2 epitaxial substrate for the first time. One LED array chip consists of 256 LEDs. In general, LED arrays are fabricated by vapor-phase zinc diffusion. From the viewpoint that shallow junctions should be formed to fabricate a very high-density LED array, solid-phase diffusion seems to be more suitable. We fabricated the LED array using selectively-masked solid-phase zinc diffusion, and the diffusion depth was controlled at 1 µm. The diffusion depth was uniform under the diffusion window. The ratio of the length of lateral diffusion to the diffusion depth was about 1.7. These features imply that Zn diffusion was well controlled. In the Zn diffusion, the carrier concentration in the Zn diffusion region was high enough and the sheet resistance of the diffusion region with a diffusion depth of 1 µm was low enough to obtain a sufficient level of emitted light power. The results of performance tests showed that the characteristics of the LED array chip are satisfactory for application in optical printer print heads, because of the array's highly-resolved near-field pattern characteristic, ample emitted light power, low emitted-light-power deviation, and long life.

Heavy-ion-induced soft errors (single event upset) in submicron silicon-on-insulator (SOI) MOSFETs under space environmental conditions are studied over the temperature range of 100-400 K using three-dimensional device simulator with full-temperature models. The temperature dependence of the drain collected charge is examined in detail when a heavy-ion strikes the gate center perpendicularly. At very low temperatures, SOI MOSFETs have very high immunity to the heavy-ion-induced soft errors. In particular, alpha-particle-induced soft errors hardly occur at temperatures below 200 K. As the temperature increases, the collected charge shows a marked rate of increase. The problem of single event upset in SOI MOSFETs becomes more serious with increasing working temperature. This is because the induced bipolar mechanism is a main factor to cause charge collection in SOI MOSFETs and the bipolar current increases exponentially with increasing temperature. At room and high temperatures, the drain collected charge is strongly dependent on channel length and SOI film thickness.

Periodic solutions of slow-fast systems called "canards," "ducks," or "lost solutions" are examined in a second order autonomous system. A characteristic feature of the canard is that the solution very slowly moves along the negative resistance of the slow curve. This feature comes from that the solution moves on or very close to a curve which is called slow manifolds or "rivers." To say reversely, solutions which move very close to the river are canards, this gives a heuristic definition of the canard. In this paper, the generation mechanism of the canard is examined using a piecewise linear system in which the cubic function is replaced by piecewise linear functions with three or four segments. Firstly, we pick out the rough characteristic feature of the vector field of the original nonlinear system with the cubic function. Then, using a piecewise linear model with three segments, it is shown that the slow manifold corresponding to the less eigenvalue of two positive real ones is the river in the segment which has the negative resistance. However, it is also shown that canards are never generated in the three segments piecewise linear model because of the existence of the "nodal type" invariant manifolds in the segment. In order to generate the canard, we propose a four segments piecewise linear model in which the property of the equilibrium point is an unstable focus.

Let L be any class of languages, L' be a class of languages which is closed under λ-free homomorphisms, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L1 in L' over ΣXk such that L=Red(L1)Σ*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ*Σ*, a Dyck language D over Γ, and a language L2 in L' over Γ such that L=h(DL2). We also give an application of this result.

We introduce two probabilistic algorithms to determine the motion parameters of a planar shape without knowing a priori the point-to-point correspondences. If the target is limited to rigid objects, an Euclidean transformation can be expressed as a linear equation with six parameters, i.e. two translational parameters and four rotational parameters (the axis of rotation and the rotational speed about the axis). These parameters can be determined by applying the randomized Hough transform. One remarkable feature of our algorithms is that the calculations of the translation and rotation parameters are performed by using points randomly selected from two image frames that are acquired at different times. The estimation of rotation parameters is done using one of two approaches, which we call the triangle search and the polygon search algorithms respectively. Both methods focus on the intersection points of a boundary of the 2D shape and the circles whose centers are located at the shape's centroid and whose radii are generated randomly. The triangle search algorithm randomly selects three different intersection points in each image, such that they form congruent triangles, and then estimates the rotation parameter using these two triangles. However, the polygon search algorithm employs all the intersection points in each image, i.e. all the intersection points in the two image frames form two polygons, and then estimates the rotation parameter with aid of the vertices of these two polygons.

The concept of a basis matrix is introduced to investigate the trade-off between complexity and storage for multiplication in a finite field. The effect on the storage requirements of using polynomial and normal bases for element representation is also considered.

This paper describes the design and evaluation of fully scannable embedded memory arrays. A memory array, such as a register file, is made scannable by adding a small auxiliary circuit including a counter and multiplexers. Plural memory arrays can be chained into a single scan path along with ordinary flip-flops. Detailed configuration and implementation of the scannable CMOS and bipolar LCML register file macros are discussed. The overhead ratio of the CMOS register file macro with 16-word by 16-bit results in an 8.6% transistor count and a 6.4% die area. The access time overhaead is 7.8% and the set-up time increases by about 50ps. Bipolar LCML register file macros have been applied to gate array LSIs which have successfully achieved average stuck-at fault coverage of 99.2%.

The key circuit technologies for future giga-bit/low voltage operating high performance SOI-DRAM is described. Emphasis is made especially on the considerations for ways to overcome floating-body effects in order to obtain very long static/dynamic data retention time. A new scheme called a super body synchronous sensing scheme is proposed for low voltage operation at 1 V.

In this paper, we extend the circuit partitioning algorithm which we have proposed for multi-FPGA systems and present a new algorithm in which the delay of each critical signal path is within a specified upper bound imposed on it. The core of the presented algorithm is recursive bipartitioning of a circuit. The bipartitioning procedure consists of three stages: 0) detection of critical paths; 1) bipartitioning of a set of primary inputs and outputs; and 2) bipartitioning of a set of logic-blocks. In 0), the algorithm computes the lower bounds of delays for paths with path delay constraints and detects the critical paths based on the difference between the lower and upper bound dynamically in every bipartitioning procedure. The delays of the critical paths are reduced with higher priority. In 1), the algorithm attempts to assign the primary inputs and outputs on each critical path to one chip so that the critical path does not cross between chips. Finally in 2), the algorithm not only decreases the number of crossings between chips but also assigns the logic-blocks on each critical path to one chip by exploiting a network flow technique. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it resolves almost all path delay constraints with maintaining the maximum number of required I/O blocks per chip small compared with conventional alogorithms.