Byungsoo KIM Kyesuk JUN Ihn Seok KIM
In this paper, the absorbing property of the discrete Green's function ABC, which was based on a powerful concept of the TLM method, has been improved by relocating loss process from the time domain to the space domain. The proposed scheme simply adds a loss matrix to the connection matrix in the basic TLM algorithm to make the formulation of the ABC more efficient. Various lengths of absorbing layers discretized for a WR-90 empty waveguide have been tested in terms of reflection property. An expression for an optimum absorbing property has been also derived with respect to the length of the layer. Comparison of the layer with the discrete Green's function ABC shows that the layer in this study has improved reflection property better than approximately 3 and 6 dB, respectively, when 50Δ
Youhua SHI Zhe ZHANG Shinji KIMURA Masao YANAGISAWA Tatsuo OHTSUKI
Reseeding technique is proposed to improve the fault coverage in pseudo-random testing. However most of previous works on reseeding is based on storing the seeds in an external tester or in a ROM. In this paper we present a built-in reseeding technique for LFSR-based test pattern generation. The proposed structure can run both in pseudorandom mode and in reseeding mode. Besides, our method requires no storage for the seeds since in reseeding mode the seeds can be generated automatically in hardware. In this paper we also propose an efficient grouping algorithm based on simulated annealing to optimize test vector grouping. Experimental results for benchmark circuits indicate the superiority of our technique against other reseeding methods with respect to test length and area overhead. Moreover, since the theoretical properties of LFSRs are preserved, our method could be beneficially used in conjunction with any other techniques proposed so far.
Carlo MARCHETTI Sara Tucci PIERGIOVANNI Roberto BALDONI
The deployment of server replicas of a service across an asynchronous distributed system (e.g., Internet) is a real practical challenge. This target cannot be indeed achieved by classical software replication techniques (e.g., passive and active replication) as these techniques usually rely on group communication toolkits that require server replicas to run over a partially synchronous distributed system to solve the underlying agreement problem. This paper proposes a three-tier architecture for software replication that encapsulates the need of partial synchrony in a specific software component of a mid-tier to free replicas and clients from the need of underlying partial synchrony assumptions. Then we propose how to specialize the mid-tier in order to manage active replication of server replicas.
Masahiro SERIZAWA Hironori ITO
This paper proposes a packet loss recovery method using packets arrived behind the playout time for CELP (Code Excited Liner Prediction) decoding. The proposed method recovers synchronization of the filter states between encoding and decoding in the period following packet loss. The recovery is performed by replacing the degraded filter states with the ones calculated from the late arrival packet in decoding. When the proposed method is applied to the AMR (Adaptive Multi-Rate) speech decoder, it improves the segmental SNR (Signal-to-Noise Ratio) by 0.2 to 1.8 dB at packet loss rates of 2 to 10 % in case that all the packet losses occur due to their late arrival. PESQ (Perceptual Evaluation of Speech Quality) results also show that the proposed method slightly improves the speech quality. The subjective test results show that five-grade mean opinion scores are improved by 0.35 and 0.28 at a packet loss rate of 5 % at speech coding bitrates of 7.95 and 12.2 kbit/s, respectively.
Wenliang DAI Zhengfan LI Junfa MAO
A novel double-image Green's function approach is proposed to compute the frequency- dependent capacitance and conductance for the general CMOS oriented transmission lines with one protective layer. The ε-algorithm of Pade approximation is adopted to reduce the time for establishing coefficient matrix in this letter. The parameters gained from this new approach are shown to be in good agreement with the data obtained by the full-wave method and the total charge Green's function method.
Ryoji ISHIKAWA Goro KODA Kensuke SHIMIZU
The discrete nature of data in a functional domain can generally be replaced by the global nature of data in the spectrum domain. In this paper we propose a fast procedure to detect autosymmetric function as an application of the spectrum technique. The autosymmetric function differs from the usual symmetric function and strongly relates with EXOR-based representations. It is known that many practical logical networks are autosymmetric, and this nature allows a useful functional class to realize a compact network with EXOR gates. Our procedure is able to detect autosymmetric functions quickly by using spectral coefficients. In experiments, our technique can detect the autosymmetry of most networks with a small number of checks of the spectrum.
Yasuo SATO Motoyuki SATO Koki TSUTSUMIDA Kazumi HATAYAMA Kazuyuki NOMOTO
We analyze the timing design methodology for testing chips using a multiple-clock domain scheme. We especially focus on the layout design of the design-for-test (DFT) circuits and the clock network. First, we demonstrate the built-in-self-testing (BIST) scheme for multiple-clock domains. Then, we discuss the layout method that achieves a low clock-skew between different clock domains with a small modification of the original user logic layout. Finally, we evaluate the fault coverage of our large ASIC chips designed using our new methodology. The short design period and high fault coverage of our methodology are confirmed using actual industrial designs. We introduce a viable approach for industrial designs because designers don't have to pay much attention to DFT. Our approach also provides designers with an easy method for LSI debugging and diagnostics.
Kenichi ICHINO Ko-ichi WATANABE Masayuki ARAI Satoshi FUKUMOTO Kazuhiko IWASAKI
We propose a technique of selecting seeds for the LFSR-based test pattern generators that are used in VLSI BISTs. By setting the computed seed as an initial value, target fault coverage, for example 100%, can be accomplished with minimum test length. We can also maximize fault coverage for a given test length. Our method can be used for both test-per-clock and test-per-scan BISTs. The procedure is based on vector representations over GF(2m), where m is the number of LFSR stages. The results indicate that test lengths derived through selected seeds are about sixty percent shorter than those derived by simple seeds, i.e. 0001, for a given fault coverage. We also show that seeds obtained through this technique accomplish higher fault coverage than the conventional selection procedure. In terms of the c7552 benchmark, taking a test-per-scan architecture with a 20-bit LFSR as an example, the number of undetected faults can be decreased from 304 to 227 for 10,000 LFSR patterns using our proposed technique.
Herng-Jer LEE Chia-Chi CHU Wu-Shiung FENG
A novel method is presented to compute moments of high-speed VLSI interconnects, which are modeled as coupled RLC trees. Recursive formulae of moments of coupled RC trees are extended to those for coupled RLC trees by considering both self inductances and mutual inductances. Analytical formulae for voltage moments at each node are derived explicitly. The formulae can be efficiently used for estimating delay and crosstalk noise. The inductive crosstalk noise waveform can be accurately and efficiently estimated using the moment computation technique in conjunction with the projection-based order reduction method. Fundamental aspects of the proposed approach are described in details. Experimental results show the increased accuracy of the proposed method over that of the traditional ones.
Sarat C. MARUVADA Karthik KRISHNAMOORTHY Florin BALASA Lucian M. IONESCU
The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves. This paper presents a novel exploration technique for analog placement, operating on a subset of tree representations of the layout, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The efficiency of the novel approach is due to the use of red-black interval trees, data structures employed to support operations on dynamic sets of intervals.
Toshiyuki MIYAMOTO Syoji YAMASHITA Sadatoshi KUMAGAI Hideaki OHTA Koichi FUKUMOTO Yoichi NAGAO
The present paper discusses an assembly line balancing problem (ALBP). ALBP discussed up to now does not consider rack spaces where tools or parts are stored. We introduce an extended resource planning and assembly line balancing problem that takes the rack space into account. An exact search method for solving the problem by using a graph structure, and a heuristics for the method are proposed. The proposed method is evaluated by computational experiments.
In speech enhancement with adaptive microphone array, the voice activity detection (VAD) is indispensable for the adaptation control. Even though many VAD methods have been proposed as a pre-processor for speech recognition and compression, they can hardly discriminate nonstationary interferences which frequently exist in real environment. In this research, we propose a novel VAD method with array signal processing in the wavelet domain. In that domain we can integrate the temporal, spectral and spatial information to achieve robust voice activity discriminability for a nonstationary interference arriving from close direction of speech. The signals acquired by microphone array are at first decomposed into appropriate subbands using wavelet packet to extract its temporal and spectral features. Then directionality check and direction estimation on each subbands are executed to do VAD with respect to the spatial information. Computer simulation results for sound data demonstrate that the proposed method keeps its discriminability even for the interference arriving from close direction of speech.
Yong Up LEE Joong-Hoo PARK Yeongjun SEO
The performance enhancement technology for indoor-to-outdoor wireless communication systems is discussed in this study. In outdoor communication systems, transmitted signals may be severely degraded mainly by multipath fading effect of the channel and this problem can be overcome using conventional multiple antenna technology and array signal processing algorithms. But, since channel characteristics depend on both multipath fading and angle spread in indoor-to-outdoor communication systems, conventional algorithms which do not consider the effect caused by angle spread cannot give good results. In this letter, characteristics of indoor-to-outdoor channels are analyzed and a channel model suitable for this situation is proposed. And a new array antenna processing algorithm exploiting the concept of the mean steering vector is presented and the system performance is analyzed. It can be shown that the proposed algorithm outperforms conventional methods through computer simulations for the case in which signals sent from indoor transmitters arrive at outdoor receivers.
Yusuke OIKE Makoto IKEDA Kunihiro ASADA
A high-speed 3-D camera has a future possibility of wide variety of application fields such as quick inspection of industrial components, observation of motion/destruction of a target object, and fast collision prevention. In this paper, a row-parallel position detector for a high-speed 3-D camera based on a light-section method is presented. In our row-parallel search method, the positions of activated pixels are quickly detected by a row-parallel search circuit in pixel and a row-parallel address acquisition of O(log N) cycles in N-pixel horizontal resolution. The architecture keeps high-speed position detection in high pixel resolution. We have designed and fabricated the prototype position sensor with a 12816 pixel array in 0.35 µm CMOS process. The measurement results show it achieves quick activated-position acquisition of 450 ns for "beyond-real-time" 3-D imaging and visual feedback. The high-speed position detection of the scanning sheet beam is demonstrated.
In this paper, a novel technique using proportional current feedback is proposed to improve dynamic response of digital PWM DC-DC converters. Generally, digital controllers are implemented using microprocessors or DSPs. Additional A/D converters are required to sense feedback signals. Proposed simple structure makes it feasible to integrate both A/D converter and digital controller on a single chip. System complexity and hardware cost are therefore greatly reduced. A behavioral time domain circuit model is proposed and analyzed using MATLAB. Both simulation and experimental results showed satisfactory performance to meet power requirements of microprocessors.
Dong XIANG Shan GU Hideo FUJIWARA
A two stage non-scan design for testability method is proposed. The first stage selects test points based on an earlier testability measure conflict. A new design for testability algorithm is proposed to select test points by a fault-oriented testability measure conflict+ in the second stage. Test points are selected in the second stage based on the hard faults after the initial ATPG run of the design for testability circuit in the preliminary stage. The new testability measure conflict+ based on conflict analysis of hard-faults in the process of test generation is introduced, which emulates most general features of sequential ATPG. The new testability measure reduces testability of a fault to the minimum D or
Kenji SHIMIZU Tsuyoshi OGURA Tetsuo KAWANO Hiroyuki KIMIYAMA Mitsuru MARUYAMA
We have developed an OC-48c (2.4 Gbps) PCI-compliant network interface card and drivers with the aim of evaluating the effectiveness of our proposed link layer protocol MAPOS. In this paper, we study the effectiveness of MAPOS particularly from the viewpoint of the influence of packet sizes up to the 64-kbyte jumbo MTU size and the effectiveness of our new implementation of the non-interrupt-driven sending process and interrupt batching receiving process deployed to improve the throughput in short-packet transmissions. Our main findings are as follows; Enlarging the packet size up to 64-kbyte MTU improves the performance in transmission. OC-48c wire speed is achieved with packet sizes larger than 16 kbytes. Implementation of the non-interrupt-driven sending process and the interrupt batching receiving process improves the performance of short-packet transmission. In particular, the transmission throughput is improved by 50% when 64-byte short packets are used. The maximum loss-free receive rate is also raised by 50% when 4-kbyte packets arrive. With a high-performance CPU, the data-transfer speed of the DMA controller for jumbo packets cannot keep up with the packet-queueing speed of the CPU. Our proposed procedure for adaptive algorithm switching method can resolve this problem. The maximum TCP throughput observed in our measurement using the latest PCs and MAPOS OC-48c PCI card was 2342.5 Mbps. This throughput represents the highest performance in a legacy-PCI-based system according to the results database of the benchmarking software.
Hon-Chan CHEN Shin-Huei WU Chang-Biau YANG
A tree 3-spanner T of a graph G is a spanning tree of G such that the distance between any two vertices in T is at most 3 times of their distance in G. Madanlal et al. have presented an O(n + m) time algorithm for finding a tree 3-spanner of a permutation graph. However, the complexity of their algorithm is not optimal, and their algorithm can not be easily parallelized. In this paper, we will propose an improved algorithm to solve the same problem in O(n) time. Moreover, our algorithm can be easily parallelized so that a tree 3-spanner of a permutation graph can be found in O(log n) time with processors on the EREW PRAM computational model.
Analysis of concurrent systems, such as computer/communication networks and manufacturing systems, usually employs formal discrete event models. The analysis then includes model validation, property verification, and performance evaluation of such models. The DEVS (Discrete Event Systems Specification) formalism is a well-known formal modeling framework which supports specification of discrete event models in a hierarchical, modular manner. While validation and verification using formal models may not resort to discrete event simulation, accurate performance evaluation must employ discrete event simulation of formal models. Since formal models, such as DEVS models, explicitly represent communication semantics between component models, their simulation cost is much higher than using simulation languages with informal models. This paper proposes a method for simulation speedup in performance evaluation of concurrent systems using DEVS models. The method is viewed as a compiled simulation technique which eliminates run-time interpretation of communication paths between component models. The elimination has been done by a behavior-preserved transformation method, called model composition, which is based on the closed under coupling property in DEVS theory. Experimental results show that the simulation speed of transformed DEVS models is about 14 times faster than original ones.
Norimasa NAKASHIMA Mitsuo TATEIBA
The boundary element method (BEM), a representative method of numerical calculation of electromagnetic wave scattering, has been used for solving boundary integral equations. Using BEM, however, we finally have to solve a linear system of L equations expressed by dense coefficient matrix. The floating-point operation is O(L2) due to a matrix-vector product in iterative process. Greengard-Rokhlin's fast multipole algorithm (GRFMA) can reduce the operation to O(L). In this paper, we describe GRFMA and its floating-point operation theoretically. Moreover, we apply the fast Fourier transform to the calculation processes of GRFMA. In numerical examples, we show the experimental results for the computation time, the amount of used memory and the relative error of matrix-vector product expedited by GRFMA. We also discuss the convergence and the relative error of solution obtained by the BEM with GRFMA.