This paper describes a procedural detailed compaction method for the symbolic layout design of CMOS leaf cells and its algorithmic aspects. Simple symbolic representations that are loosely designed by users in advance are automatically converted into densely compacted physical patterns in two phases: symbolic–to–pattern conversion and segment–based detailed compaction. Both phases are executed using user-defined procedures and a specified set of design rules. The detailed compaction utilizes a segment–based constraint graph generated by an extended plane sweep method where various kinds of design rules can be applied. Since various kinds of basic operations can be applied to the individual segments of patterns in the procedures, the detailed procedure for processing can be described in accordance with fabrication process technologies and the corresponding sets of design rules. This combined stepwise procedure provides a highly flexible framework for the symbolic layout of CMOS leaf cells. The proposed approach was implemented in a symbolic layout system called CAMEL. To date, more than 300 kinds of symbolic representations of CMOS leaf cells have been designed and are stored in the database. Using several different sets of design rules, symbolic representations have been automatically converted into compacted patterns without design rule violations. The areas of those generated patterns were averaged at 98% of the manually designed patterns. Even in the worst case, the increases in area were less than about 10% of the manually designed ones. Furthermore, since processing times are much shorter than manual design periods, for example, 300 kinds of symbolic representations can be converted to corresponding physical patterns in only a day. It is evident, through these practical design experiences with CAMEL, that our approach is more flexible and process–tolerant than conventional ones.

We propose an optimal throughput problem using graph transformations to maximize throughput of a pipelined data path with some loops. The upper bound of the throughput, equals to the lower bound of the iteration interval between the start of two successive iterations, is limited by the length of a critical loop. Therefore we can maximize the throughput by minimizing the length of the critical loop. The proposed method first schedules an initial Data Flow Graph (DFG) under the initial iteration interval as few as it can use resources, then it transforms the DFG into the flow graph with the minimal length of the critical loop by rescheduling the given initial scheduling result. If there are any control steps which violate the resource constraints owing to the transformations, then these operations are adjusted so as to satisfy given resource consrtraints. Finally by rescheduling the transformed DFG, it gives a schedule with maximum throughput. Experiments show the efficiency of our proposed approach.

Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (CO-trees) and their computing methods. A CO-tree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between CO-trees. The time complexities to compute the distances between two CO-trees Ta and Tb are OT (N 2aN 2b) for the distance based on a TM and OT(mambNaNb) for that on an SSPM, respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The space complexities of both methods are Os(NaNb). Those distances can be applied to the clustering of CO-trees.

A W-graph is a partially known graph which contains wild-components. A wild-component is an incompletely defined connected subgraph having p vertices and p-1 unspecified edges. The informations we know on a wild-component are which has a vertex set and between any two vertices there is one and only one path. In this paper, we discuss the properties of circuits in a W-graph (called W-circuits). Although a W-graph has unspecified edges, we can obtain some important properties of W-circuits. We show that the W-ring sum of W-circuits is also a W-circuit in the same W-graph. The following (1) and (2) are proved: (1) A W-circuit Ci of a W-graph can be transformed into either a circuit or an edge disjoint union of circuits, denoted by Ci*, of a graph derived from the W-graph, (2) if W-circuits C1, C2, , Cn are linearly independent, then C1*, C2*, , Cn* obtained in (1) are also linearly independent.

This paper describes a preconstrained compaction method and its application to the direct design-rule conversion of CMOS layouts. This approach can convert already designed physical patterns into compacted layouts that satisfy user-specified design rules. Furthermore, preconstrained compaction can eliminate unnecessarily extended diffusion areas and polysilicon wires which tend to be created with conventional longest path based compactions. Preconstrained compaction can be constructed by combining a longest path algorithm with forward and backward slack processes and a preconstraint generation process. This contrasts with previously proposed approaches based on longest path algorithms followed by iterative improvement processes, which include applications of linear programming. The layout styles in those approaches are usually limited to a model where fixed-shaped rectilinear blocks are moved so as to minimize the total length of rectilinear interconnections among the blocks. However, preconstrained compaction can be applied to reshaping polygonal patterns such as diffusion and channel areas. Thus, this compaction method makes it possible to reuse CMOS leaf and macro cell layouts even if design rules change. The proposed preconstrained compaction approach has been applied to direct design-rule conversion from 0.8-µm to 0.5-µm rules of CMOS layouts containing from several to 10,195 transistors. Experimental results demonstrate that a 10.6% reduction in diffusion areas can be achieved without unnecessary extensions of polysilicon wires with a 39% increase in processing times compared with conventional approaches.

In a distributed system, the protocol entities must exchange some data values and synchronization messages in order to ensure the temporal ordering of the events described in a service specification for the distributed system. It is desirable that a correct protocol specification can be derived automatically from a given service specification. In this paper, we propose an algorithm which synthesizes automatically a correct protocol specification from a service specification described as a Marked Graph with Registers (MGR) model and resources (registers and gates) allocation information. This model has a finite control modeled as a marked graph. Therefore, parallel events can be described. In our method, to minimize the number of the exchanged messages, we use a procedure to calculate an optimum solution for 0-1 integer linear programming problems. The number of the steps which each protocol entity needs to simulate one transition in the service specification is also minimized. Ways to avoiding conflict of registers are also described. Our approach has the following advantages. First, parallel events can be described in a service specification. Secondly, many practical systems can be described in the MGR model. Finally, at the protocol specification level, we can understand what events can be executed in parallel.

In this paper, we present Branching Oriented System Equation based on-line error correction scheme for recursive digital signal processing. The target digital signal processing is linear and time-invariant, and the algorithm includes multiplications with constant coefficient, additions and delays. The difficulties of the algorithm-level fault tolerance for such algorithm without structural regularity include error distribution problem and right timing of error correction. To escape the error distribution problem, multiple fan-out nodes in an algorithm are specified as the nodes at which error corrections are performed. The Branching Oriented Graph and Branching Oriented System Equation are so introduced to formulate on-line correction schemes based on this strategy. The Branching Oriented Graph is treated as the collection of computation sub-blocks. Applying checksum code independently to each sub-block is our most trivial on-line error correction scheme, and it results in, with appropriate selection of error identification process, TMR in sub-block level. One of the advantages of our method is in the reduction of redundant operations performed by merging some computation sub-blocks. On the other hand, the schedulability of the system is an important issue for our method since our on-line error correction mechanism induces additional data dependencies. In this paper, the schedulability condition and some modifications on the scheme are also discussed.

Mode separation of a multiplex mode in a mode-division multiplexing system is studied. The clear, desired single-mode pattern, which is separated from the multiplex mode by using a holographic filter, is observed in the experiment.

Kumar and Billinton have presented a new technique for obtaining the steady-state probabilities from a flow graph based on Markov model. By examining the graph and choosing suitable input and output nodes, the steady-state probabilities can be obtained directly by using the flow graph. In this paper this graphical technique is applied for a k-out-of-n: G repairable system. Consequently a new derivation way of the formulae for the steady-state availability and MTBF is obtained.

A uniquely decodable (UD) code pair (C, S) is considered for the two-user binary adder channel. For a class of linear codes C, the maximum independent set of the graph associated with C, which is the second code S, is evaluated. When the rate R1 of C is less than 0.5, there exist UD codes (C, S)'s such that the rate R2 of S exceeds the Khachatrian's and Guo's results in amount.

This paper describes the architecture and new circuit technologies of a proposed Pixel (bit) -Aligned Triple-port DRAM (PATDRAM). The PATDRAM has a 270 K word 16 b Random Access Memory (RAM), a 512 word 8 b Serial Access Memory-(a) (SAMa) and a 1024 word 4 b Serial Access Memory-(b) (SAMb). The random port, serial-a and serial-b port can be operated by three independent synchronous clocks. In these three ports, word data can be aligned to the location of an arbitrary bit position. Data transfer from SAMb to RAM can be individually masked by transfer mask data. The RAM operates by 33 MHz synchronous clock and two SAMs operate by 40 MHz clocks. Novel architecture of the PATDRAM accelerates graphics performance and simplifies in multimedia systems which manage both realtime video and computer graphics data, and also accelerates graphics performance in both two-dimensional (2D) and three-dimensional (3D) graphics systems. PATDRAM was designed using a 0.6 µ double metal, triple poly, stacked capacitor, CMOS process technology in a 10.98 mm9.88 mm die area integrated 4.4 Mb RAM, 8 Kb SAM, 4 Kb transfer mask register and 5 Kgate logic.

The progress of LSI technologies makes it possible to fabricate 256 MDRAM. However, it depends on the cost effectiveness of device fabrication that LSI memory can continue to be the technology driver or not. It is indispensable to make the device, process, and equipment as simple as possible for next generation LSI. For example, wavefront technologies in lithography, high energy ion implantation, and simple DRAM cell with SOI structure or high dielectric constant capacitor, are under development to satisfy both device performance improvement and process simplicity.

In this paper we propose a new algorithm for recognizing 3-D objects from 2-D images. The algorithm takes the multiple view approach in which each 3-D object is modeled by a collection of 2-D projections from various viewing angles where each 2-D projection is called an object model. To select the candidates for the object model that has the best match with the input image, the proposed algorithm computes the surface matching score between the input image and each object model by using Hopfield nets. In addition, the algorithm gives the final matching error between the input image and each candidate model by the error of the pose-transform matrix proposed by Hong et al. and selects an object model with the smallest matching error as the best matched model. The proposed algorithm can be viewed as a combination of the algorithm of Lin et al. and the algorithm of Hong et al. However, the proposed algorithm is not a simple combination of these algorithms. While the algorithm of Lin et al. computes the surface matching score and the vertex matching score berween the input image and each object model to select the candidates for the best matched model, the proposed algorithm computes only the surface matching score. In addition, to enhance the accuracy of the surface matching score, the proposed algorithm uses two Hopfield nets. The first Hopfield net, which is the same as that used in the algorithm of Lin et al., performs a coarse matching between surfaces of an input image and surfaces of an object model. The second Hopfield net, which is the one newly proposed in this paper, establishes the surface correspondences using the compatibility measures between adjacent surface-pairs of the input image and the object model. the results of the experiments showed that the surface matching score obtained by the Hopfield net proposed in this paper is much more useful for the selectoin of the candidates for the best matched model than both the sruface matching score obtained by the first Hopfield net of Lin et al. and the vertex matching score obtained by the second Hopfield net of Lin et al. and, as the result, the object recognition algorithm of this paper can perform much more reliable object recognition than that obtained by simply combining the algorithm of Lin et al. and the algorithm of Hong et al.

This paper proposes RSA-type cryptosystems over elliptic curves En(O, b) and En(a, O),where En(a, b): y2 x3+ax+b (mod n),and n is a product of from-free primes p and q. Although RSA cryptosystem is not secure against a low exponent attack, RSA-type cryptosystems over elliptic curves seems secure against a low multiplier attack. There are the KMOV cryptosystem and the Demytko cryptosystem that were previously proposed as RSA-type cryptosystems over elliptic curves. The KMOV cryptosystem uses form-restricted primes as p q 2(mod 3)or p q 3(mod 4), and encrypts/decrypts a 2log n-bit message over varied elliptic curves by operating values of x and y coordinates. The Demytko cryptosystem, which is an extension of the KMOV cryptosystem, uses form-free primes, and encrypts/decrypts a log n-bit message over fixed elliptic curves by operating only a value of x coordinates. Our cryptosystems, which are other extensions fo the KMOV cryptosystem, encrypt/decrypt a 2log n-bit message over varied elliptic curves by operating values of x and y coordinates. The Demytko cryptosystem and our cryptosystems have higher security than the KMOV cryptosystem because from-free primes hide two-bit information about prime factors. The encryption/decryption speed in one of our cryptosystems is about 1.25 times faster than that in the Demytko cryptosystem.

In this paper, symbols and numerals in topographic maps are recognized by the multi-angled parallelism (MAP) matching method, and small dots and lines are extracted by the MAP operation method. These results are then combined to determine the value, position, and attributes of elevation marks. Also, we reconstruct three dimensional surfaces described by contours, which is difficult even for humans since the elevation symbols are sparse. In reconstruction of the surface, we define an energy function that enfores three constraints: smoothness, fit, and contour. This energy function is minimized by solving a large linear system of simultaneous equations. We describe experiments on 25,000:1 scale topographic maps of the Tsukuba area.

The present study describes using the state transition type of drawing understanding framework to construct a multi-purpose drawing understanding system. This new system employs an understanding process that complies with the understanding rules, which are easily obtained by the user. The same set of user-provided rules must be used for the same type of target drawings, but for slightly different ones, fine tuning is required to obtain understanding rules. To overcome this inherent drawback in constructing drawing understanding systems, we extended the system using a newly constructed understanding rule generating support system. The resultant integrated system is based on a man-machine cooperation type interface, and can automatically generate rules from user-provided simple interactions using a graphical user interace (GUI). To obtain efficient rule generation, the system employs an inductive inference method as a learning algorithm. Map-drawing experiments were successfully carried out, and an evaluation based on a rule leaning error criterion subsequently revealed an efficient rule generation process.

The demand for mobile communication services is rapidly increasing, because the mobile communication service is synonymy of an ideal communication style realizing communication in anytime, anywhere and with anyone. The development of economic and social activities is a primary factor of the increasing demand for mobile communication services. The demand stimulates the development of technology in mobile communication including personal communication services. Thus mobile communication has been one of the most active research in communications in the last several years. There exist various problems to which graph & network theory is applicable in mobile communication services (for example, channel assignment algorithm in cellular system, protocol in modile communication networks and traffic control in mobile communication ). A model of a cellular system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, two types of coloring problems on graphs or networks related to the channel assignment problem were proposed. Mainly, we introduce these coloring problems and show some results on these problems in this paper.

An experimental SAR (Specific Absorption Rate) estimation system based upon the thermograph method using a thermograph camera and newly developed homogeneous dry-phantom human models are presented. Experiments are conducted using this system and UHF fields to obtain SAR distributions in the human head irradiated by hand-held portable radios. Experiment results show that the estimated peak SAR's due to the radiation waves from radios of 1W transmitting power are lower than 2W/kg and so conform to the recommendations of the radio-frequency radiation safety guidelines. The developed system enables the surface SAR distributions on the phantom model to be precisely estimated; a function not available with the original system. System parameters required for providing precise estimations are discussed first, and then experiments are conducted to estimate SAR's in the human head exposed to a UHF hand-held portable radio's near field. Finally, estimated data are examined from the viewpoint of radio-frequency exposure safety guidelines.

The linear array processor architecture is an important class of interconnection structures that are suitable for VLSI. In this paper we study the problem of mapping a task tree onto a linear array to minimize the total execution time. First, an optimization algorithm is presented for a message scheduling probrem which occurs in the task tree mapping problem. Next, we give a heuristic algorithm for the task tree mapping problem. The algorithm partitions the node set of a task tree into clusters and maps these clusters onto processors. Simulation experiments showed that the proposed algorithm is much more efficient than a conventional algorithm.

Wave digital filters are a class of digital filters. They are equivalent to commensurate transmission line circuits synthesized with uniform, lossless, and commensurated transmission lines. In order to extend their applications to physical wave phenomena including quantum electronics, it is necessary to consider a generalized distributed line whose velocity of energy flow has frequency characteristics. This paper discusses a generalized distributed circuit, and we obtain two types of lines, lossless and cut-off. In order to analyze these lines, we discuss signal flow graphs of steady state voltage and current. The reflection factors we obtain here are the same as that for an active power or a diagonal element of a scattering matrix, which is zero in conjugate matching. By using this reflection factor, we obtain band-pass filters synthesized with the cut-off lines. We also describe an analysis method for nonuniform line related to Riccati differential equation.