This paper describes a sparse realization of passive reduced-order interconnect models via PRIMA to provide the SPICE compatible models. It is demonstrated that, if the SPICE models are directly realized so that the reduced-order equations obtained via PRIMA are stamped into the MNA matrix, the simulations of networks containing the macromodels become computationally inefficient when size of the reduced-order equations is relatively large. This is due to dense coefficient matrices of the reduced-order equations resulting from congruent transformations in PRIMA. To overcome this disadvantage, we propose a sparse realization of the reduced-order models. Since the expression is equivalent to the reduced-order equations, the passivity of the SPICE models generated is also guaranteed. Computational efficiency on SPICE is demonstrated in performing the transient analysis of circuits containing the proposed macromodels.

With the progress of integration of circuits and PCBs (Printed Circuit Boards), novel techniques have been required for verification of signal integrity. Noise analysis of the power/ground planes is one of the most important issues. This paper describes a high-speed simulator for PCBs which contain the interconnects with nonlinear terminations. This simulator is based on the environmental tool ASSIST (Assistant System for Simulation Study) constructed for development of the circuit simulators, and is combined with PRIMA (Passive Reduced-Order Interconnect Macromodeling Algorithm). In this simulator, an efficient implementation of PRIMA is considered with using a voltage-controlled current source (VCCS) model. Finally, this simulator is applied to the analysis of power/ground planes of the simple PCBs, and the validity is verified.

Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = pr q. It has been reported that RSA decryption speed can be greatly improved by using N = pr q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = pr q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = pr q for large r and gives a new characterization of r such that factoring integers N = pr q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.

For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical programming techniques have been used and proved to be very useful. In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combinatorial optimization problems.

In this paper, we show two process allocation schemes to tolerate multiple faults when the primary-backup replication method is used. The first scheme, called multiple backup scheme, is running multiple backup processes for each process to tolerate multiple faults. The second scheme, called regenerative backup scheme, is running only one backup process for each process, but re-generates backup processes for processes that do not have a backup process after a fault occurrence to keep the primary-backup process pair available. In both schemes, we propose heuristic process allocation methods for balancing loads in spite of the occurrence of faults. Then we evaluate and compare the performance of the proposed heuristic process allocation methods using simulation. Next, we analyze the reliability of two schemes based on their fault-tolerance capability. For the analysis of fault-tolerance capability, we find the degree of fault tolerance for each scheme. Then we find the reliability of each scheme using Markov chains. The comparison results of two schemes indicate that the regenerative single backup process allocation scheme is more suitable than the multiple backup allocation scheme.

This paper presents a new methodology for diagnosing transistor leakage faults in a CMOS circuit by using both IDDQ and logic value information. A hierarchical procedure is used to identify and delete impossible fault candidates efficiently and a procedure is employed to generate diagnostic tests for improving diagnostic resolution. A novel approach for handling the intermediate output voltage of a faulty gate is used in new methods for fault simulation and diagnostic test generation based on primary output values. Experimental results on ISCAS85 circuits show the effectiveness of the proposed methodology.

One serious problem affecting the rest and active state images obtained during a functional MRI (fMRI) study is that of involuntary subject movements inside the magnet while the imaging protocol is being carried out. The small signal intensity rise and small activation areas observed in the fMRI results, such as the statistical maps indicating the significance of the observed signal intensity difference between the rest and active states for each pixel, are greatly affected even by head displacements of less than one pixel. Near perfect alignment in the subpixel level of each image with respect to a reference, then, is necessary if the results are to be considered meaningful, specially in a clinical setting. In this paper we report the brain displacements that take place during a fMRI study with an image alignment method based on a refined crosscorrelation function which obtains fast (non-iterative) and precise values for the inplane rotation and X and Y translation correction factors. The performance of the method was tested with phantom experiments and fMRI studies using normal subjects executing a finger-tapping motor task. In all cases, subpixel translations and rotations were detected. The rest and active phases of the time course plots obtained from pixels in the primary motor area were well differentiated after only one pass of the motion correction program, giving enhanced activation zones. Other related areas such as the supplementary motor area became visible only after correction, and the number of pixels showing false activation was reduced.

In this paper, we give a new approach to the computation of primary decomposition and associated prime components of a zero-dimensional polynomial ideal (f1,f2,. . . ,fn), where fi are multivariate polynomials on Z (the ring of integer). Over the past several years, a considerable number of studies have been made on the computation of primary decomposition of a zero-dimensional polynomial ideal. Many algorithms to compute primary decomposition are proposed. Most of the algorithms recently proposed are based on Groebner basis. However, the computation of Groebner basis can be very expensive to perform. Some computations are even impossible because of the physical limitation of memory in a computer. On the other hand, recent advance in numerical methods such as homotopy method made access to the zeros of a polynomial system relatively easy. Hence, instead of Groebner basis, we use the zeros of a given ideal to compute primary decomposition and associated prime components. More specifically, given a zero-dimensional ideal, we use LLL reduction algorithm by Lenstra et al. to determine the integer coefficients of irreducible polynomials in the ideal. It is shown that primary decomposition and associated prime components of the ideal can be computed, provided the zeros of the ideal are computed with enough accuracy. A numerical experiment is given to show effectiveness of our algorithm.

In this paper, we propose a new design method to construct the highly reliable ATM network based on the virtual path (VP) concept. Through our method, we can guarantee a network survivability, by which we mean that connectivity between every pair of two end nodes is assured even after the failure, and that quality of service (QoS) requirements of each VC connection are still satisfied. For achieving a reliable network, every VP connection between two end nodes is equipped with a secondary VP connection such that routes of primary and secondary VPs are established on completely disjoint physical paths. Our primary objective of the current paper is that the construction cost of the VP-based network with such a survivability is minimized while the QoS requirement of traffic sources in fulfilled. For this purpose, after all the routes of VPs are temporarily established by means of the shortest paths, we try to minimize the network cost through (1) the alternation of VP route and (2) the separation of a single VP into several VPs, and optionally through (3) the introduction of VCX nodes. Through numerical examples, we show how the increased cost for the reliable network can be sustained by using our design method.

In 1985, Kues et al. (Bioelectromagnetics, 6, pp.177-188, 1985) reported that corneal endothelial abnormalities were observed after a 4-hour exposure of anesthetized monkey eyes to 2.45GHz CW. We have traced their experimental study without anesthetization. Although we irradiated with power density exceeding the threshold of 30mW/cm2 obtained by them, we could not observe the same abnormalities as they did.

For improving the RSA cryptosystem, more desirable conditions on key structures have been intensively studied. Recently, M.J.Wiener presented a cryptanalytic attack on the use of small RSA secret exponents. To be secure against the Wiener's attack, the size of a secret exponent d should be chosen more than one-quarter of the size of the modulus n = pq (in bits). Besides, it is more desirable, in frequent cases, to make the public exponent e as small as possible. However if small d is chosen first, in such case as the digital signature system with smart card, the size of e is inevitably increased to that of n when we use the conventional key generation algorithm. This paper presents a new algorithm, Algorithm I, for generating of the secure RSA keys against Wiener's attack. With Algorithm I, it is possible to choose the smaller sizes of the RSA exponents under certain conditions on key parameters. For example, with Algorithm I, we can construct the RSA keys with the public exponent e of two-thirds and secret exponent d of one-third of the size of modulus n (in bits). Furthermore we present a modified version of Algorithm I, Algorithm II, for generating of the strong RSA keys having the difficulty of factoring n. Finally we analyze the performances of Algorithm I and Algorithm II.

In this paper, we present an efficient method for the fault simulation of the reconvergent fan-out stem. Our method minimizes the fault propagating region by analyzing the topology of the circuit, whose region is smaller than that of Tulip's. The efficiency of our method is illustrated by experimental results for a set of benchmark circuits.

A fully integrated digital PLL (Phase Locked Loop) with on-chip CMOS oscillator is described. Nominal division number of the variable divider is automatically tuned in this digital PLL and this feature makes it possible to widen the pull-in range. In general, output jitter may increase if the pull-in range is widened. To overcome this problem, output jitter is reduced by utilizing the dual loop architecture. Wide pull-in range enables us on-chip oscillator, which is not so precise as the expensive crystal oscillator. This CMOS oscillator must be carefully designed to be stable against the temperature and the supply voltage variations. Using these digital PLL techniques, together with the on-chip CMOS oscillator, a fully integrated PLL can be achieved. Circuits are designed for 1.544 Mbit/s ISDN primary rate interface, and 6.25% pull-in range is obtained.