An idea of optimal output permutation of multiple-valued sum-of-products expressions is presented. The sum-of-products involve the TSUM operator on the MIN of window literal functions. Some bounds on the maximum number of implicants needed to cover an output permuted function are clarified. One-variable output permuted functions require at most p1 implicants in their minimal sum-of-products expressions, where p is the radix. Two-variable functions with radix between three and six are analyzed. Some speculations of maximum number of the implicants could be established for functions with higher radix and more than 2-variables. The result of computer simulation shows that we can have a saving of approximately 15% on the average using permuting output values. Moreover, we demonstrate the output permutation based on the output density as a simpler method. For the permutation, some speculation is shown and the computer simulation shows a saving of approximately 10% on the average.

In this paper, we are concerned with a problem of obtaining an approximate solution of a finite-dimensional nonlinear equation with guaranteed accuracy. Assuming that an approximate solution of a nonlinear equation is already calculated by a certain numerical method, we present computable conditions to validate whether there exists an exact solution in a neighborhood of this approximate solution or not. In order to check such conditions by computers, we present a method using rational arithmetic. In this method, both the effects of the truncation errors and the rounding errors of numerical computation are taken into consideration. Moreover, based on rational arithmetic we propose a new modified Newton interation to obtain an improved approximate solution with desired accuracy.

The mechanism of environment-dependent self-organization of "positional information" in a coupled nonlinear oscillator system is proposed as a new principle of realtime coordinative control in biological distributed system. By modeling the pattern formation in tactic response of Physarum plasmodium, it is shown that a global phase gradient pattern self-organized by mutual entrainment encodes not only the positional relationship between subsystems and the total system but also the relative relationship between internal state of the system and the environment.

Process and device technologies of CMOS devices for low-voltage operation are described. First, optimum power-supply voltage for CMOS devices is examined in detail from the viewpoints of circuit performance, device reliability and power dissipation. As a result, it is confirmed that power-supply voltage can be reduced without any speed loss of the CMOS device. Based upon theoretical understanding, the author suggests that lowering threshold voltage and reduction of junction capacitance are indispensable for CMOS devices with low-voltage supply, in order to improve the circuit performance, as expected from MOS device scaling. Process and device technologies such as Silicon On Insulator (SOI) device, low-temperature operation and CMOS Shallow Junction Well FET (CMOS-SJET) structure are reviewed for reduction of the threshold voltage and junction capacitance which lead to high-seed operation of the COMS device at low-voltage.

This paper addresses onboard processing architecture employing direct regeneration. The advantage of direct regeneration is its hardware simplicity, even though the bit error rate performance is slightly inferior to that of demodulation-remodulation scheme with coherent detection. The channel filtering schemes as well as achievable capacities are examined by computer simulation. It is found that the system with direct regeneration has advantage in channel capacity and transmit earth station e.i.r.p. for small earth stations. A possible configuration of direct regeneration onboard in future satellite systems is proposed.

This paper describes a monolithic 10-b A/D converter that realized a maximum conversion frequency of 300 MHz. Through the development of the interpolated-parallel scheme, the severe requirement for the transistor Vbe matching can be alleviated drastically, which improves differential nonlinearity (DNL) significantly to within 0.4 LSB. Furthermore, an extremely small input capacitance of 8 pF can be attained, which translates into better dynamic performance such as SNR of 56 dB and THD of 59 dB for an input frequency of 10 MHz. Additionally, the folded differential logic circuit has been developed to reduce the number of elements, power dissipation, and die area drastically. Consequently, the A/D converter has been implemented as a 9.0 4.2-mm2 chip integrating 36K elements, which consumes 4.0 W using a 1.0-µm-rule, 25-GHz ft, double-polysilicon self-aligned bipolar technology.

Under the conditions of Poisson arrivals and single copy transmission, we designed a minimum delay protocol for packet satellite communications. The approach is to assume a hybrid random-access/reservation protocol, derive its average delay and minimize the delay with respect to all tunable system parameters. We found that for minimum average delay,1) a spare reservation should normally but not always be made for each packet transmission.2) all unreserved slots (i.e. Aloha slots) should be filled with a packet rate of one per slot whenever possible. In other words, the utilization of Aloha slots should be maximized.3) an optimum balance between transmitting packets and making reservations before transmission should be maintained.

The performance of copper interconnects formed by the low-kinetic-energy ion bombardment process has been investigated. The copper films formed on SiO2 by this technology under a sufficient amount of ion energy deposition exhibit perfect orientation conversion from Cu (111) to Cu (100) upon post-metallization thermal annealing. We have discovered such crystal orientation conversion is always accompanied by a giant-grain growth as large as 100 µm. The copper film resistivity decreases due to the decrease in the grain boundary scattering, when the giant-grain growth occurs in the film. The resistivity of giant-grain copper film at a room temperature is 1.76 µΩcm which is almost equal to the bulk resistivity of copper. Furthermore, a new-accelerated electromigration life-test method has been developed to evaluate copper interconnects having large electromigration resistance within a very short period of test time. The essence of the new method is the acceleration by a large-current-stress of more than 107 A/cm2 and to utilize the self heating of test interconnect for giving temperature stress. In order to avoid uncontrollable thermal runaway and resultant interconnect melting, we adopted a very efficient cooling system that immediately removes Joule heat and keeps the interconnect temperature constant. As a result, copper interconnects formed by the low-kinetic-energy ion bombardment process exhibit three orders of magnitude longer lifetime at 300 K than Al alloy interconnects.

Two kinds of nitrided ultrathin (510 nm) SiO2 films were formed on the silicon (100) face using rapid thermal NH3-nitridation (RTN) and rapid thermal N2O-oxynitridation (RTON) technologies. The MOS capacitors with RTN SiO2 film showed that by Fowler-Nordheim (F-N) electron injection, both electron trap density and low-field leakage increase by the NH3-nitridation. In addition, the charge-to-breakdown (QBD) value decreases owing to NH3-nitridation. By contrast, RTON SiO2 films exhibited extremely low electron trap density, almost no increase of the leakage current, and large QBD value above 200C/cm2. The oxide film composition was evaluated by secondary ion mass spectroscopy (SIMS). The chemical bonding states were also examined by Fourier transform-infrared reflection attenuated total reflectance (FT-IR ATR) and X-ray photoelectron spectroscopy (XPS) measurements. These results indicate that although a large number of nitrogen (N) atoms are incorporated by the RTN and RTON, only the RTN process generates the hydrogen-related species such as NH and SiH bounds in the film, whereas the RTON film indicates only SiN bonds in bulk SiO2. From the dielectric and physical properties of the oxide films, it is considered that the oxide wearout by high-field stress is the result of the electron trapping process, in which anomalous leakage due to trap-assisted tunneling near the injected interface rapidly increases, leading to irreversible oxide failure.

The effects of low temperature etching for sub-half micron multi-layer resist are investigated. The low temperature etching with pure O2 gas provides higher anisotropic profiles than with an additional gas such as Cl2, N2. This is caused by the difference in the formative process of the side wall protection. With pure O2 gas at 80, highly anisotropic profiles for 0.35 µm patterns can be performed while the maximum tolerable width loss is below 0.03 µm.

Fiber-optic local area networks (LANs) with Fiber Distributed Digital Interface (FDDI) protocol have come into use as backbones connecting other small LANs. This paper describes the current status of LANs, reviews a number of issues that stand in the way of further development and look at the future of LANs. Demands for wide-area networks (WANs) connecting LANs and multimedia LANs including voice and image capability has been extremely strong, spurring progress in geographical expansion and throughput increase, now over 100Mbit/s. The logical choice of transmission medium for next-generation systems is single-mode optical fiber, not only for backbone LANs but also, eventually, for floor LANs.

Single-mode fibers with intentionally induced periodical residual strains (IIPRS) along the fiber length are proposed for the suppression of the stimulated Brillouin scattering (SBS). A change of the residual strain along a fiber will change the Brillouin frequency shift, resulting in a broadening of the Brillouin gain profile. Such an increase of the line-width of the gain profile will cause a decrease of the gain coefficient which will raise the threshold power of the stimulated Brillouin scattering in optical fibers. Two types of the IIPRS fibers were fabricated. The residual strain of one IIPRS fiber is modified rectangularly while that of the other is changed triangularly. The measured spectra of the SBS are compared with that of a fiber with a constant strain. Using a novel mathematical model presented in this report, the possible improvements of the threshold powers for these two IIPRS fibers over the constant-strain fiber can be assessed through the SBS spectra. Finally, the achieved improvements are confirmed with the experimental results. The estimated improvement of the threshold for the IIPRS fiber with the rectangular profile is 2.9dB while the measured is 2.4dB. In case of the IIPRS fiber with a triangular profile, the improvement of the threshold is 5.4dB by estimation and is 5.1dB by experiment. While the limit of the threshold improvement for rectangular IIPRS fibers is 3dB, the threshold improvement for triangular IIPRS fibers is limited only by the allowable deviation of the tension applied during the drawing of fibers. It is estimated that a 5dB improvement is not difficult to realize.

Self-aligned aluminum-gate MOSFET's have been successfully fabricated by employing ultraclean ion implantation technology. The use of ultra high vacuum ion implanter and the suppression of high-energy ion-beam-induced metal sputter contamination have enabled us to form ultra-shallow low-leakage pn junctions by furnace annealing at a temperature as low as 450. The fabricated aluminum-gate MOSFET's have exhibited good electrical characteristics, thus demonstrating a large potential for application to realizing ultra-high-speed integrated circuits.

We designed and fabricated a prototype 0.4-µm-gate CMOS/SIMOX PLL LSI in order to verify the potential usefulness of ultrathin-film SIMOX technology for creating an extremely low-power LSI containing high-speed circuits operating at frequencies of at least 1 GHz and at low supply voltages. This PLL LSI contains both high-frequency components such a prescaler and low-frequency components such as a shift register, phase frequency comparator, and fixed divider. One application of the LSI could be for synthesizing communication band frequencies in the front-end of a battery-operated wireless handy terminal for personal communications. At a supply voltage of 2 V, this LSI operates at up to 2 GHz while dissipating only 8.4 mW. Even at only 1.2 V, 1 GHz-operation can be obtained with a power consumption of merely 1.4 mW. To explain this low-power feature, we extensively measured the electrical characteristics of individual CMOS/SIMOX basic circuits as well as transistors. Test results showed that the high performance of the LSI is mainly due to the advanced nature of the CMOS/SIMOX devices with low parasitic capacitances around source/drain regions and to the new circuit design techniques used in the dual-modulus prescalar.

Phosphorus-doped amorphous or polycrystalline silicon can yield a conformal, low resistance, thermallystable plug for the high-aspect-ratio, sub-half-micron contactholes found in current development prototypes of future 64 and 256 Mega-bit DRAMs. When directly contacted to a silicide layer, however, such as WSix found in polycide gate or bit line metallization/contact structures, the outdiffusion of phosphorus from the doped-silicon layer into the silicide can occur, resulting in an increase in resistance. The characteristics of both the doped-silicon and WSix layers influence the outdiffusion. The grain size of the doped silicon appears to control diffusion at the WSix/doped-silicon interface while the transition of WSix from an as-deposited amorphous to a post-annealed polycrystalline state appears to help cause uniform phosphorus diffusion throughout the silicide film. The results of phosphorus pre-doping of the silicide to reduce the effects of outdiffusion are dependent upon the relative material volumes and interfacial areas of the layers. Due to the effectiveness of the TiN barrier layer/Ti contact layer structure used in Al-based contacts, Ti and TiN were evaluated on their ability to prevent phosphorus outdiffusion. Ti reacts easily with doped silicon and to some extent with WSix, thereby allowing phosphorus to outdiffuse through the TiSix into the overlying WSix. TiN, however, is very effective in preventing phosphorus outdiffusion and preserving polycide interface smoothness. A WSix/TiN/Ti metallization layer on an in situ-doped (ISD) silicon layer with ISD silicon-plugged contactholes yields contact resistances comparable to P+-implanted or non-implanted WSix layers on similar ISD layers/plugs for contact sizes greater than approximately 0.5 µm but for contacts of 0.4 µm or below the trend in contact resistance is lowest for the polycide with TiN barrier/Ti contact interlayers. A 20 nm-thick TiN film retains its barrier characteristics even after a 4-hour 850 anneal and is applicable to the silicide-on-doped-silicon structures of future DRAM and other ULSI devices.

Copper contamination behavior is studied, depending on the pH level, conductivity type P or N of a silicon substrate, and contamination method of copper. If the pH level of a copper containing solution is adjusted by using ammonia, copper atoms and ammonia molecules produce copper ion complexes. Accordingly, the amount of copper adsorption on the substrate surface is decreased. When N-type silicon substrates are contaminated by means of copper containing solutions, copper atoms on the surfaces diffuse into bulk crystal even at room temperature. But for P-type silicon substrates, copper atoms are transferred into bulk crystal only after high temperature annealing. In the case of silicon substrates contaminated by contact with metallic copper, no copper atom diffusion into bulk crystal was observed. The above mentioned copper contamination behavior can be explained by the charge transfer interaction of copper atoms with silicon substrates.

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

In this paper we propose a new application of Wu's mechanical theorem proving method to reconstruct polyhedra in 3-D space from their projection image. First we set up three groups of equations. The first group is of the geometric relations expressing that vertices are on a plane segment, on a line segment, and forming angle in 3-D space. The second is of those relations on image plane. And the rest is of the relations between the vertices in 3-D space and their correspondence on image plane. Next, we classify all the groups of equations into two sets, a set of hypotheses and a conjecture. We apply this method to seven cases of models. Then, we apply Wu's method to prove that the hypotheses follow the conjecture and obtain pseudodivided remainders of the conjectures, which represent relations of angles or lengths between 3-D space and their projected image. By this method we obtained new geometrical relations for seven cases of models. We also show that, in the region in image plane where corresponding spatial measures cannot reconstructed, leading coefficients of hypotheses polynomials approach to zero. If the vertex of an image angle is in such regions, we cannot calculate its spatial angle by direct manipulation of the hypothesis polynomials and the conjecture polynomial. But we show that by stability analysis of the pseudodivided remainder the spatial angles can be calculated even in those regions.

In this letter, we propose an algorithm to estimate the optical flow fields based on a hierarchical structure composed of spatio-temporal image pyramids obtained from repetitive application of the Gaussian filtering and decimation in both the spatial and temporal domain. In our approach, an inter-level motion smoothness constraint between adjacent pyramid levels is introduced to estimate a unique optical flow field. We show that the pyramid structure allows us to employ the multigrid algorithm, which is known to accelerate the convergence rate. The multigrid algorithm provides a scheme for efficient combination of local and global information to estimate the optical flow field. The experimental results reveal that the combination of local and global information yields a fast convergence behavior and accurate motion estimation results.

This paper presents an optimal constraint graph generation algorithm for graph-based one-dimensional layout compaction. The first published algorithm for this problem was the shadow-propagation algorithm. However, without sophisticated implementation of a shadow-front, complexity of the algorithm could fall into O(n2), where n is the number of layout objects. Although our algorithm, called the enhanced plane-sweep based graph generation algorithm, is an extension of the shadow-propagation algorithm, such a drawback is resolved by introducing an enhanced plane-sweep technique. The algorithm maintains multiple shadow-fronts simultaneously by storing them in a work-list called previous-boundary. Since a balanced search tree is selected for implementation of the worklist, total complexity of the algorithm is O(n log n) which is optimal. Experimental results show that the enhanced plane-sweep based graph generation algorithm runs in almost linear time with respect to the number of layout objects and is faster than the perpendicular plane-sweep algorithm which is also optimal in terms of time complexity.