Masayuki TAKAHASHI Jin-Qin LU Kimihiro OGAWA Takehiko ADACHI
In this paper, we describe a worst-case design optimization approach for statistical design of integrated circuits with a circuit performance model scheme. After formulating worst-case optimization to an unconstrained multi-objective function minimization problem, a new objective function is proposed to find an optimal point. Then, based on an interpolation model scheme of approximating circuit performance, realistic worst-case analysis can be easily done by Monte Carlo based method without increasing much the computational load. The effectiveness of the presented approach is demonstrated by a standard test function and a practical circuit design example.
The discrete-time short-time Fourier transform (STFT) is known as a useful tool for analyzing and synthesizing signals. This paper introduces an extention of the well-known STFT to a general form which is more suitable for high resolutional signal analysis. A channel frequency division scheme is developed for realizing arbitrary bandwidth and center frequency so as to improve resolution performance. It is based on a nonuniform filter bank structure with integer decimation and interpolation factors. A design example of the generalized STFT using symmetric windows is given.
We give an efficient shortest path algorithm on a mesh-connected processor array for nn banded matrices with bandwidth b. We use a b/2b/2 semisystolic processor array. The input data is supplied to the processor array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n4b/21 steps.
Tadanao TSUBOTA Masahiro KAWAKITA Takahiro WATANABE
The main aim of device-level global routing is to obtain high-performance detailed routing under various layout constraints. This paper deals with global routing for analog function blocks. For analog LSIs, especially for those operating at high frequency, various layout constraints are specified prior to routing. Those constrainsts must be completely satisfied to achieve the required circuit performance. However, they are sometimes too hard to be solved by any heuristic method even if a problem is small in size. Thus, we propose a method based on the branch-and-bound algorithm, which can generate all possible solutions to find the best one. Unfortunately, the method tends to take a large amount of processing time. In order to defeat the drawbacks by accelerating the process, constraints are classified into two groups: constraints on single nets and constraints between two nets. Therefore our method consists of two parts: in the first part only constraints on single nets are processed and in the second part only constraints between two nets are processed. The method is efficient because many possible routes that violate layout constraints are rejected immediately in each part. This makes it possible to construct a smaller search tree and to reduce processing time. Additionally this idea, all nets processed in the second phase are sorted in the proper order to reduce the number of edges in the search tree. This saves much processing time, too. Experimental results show that our method can find a good global route for hard layout constraints in practical processing time, and also show that it is superior to the well-known simulated annealing method both in quality of solutions and in processing time.
We model a road network as a directed graph G(V,E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function αv with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e E whicn is defined to be the traffic f(e) passing through e in order to assign the required traffic Fst(0) from s to t along only shortest s-t paths in accordance with the distribution function αv at each vertex v.
Connectivity (of node-to-node) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine node-to-area connectivity rather than node-to-node connectivity. In a previous paper, we proposed node-to-area (NA) connectivity using area (subset of nodes) graph. In this paper, we consider a further constraint: "there is a path that does not include other nodes in the source node area." We call this property, directly NA-connected. Application of this constraint makes telecommunications networks robust against locally striking disasters. The problem of finding the maximum number of edge deletions that still preserves the direct NA-connection is shown to be NP-hard. It was shown in our previous paper that an NA-connected spanning tree is easily found; this paper shows that the problem of finding a directly NA-connected spanning tree is also NP-hard. We propose an O(|E||X|) approximation algorithm that finds a directly NA-connected spanning subgraph with an edge nummber not exceeding 2|V|3 for any NA-connected area graph that satisfies a described simple condition. (|V|,|E|,and |X| are the numbers of nodes, edges, and areas, respectively.)
Hiroki OKA Nobuaki SUGIURA Kei-ichi YASUDA
B-ISDN telecommunication systems will require signal processing speeds up to 600 Mbps or more. We must therefore consider the affects of signal reflection, signal attenuation, time dalay, and so on when designing these systems. The higher the signal speed, the larger the electrical noise induced around the connector, especially in the plated through holes (PTHs) area. This paper presents the results of our investigation focused on connector mounting configurations in the signal transmission line, especially whether or not signals transmit through the PTH in a printed circuit board (PCB). How the signal reflection characteristics depend upon transmission line configurations are discussed and experimental results and simulation analyses for a transmission line system using a small miniature A-type (SMA) connector as an example are performed. It is suggested that designs for future high-speed signal transmission circuits take into account the PTH diameter and/or the PTH pitch conditions, values for which can be determined from simulation analysis.
Cong-Kha PHAM Mamoru TANAKA Katsufusa SHONO
In this paper, bifurcation and chaotic behavior which occur in simple looped MOS inverters with high speed operation are described. The most important point in this work is to change a nonlinear transfer characteristic of a MOS inverter to the nonlinearity generating a chaos. Three types of circuits which include four, three and one MOS inverters, respectively, are proposed. A switched capacitor (SC) circuit to operate sampling holding is added in the loop in each of the circuits. The bifurcation and chaotic behavior have been found along with a variation of an external input, and/or a sampling clock frequency. The bifurcation and chaotic behavior of the proposed simple looped MOS inverters are verified by employing SPICE circuit simulator as well as the experiments. For the first type of four looped CMOS inverters, Lyapunov exponent λ which has the positive regions for the chaotic behavior can be calculated by use of the fitting nonlinear function synthesized from two sigmoid functions. For the second type of three looped CMOS inverters and the third type of one looped MOS inverter, the nonlinear charge/discharge characteristics of the hold capacitor in the SC circuit is utilized efficiently for forming the nonlinearity generating the bifurcation and chaotic behavior. Their bifurcation can be generated by the sampling clock frequency parameter which is controlled easily.
Vasily G. MOSHNYAGA Yutaka MORI Keikichi TAMARU
In order to shorten the time-to-market, Application-Specific Integrated Circuits (ASIC's) are designed from a library of pre-defined layout implementations for register-transfer modules such as multipliers, adders, RAM, ROM, etc. Current approaches to selecting the implementations from the library usually deal with their timing-area estimates and do not consider delay of the intermodule wiring. However, as sub-micron design rules are utilized for IC fabrication, wiring delay becomes comparable to the functional unit delay and can not longer be ignored even in register-transfer synthesis. In this paper we propose an algorithm that combines module selection with Performance-Driven module placement and reduces an impact of wiring on sub-micron ASIC performance. The algorithm not only efficiently exploits multiple module realizations in the design library, but also finds the module placement which minimizes wiring delay. Experimental results on several benchmarks show that considering both module and wiring issues, more than 30% reduction of the total circuit delay can be achieved.
Akira YAMAMOTO Masaya OHTA Hiroshi UEDA Akio OGIHARA Kunio FUKUNAGA
We propose an asymmetric neural network which can solve inequality-constrained combinatorial optimization problems that are difficult to solve using symmetric neural networks. In this article, a knapsack problem that is one of such the problem is solved using the proposed network. Additionally, we study condition for obtaining a valid solution. In computer simulations, we show that the condition is correct and that the proposed network produces better solutions than the simple greedy algorithm.
Naomichi OKAMOTO Xue Jun MENG Okihiro SUGIHARA
We analyze all-optical switching property of a nonlinear directional coupler (NLDC) having an MQW coupling layer with both nonlinear and linear losses, and examine the effect of nonlinear losses. We use the Galerkin finite element method accompanied by a prodictor-corrector algorithm. The propagation loss along the strongly-coupled NLDC decreases with increasing nonlinear absorption coefficient due to saturation in absorption. A propagation loss of 8.18 dB or 2.38 dB in the bar state of the cross state is much smaller than the bulk loss of MQW structure which exceeds 50 dB. The nonlinear losses lengthen the coupling length and bring it close to that of a lossfree NLDC, while the linear losses shorten. It is found that the property of the cross state is greatly improved by counting the nonlinear losses: The cross-state output power and the output power ratio of two waveguides increase, and the cross state input power, that is, the switching power decreases.
Sadayuki MURASHIMA Takayasu FUCHIDA Toshihiro IDA Takayuki TOYOHIRA Hiromi MIYAJIMA
A noise tolerant auto-correlation associative memory is proposed. An associated energy function is formed by a multiplication of plural Hopfield's energy functions each of which includes single pattern as its energy minimum. An asynchronous optimizing algorithm of the whole energy function is also presented based on the binary neuron model. The advantages of this new associative memory are that the orthogonality relation among patterns does not need to be satisfied and each stored pattern has a large basin of attraction around itself. The computer simulations show a fairly good performance of associative memory for arbitrary pattern vectors which are not orthogonal to each other.
Toshiki HIRANO Tomotake FURUHATA Hiroyuki FUJITA
A new electrostatic wobble motor design and fabrication method were proposed, and micromotors were successfully fabricated and operated. The advantages are (1) thicker structural size, resulting in larger torque, (2) simple and safe fabrication process and (3) needle-shaped bearing to support the rotor. Needle-shaped bearing used here is expected to have lower friction comparing with the existing motor, since the load is smaller for this kind of bearing structure. Two major sources of the load, electrostatic force and capillary force, were considered to prove this tendency. Diamond-like Carbon (DLC) film was employed as a solid lubricant for its bearing. The friction of DLC and that of ilicon-dioxide were compared by experiment.
Haruo OGAWA Yuichiro TAKAHASHI Jun INAHASHI Toru SENGA
The objective of this study is to realize a manipulator of 0.5 mm in outside diameter as a part of 'research and development of micro machine technology.' This manipulator is intended as a part of a working robot to fix or observe the inside wall of a small pipe. One of the important problems of this research is to establish a processing method of a tubular small structure. MIM, metal injection molding, has been adopted to fabricate such a small structure. As a processing method to machine small molds for MIM, finish processing with surface roughness of Rmax 0.1 µm has been under our research applying 'vibrational processing technology,' which was developed on our own. This paper presents the results of 'vibrational processing technology' surface finishing of molds for metal injection.
Su FENG Toshiki SAKABE Yasuyoshi INAGAKI
Dynamic Term Rewriting Calculus (DTRC) is a new computation model aiming at formal description and verification of algorithms treating Term Rewriting Systems (TRSs). In this paper, we show that we can use DTRC to mechanize explicit induction for proving an inductive theorem, that is, we can translate the statements of base and induction steps for proving by induction into a DTRC term. The translation reduces the proof of the statements into the evaluation of the corresponding DTRC term.
Xiaoging WEN Kozo KINOSHITA Hideo TAMAMOTO Hiroshi YOKOYAMA
The efficiency of a guided-probe fault location process is affected by the number of the probed lines. This number depends on the size of the target area and the method by which a line is selected for probing. This paper presents a method for reducing the size of the target area in a sequential circuit by introducing the concepts of Type- and Type- faults. This paper also presents a method of selecting lines for probing in a more efficient way. The efficiency of the proposed methods is demonstrated by experimental results.
Toshihiko SHIBAZAKI Teruhiro KINOSHITA Ryoji SHIN'YAGAITO
The precise phase characteristics of the reflected and transmitted waves are obtained for electromagnetic scattering by inductive discontinuities of finite thickness located in rectangular waveguides. The incident wave is assumed to be the dominant mode, and the modified residue-calculus method is used for numerical analysis. The phase characteristics when the thickness and width of the iris are varied, and characteristics of the reflected and transmitted waves when resonance appears, are discussed. In addition, an X-band experiment is performed and the calculations for both the reflected and transmitted waves are shown to agree well with the experimental values.
Kazuyuki WADA Nobuo FUJII Shigetaka TAKAGI
A method of driving the effects caused by finite input impedance and nonzero output impedance of functional building blocks into a frequency shift of transfer characteristics is proposed. The method is quite simple and systematic. The input and output impedances can have arbitrary values under a simple condition which meets the monolithic integration of circuits. The effects of non ideal input and output impedances are converted to a change of integrator gain leading to a simple frequency shift of circuits. The frequency shift can easily be adjusted by conventional methods. A typical example shows a remarkable effect of the method.
For symmetric cryptosystems, their transformations should have nonlinear elements to be secure against various attacks. Several nonlinearity criteria have been defined and their properties have been made clear. This paper focuses on, among these criteria, the propagation criterion (PC) and the strict avalanche criterion (SAC), and makes a further investigation of them. It discusses the sets of Boolean functions satisflying the PC of higher degrees, the sets of those satisfying the SAC of higher orders and their relationships. We give a necessary and sufficient condition for an n-input Boolean function to satisfy the PC with respect to a set of all but one or two elements in {0,1}n{(0,...,0)}. From this condition, it follows that, for every even n 2, an n-input Boolean function satisfies the PC of degree n 1 if and only if it satisfies the PC of degree n. We also show a method that constructs, for any odd n 3, n-input Boolean functions that satisfy the PC with respect to a set of all but one elements in {0,1}n{(0,...,0)}. This method is a generalized version of a previous one. Concerned with the SAC of higher orders, it is shown that the previously proved upper bound of the nonlinear order of Boolean functions satisfying the criterion is tight. The relationships are discussed between the set of n-input Boolean functions satisfying the PC and the sets of those satisfying the SAC.
Kazuhisa OKADA Hidetoshi ONODERA Keikichi TAMURA
We propose a new compaction problem that allows layout elements to have many shape possibilities. The objective of the problem is to find not only positions but also shapes of layout elements. We present an efficient method to solve the problem--compaction with shape optimization. This method simplifies the problem by considering the optimization of shapes only for the layout elements on a critical path. The layout is compacted step by step while optimizing the shapes of layout elements. Another importance of this compaction technique is that it makes layout to be "recyclable" for other set of device parameters. The experimental examples, which attempt shape optimization and recycle of analog layout, confirms the importance and efficiency of our method.