Recently, efficient algorithms that exploit the separability of nonlinear mappings have been proposed for finding all solutions of piecewise-linear resistive circuits. In this letter, it is shown that these algorithms can be extended to circuits containing piecewise-linear resistors that are neither voltage nor current controlled. Using the parametric representation for these resistors, the circuits can be described by systems of nonlinear equations with separable mappings. This separability is effectively exploited in finding all solutions. A numerical example is given, and it is demonstrated that all solutions are computed very rapidly by the new algorithm.

A new approach to the problem of optimal software testing time is described. Most models implicitly assume the testing is terminated at the end of a prescribed period of time without user's approval. It means the release time and the in-service reliability are determined unilaterally by the developer. If software developer uses and maintains it, the assumption is appropriate. But, it may be inappropriate, if a software requiring more stringent reliability is developed by second party on a contract basis. In this case, the time of release is usually determined with the user's approval. To overcome the weaknesses of the assumption, a two stage testing with failure-free release policy is proposed. A software, after being tested by the developer for some time (in-house testing), is transferred to acceptance testing performed jointly with the user. During the acceptance testing, it is released when τ units of time specified by user is observed to be failure-free for the first time. The policy may be attractive to a user because he can determine the time of release, and extend the testing time by increasing τ. A software cost model for the policy is developed. For the software developer, an optimal in-house testing time minimizing software cost, and various quantities of interests, such as expected periods of acceptance testing, are derived based on the Jelinski-Moranda software reliability model. Finally, numerical examples are shown to illustrate the results.

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 describes the formation of ultra-thin tantalum oxide capacitors, using rapid thermal nitridation (RTN) of the storage-node polycrystalline-silicon surface prior to low-pressure chemical vapor deposition of tantalum oxide, using penta-ethoxy-tantalum [(Ta(OC2H5)5) and oxygen gas mixture. The films are annealed at 600-900 in dry O2 atmosphere. Densification of the as-deposited film by annealing in dry O2 is indispensable to the formation of highly reliable ultra-thin tantalum oxide capacitors. The RTN treatment reduces the SiO2 equivalent thickness and leakage current of the tantalum oxide film, and improves the time dependent dielectric breakdown characteristics of the film.

This paper presents a linear time algorithm for testing whether or not there is a path ,vm> of an undiercted tree T (|V(T)|n) that coincides with a string ss1sm (i.e., label(v1)label(vm)s1sm). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).

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.

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.

This paper describes a color segmentation method which is essential for automatic diagnosis of stained images. This method is applicable to the variance of input images using a three-layered neural network model. In this network, a back-propagation algorithm was used for learning, and the training data sets of RGB values were selected between the dark and bright images of normal mammary glands. Features of both normal mammary glands and breast cancer tissues stained with hematoxylin-eosin (HE) staining were segmented into three colors. Segmented results indicate that this network model can successfully extract features at various brightness levels and magnifications as long as HE staining is used. Thus, this color segmentation method can accommodate change in brightness levels as well as hue values of input images. Moreover, this method is effective to the variance of scaling and rotation of extracting targets.

This paper proposes new algorithms for adaptive FIR filters. The proposed algorithms provide both fast convergence and small final misadjustment with an adaptive step size even under an interference to the error. The basic algorithm pays special attention to the interference which contaminates the error. To enhance robustness to the interference, it imposes a special limit on the increment/decrement of the step-size. The limit itself is also varied according to the step-size. The basic algorithm is extended for application to nonstationary signals. Simulation results with white signals show that the final misadjustment is reduced by up to 22 dB under severe observation noise at a negligible expense of the convergence speed. An echo canceler simulation with a real speech signal exhibits its potential for a nonstationary signal.

A local area network (LAN) can now provide high-speed data communications in a local area environment to establish distributed processing among personal computers and workstations, and the need for interconnecting LANs, which are geographically distributed, is naturally arising. Asynchronous Transfer Mode (ATM) technology has been widely recognized as a promising way to provide the high-speed wide area networks (WAN) for Broadband Integrated Services Digital Network (B-ISDN), and the commercial service offerings are expected in the near future. The ATM network seems to have a capability as a backbone network for interconnecting LANs, and the LAN interconnection is expected to be the first service in ATM networks. However, there remain some technical challenges for this purpose; one of the main difficulties in LAN interconnection is the support of connectionless traffic by the ATM network, which is basically a connection-oriented network. Another one is the way of achieving the very high-speed data transmission over the ATM network. In this paper, we first discuss a LAN internetworking methodology based on the current technology. Then, the recent deployments of LAN interconnection methods through B-ISDN are reviewed.

A method of range image segmentation using four Markov random field(MRF)s is described in this paper. MRFs are used in depth smoothing, gradient smoothing, edge detection and surface type labeling stage. First, range and its gradient images are smoothed preserving jump and roof edges respectively using line process concept one after another. Then jump and roof edges are extracted, combined and refined using penalizing undesirable edge patterns. Finally, curvatures are computed and the surface types are labeled according to the signs of principal curvatures. The surface type labels are refined using winner-takes-all layers in the stage. The final output is a set of regions with its exact surface type. The energy function is used in order to represent constraints of each stage and the minimum energy state is found using iterative method. Several experimental results show the generality of our approach and the execution speed of the proposed method is faster than that of a typical region merging method. This promises practical applications of our method.

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.

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.

Using Ti self-aligned silicide (salicide) process, we fabricated subquarter-micron complementary metal-oxide semiconductor (CMOS) devices, and studied the mechanism of increasing resistivity of TiSi2 on poly-Si gates from 0.075 to 20 µm long and 10 µm wide. In the gates less than 0.1 µm long, we found that agglomeration of TiSi2 takes place during low temperature annealing at 675 for 30 seconds leading to discontinuous TiSi2 lines. The discontinuity of TiSi2 abruptly increases the gate resistance, and remarkably reduces the circuit speed of CMOS ring oscillators. On the other hand, Raman spectroscopy reveals that the phase transition from high-resistivity C49 to low-resistivity C54 occurs in plane TiSi2 by annealing at 800 for 30 seconds, while it does not occur in TiSi2 gates less than 5 µm long. From these results we found that the gate sheet resistance can not be reduced to less than 5 Ω/sq by conventional Ti salicide technology in gates shorter than 0.4 µm due to increase in gate resistance caused by agglomeration and lack of phase transition.

Single-drain PMOSFET's with a very shallow source and drain were fabricated using a new doping method called rapid vapor-phase doping (RVD). This process is carried out in hydrogen atmosphere using B2H6 as a source gas. By varying flow rate of B2H6 and the doping time, shallow boron doped layers which are suitable for source and drain regions of MOSFET's are formed. The fabricated RVD-PMOSFET's have 50-nm source and drain regions with peak concentration of 41020 cm-3 which were formed under the condition of 800, B2H6 flow rate of 50 ml/min. The junction depth was one third of those formed by conventional low-energy BF2 ion implantation. RVD-PMOSFET's showed normal operation down to poly-Si gate length Lg of 0.18 µm. The advantage of shallow junction was clearly shown by the threshold voltage roll-off characteristics, that is, it was suppressed down to 0.18 µm, whereas in conventional device, roll-off occurred below 0.6 µm. This better short channel behavior suggests that RVD forms shallow source and drain regions with weaker lateral diffusion. This result confirms that RVD is an effective method for forming shallow junctions for MOSFET's.

Characterization of silicon devices incorporating the capacitor which uses ferroelectric thin films as capacitor dielectrics is presented. As cases in point, a DRAM cell capacitor and an analog/digital silicon IC using the thin film of barium strontium titanate (Ba1-xSRxTiO3) are examined. Production and characterization of the ferroelectric thin films are also described, focusing on a Metal Organic Deposition technique and liquid source CVD.

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.

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.

A 0.25-µm BiCMOS technology has been developed using three sophisticated technologies; the HSST/BiCMOS device, synchrotron orbital radiation (SOR) X-ray lithography, and an advanced two-level metallization. The HSST/BiCMOS provides a 25.4-ps double-poly bipolar device using High-performance Super Self-Aligned Process Technology (HSST), and a 42 ps/2 V CMOS inverter. SOR lithography allows a 0.18 µm gate and 0.2 µm via-hole patternings by using single-level resists. The metallization process features a new planarization technique of the 0.3-µm first wire, and a selective CVD aluminum plug for a 0.25 µm via-hole with contact resistance lower than 1Ω. These 0.25-µm technologies are used to successfully fabricate a 4 KG 0.25 µm CMOS gate-array LSI on a BiCMOS test chip of 12 mm square, which operates at 58 ps/G at 2 V. This result demonstrates that SOR lithography will pave the way for the fabrication of sub-0.25-µm BiCMOS ULSIs.

There has been growing interest in Broadband ISDN (B-ISDN) based on ATM (Asynchronous Transfer Mode) technologies, since ATM is expected to support a wide range of applications through high-speed and flexible multimedia communication capabilities. This paper reviews and discusses technical issues on multimedia communication protocols and services from the integration points of view of computer and communication technologies. An ISDN-based distributed multimedia and multi-party desktop conference system called MERMAID is introduced as an example which offers highly-sophisticated functions for remote collaborations among multiple users. This system, which was developed in early 1989 and has been used for daily research work since then, involves B-ISDN key technologies related to multimedia and multicast protocols, and computer architecture for groupware applications.