Toru MURASE Masahiko TSUKAMOTO Shojiro NISHIO
In recent years, the rapid advancements of wireless communication technology and computer down-sizing technology have enabled users to utilize computing resources anywhere in the computer network. New applications constructed on the mobile database system are becoming popular. However, the current database systems do not provide special facilities for specific update operations in a mobile computing environment. Moreover, due to the lack of a common data handling method and a mutual communication mechanism, varieties in implementations may cause applications to be incompatible with each other. In this paper, we take up the issue of data handling, in a mobile computing environment, and propose an active mobile database system (AMDS) to solve this issue. First, we review the difficulties of dynamic update of databases in a mobile computing environment, and provide a basic concept of AMDS as a solution for these difficulties. In order to construct an AMDS, we focus on asynchronous events such as the appearance and disappearance of a mobile computer in a wireless communication cell. Then we provide a facility to specify the behavior of each system in Event-Condition-Action(ECA) rules in the same way as normal active database systems. Moreover, we show the architecture and the design of our implementation of AMDS. And, finally AMDS can be easily implemented as a common database infrastructure and work well on heterogeneous systems through indoor experiments.
Akira MATSUBAYASHI Shuichi UENO
The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.
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.
Yukihisa OKADA Ichiro KOIWA Kinya ASHIKAGA Katsuaki KAIFU
We prepared alkoxide solutions to fabricate SrBi2Ta2O9 (SBT) ferroelectric capacitors with IrO2 electrodes. In this process, to minimize excess bismuth, the Sr : Bi : Ta mole ratio was kept at 0. 9 : 2. 1 : 2. 0, i. e. , nearly stoichiometric. Three types of solution - mixed-only (MIX), complexed (COMP), and hydrolyzed (HYD) - were used. The HYD capacitor had low absolute leakage current, 10-7 A/cm2 order, and good saturation properties to 6 V. When voltage was applied to each capacitor at 2 to 6 V, MIX and COMP capacitors showed only partial hysteresis loops due to a high leakage current, reflecting the I-V characteristics. These results are probably due to film density caused by metaloxane network bonding. A fatigue endurance test was conducted using cycling of polarization switching at 6 V using the HYD capacitor with IrO2 electrodes. Slight changes were, however, observed in hysteresis loop configuration, but good hysteresis properties were kept up to 1. 04 1012 cycles. We compared SBT ferroelectric thin films fabricated with Pt electrodes and with IrO2 electrodes. Scarcely any difference due to SBT in the XRD pattern was seen, depending on the substrate material. We found that the use of IrO2 electrodes had the effect of decreasing the crystallization temperature. On Pt and IrO2 electrodes, the two films have surface morphology quite different from that of the rod-like structure wellknown for SBT films prepared using a metal 2-ethylhexanate solution. Their surfaces show a similar morphology with relatively large, closely packed grains. A comparison of the I-V characteristics after reannealing showed that the capacitor with IrO2 electrodes had a higher leakage current than that with Pt electrodes. The leakage current was probably due to the density of the film and interface between the SBT film and electrodes.
Akira NAKA Toshiya MATSUDA Shigeru SAITO
RZ signal transmission in an anomalous region with periodic dispersion compensation is examined by a straight-line experiment in terms of the compensation ratio, the signal power, and the pulse width. The optimum condition enables single-channel 20-Gbit/s RZ signal and two-WDM-channel 20-Gbit/s signals (40-Gbit/s in total) to be transmitted over 5,520 km and 2,160 km, respectively. Numerical simulations with the assistance of a basic theory enables analysis of the experimental results. It is shown that the balance between the waveform distortion and the remaining Gordon-Haus jitter determines the optimum conditions to achieve the longest transmission distance. Excess dispersion compensation results in waveform distortion, while insufficient compensation causes a greater amount of remaining jitter. Moreover, spectrum deformation during propagation is experimentally and numerically clarified to have a large effect on the transmission performance, especially for WDM transmission.
Ken-ichi IWATA Masakatu MORII Tomohiko UYEMATSU Eiji OKAMOTO
Many Ziv-Lempel algorithms have a similar property, that is, slow encoding and fast decoding. This paper proposes a simple improved Ziv-Lempel algorithm to encode a large amount of data quickly as well as compactly by using multiple-processor system.
Isao NAKANISHI Yoshihisa HAMAHASHI Yoshio ITOH Yutaka FUKUI
In this paper, we propose a new structure of the frequency domain adaptive filter (FDAF). The proposed structure is based on the modified DFT pair which consists of the FIR filters, so that un-delayed output signal can be obtained with stable convergence and without accumulated error which are problems for the conventional FDAFs. The convergence performance of the proposed FDAF is examined through the computer simulations in the adaptive line enhancer (ALE) comparing with the conventional FDAF and the DCT domain adaptive filter. Furthermore, in order to improve the error performance of the FDAF, we propose a composite algorithm which consists of the normalized step size algorithm for fast convergence and the variable step size one for small estimation error. The advantage of the proposed algorithm is also confirmed through simulations in the ALE. Finally, we propose a reduction method of the computational complexity of the proposed FDAF. The proposed method is to utilize a part of the FFT flow-graph, so that the computational complexity is reduced to O(N log N).
Tadashi MATSUMOTO Yasushi MIYANO
A formal necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among known nonnegative integer solutions of state equation and unifying all the causes of those spurious solutions into a maximal-strongly-connected and siphon-and-trap subnet Nw. This result is based on the decomposition of a given net (N, Mo) with Md and the concepts of "no immature siphon at the reduced initial marking Mwo" and "no immature trap at the reduced end marking Mwd" on Nw which are both extended from "no token-free siphon at the initial marking Mo" and "no token-free trap at the end marking Md" on N, respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses.
Young-Han CHOE Dong-Ik LEE Sadatoshi KUMAGAI
Basic structural characteristics, which are useful in modular synthesis based on strongly connected state machines, of SMA/LBFC nets are discussed in this paper. A more convincing and direct proof of the equivalence of two structural characterization of the class of Petri nets is given. This proof will give clearer view of the structural characteristics of LBFC/SMA nets. On the other hand, however, the structural characteristics are not practically amenable in application to modular synthesis of SMA nets from a given set of SCSM's since all possible SCSM's should be examined for the verification of the given conditions. The later half of this paper is devoted into strengthening the results, i. e. , in composition of an SMA net from a given set of SCSM's the condition is also satisfied in any SCSM generated by composition.
In this paper, we propose a transformation technique for the multiplications of one variable with multiple constants, which are frequently seen in the various applications of signal processing, image processing, and so forth. The method is based on the exploration of common subexpressions among constants and reduces the number of shifts, additions, and subtractions to implement linear computations with hardware. Our method searches for regularity among elements of a linear transform using matrix decomposition and generates a reduced data-flow graph which preserves the full regularity. We show experimental results obtained using Discrete Cosine Transform (DCT) and Fast Fourier Transform (FFT) and illustrate the effectiveness of the method.
Jun YANG Dili ZHANG Noboru OHNISHI Noboru SUGIE
We discuss the uniqueness of 3-D shape reconstruction of a polyhedron from a single shading image. First, we analytically show that multiple convex (and concave) shape solutions usually exist for a simple polyhedron if interreflections are not considered. Then we propose a new approach to uniquely determine the concave shape solution using interreflections as a constraint. An example, in which two convex and two concave shapes were obtained from a single shaded image for a trihedral corner, has been given by Horn. However, how many solutions exist for a general polyhedron wasn't described. We analytically show that multiple convex (and concave) shape solutions usually exist for a pyramid using a reflectance map, if interreflection distribution is not considered. However, if interreflection distribution is used as a constraint that limits the shape solution for a concave polyhedron, the polyhedral shape can be uniquely determined. Interreflections, which were considered to be deleterious in conventional approaches, are used as a constraint to determine the shape solution in our approach.
Victor R. L. SHEN Feng-Ho KUO Feipei LAI
As expert system technology gains wider acceptance in digital system design, the need to build and maintain a large scale knowledge base will assume greater importance. However, how to build a correct and efficient rule base is even a hard part in the knowledge-based system development. In this paper, we develop FARHDL (Frame-And-Rule-based Hardware Description Language) to form a knowledge base. The FARHDL is simple but powerful to specify the hardware requirements and can be directly simulated by PROLOG. Through the knowledge base transformed from FARHDL, a formal method can be developed to design, implement, and validate the digital hardware systems. Furthermore, behavioral properties, anomaly properties, structural properties, and timing properties are applied to analyze the requirements specification. The purposes of those properties are used to detect explicit/implicit incorrect specification clauses and to capture some desired requirements, such as completeness and consistency. Finally, the analysis results can be a useful tool for finding obscure problems in tricky digital system designs and can also aid in the development of formal specifications.
Kaoru WATANABE Masakazu SENGOKU Hiroshi TAMURA Shoji SHINODA
The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.
Mitsuhiko YAGYU Akinori NISHIHARA Nobuo FUJII
FIR digital filters composed of parallel multiple subfilters are proposed. A binary expression of an input signal is decomposed into multiple shorter words, which drive the subfilters having different length. The output error is evaluated by mean squared and maximum spectra. A fast algorithm is also proposed to determine optimal filter lengths and coefficients of subfilters. Many examples confirm that the proposed filters generate smaller output errors than conventional filters under the condition of specified number of multiplications and additions in filter operations. Further, multiplier and adder structures (MAS) to perform the operations of the proposed filters are also presented. The number of gates used in the proposed MAS and its critical path are estimated. The effectiveness of the proposed MAS is confirmed.
Nakaba KOGURE Nobuhiko SUGINO Akinori NISHIHARA
Digital signal processors (DSPs) usually employ indirect addressing using an address register (AR) to indicate their memory addresses, which often introduces overhead codes in AR updates for next memory accesses. In this paper, AR update scheme is extended such that address can be efficiently modified by 2 in addition to conventional 1 updates. An automatic address allocation method of program variables for this new addressing model is presented. The method formulates program variables and AR modifications by a graph, and extracts a maximum chained triangle graph, which is accessed only by AR 1 and 2 operations, so that the estimated number of overhead codes is minimized. The proposed methods are applied to a DSP compiler, and memory allocations derived for several examples are compared with memory allocations by other methods.
Martin GUY Stanislav CHERNIKOV Roy TAYLOR
Electroabsorption modulators are high speed devices that are rapidly being commercialised and finding applications in a number of areas, particularly in telecommunications. A CW laser diode modulated by an electroabsorption modulator constitutes an extremely stable, robust and simple source of high quality, high repetition rate ultrashort optical pulses. In this paper we describe the capabilities and limitations of such pulse sources, and present nonlinear pulse compression and manipulation techniques that allow one to overcome these limitations. We also present the design of a new class of comb-like dispersion-profiled fibre compressor. Such a compressor is easily fabricated from commercially available fibres and represents a simple yet powerful way of extending the range of pulse durations available. As the electroabsorption modulator is essentially a high speed switch it is also applicable to optical processing problems, and we report the application of such a device to demultiplexing.
We study nonlinear pulse propagation in an optical transmission system with dispersion compensation. This is particularly important for designing an ultra-fast long-haul communication system in the next generation. There exists a quasi-stationary pulse solution in such a system whose width and chirp are rapidly oscillating with the period of dispersion compensation. This pulse also has several new features such as enhanced power when compared with the soliton case with a uniform dispersion and a deformation from the sech-shape of soliton. We use the averaging method, and the averaged equation to describe the core of the pulse solution is shown to be the nonlinear Schrodinger equation having a nontrapping quadratic potential. Because of this potential, a pulse propagating in such a system eventually decays into dispersive waves in a way similar to the tunneling effect. However in a practical situation, the tunneling effect is estimated to be small, and the decay may be neglected.
Georgios Y. LAZAROU Victor S. FROST Joseph B. EVANS Douglas NIEHAUS
Predicting the performance of high speed wide area ATM networks (WANs) is a difficult task. Evaluating the performance of these systems by means of mathematical models is not yet feasible. As a result, the creation of simulation models is usually the only means of predicting and evaluating the performance of such systems. In this paper, we use measurements to validate simulation models of TCP/IP over high speed ATM wide area networks. Validation of simulations with measurements is not common; however, it is needed so that simulation models can be used with confidence to accurately characterize the performance of ATM WANs. In addition, the appropriate level of complexity of the simulation models needs to be determined. The results show that under appropriate conditions simulation models can accurately predict the performance of complex high speed ATM wide area networks. This work also shows that the user perceived performance is dependent on host processing demands.
It is shown from the Hilberts theory that if the real function Π(θ) has no zeros over the interval [0, 2π], it can be factorized into a product of the factor π+(θ) and its complex conjugate π-(θ)(=). This factorization is tested to decompose a real far-zone field pattern having zeros. To this end, the factorized factors are described in terms of bicomplex mathematics. In our bicomplex mathematics, the temporal imaginary unit "j" is newly defined to distinguish from the spatial imaginary unit i, both of which satisfy i2=-1 and j2=-1.
The effect of sampling-pulse pedestals, generated by pulse compression, on the temporal resolution in electro-optic (EO) sampling is studied both theoretically and experimentally. Analysis is made on how the pedestals degrade a measurement bandwidth and a temporal waveform. Based on the analysis, a practical guideline on the suppression of pedestals is also given. Gain-switched laser diode (LD) pulses adiabatically soliton-compressed using a dispersion decreasing fiber are used to confirm the theoretical results, and are successfully applied to high-temporal-resolution (>100 GHz) EO sampling measurements.