Sung-Jin CHUNG Sung-Pil HONG Hoo-Sang CHUNG
In this paper, we are concerned in obtaining multicast trees in packet-switched networks such as ATM nets, when there exist constraints on the packet (cell)-replication capabilities of the individual switching nodes. This problem can be formulated as the Steiner tree problem with degree bounds on the nodes, so we call it the Degree-Constrained Steiner Tree problem (DCST). Four heuristic algorithms are proposed: the first is a combined version of two well-known Steiner tree algorithms, heuristic Naive and the shortest path heuristic (SPH), and the second is a relaxation algorithm based on a mathematical formulation of the DCST, and the last two use a tree reconfiguration scheme based on the concept of 'logical link. ' We experimentally compare our algorithms with the previous ones in three respects; number of solved instances, objective value or tree cost, and computation time. The experimental results show that there are few instances unsolved by our algorithms, and the objective values are mostly within 5% of optimal. Computation times are also acceptable.
Toshiya NAKAGUCHI Shinya ISOME Kenya JIN'NO Mamoru TANAKA
We propose hysteresis neural network solving combinatorial optimization problems, Box Puzzling Problem. Hysteresis neural network searches solutions of the problem with nonlinear dynamics. The output vector becomes stable only when it corresponds with a solution. This system does never become stable without satisfying constraints of the problem. After estimating hardware calculating time, we obtain that numerical calculating time increases extremely comparing with hardware time as problem's scale increases. However the system has possibility of limit cycle. Though it is very hard to remove limit cycle completely, we propose some methods to remove this phenomenon.
Shin-ichi TAKAGI Tomohisa MIZUNO Naoharu SUGIYAMA Tsutomu TEZUKA Atsushi KUROBE
An effective way to realize scaled CMOS with both requirements of high current drive and low supply voltage is to introduce high mobility channel such as strained Si. This paper proposes a new device structure using the strained-Si channel, strained-Si-on-Insulator (strained-SOI) MOSFET, applicable to sub-100 nm Si CMOS technology nodes. The device structure and the advantages of strained-SOI MOSFETs are presented. It is demonstrated that strained-SOI MOSFETs are successfully fabricated by combining SIMOX technology with re-growth of strained Si and that n- and p-MOSFETs have mobility of 1.6 and 1.3 times higher than the universal one, respectively. Furthermore, it is also shown that ultra-thin SiGe-on-Insulator (SGOI) virtual substrates with higher Ge content, necessary to further increase mobility and to realize fully-depleted SOI MOSFETs, can be made by oxidation of SGOI structure with lower Ge content.
Tatsuo WATANABE Nagisa ISHIURA
This letter presents a method which attempts to minimize the number of spill codes to resolve usage conflicts of distributed registers in application specific DSPs. It searches for a set of ordering restrictions among operations which sequentialize the lifetimes of the values residing in the same register as much as possible. Experimental results show that the proposed analysis method reduces the number of register spills into 28%.
We present a new family of algorithms that solve the bias problem in the equation-error based adaptive infinite impulse response (IIR) filtering. A novel constraint, called the constant-norm constraint, unifies the quadratic constraint and the monic one. By imposing the monic constraint on the mean square error (MSE) optimization, the merits of both constraints are inherited and the shortcomings are overcome. A new cost function based on the constant-norm constraint and Lagrange multiplier is defined. Minimizing the cost function gives birth to a new family of bias-free adaptive IIR filtering algorithms. For example, two efficient algorithms belonging to the family are proposed. The analysis of the stationary points is presented to show that the proposed methods can indeed produce bias-free parameter estimates in the presence of white noise. The simulation results demonstrate that the proposed methods indeed produce unbiased parameter estimation, while being simple both in computation and implementation.
David Chee Kheong SIEW Gang FENG
The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP complete. Heuristic based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient multicast connection setup in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes. This can reduce the connection establishment time for subsequent connection requests which have some common multicast members, by an efficient reuse of cached trees without having to re-run a multicast routing algorithm for the whole group. This method can provide an efficient way to eliminate, when ever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching and then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy performs very well and can significantly reduce the computation complexity for setting up multicast connections.
Tomohiro FUJITA Hidetoshi ONODERA
This paper presents a method of statistical system optimization. The method uses a constraint generation, which is a design methodology based on a hierarchical top-down design, to give specifications to sub-circuits of the system. The specifications are generated not only to reduce the costs of sub-circuits but also to take adequate margin to achieve enough yield of the system. In order to create an appropriate amount of margin, a term which expresses a statistical figure based on Mahalanobis' distance is added to the constraint generation problem. The method is applied to a PLL, and it is confirmed that the yield of the lock-up time reaches 100% after the optimization.
Takuya ASAKA Takumi MIYOSHI Yoshiaki TANAKA
Many new multimedia applications involve multiple dynamically changing participants, have stringent source-to-end delay requirements, and consume large amounts of network resources. A conventional algorithm that allows "two coming paths," where nodes in a multicast tree transmit several identical data flows, is therefore not practical. We have developed an algorithm for delay-constrained dynamic routing. This algorithm uses a QoS label to prevent the occurrence of "two coming paths," and can construct an efficient multicast tree for any traffic volume. The proposed algorithm was superior to conventional routing algorithms in terms of cost when nodes were added to or removed from the multicast group during a steady-state simulation.
Jun'ichiro MINAMI Tetsushi KOIDE Shin'ichi WAKABAYASHI
This paper presents a timing-driven iterative improvement circuit partitioning algorithm under path delay constraints for the general delay model. The proposed algorithm is an extension of the Fiduccia & Mattheyses (FM) method so as to handle path delay constraints and consists of the clustering and iterative improvement phases. In the first phase, we reduce the size of a given circuit, with a new clustering algorithm to obtain a partition in a short computation time. Next, the iterative improvement phase based on the FM method is applied, and then a new path-based timing violation removal algorithm is also performed so as to remove all the timing violations. From experimental results for ISCAS89 benchmarks, we have demonstrated that the proposed algorithm can produce the partitions which mostly satisfy the timing constraints.
Yegui XIAO Takahiro MATSUO Katsunori SHIDA
Fourier analysis of sinusoidal and/or quasi-periodic signals in additive noise has been used in various fields. So far, many analysis algorithms including the well-known DFT have been developed. In particular, many adaptive algorithms have been proposed to handle non-stationary signals whose discrete Fourier coefficients (DFCs) are time-varying. Notch Fourier Transform (NFT) and Constrained Notch Fourier Transform(CNFT) proposed by Tadokoro et al. and Kilani et al., respectively, are two of them, which are implemented by filter banks and estimate the DFCs via simple sliding algorithms of their own. This paper presents, for the first time, statistical performance analyses of the NFT and the CNFT. Estimation biases and mean square errors (MSEs) of their sliding algorithms will be derived in closed form. As a result, it is revealed that both algorithms are unbiased, and their estimation MSEs are related to the signal frequencies, the additive noise variance and orders of comb filters used in their filter banks. Extensive simulations are performed to confirm the analytical findings.
We present a new basis for discrete representation of stereo correspondence. This center referenced basis permits a more natural, complete and concise representation of constraints in stereo matching. In this context a MAP formulation for disparity estimation is derived and reduced to unconstrained minimization of an energy function. Incorporating natural constraints, the problem is simplified to the shortest path problem in a sparsely connected trellis structure which is performed by an efficient dynamic programing algorithm. The computational complexity is the same as the best of other dynamic programming methods, but a very high degree of concurrency is possible in the algorithm making it suitable for implementation with parallel procesors. Experimental results confirm the performance of this method and matching errors are found to degrade gracefully in exponential form with respect to noise.
We studied theoretically and experimentally an InGaAs/InAlAs/InP polarization-insensitive multiple quantum well (MQW) electroabsorption (EA) modulator operating over a very wide wavelength range in 1.55 µm wavelength region. One of the simplest possible potential-tailored quantum well, "pre-biased" quantum well (PBQW) is used to achieve wide-wavelength polarization insensitivity. PBQW is basically a rectangular quantum well with a thin barrier inserted near one edge of well. This thin barrier effectively introduces "pre-bias" to a rectangular quantum well and the same amount of Stark shift is achieved for electron-heavy hole and electron-light hole transition energies. By incorporating tensile strain into PBQW, polarization-insensitive modulation is achieved over 60 nm wavelength range, from 1510 nm to 1570 nm. This MQW-EA modulator plays an important role in wavelength division multiplexing (WDM) transmission and switching systems.
Younggeun HAN Chang-Seok KIM Un-Chul PAEK Youngjoo CHUNG
We will discuss performance optimization of strain and temperature sensors based on long period fiber gratings (LPFGs) through control of the temperature sensitivity of the resonant peak shifts. Distinction between the effects of strain and temperature is a major concern for applications to communication and sensing. This was achieved in this work by suppressing or enhancing the temperature sensitivity by adjusting the doping concentrations of GeO2 and B2O3 in the core or cladding. The LPFGs were fabricated with a CO2 laser by the mechanical stress relaxation and microbending methods. The optimized temperature sensitivities were 0.002 nm/ for the suppressed case and 0.28 nm/ for the enhanced case, respectively. These LPFGs were used for simultaneous measurement of strain and temperature. The result indicates the rms errors of 23 µstrain for the strain and 1.3 for the temperature.
A correlation-based technique for measuring Brillouin gain spectrum distribution along an optical fiber is proposed, which employs frequency-modulated pump and probe lightwaves. The spatial-resolution of about 40 cm is demonstrated, which cannot be realized by the conventional pulse-based technique.
A short review of distributed and multiplexed sensor technology, based on fibre gratings, is given. This is followed by details of more specific work in this area at the University of Southampton, particularly grating fabrication, distributed and multiplexed addressing and important practical aspects such as temperature and strain discrimination. The paper concludes with a short discussion of the problems that must be avoided in order to construct viable systems for engineering requirements.
Norifumi YASUE Hiroshi NARUSE Jun-ichi MASUDA Hironori KINO Toshio NAKAMURA Taketoshi YAMAURA
This paper describes a load carrying test for a concrete pipe designed to study the effectiveness of distributed strain measurement using an optical fiber sensor. We performed a load carrying test on a concrete pipe and attempted to detect the distributed strain inside it using an optical fiber sensor mounted inside the pipe. We confirmed that it was possible to detect the strain in a concrete structure by using an optical fiber sensor after a crack had occurred on the concrete surface. This paper shows that measurement using the optical fiber sensor was effective despite great changes in the strain conditions of the measured object over a short distance.
Hiroshi NARUSE Yasuomi UCHIYAMA Toshio KURASHIMA Shuji UNNO
Since river levee collapse causes great damage, it is socially very important to prevent such disasters by using a monitoring system which can detect changes in the state of a river levee. To investigate the possibility of detecting the collapse of a levee slope at an early stage, we performed an experiment in which we used artificial rainfall and penetration to collapse a full-scale levee model, and measured the change in the levee state using a detection system during collapse. The system consists of sensor plates, a distributed fiber optic strain sensor, and a personal computer. With this system, the stretching produced in the sensor plates by the force resulting from the movement of the soil on the levee slope face is detected as strain by a sensing optical fiber fixed to the plates. Since the distributed fiber optic strain sensor can measure strain continuously and for a long distance along a fiber, it is suitable for monitoring civil structures such as river levees. The experiment confirmed that a change in a levee can be clearly detected when the slope face collapse progresses near the place where the sensor plates are buried. The results suggest the feasibility of being able to foresee the collapse of a levee slope.
Sandeep VOHRA Gregg JOHNSON Michael TODD Bruce DANVER Bryan ALTHOUSE
This paper describes the implementation of a Bragg grating-based strain-monitoring system on the Viaduc des Vaux bridge during its construction in 1997 and 1998. The bridge was constructed in a cantilevered, push/pull incremental launching method, and data obtained from two tests were shown to reveal interesting features of the box-girder strain response during the push and pull phases, particularly with regard to limit loads and local buckling. When appropriate, data were compared to data obtained from conventional resistive strain gages and from simple analytical models.
Guided Scrambling (GS) is used for control of the runlength within code blocks, such as d or k, as well as for DC component suppression. A code designed by the GS technique, called a weakly constrained code, does not strictly guarantee the imposed k-constraint, but rather generates code blocks that violate the prescribed constraint with very low probability. In this case, the code rate and efficiency become very high, compared with typical RLL codes using a small constrained length. In this paper, weakly constrained codes based on the convolutional GS and GF-addition GS generate the weakly k-constraint sequences. The probability that a code block violates the k-constraint is measured. To show the superior performance of the GS, the occurrence probability of each runlength is also investigated and compared with the 24/25(0, 8) block code which has a high code rate and adheres to channel constraints. We also compare it with the runlength distribution of a maxentropic RLL sequence and show that the statistical property of the GS-encoded sequences is similar to that of the maxentropic RLL sequence on runlength distribution.
Zhenqiang SUN Shigetomo KIMURA Yoshihiko EBIHARA
This paper presents the generator polynomial matrices and the upper bound on the constraint length of punctured convolutional codes (PCCs), respectively. By virtue of these properties, we provide the puncturing realizations of the good known nonsystematic and systematic high rate CCs.