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.

The performance of synchronous VLSI system is limited by the speed of the global clock which is further constrained by the clock skew. Self-timed design technique, based on the Muller model, improves performance by eliminating the global clock. In order to prevent hazard, a self-timed system should satisfy certain assumptions and timing constraints, therefore special cells are required. The novel Self-timed Cell Library is designed for 1.2µm CMOS technology which contains Muller C-elements, DCVSL circuits, latches and delay elements. It is very useful because: (1) It avoids any possible violations of the assumptions and timing constraints since all cells are custom designed; (2) It provides a fast and reliable model for self-timed system verification using either SPICE simulator or Verilog simulator; (3) It is flexible since it is compatible with an existing Standard Cell Library. In this paper, the library is described. Moreover, the simulated and measured cell characteristics are compared. Using the library, two [18] [81] matrix multipliers employing (1) DCVSL technique, and (2) micropipeline technique have been implemented as design examples and the results are compared. In addition, this paper also demonstrates the benefits of custom-layouted C-elements and a new way to realize delay element for micropipeline. The last but not least, two new HCCs are also proposed.

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.

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.

This paper proposes a synthesis method to obtain speed-independent asynchronous circuits directly from signal transition graph (STG) specifications with single cycle signals which can be non-persistent and have free-choice operations. The resulting circuits are implemented with basic gates and asynchronous latches, and operate correctly under finite but unbounded gate delays and the zero wire delay assumptions. The proposed method introduces 5 types of lock relations to implement a non-persistent STG. A non-persistent STG can be implemented if every non-persistent signal to a signal t is super-locked with t. The resulting circuits are optimized by extracting of literals, mapping onto asymmetric C-elements, etc. Experimental results show that the proposed synthesis method outperforms the existing synthesis systems such as SYN and SIS.

Signal Transition Graphs (STG's) are Petri nets, which were introduced to represent a behavior of asynchronous circuits. To derive logic functions from an STG, the reachability graph should be constructed. In the verification of STG's some method based on an Occurrence net (OCN) and its prefix, called an unfolding, has been proposed. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating sub state space of a given STG using the structural properties of OCN.

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.

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.

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.

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.

Many different edge detectors have been proposed. Most of them output the edge intensity and the edge orientation as edge features. In this paper we state necessity of a measure which can discriminate a clear edge with small edge height from a noisy edge with large edge height. To find such a measure as an edge feature, we analyze variances within a window around the edge and propose an edge-feature extractor based on this analysis. Then it is noticed that the traditional edge intensity can be considered as two elements: edge height and edge reliability. In multiple edge cases, the condition is clarified for calculating accurate edge locations by analyzing the edge-height function. From this analysis we suggest a method for determining edge points by thresholding edge height. Our detector is compared to Canny's detector both in synthetic models and in a real image and it is demonstrated that our method produces better results in edge locations than Canny's. We also show that our method can detect edges with low edge height and high edge reliability.

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 X_k, Dyck reduction Red over X_k, and a language L₁ in L' over ΣX_k such that L=Red(L₁)Σ^*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ^*Σ^*, a Dyck language D over Γ, and a language L₂ in L' over Γ such that L=h(DL₂). We also give an application of this result.