Due to the large number of I/O's in a Ball-Grid-Array (BGA) package, routing becomes more and more an important work. A ring-based router for the BGA package is presented in this paper to interconnect each I/O pad of a chip to a corresponding ball distributed on the substrate area. The major phases for the router consist of layer assignment, topological routing, and physical routing. Using this router, we can generate an even distribution of planar and any-angle wires to improve manufacturing yield. We have also conducted various testing examples to verify the efficiency of this router. Experiments show that the router produces very good results, far better than the manual design, thus it can be applied to the practical packaging of integrated circuits.

RSPICE, a fast timing simulator for large digital MOS circuits, is presented in this paper. A new table-based region-wise linear MOS transistor model and the analytical solution of the generic sub-circuit primitive are applied to calculate the transient response of digital MOS circuits. The body effect of pass transistors is included in the MOS model and the floating capacitor network can be handled by this sub-circuit primitive as well. In RSPICE, MOS transistors with a DC path are grouped into a DC-connected block (DCCB), and DCCBs with a feedback path are combined as a strongly connected component (SCC). RSPICE orders SCCs by Tarjan's algorithm and simulates ordered SCCs one by one. DCCBs are basic cells in RSPICE and any DCCB can be mapped into one or more sub-circuit primitives. In order to calculate the transient response of these primitives analytically, RSPICE approximates the input signals of the primitive by piecewise linear functions. To compromise the simulation accuracy and run time, partial waveform and partial time convergent (PWPTC) combined with dynamic windowing technique is applied to simulate SCCs. Other key issues of RSPICE, such as circuit partition, pass-transistor and floating-capacitor processing, simulation-flow control and waveform modification are also discussed in detail. Compared with HSPICE , the simulation result of RSPICE is very accurate with an error less than 3%, but the speed is 1-2 orders over HSPICE.

This paper presents an algorithm for the scan-chain optimization problem in multiple-scan design methodology. The proposed algorithm, which consists of four phases, first determines pairs of scan-in and scan-out pins (Phase 1), and then assigns flip-flops to scan-paths by using a graph theoretical method (Phase 2). Next the algorithm decides connection-order of flip-flops in each scan-path by using TSP (Traveling Salesman Problem) heuristics (Phase 3), and finally exchanges flip-flops among scan-paths in order to reduce total scan-path length (Phase 4). Experiments using actual design data show that, for ten scan-paths, our algorithm achieved a 90% reduction in scan-test time at the expense of a 7% total scan-path length increase as compared with the length of a single optimized scan-path. Also, our algorithm produced less total scan-path length than other three possible algorithms in a reasonable computing time.

A resonant-tunneling-diode (RTD) based sense amplifier circuit design has been proposed for the first time to envision a very high-speed and low-power memory system that also includes refresh-free, compact RTD-based memory cells. By combining RTDs with n-type transistors of conventional complementary metal oxide semiconductor (CMOS) devices, a new quantum MOS (Q-MOS) family of logic circuits, having very low power-delay product and good noise immunity, has recently been developed. This paper introduces the design and analysis of a new QMOS sense amplifier circuit, consisting of a pair of RTDs as pull-up loads in conjunction with n-type pull-down transistors. The proposed QMOS sensing circuit exhibits nearly 20% faster sensing time in comparison to the conventional design of a CMOS sense amplifier. The stability analysis done using phase-plot diagram reveals that the pair of back-to-back connected static QMOS inverters, which forms the core of the sense amplifier, has meta-stable and unstable states which are closely related to the I-V characteristics of the RTDs. The paper also analyzes in details the refresh-free memory cell design, known as tunneling static random access memory (TSRAM). The innovative cell design adds a stack of two RTDs to the conventional one-transistor dynamic RAM (DRAM) cell and thereby the cell can indefinitely hold its charge level without any further periodic refreshing. The analysis indicates that the TSRAM cell can achieve about two orders of magnitude lower stand-by power than a conventional DRAM cell. The paper demonstrates that RTD-based circuits hold high promises and are likely to be the key candidates for the future high-density, high-performance and low-power memory systems.

It is known that AND-EXOR two-level networks obtained by AND-EXOR expressions with positive literals are easily testable. They are based on the single-rail-input logic, and require (n+4) tests to detect their single stuck-at faults, where n is the number of the input variables. We present three-level networks obtained from single-rail-input OR-AND-EXOR expressions and propose a more easily testable realization than the AND-EXOR networks. The realization is an OR-AND-EXOR network which limits the fan-in of the AND and OR gates to n/r and r respectively, where r is a constant (1 r n). We show that only (r+n/r) tests are required to detect the single stuck-at faults by adding r extra variables to the network.

In this paper, we present the theoretical development to stabilize a class of uncertain time-delay system. The system under consideration is described in state space model containing distributed delay, uncertain parameters and disturbance. The main idea is to transform the system state into an equivalent one, which is easier to analyze its behavior and stability. Then, a computational method of robust controller design is presented in two parts. The first part is based on solving a Riccati equation arising in the optimal control theory. In the second part, the finite dimensional Lyapunov min-max approach is employed to cope with the uncertainties. Finally, we show how the resulting control law ensures asymptotic stability of the overall system.

We analyze the dynamics of self-organizing cortical maps under the influence of external stimuli. We show that if the map is a contraction, then the system has a unique equilibrium which is globally asymptotically stable; consequently the system acts as a stable encoder of external input stimuli. The system converges to a fixed point representing the steady-state of the neural activity which has as an upper bound the superposition of the spatial integrals of the weight function between neighboring neurons and the stimulus autocorrelation function. The proposed theory also includes nontrivial interesting solutions.

Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.

This paper clarifies the appropriate traffic domains for combination between two database schemes (i. e. , HLR database scheme and VLR database scheme) and two call routing schemes (i. e. , Redirection Routing scheme and Look-a-head Routing scheme) in the Global Mobility Network (GLOMONET), which is able to provide global roaming service for the personal telecommunication user. The appropriate domains for combination between each scheme are shown to depend on user's mobility (i. e. the frequency of a user's access to a network where the user stays, the length of the period during which the user stays in the same network). Whether the appropriate domains for the HLR database scheme exist depends only on the frequency of the user's access to the network. When there are appropriate domains for the HLR database scheme, increasing the frequency of the user's access to the network, decreasing the length of the period the user stays in the user's home network, or increasing the length of the period the user stays in a network that isn't the user's home network widens the domains where the VLR database scheme is appropriate.

When designing microwave amplifiers, it is the task to select values of the source (input generator) and load reflection coefficients for the transistor, to achieve certain amplifier performance requirements and ensure stability. For unconditionally stable transistors, simultaneous conjugate matching can be achieved using well-known design formulae. Under this condition, the gain is maximised, and the input and output ports are matched. On the other hand when the transistor is conditionally stable, source and load reflection coefficients are selected using graphical design methods, involving gain and stability circles. To eliminate the reliance on graphical techniques, this paper shows the derivation of explicit design formulae that ensure maximum gain for a minimum specified safety margin, with one port matched. In this work, the safety margin is the distance between the chosen source or load reflection coefficient and its respective stability circle. In a production environment, where the circuit and transistor parameters are subject to random variations, the safety margin therefore makes allowance for such variations. This paper shows that the design problem for conditionally stable transistors can be reduced from the selection of values for two complex variables (port terminations) to the selection of the value for just one scalar variable.

In this paper, we present a simple codeword length generation algorithm and its hardware implementation. The proposed technique is based on the dividing the Huffman table as two parts; with leading 0'bits and following bits. The method is shown to be efficient in the memory requirement and searching speed since only logic gates are needed in the implementation and searching can be process parallel without looking up the memory table. The total equivalent gates for the implementation are about only 100 gates and critical path delay is 10 ns. The results of experiments show that the proposed algorithm has a very high speed and a good performance. The designed blocks are synthesized by Compass synthesis with 0.5 µm CMOS, 3.3V, technology.

A service control node in the Advanced Intelligent Network (AIN) allocates data for customers among multiple modules and performs distributed processing of multiple transactions. In such a node, load can vary among the modules due to dispersion in the amount of traffic for each customer. It is therefore important to balance out this load variation and raise the utilization of each module in order to achieve an efficient distributed processing system. We first propose a method for balancing the load among modules by dynamically transferring customer data in units of records from high-load modules to low-load modules. Then, based on this method, a method for selecting records to be transferred between modules is also proposed. And we clarify the processor overhead for transferring records. The effect of the reduction of number of modules by load balancing is also evaluated. Based on the these results, it is shown that dynamic transferring of records is an effective scheme for balancing load among modules in a service control node of the AIN.

This paper presents a new data path synthesis algorithm which takes into account simultaneously three important design criteria: testability, design area, and total execution time. We define a goodness measure on the testability of a circuit based on three rules of thumb introduced in prior work on synthesis for testability. We then develop a stepwise refinement synthesis algorithm which carries out the scheduling and allocation tasks in an integrated fashion. Experimental results for benchmark and other circuit examples show that we were able to enhance the testability of circuits significantly with very little overheads on design area and execution time.

A software system has dynamic adaptability if it can adapt itself to dynamically changing runtime environments. As open-ended distributed systems and mobile computing systems have spread widely, the need for software systems with dynamic adaptability increases. We propose a software model with dynamic adaptability called DAS and its description language LEAD++. The basic mechanism for dynamic adaptability is called adaptable procedure. An adaptable procedure is a special kind of generic procedures (functions) whose methods are selected based upon the state of its runtime environment. Furthermore, control mechanisms of adaptable procedures -- including method selection strategies -- are realized using generic procedures. This sort of reflective architecture enables us to write a dynamically adaptable software system in highly flexible, extensible, readable and maintainable way. LEAD++ is an object-oriented reflective language that provides adaptable procedures and their control mechanisms as its basic language functionalities. We are currently implementing a prototype of LEAD++ as a pre-processor of Java. Using LEAD++, we can systematically describe dynamically adaptable applets, mobile objects, etc.

This paper proposes a new distributed connection establishment scheme involving several competing network providers in a multimedia telecommunications environment. This connection establishment scheme, which is based on the concept of open competitive bidding, enables mutual selection by users and network providers. By employing this proposed scheme, both network providers and users can pursue their own objectives, according to their own bidding and awarding strategies. In this paper, a simple bidding strategy for network providers is presented, and the effectiveness of this strategy is evaluated by means of computer simulation. It is shown that each network provider can improve its profit by adopting this strategy. In this paper, an example of utility functions for users is presented, and the effectiveness of the mechanism with which users can select a network provider is also evaluated by means of computer simulation. Each user can improve his/her utility by selecting an appropriate network provider based on this utility function.

The change over from IPv4 to IPv6 entails a potential increase in the number of records that the Registry System must maintain. Currently, only a few Network Information Centers (NICs), controlled by Internet Assigned Number Authority (IANA), operate their Registry Systems. As they concentrates data into several Registry System, it is not scalable. This paper focuses on the scalability issue in a Registry System and Mie Advanced Registry System (MARS) is proposed. Through the collaboration of independent Registry Systems, MARS ensures data consistency as well as making it possible to access data managed by other Registry Systems. A prototype system of MARS is implemented, maintained and managed on the WIDE 6bone. Some lessen from the operation of MARS give also described.

In a mobile computing environment, in which communication channels are limited and have low-bandwidths, mobile transactions are long-lived and frequently disconnected with their wireless network in processing. Such peculiarities of mobile transactions make existing transaction scheduling schemes inadequate and raise new challenging research problems. In this paper, we propose a new scheduling scheme called OTS/MT (Optimistic Timestamp Scheme for Mobile Transactions) for mobile transaction scheduling. OTS/MT is based on an optimistic approach that is suitable for low data contention, and prevents indefinite postponement and cascading delay which are major drawbacks of the existing optimistic concurrency control scheme and the timestamp ordering scheme. In addition, the OTS/MT algorithm is inherently a deadlock-free scheduling scheme. In order to schedule mobile transactions, OTS/MT postpones the detection of conflict between mobile transactions until transaction commit time to improve the performance deterioration of TO. In this paper, we attempt to show that this application of optimism to TO is justified by way of simulation.

This paper proposes a fast depth-constrained technology mapping algorithm for logic-blocks composed of tree-structured lookup tables. First, we propose a technology mapping algorithm which minimizes the number of logic-blocks if an input Boolean network is a tree. Second, we propose a technology mapping algorithm which minimizes logic depth for any input Boolean network. Finally, we combine those two technology mapping algorithms and propose an algorithm which realizes technology mapping whose depth is bounded by a given upper bound dc. Experimental results demonstrate the effectiveness and efficiency of the proposed algorithm.

Human faces convey various information, including that is specific to each individual person and that is part of mutual communication among persons. Information exhibited by a "face" is what is called "non-verbal information" and usually verbal media cannot easily describe such information appropriately. Recently, detailed studies on the processing of face images by a computer have been carried out in the engineering field for applications to communication media and human computer interaction as well as automatic identification of human faces. Two main technical topics are the recognition of human faces and the synthesis of face images. The objective of the former is to enable a computer to detect and identify users and further to recognize their facial expressions, while that of the latter is to provide a natural and impressive user interface on a computer in the form of a "face. " These studies have also been found to be useful in various non-engineering fields related to a face, such as psychology, anthropology, cosmetology and dentistry. Most of the studies in these different fields have been carried out independently up to now, although all of them deal with a "face. " Now in virtue of the progress in the above engineering technologies a common study tools and databases for facial information have become available. On the basis of these backgrounds, this paper surveys recent research trends in the processing of face images by a computer and its typical applications. Firstly, the various characteristics of faces are considered. Secondly, recent research activities in the recognition and synthesis of face images are outlined. Thirdly, the applications of digital processing methods of facial information are discussed from several standpoints: intelligent image coding, media handling, human computer interaction, caricature, facial impression, psychological and medical applications. The common tools and databases used in the studies of processing of facial information and some related topics are also described.

There are two dynamics issues in vision chips: (i) The temporal dynamics issue due to the parasitic capacitors in a CMOS chip, and (ii) the spatial dynamics issue due to the regular array of processing elements in a chip. These issues are discussed in [1]-[3] for the resistor network with only associated parasitic capacitances. However, in this paper we consider also parasitic inductances as well as parasitic capacitances for a more precise network dynamics model. We show that in some cases the temporal stability condition for the network with parasitic inductances and capacitances is equivalent to that for the network with only parasitic capacitances, but in general they are not equivalent. We also show that the spatial stability conditions are equivalent in both cases.