Yusuke ICHIKAWA Zenjiro KONISHI Yoshihiko FUTAMURA
Recursive programs are often easier to read and write than iterative ones, but their execution frequently requires large numbers of procedure calls and stack operations. This causes problems in program optimization related to inline coding and the locality of data references. In addition to these problems, defining programs recursively sometimes leads to repetitive execution of similar computations, causing programs to have exponential time complexity. As a result, recursion removal methods, which transform a given recursive program to an iterative one without using the stack and increasing the amount of computation time, have been studied since the 1970s. In 1998, our group proposed a recursion removal method for a linear recursive program. In this paper, we extend the method to deal with non-linear recursive programs with one descent function (RPODs), which are programs of the form f(x) = if p(x) then b(x) else a(c(x),f(d(x)),f(d2(x)),...,f(dn(x))). First, we define the cumulative function for an RPOD. Next, based on the new cumulative function, several transformation techniques for RPODs are shown. These include a unified method of deriving logarithmic-order iterative programs or loop-free programs. Finally, the relationships between our method and various tupling strategies are discussed.
Chia-Chi CHU Herng-Jer LEE Wu-Shiung FENG
Projection-based model reductions become a necessity for efficient interconnect modeling and simulations. In order to choose the order of the reduced system that can really reflect the essential dynamics of the original interconnect, the residual error of the transfer function can be considered as a stopping criteria to terminate the Arnoldi iteration process. Analytical expressions of this residual error are derived in detail. Furthermore, it can be found that the approximate transfer function can also be expressed as the original interconnect model with some additive perturbations. The perturbation matrix only involves resultant vectors at the previous step of the Arnoldi algorithm. These error information will provide a guideline for the order selection scheme used in the Krylov subspace model-order algorithm.
This paper presents an improved architecture of the multistage multibit sigma-delta modulators (ΣΔMs) for wide-band applications. Our approach is based on two resonator topologies, high-Q cascade-of-resonator-with-feedforward (HQCRFF) and low-Q cascade-of-integrator-with-feedforward (LQCIFF). Because of in-band zeros introduced by internal loop filters, the proposed architecture enhances the suppression of the in-band quantization noise at a low OSR. The HQCRFF-based modulator with single-bit quantizer has two modes of operation, modulation and oscillation. When the HQCRFF-based modulator is operating in oscillation mode, the feedback path from the quantizer output to the input summing node is disabled and hence the modulator output is free of the quantization noise terms. Although operating in oscillation mode is not allowed for single-stage ΣΔM, the oscillation of HQCRFF-based modulator can improve dynamic range (DR) of the multistage (MASH) ΣΔM. The key to improving DR is to use HQCRFF-based modulator in the first stage and have the first stage oscillated. When the first stage oscillates, the coarse quantization noise vanishes and hence circuit nonidealities, such as finite op-amp gain and capacitor mismatching, do not cause leakage quantization noise problem. According to theoretical and numerical analysis, the proposed MASH architecture can inherently have wide DR without using additional calibration techniques.
Bandpass sampling algorithm is effectively adopted to obtain the digital signal with significantly reduced sampling rate for a single radio frequency(RF) signal. In order to apply the concept to multiple RF signals, we propose bandpass sampling algorithms with the normal and the inverse placements since we are interested in uniform order of the spectrum in digital domain after bandpass sampling. In addition, we verify the propose algorithms with generalized equation forms for the multiple RF signals.
Wei-Tsong LEE Kuo-Chi CHU Kun-Chen CHUNG Jen-Yi PAN Pau-Choo CHUNG
The multi-channel Hybrid Fiber Coaxial (HFC) network is essentially a shared medium with multi-channels. Its operation requires the use of a scheduling algorithm to manage the data transmission within each channel. The Data-Over-Cable Service Interface Specification (DOCSIS) protocol is an important standard for HFC networks. Since this protocol does not explicitly specify the scheduling algorithm to be used, many alternative algorithms have been proposed. However, none of these algorithms are applicable to the scheduling of non-Unsolicited Grant Service (UGS) data in multi-channel HFC networks. Accordingly, the present study develops a multi-channel scheduling algorithm which optimizes the scheduling delay time of each transmitted non-UGS request. This algorithm manages the amount of data transmission in each upstream channel according to the overall network load and the bandwidth available in each channel. This study constructs a mathematical model of the algorithm and then uses this model as the basis for a series of simulations in which the performance of the scheduling algorithm is evaluated.
Retdian A. NICODIMUS Hiroto SUZUKI Kazuyuki WADA Shigetaka TAKAGI
A design optimization of active shield circuit using noise averaging method is proposed. The relation between the averaged noise and the design parameters of the active shield circuit such as circuit gain and on-chip layout is examined. A simple design guideline is also provided. Simulation results show that the active shield circuit designed by the proposed optimization method gives a better noise suppression performance of about 28% than the conventional one.
This paper describes a second-order continuous-time ΔΣ modulator for a W-CDMA receiver, which operates at a supply voltage of 0.9 V, the lowest so far reported for W-CDMA. Inverter-based balanced OTAs without using differential pair are proposed for a low-voltage operation. Circuit parameters are optimized by system simulations. The modulator was implemented in a 0.13-µm CMOS technology. It consumes only 1.5 mW. The measured SNDR is 50.9 dB over a bandwidth of 1.92 MHz.
Pornanong PONGPAIBOOL Toru UNO Takuji ARIMA
A numerical technique for improving the accuracy of a rectangular loop antenna based on the Finite Difference Time Domain (FDTD) method is proposed. In this technique, a quasi-static field behaviour is incorporated into the FDTD update equations, and the more accurate numerical technique can be obtained without the need of using fine cells. The simulation results of this proposed technique are compared with the Method of Moment to confirm the effectiveness of the technique.
Hajime OTA Tatsuoki NAGAISHI Eiichi ARAI
The Time Domain Electromagnetic Method (TDEM) survey is one of the several geophysical exploration methods. In the conventional TDEM survey, an induction coil is used as the magnetometer. However, the measurement depth is limited to about 500 m. Using high Tc SQUIDs, there are expectations of large bandwidth and high sensitivity for the TDEM. We developed the high Tc SQUID TDEM system. We have reduced the system noise by developing a 20 mm20 mm step-edge type direct coupled SQUID and a low noise direct readout flux locked loop (FLL) circuit. We have also improved the slew rate, optimizing the parameter of the FLL circuit. Consequently, the system noise of less than 0.2 pT/Hz1/2 at 1 kHz was achieved in the earth's magnetic field. The slew rate was 7.3 mT/sec. We conducted field trials and confirmed that the TDEM using high Tc SQUIDs obtains information of deeper region with high precision compared with the TDEM using induction coils.
Yoshihito HASHIMOTO Shinichi YOROZU Yoshio KAMEDA Akira FUJIMAKI Hirotaka TERAI Nobuyuki YOSHIKAWA
To enable the use of passive transmission lines (PTLs) for the interconnection of single-flux-quantum (SFQ) circuits, we have implemented a driver and a receiver and have developed a method for designing SFQ circuits with passive interconnections. Basic components and properties of passive interconnections, such as the frequency characteristics of the driver and receiver, the PTL delay, and the crosstalk between PTLs, have been experimentally verified. Our developed components and design method have been applied to actual SFQ circuits, such as a 44 switch having block-to-block passive interconnections and a 22 switch having gate-to-gate passive interconnections. We have also shown the advantages of PTLs over Josephson transmission lines (JTLs). We also discuss the prospects of SFQ circuits having passive interconnections.
Yuh-Shyan HWANG Jen-Hung LAI Ming-Chieh CHANG
Linear transformation transistor-only high-order current-mode filters are presented in this Letter. Based on the systematic design procedure, we can realize high-order current-mode filters employing switched-current technique efficiently. Only two kinds of switched-current basic cells are needed in our design to obtain simple architectures. The fifth-order Chebychev lowpass filter is designed to verify the proposed synthesis method. Simulation results that confirm the theoretical analysis are obtained.
In this paper, we describe an accelerative current-programming method for active matrix OLED (AM-OLED) display. This new method uses common source configuration, "Acceleration Control" line and some mechanisms to prevent the programming current from flowing through OLED device. It would solve the basic problem of the current-programming pixel circuit: a long programming period, especially at the dark gray-level. The proposed method accelerates the current programming process at any gray levels, and it would be the solution for the problem.
Xiren WANG Deyan LIU Wenjian YU Zeyi WANG
Efficient extraction of interconnect parasitic parameters has become very important for present deep submicron designs. In this paper, the improved boundary element method (BEM) is presented for 3-D interconnect resistance extraction. The BEM is accelerated by the recently proposed quasi-multiple medium (QMM) technology, which quasi-cuts the calculated region to enlarge the sparsity of the overall coefficient matrix to solve. An un-average quasi-cutting scheme for QMM, advanced nonuniform element partition and technique of employing the linear element for some special surfaces are proposed. These improvements considerably condense the computational resource of the QMM-based BEM without loss of accuracy. Experiments on actual layout cases show that the presented method is several hundred to several thousand times faster than the well-known commercial software Raphael, while preserving the high accuracy.
Naoya KAWAMOTO Naoto MATSUO Atsushi MASUDA Yoshitaka KITAMON Hideki MATSUMURA Yasunori HARADA Tadaki MIYOSHI Hiroki HAMADA
The role of hydrogen in the Si film during excimer laser annealing (ELA) has been successfully studied by using a novel sample structure, which is stacked by a-Si film and SiN film. Hydrogen contents in the Si films during ELA are changed by preparing samples with hydrogen content of 2.3-8.2 at.% in the SiN films with a use of catalytic (Cat)-CVD method. For the low concentration of hydrogens in the Si film, the grain size increases by decreasing hydrogen concentration in the Si film, and the internal stress of the film decreases as increasing the shot number. For the high concentration of hydrogens in the Si film, hydrogen burst was observed at 500 mJ/cm2 and the dependence of the internal stress on the shot number becomes weak even at 318 mJ/cm2. These phenomena can be understood basically using the secondary grain growth mechanism, which we have proposed.
Kiyohiro FURUTANI Takeshi HAMAMOTO Takeo MIKI Masaya NAKANO Takashi KONO Shigeru KIKUDA Yasuhiro KONISHI Tsutomu YOSHIHARA
This paper describes two circuit techniques useful for the design of high density and high speed low cost double data rate memories. One is a highly flexible row and column redundancy circuit which allows the division of flexible row redundancy unit into multiple column redundancy unit for higher flexibility, with a new test mode circuit which enables the use of the finer pitch laser fuse. Another is a compact read data path which allows the smooth data flow without wait time in the high frequency operation with less area penalty. These circuit techniques achieved the compact chip size with the cell efficiency of 60.6% and the high bandwidth of 400 MHz operation with CL=2.5.
Shinji WATANABE Yasuhiro MINAMI Atsushi NAKAMURA Naonori UEDA
A Shared-State Hidden Markov Model (SS-HMM) has been widely used as an acoustic model in speech recognition. In this paper, we propose a method for constructing SS-HMMs within a practical Bayesian framework. Our method derives the Bayesian model selection criterion for the SS-HMM based on the variational Bayesian approach. The appropriate phonetic decision tree structure of the SS-HMM is found by using the Bayesian criterion. Unlike the conventional asymptotic criteria, this criterion is applicable even in the case of an insufficient amount of training data. The experimental results on isolated word recognition demonstrate that the proposed method does not require the tuning parameter that must be tuned according to the amount of training data, and is useful for selecting the appropriate SS-HMM structure for practical use.
In this work we give an extension of Kauffman's NK-Landscapes to multiobjective MNK-Landscapes in order to study the effects of epistasis on the performance of multiobjective evolutionary algorithms (MOEAs). This paper focuses on the development of multiobjective random one-bit climbers (moRBCs). We incrementally build several moRBCs and analyze basic working principles of state of the art MOEAs on landscapes of increased epistatic complexity and number of objectives. We specially study the effects of Pareto dominance, non-dominance, and the use of memory and a population to influence the search. We choose an elitist non-dominated sorting multiobjective genetic algorithm (NSGA-II) as a representative of the latest generation of MOEAs and include its results for comparison. We detail the behavior of the climbers and show that population based moRBCs outperform NSGA-II for all values of M and K.
Jun CHOI Deukjo HONG Seokhie HONG Sangjin LEE
One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.
Extensive studies have been made of the public key cryptosystems based on multivariate polynomials over F2. However most of the proposed public key cryptosystems based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public key cryptosystems based on randomly generated singular simultaneous equations. One of the features of the proposed cryptosystems is that the sets of random singular simultaneous equations significantly enlarges the size of the transformation.
Ruey-Shun CHEN Duen-Kai CHEN Szu-Yin LIN
The traffic congestion problem in urban areas is worsening since traditional traffic signal control systems cannot provide] efficient traffic regulation. Therefore, dynamic traffic signal control in Intelligent Transportation System (ITS) recently has received increasing attention. This study devised a multi-agent architecture, the Adaptive and Cooperative Traffic light Agent Model (ACTAM), for a decentralized traffic signal control system. The proposed architecture comprises a data storage and communication layer, a traffic regulation factor processing layer, and a decision-making layer. This study focused on utilizing the cooperation of multi-agents and the prediction mechanism of our architecture, the Forecast Module, to forecast future traffic volume in each individual intersection. The Forecast Module is designed to forecast traffic volume in an intersection via multi-agent cooperation by exchanging traffic volume information for adjacent intersections, since vehicles passing through nearby intersections were believed to significantly influence the traffic volume of specific intersections. The proposed architecture can achieve dynamic traffic signal control. Thus, total delay time of the traffic network under ACTAM can be reduced by 37% compared to the conventional fixed sequence traffic signal control strategy. Consequently, traffic congestion in urban areas can be alleviated by adopting ACTAM.