This paper studies the problem of embedding a graph into a book with nodes on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. Atneosen as well as Bernhart and Kainen has shown that every graph can be embedded into a 3-page book when each edge can be embedded in more than one page. The time complexity of Bernhart and Kainen's method is Ω(ν(G)), where ν(G) is the crossing number of a graph G. A new 0(mn) algorithm is derived in this paper for embedding a graph G=(V, E), where m=│E│ and n= │V│ . The number of points at which edges cross over the spine in embedding a complete graph into a 3-page book is also investigated.

A new evaluation technique of hot carrier degradation is proposed and applied to practical evaluation of p-channel polycrystalline silicon thin film transistors (TFT). The proposed technique introduces emission microscopy which is particularly effective for evaluating TFT devices. We have developed an automatic measurement system in which measurement of the electrical characteristics and monitoring the photo emission are done simultaneously. Using this system, we have identified the dominant mechanism of hot carrier degradation in TFTs, and evaluated the effect of plasma hydrogenation on hot carrier degradation.

A modified beam propagation method based on the Galerkin's technique (FE-BPM) has been implemented and applied to the analysis of optical beam propagation in a tapered dielectric waveguide. It is based on a new calculation procedure using non-uniform sampling spacings along the transverse coordinate. Comparison with a conventional FE-BPM shows a definite improvement in saving computation time. The differences of a propagation field and a mean square power given by the proposed FE-BPM are discussed in comparison with the conventional FE-BPM.

This paper investigates the properties of synchronized alternating one-way multicounter machines (lsamcm's) which operate in real time (lsamcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hieracrchies of lsamcm-real's based on the number of counters and constant leaf-sizes. We next show that lsamcm-real's are less powerful than lsamcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that limn[L(n) log n/n]0 and L(n)2.

The main problem in statistical pattern recognition is to design a classifier. Many researchers point out that a finite number of training samples causes the practical difficulties and constraints in designing a classifier. However, very little is known about the performance of a classifier in small training sample size situations. In this paper, we compare the classification performance of the well-known classifiers (k-NN, Parzen, Fisher's linear, Quadratic, Modified quadratic, Euclidean distance classifiers) when the number of training samples is small.

For the efficient circuit simulation, several direct/relaxation-based mixed mode simulation techniques have been studied. This paper proposes the combination of selective trace, which is well-known in the logic simulation, with dynamic network separation. In the selective trace method, the time points to be analyzed are selected for each subcircuit. Since the separation technique enables the analysis of each subcircuit independently, it is possible to skip solving the latent subcircuits, according to selective trace. Selecting the time points in accordance with activity of each subcircuit is analogous to multirate numerical integration technique used in the waveform relaxation algorithm.

In this paper, an efficient and robust circuit parameter determination method suitable for analog circuit synthesis is presented. The method uses block diagram representation of circuits as implicit design knowledge. Circuit parameter determination is carried out by propagating known values along signal flow in the block diagram. The circuit parameter determination using signal propagation performs successfully when unknown circuit parameters can be solved in one way. However, when the block diagram involves implicit calculation, the propagation stops before all unknown parameters are determined. In order to cope with this problem, we introduced a method that employs a symbolic analysis technique combined with a numerical method. When the propagation of known values stops, one of unknown signals is selected, a unique symbol is assigned to the selected signal, and the signal propagation is restarted. This operation is repeated until there is no unknown signal. When the symbol propagation reaches the signal where the signal value is already set, one nonlinear equation for the signal is obtained by equating both signal values. It can be solved by a numerical method, such as Newton's method. The parameter determination method using procedural description is superior to the optimization based method because it is straightforward to incorporate design knowhow in the description. However, it is burdensome for designers to develop design procedures for each circuit to be synthesized. Because the block diagram based calculation method can be used as subroutine calls during the design procedure development, it simplifies the design procedural description and lowers the burden of designers. The method was applied to the element value determination of bias circuits to demonstrate its effectiveness.

This paper deals with methods for interconnection between two local private networks that are geographically separated. A scheme is first presented to chain low bit-rate physical circuits into one logical circuit, over which ATM cells are transmitted as if there is one circuit with a high bit-rate capacity. In particular, use of existing low bit-rate circuits, e.g., 384/1536 kbit/s PDH leased line services and N-ISDN switched channels, is considered. The paper discusses two methods to permit chaining of physical circuits, and identifies their advantages and applications. By using the ATM-based circuit-chaining method, dynamic capacity control of the interconnection is then introduced with the use of an ATM-based rate adaptation. This is intended to provide a flexible and cost-effective capacity control compared to the existing TDM-based control. It is also possible to realize non-stop operation of changing capacity by establishment and release of chained circuits, which will lead to high reliability and robustness of private networks. Finally, delay characteristics introduced by the method are evaluated based on a computer simulation which gives a short and acceptable delay.

A polyomino is a configuration composed of squares connected by sharing edges. A k-coloring of a polyomino is an assignment of k colors to the squares of the polyomino in such a way no two adjacent squares receive the same color. A k-coloring is called balanced if the difference of the number of squares in color i and that of squares in color j is at most one for any two colors i and j. In this paper, we show that any polyomino has balanced k-coloring for k3.

A sequence of nonnegative integers S=(s1, s2, , sn) is graphical if there is a graph with vertices v1,v2, ,vn such that deg(vi)=si for each i=1, 2, , n. The graphical degree sequence problem is： Given a sequence of nonnegative integers, determine whether it is graphical or not. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.

IC performance simulation for statistical purpose is usually very time-consuming since the scale and complexity of IC have increased greatly in recent years. A common approach for reduction of simulation cost is aimed at the nature of simple modeling instead of actual circuit performance simulations. In this paper,a stochastic interpolation model (SIM) scheme is proposed which overcomes the drawbacks of the existing polynomial-based approximation schemes. First,the dependence of the R2press statistic upon a parameter in SIM is taken into account and by maximizing R2press this enables SIM to achieve the best approximation accuracy in the given sample points without any assumption on the sample data. Next, a sequential sampling strategy based on variance analysis is described to effectively construct SIM during its update process. In each update step, a new sample point with a maximal value of variance is added to the former set of the sample points. The update process will be continued until the desired approximation accuracy is reached. This would eventually lead to the realization of SIM with a quite small number of sample points. Finally, the coefficient of variance is introduced as another criterion for approximation accuracy check other than the R2press statistic. The effectiveness of presented implementation scheme is demonstrated by several numerical examples as well as a statistical circuit analysis example.

A C1 interpolation scheme for constructing surface patch on n-sided region (n5, 6) is presented. The constructed surface patch matches the given boundary curves and cross-boundary slopes on the sides of the n-sided region (n5, 6). This scheme has relatively simple construction, and offers one degree of freedom for adjusting interior shape of the constructed interpolation surface. The polynomial precision set of the scheme includes all the polynomials of degree three or less. The experiments for comparing the proposed scheme with two schemes proposed by Gregory and Varady respectively and also shown.

A technique to realize a transconductance which is relatively insensitive over temperature variations is reported. Simulation results with MOS and bipolar transistors indicate substantial improvement in temperature insensitivity over a range exceeding 100 degrees Celsius. It should find useful applications in analog LSI/VLSI systems operating over a wide range of temperature.

As a generalization of the concept of pseudo-biorthogonal bases (PBOB), we already presented in Ref. [3] the theory of the so-called extended pseudo-biorthogonal bases (EPBOB). We introduce in this paper two special types of EPBOB called EPBOB's of type O and of type L. This paper discusses characterizations, construction methods, inherent properties, and mutual relations of these types of EPBOB.

An automatic tracing algorithm of the transistor-level performance faults in the waveform-based approach with CAD-linked electron beam test system which utilizes a transistor-level circuit data in CAD database is proposed. Performance faults mean some performance measure such as the temporal parameters (rise time, fall time and so on) lies outside of the specified range in a VLSI. Problems on automatic fault tracing in the transistor level are modeled by using graphs. Combinational circuits which consist of MOS transistors are considered. A single fault is assumed to be in a circuit. The algorithm utilizes Depth-First Search algorithm where faulty upstream interconnections are searched as deeply as possible. Treatment of the faults on downstream interconnections and on unmeasurable interconnections is given. Application of this algorithm to the 2k-transistor block of a CMOS circuit showed its validity in the simulation.

New critical-dimension controlling technique of off-axis illumination for aperiodic patterns has been developed. By means of arranging not-imaging additional pattern near 0.25 micron isolated patterns, the depth of focus of an isolated pattern was improved as well as the periodic patterns. Simulation and experimental results were verified on a 0.48 numerical-aperture, KrF excimer laser stepper. Using new deep-ultra-violet hardening technique for chemically amplified positive resist, the critical dimension loss of resist pattern was prevented. 0.25 micron design rule pattern was obtained with excellent mask linearity without critical-dimension-loss. The combination techniques are achieved quarter micron design rule complex circuit pattern layouts.

In this paper, we study a dynamic bandwidth control which is expected an effective use of network resources in transmitting highly bursty traffic generated by, e.g., interconnected LAN systems. First, a new LAN traffic model is proposed in which correlation of not only packet interarrival times but also packet lengths are considered. An analytic model for a LAN-ATM gateway is next introduced. It employs the dynamic bandwidth control using the proposed LAN traffic model and some performance measures are derived by it. The analytic model takes into account the probability that a bandwidth increase request may be rejected. Finally, some numerical examples are provided using the analysis method and performance comparisons between the dynamic and fixed bandwidth controls are made. As a result, it is quantitatively indicated that () if the equivalent bandwidth is used in average, the dynamic bandwidth control keeps packet and cell loss rates one to two orders lower than the fixed bandwidth control, () when the more strict QOS in terms of loss rate is requested, the dynamic bandwidth control can become more effective.

This paper discusses a way of identifying the network configuration of ATM-LANs, which are composed of a number of ATM hubs. In general, a Network Management System (NMS) sets and gets the necessary data to and from the network elements. In managing an ATM-LAN, the ATM connection between the NMS and each network element, namely the ATM hub, must be established in order to get and set the necessary data. This forms a remarkable contrast with conventional LANs such as the IEEE802.3 LAN, which is a shared media network and enables broadcast communication without setting up any connection. This paper proposes a new protocol and a procedure that establishes the ATM connection between the NMS and each ATM hub, while identifying the overall network configuration. First, this paper makes clear the peculiarity of the ATM-LAN in terms of automatically identifying the network configuration. Next, the identification protocol that achieves the required properties is precisely explained. Then, the proposed identification protocol is evaluated in terms of required bandwidth and identification time.

Asynchronous Transfer Mode (ATM) shared buffer switches have numerous advantages, but have the principal disadvantage that all switch traffic must pass through the bottleneck of a single memory. To achieve the most efficient usage of this bottleneck, the shared buffer is made blockable, resulting in a switch architecture that we call "throttled-buffer", which has several advantageous properties. Shared buffer efficiency is maximized while decreasing both capacity and power requirements. Asynchronous operation is possible, whereby peak link data rates are allowed to approach the aggregate switch rate. Multicasting is also efficiently supported. The architecture and operation of this low-cost switch are described in detail.

This paper describes a new method to estimate traffic load of communication nodes, such as switching systems. The new method uses the system identification, which is often used in designing control systems of real systems. First, this paper makes clear that, under certain conditions, the input and output relation of a communication system, which is composed of a number of communication nodes, is formulated into a dynamic state equation that is classed as a time-invariant, single-input single-output, discrete-time system. Next, it is explained that traffic load information is estimated by identifying the dynamic state equations of the communication system. Then, the traffic load estimator is synthesized using the system identification in it. Finally, it is clarified by computation simulations that the proposed method is very applicable in estimating the traffic load of each communication node.