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 R²_press statistic upon a parameter in SIM is taken into account and by maximizing R²_press 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 R²_press statistic. The effectiveness of presented implementation scheme is demonstrated by several numerical examples as well as a statistical circuit analysis example.

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.

We have studied a circuit partitioning approach in the view of parallel circuit simulation on a MIMD parallel computer. In parallel circuit simulation, a circuit is partitioned into equally sized subcircuits while minimizing the number of interconnection nodes. Besides circuit partitioning time should be short enough compared with the total simulation time. From the details of circuit simulation time, we found that balancing subcircuits is critical for low parallel processing, whereas minimizing the interconnection nodes is critical for highly parallel processing. Our circuit partitioning approach consists of four steps： Grouping transistors, initial partitioning the transistor-groups, minimizing the number of interconnection nodes, and balancing the subcircuits. It is based on an algorithmic approach, and can directly control the tradeoffs between balancing subcircuits and minimizing the interconnection nodes by adjusting the parameters. We partitioned a test circuit with 3277 transistors into 4, 9, ... , 64 subcircuits, and did parallel simulations using PARACS, our parallel circuit simulator, on an AP1000 parallel computer. The circuit partitioning time was short enough-less than 3 percent of the total simulation time. The highest performance of parallel analysis using 49 processors was 16 times that of a single processor, and that for total simulation was 9 times.

The scope of this paper is the realization of FIR digital filters with an emphasis on linear phase and maximally flat cases. The transfer functions of FIR digital filters are polynomials and polynomial evaluation algorithms can be utilized as realization schemes of these filters. In this paper we investigate the application of a class of polynomial evaluation algorithms called "recursive triangles" to the realization of FIR digital filters. The realization of an arbitrary transfer function using De Casteljau algorithm, a member of the recursive triangles used for evaluating Bernstein polynomials, is studied and it is shown that in some special and important cases it yields efficient modular structures. Realization of two dimensional filters based on Bernstein approximation is also considered. We also introduce recursive triangles for evaluating the power basis representation of polynomials and give a new multiplier-less maximally flat structure based on them. Finally, we generalize the structure further and show that Chebyshev polynomials can also be evaluated by the triangles. This is the triangular counterpart of the well-known Chebyshev structure. In general,the triangular structures yield highly modular digital filters that can be mapped to an array of concurrent processors resulting in high speed and effcient filtering specially for maximally flat transfer functions.

This paper deals with the size of switching functions in Exclusive-OR sum-of-products expressions (ESOPs). The size is the number of products in ESOP. There are no good algorithms to find an exact minimum ESOP. Since the exact minimization algorithms take a time in double exponential order, it is almost impossible to minimize ESOPs for an arbitrary n-variable functions with n5. Then,it is necessary to study the size of some concrete functions. These concrete functions are useful for testing heuristic minimization algorithms. In this paper we present the lower bounds on size of periodic functions in ESOPs. A symmetric function is said to be periodic when the vector of weights of inputs X such that f(X)1 is periodic. We show that the size of a 2^t+1-periodic function with rank r is proportional to n^2t+r, where t0 and 0r2^t, i.e., in polynomial order,and thet the size of a (2s+1)2^t-periodic function with s0 and t0 is greater than or equal to (3/2)^n-(2s+1)2t, i.e., in exponential order. The concrete function the size of which is greater than or equal to 32(3/2)^n-8 is presented. This function requires the largest size among the concrete functions the sizes of which are known. Some results for non-periodic symmetric functions are also given.

This paper describes the current implementation and experimental results of a hardware/software codesign system for ASIP (Application Specific Integrated Processor) development： the PEAS-I System. The PEAS-I system accepts a set of application programs written in C language, associated data set, module database, and design constraints such as chip area and power consumption. The system then generates an optimized CPU core design in the form of an HDL as well as a set of application program development tools such as a C compiler, an assembler and a simulator. Another important feature of the PEAS-I system is that the system is able to give accurate estimations of chip area and performance before the detailed design of the ASIP is completed. According to the experimental results, the PEAS-I system has been found to be highly effective and efficient for ASIP development.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

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 proposes the Total High Performance Time as a performance-related reliability measure in degradable/recoverable real-time systems. This measure reflects the effect of system behavior in pending states that are temporary states between the normal state and degraded states where the system operates in a degraded mode as a consequence of component failures. Such systems have to perform not only normal procedures but also error/recovery procedures in pending states, so the performance there is lower than that in the degraded states. In real-time systems, if performance is less than a lower limit, the response time for on-line transactions cannot meet the deadline. The consequences of failing to meet the deadline could be system failure. Therefore, the system reliability is affected significantly by whether the performance there is higher than the lower limit or not. A state where the level of performance is higher than the lower limit is called a High Performance State. We define the Total High Performance Time as the total time that the system spends operating in High Performance States. Moreover, this paper explains how to utilize the Total High Performance Time in system design. We model a method of controlling a system in pending states by using Extended Stochastic Petri Nets and obtain the characteristics necessary for evaluating the Total High Performance Time by analyzing the model. This approach is applied to a storage system that controls mirrored disks, and shown to be helpful for designing a method of controlling a system in pending states, which has been considered difficult because of the trade-off between performance and reliability.

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.

Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S ²).Next we consider the d₂-transmission number sequence so that the distance function is defined by a special convex function.

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.

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.

A sequence of nonnegative integers S=(s₁, s₂, , s_n) is graphical if there is a graph with vertices v₁,v₂, ,v_n such that deg(v_i)=s_i 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.

Upper bounds on the bit error probability and repeat request probability, and lower bounds on the throughput are derived for a Hybrid-ARQ scheme that employs trellis-coded modulation on a fading dispersive channel. The receiver employs a modified Viterbi algorithm to perform joint maximum likelihood sequence estimation (MLSE) equalization and decoding. Retransmissions are generated by using the approach suggested by Yamamoto and Itoh. The analytical bounds are extended to trellis-coded modulation on fading dispersive channels with code combining. Comparison of the analytical bounds with simulation results shows that the analytical bounds are quite loose when diversity reception is not employed. However, no other analytical bounds exist in the literature for the trellis-coded Hybrid ARQ system studied in this paper. Therefore, the results presented in this paper can provide the basis for comparison with more sophisticated analytical bounds that may be derived in the future.

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.

For a discrete Lyapunov matrix equation, we present another such equation that shares the solution to the original one. This renders some existing lower bounds for measures of the size of the solution meaningful, when they yield only trivial bounds. A generalization of this result is suggested.

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.