Behavioral extraction from circuit description is a useful technique for logic design verification. We have proposed a technique of extraction from combinational circuits and developed a prototype system. To use this system practically, it is necessary to deal with sequential circuits. In this paper, we will present a new technique to extract behavioral descriptions from synchronous sequential circuits which include some flip-flops. Flip-flops are classified to two types. The one is a part of control registers. The other is a part of data registers. Behavior of the circuit with control registers is described by the state transition. Behavior of the circuit with data registers is described by the movement of data among registers. There are many circuits, as micro processors, which realize a function after some times of state transitions occurred. In such circuits, it is more important to abstract the function than to extract each state transition. We have progressed our system to extract such behaviors.

In most of the methods proposed so far to design approximately linear phase IIR digital filters (IIR DFs), the design takes place only in the time or in the frequency domain. However, when both magnitude and phase responses are considered, IIR DFs with better frequency responses can be obtained if their characteristics in both domains are taken into account. This paper proposes a design method for approximately linear phase IIR DFs, which is based on parameter estimation techniques in the time domain followed by a nonlinear optimization algorithm in the frequency domain. Several examples are presented, illustrating the proposed method.

This paper surveys modeling techniques for telephone call control based on a Finite State Machine (FSM) concept, and studies model simplification techniques. First, the basic concept and fundamental issues of call control modeling are described. Then, based on the analysis of layered call control configuration, it is clarified that the call control machine decomposition within the two-party service control layer has the effect of reducing the apparent size of each mate's machine. Using this effect, guidelines for call control modeling are derived, by which multiple services can be modeled independently. Finally implementation techniques and a few examples of application will be presented.

This paper describes a VLSI processor architecture designed for a back-propagation accelerator. Three techniques are used to accelerate the simulation. The first is a multi-processor approach where a neural network simulation is suitable for parallel processing. By constructing a ring network using several processors, the simulation speed is multiplied by the number of the processors. The second technique is internal parallel processing. Each processor contains 4 multipliers and 4 ALUs that all work in parallel. The third technique is pipelining. The connections of eight functional units change according to the current stage of the back-propagation algorithm. Intermediate data is sent from one functional unit to another without being stored in extra registers and data is processed in a pipeline manner. The data is in 24-bit floating point format (18-bit mantissa and 6-bit oxponent). The chip has about 88,000 gates, including microcode ROM for processor control, the processor is designed using 0.8-µm CMOS gate arrays, and the estimated performance at 40 MHz is 20 million connection updates per second (MCUPS). For a ring network with 4 processors, performance can be enhanced up to 90 MCUPS.

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

Net-Oriented Analysis and Design (NOAD) is defined as three items: (1) Various nets are utilized as an effective modeling method. (2) Inter-relationships among verious nets are determined. (3) Verification or analysis methods for nets are provided and they are implemented based on the mathematical theory, that is Net theory. Very few methods have been presented to satisfy these three items. For example, the Real-Time SA method covers item (1) only. The Object-Oriented Analysis and Design method (OOA/OOD) covers items (1) and (2). NOAD can be regarded as an extension to OOA/OOD. This paper discusses how effectively various nets have been used in actual software development support metnods and tools and evaluates such several methods and tools from the NOAD viewpoint.

We propose a hierarchical multi-layer global router for Sea-Of-Gates VLSI's, which is different from the conventional global routers, in that routing and layering are executed simultaneously. The main problems to be solved in the global routing for a multi-layer VLSI are which wire segments are laid out on upper layers and how they are connected to terminals located on lower layers. The main objective is to minimize the maximum of local congestions of all layers. We solve these problems in a hierarchical manner by routing from upper layers to lower layers.

GaAs MESFETs with a p-buffer layer (or a buried p-layer) are important devices for high-speed GaAs ICs. To study what conditions are required as a good substrate for ICs, we have investigated, by two-dimensional simulation, small-signal parameters and drain-current transients of GaAs MESFETs with a p-buffer layer on the semi-insulating substrate. It is shown that the introduction of a p-buffer layer is effective to improve the transconductance and the cuttoff frequeycy. These parameters are not degrade even if the p-layer doping is increased and a neurtral p-region exists. It is also shown that drain-current drifts and hysteresis in I-V curves can occur in a case with a p-buffer layer, too. It is concluded that the introduction of a relatively highly-doped p-layer on a substrate with low acceptor and electron trap (EL2) densities is effective to realize the stable and high performance of GaAs MESFETs.

An autonatic layout scheme dedicated to bipolar analog modules is described. A layout model is settled in such a way that the VCC/GND line is laid out on top/bottom edge of a rectangular region, within which the whole elements are placed and interconnected. According to this simple modeling, a layout scheme can be constructed of a series of the following algorithms: First clustering is executed for partitioning a given circuit into clusters, each having connections with VCC and GND lines, and then linear ordering is applied to clusters so as to be placed in a one-dimensional array. After a relative placement of circuits elements in each cluster, a block compactor is implemented by means of packing blocks in each cluster into an idle space, and then a detailed router is conducted to attain 100% interconnection. Finally a layout compactor is invoked to pack all layout patterns into a rectangle of the minimum possible area. A number of implementation results are also shown to reveal the practicability of the proposed analog module generator.

An automatic macrocell generator has been developed and applied to the analog layout of SC and active-RC filters. The generator consists of a process independent generation procedure, a leafcell library, and a circuit description of the leafcells. The unit element arrays of the whole filter are generated together to minimize the array height of the entire filter macrocell, so that the area of the generated filter is as small as that of a manually laid out filter. Three SC filters and one active-RC filter were designed and fabricated by 1.5-µm CMOS technology, that successfully yielded an S/N ratio of more than 70 dB with a quick turn around time.

This paper presents a method for LSI implementation of a long-tap acoustic echo canceller algorithm using the residue number system (RNS) and the mixed-radix number system (MRS). It also presents a quantitative comparison of echo canceller architectures, one using the RNS and the other using the binary number system (BNS). In the RNS, addition, subtraction, and multiplication are executed quickly but scaling, overflow detection, and division are difficult. For this reason, no echo canceller using the RNS has been implemented. We therefore try to design an echo canceller architecture using the RNS and the NLMS algorithm. It is shown that the echo canceller algorithm can be effectively implemented using the RNS by introducing the MRS. The quantitative comparison of echo canceller architectures shows that a long-tap acoustic echo canceller can be implemented more effectively in terms of chip size and power dissipation by the architecture using the RNS.

A one-by-four static frequency divider using AlGaAs/GaAs heterojunction bipolar transistors (HBTs) was designed to operate at a bias condition that gave a maximum cutoff frequency fT and a maximum oscillation freqency fmax. The fT and fmax applied to the divider were 68 GHz and 56 GHz, respectively. As a result of the tests, the circuit operated up to 34.8 GHz at a power supply voltage of 9 V and power dissipation of 495 mW. A low minimum input signal power level of 0 dBm was also achieved.

This paper presents a protocol verification method which verifies that the behaviors of a protocol meet requirements. In this method, a protocol specification is expressed as Extended Finite State Machines (EFSM's) that can handle variables, and requirements are expressed using a branching-time temporal logic for a concise and unambiguous description. Using the acyclic expansion algorithm extended such that it can deal with EFSM's, the verification method first generates a state transition graph consisting of executable transitions for each process. Then a branching-time temporal logic formula representing a requirement is evaluated on one of the generated graphs which is relevant to the requirement. An executable state transition graph for each process is much smaller than a global state transition graph which has been used in the conventional verification techniques to represent the behaviors of the whole protocol system consisting of all processes. The computation for generating the graphs is also reduced to much extent for a large complex protocol. As a result, the presented method achieves efficient verification for requirements regarding a state of a process, transmission and reception of messages by a process, varibales of a process and sequences that interact among processes. The validity of the method is illustrated in the paper by the verification of a path-updating protocol for requirements such as process state reachability or fair termination among processes.

This paper describes MENDELS ZONE, a Petri-net-based concurrent programming environment, which is especially suitable for cooperating discrete event systems. MENDELS ZONE adopts MENDEL net, which is a type of high level (hierarchical colored) Petri net. One of the characteristics of the MENDEL nets is a process-oriented hierarchy like CCS, which is different from the subnet-oriented hierarchy in the Jensen's hierarchical colored Petri net. In a process-oriented hierarchy, a hierarchical unit is a process, which is more natural for cooperating and decentralized discrete event control systems. This paper also proposes a design methodology for MENDEL nets. Although many Petri net tools have been proposed, most tools support only drawing, simulation, and analysis of Petri nets; few tools support the design methodology for Petri nets. While Petri nets are good final design documents easy to understand, analyzable, and executable it is often difficult to write Petri nets directly in an earlier design phase when the system structure is obscure. A proposed design methodology makes a designer to construct MENDEL nets systematically using causality matrices and temporal logic. Furthemore, constructed MENDEL nets can be automatically compiled into a concurrent programming language and executed on a parallel computer.

We have successfully developed an optical receiver and a laser driver circuit which were implemented with 0.35 µm GaAs JFETs (junction Field Effect Transistors). The 0.35 µm GaAs. JFET had the typical transconductance of 480 mS/mm with small drain conductance. An interdigit MSM (Metal Semiconductor Metal) -type photodetector and the JFETs were monolithically integrated on a GaAs substrate for the optical receiver. The fabricated optical receiver demonstrated Gb/s operation with a very low power consumption of 8.2 mW. The laser driver circuit operated at up to 4.0 Gb/s.

High frequency and low power 128/129 dual modulus prescaler ICs are developed for mobile communication applications, using 0.5 µm GaAs MESFET technology. Provided with an on-chip voltage regulator, a prescaler IC with an input amplifier operates in a wide frequency range from 200 MHz to 1,500 MHz at input power from -15 dBm to +17 dBm at the temperature of -30 to +120 with supply voltage of 2.7 V, 3.0 V and 5.0 V. At the same time, it demonstrated its low power characteristics consuming 3.68 mA with 3.0 V at +30 in operation, 0.16 mA while powered-off. Another prescaler IC without an input amplifier operates up to 1,650 MHz with Vdd=2.7 V, 3.0 V and 5.0 V at +30, dissipating 2.74 mA/3.0 V.

Recently, Burch et al. proposed symbolic model checking method to verify sequential machines formally. The method, which is based on logic function manipulation using binary decision diagram, can handle large sequential machines that cannot be handled by the conventional techniques. The expressive power of Computational Tree Logic (CTL), which was used by Burch et al., is not very powerful, for example, CTL cannot describe repetition of events. This papers shows an extension of the symbolic model checking algorithm to Branching time regular temporal logic (BRTL), which has been proposed by the authors as an improvement of CTL in terms of expressive power. The implemented verifier based on the proposed algorithm could verify behaviors of a microprocessor composed of approximately 1,600 gates and 68 flipflops.

The effectiveness of traffic shaping for VBR traffic is analyzed. Evaluation results prove that traffic shaping can improve link efficiency for most forms of bursty VBR traffic and that link efficiency gains of more than 250% can be expected without the shaping delay imposing any significant QOS deterioration. Traffic shaping increases the link efficiency to about 80% for traffic with short burst repetition periods. The traffic shaping techniques and analytical results described herein can be employed in the traffic management of future B-ISDN/ATM networks.

This paper presents the EXM-algorithm, which locates multiple logic design errors in a combinational circuit with multiple output. The error possibility index and the six-valued simulation method have been enhanced to be applied to multiple output circuit. The algorithm locates multiple errors even if they belong to different cone circuits, and processes faster than the conventional EX-algorithm for circuits with the similar gate sizes. Experimental results have shown that the algorithm locates all errors at high hit ratio for ISCAS benchmark circuits and some other circuits.

Stochastic Petri Nets and Generalized Stochastic Petri Nets as well as other extensions to Stochastic Petri Nets have been widely applied as a model of asynchronous concurrent process, or as an aid to analyze or design concurrent systems. This paper presents an Extended Stochastic Petri Net model for a shift processing system in which three kinds of sink may occur and an arbitrary time distribution is incorporated, provides an analytical method based on a Markov renewal process with some non-regeneration points to clarify the probabilistic behavior of the system, and finally evaluates the performance of the system with numerical values.