Sayaka KAMEI Hirotsugu KAKUGAWA
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1-1/l), where l is the number of leaves of optimal solution.
Michio OYAMAGUCHI Yoshikatsu OHTA
G.Huet (1980) showed that a left-linear term-rewriting system (TRS) is Church-Rosser (CR) if P Q for every critical pair
where P Q is a parallel reduction from P to Q. But, it remains open whether it is CR when Q P for every critical pair
. In this paper, we give a partial solution to this problem, that is, a left-linear TRS is CR if Q where Q generated from two rules overlapping at an occurrence u. Here, Q .
Satoshi UEMURA Miki HASEYAMA Hideo KITAJIMA
In this paper, a novel description method of the contour of a shape using extended fractal interpolation functions (EFIFs) is presented. Although the scope of application of traditional FIFs has been limited to cases in which a given signal is represented by a single-valued function, the EFIFs derived by the introduction of a new parameter can describe a multiple-valued signal such as the contour of a shape with a high level of accuracy. Furthermore, the proposed description method possesses the useful property that once a given contour has been modeled by the proposed description method, the shape can be easily expanded at an arbitrary expansion rate. Experimental results show the effectiveness and usefulness of the proposed description method for representing contours.
Takeshi MASUYAMA Hiroshi NAKAGAWA
Although many researchers have verified the superiority of Support Vector Machine (SVM) on text categorization tasks, some recent papers have reported much lower performance of SVM based text categorization methods when focusing on all types of parts of speech (POS) as input words and treating large numbers of training documents. This was caused by the overfitting problem that SVM sometimes selected unsuitable support vectors for each category in the training set. To avoid the overfitting problem, we propose a two step text categorization method with a variable cascaded feature selection (VCFS) using SVM. VCFS method selects a pair of the best number of words and the best POS combination for each category at each step of the cascade. We made use of the difference of words with the highest mutual information for each category on each POS combination. Through the experiments, we confirmed the validation of VCFS method compared with other SVM based text categorization methods, since our results showed that the macro-averaged F1 measure (64.8%) of VCFS method was significantly better than any reported F1 measures, though the micro-averaged F1 measure (85.4%) of VCFS method was similar to them.
Masataka TAKAMURA Yoshihide IGARASHI
Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.
Zhihui WANG Tohru KIRYU Keisuke SHIBAI Shinkichi SAKAHASHI
In this paper, we present a flexible distributed computing system in which it is very easy to add required computing components at any time. The system is an Internet-based solution, and mainly developed by Java and XML. Moreover, by implementing a new configuration of computing information that is setting up Public Information and Private Information, the system can accommodate various computing requests, and facilitate a flexible design. Additionally, to show the practical merit, as an example of signal processing, we presented how to apply our proposed system to selection of a suitable artificial neural network.
Wichai PONGWILAI Ryuji KOHNO Sawasd TANTARATANA
We propose a new approach associated with the use of some selected sets of Walsh Hadamard codes for joint estimation of channels and the number of transmit antennas by employing only one OFDM pilot symbol. This allows transmit antenna diversity to be applied in systems which have a limited number of training symbols (preambles), e.g. HIPERLAN/2. The proposed approach does not require any a priori knowledge about the number of transmit antennas, providing flexibility in the number of antennas to be used. In addition, adaptive scheme associated with the proposed approach provides more accurate estimations of the channels. The effectiveness of the proposed approach is evaluated through simulation. Results show that the proposed scheme provides significant improvement over previous channel estimation schemes and has almost the same performance as the ideal system with the full knowledge of the channel state information.
In this paper, we propose a self-nonself recognition algorithm based on positive and negative selection used in the developing process of T cells. The anomaly detection algorithm based on negative selection is a representative model among self-recognition method and it has been applied to computer immune systems in recent years. In biological immune systems, T cells are produced through both positive and negative selection. Positive selection is the process used to determine a MHC receptor that recognizes self-molecules. Negative selection is the process used to determine an antigen receptor that recognizes antigens, or nonself cells. In this paper, we propose a self-recognition algorithm based on the positive selection and also propose a fusion algorithm based on both positive and negative selection. To verify the effectiveness of the proposed system, we show simulation results for detecting some infected data obtained from cell changes and string changes in the self-file.
Shu-Min TSAI Jia-Ching WANG Jar-Ferr YANG Jhing-Fa WANG
In this paper, we propose a speech coding translation scheme by transferring coding parameters between GSM half rate and G.729 coders. Compared to the conventional decode-then-encode (DTE) scheme, the proposed parameter conversions provide speech interoperability between mobile and IP networks with reducing computational complexity and coding delay. Simulation results show that the proposed methods can reduce about 30% computational load and coding delay acquired in the target encoders and achieve almost imperceptible degradation in performance.
Rong-Long WANG Xin-Shun XU Zheng TANG
We present a learning algorithm of the Hopfield neural network for minimizing edge crossings in linear drawings of nonplanar graphs. The proposed algorithm uses the Hopfield neural network to get a local optimal number of edge crossings, and adjusts the balance between terms of the energy function to make the network escape from the local optimal number of edge crossings. The proposed algorithm is tested on a variety of graphs including some "real word" instances of interconnection networks. The proposed learning algorithm is compared with some existing algorithms. The experimental results indicate that the proposed algorithm yields optimal or near-optimal solutions and outperforms the compared algorithms.
Xiaodong REN Shidong ZHOU Zucheng ZHOU
This letter introduces a novel multi-user detection method, successive interference cancellation based on the order of log-likelihood-ratio(LLR-SIC), for code division multiple access (CDMA) systems. Unlike the conventional successive interference cancellation (SIC) based on the order of correlation, LLR-SIC operates on the fact that the user with the largest absolute value of log-likelihood ratio (LLR) should be first detected and cancelled from received signal. Simulation results show that LLR-SIC significantly outperforms the conventional SIC and partial parallel interference cancellation (P-PIC) over Rayleigh fading channels, and that LLR-SIC performance is not sensitive to channel estimation error at medium Eb/N0.
This paper proposes a new decision feedback decoding scheme for Alamouti-based space-time block coding (STBC) transmission over time-selective fading channels. In wireless channels, time-selective fading effects arise mainly due to Doppler shift and carrier frequency offset. Modelling the time-selective fading channels as the first-order Gauss-Markov processes, we use recursive algorithms such as Kalman filtering, LMS and RLS algorithms for channel tracking. The proposed scheme consists of the symbol decoding stage and channel tracking algorithms. Computer simulations confirm that the proposed scheme shows the better performance and robustness to time-selectivity.
Pi-Chung WANG Chia-Tai CHAN Shuo-Cheng HU Chun-Liang LEE
Rectangle search is a well-known packet classification scheme which is based on multiple hash accesses for different filter length. It shows good scalability with respect to the number of filters; however, the performance is not fast enough to fulfill the high-speed requirement of packet classification. In this paper, we propose a lookahead caching which can significantly improve the performance of hash-based algorithm. The basic idea is to filter out the un-matched probing case by using dual-hash architecture. The experimental results indicate that the proposed scheme can improve the performance by the factor of two for the 2-dimension (source prefix, destination prefix) filter database.
Yankang WANG Makoto ANDO Tomohiro TANIKAWA Kazuhiro YOSHIDA Jun YAMASHITA Hideaki KUZUOKA Michitaka HIROSE
This paper presents a block-based motion vector search algorithm for video coding based on an interpolation scheme of search blocks. The basic idea of motion vector estimation between frames is to select a block in the previous frame that best matches a block in the current frame by minimizing the difference between them. In most of the search algorithms, however, the best-match block can only be on a pre-defined grid pattern. Although using a pre-defined pattern increases the search efficiency, it may also reduce the search accuracy. To balance the two aspects and to fully utilize the block information, we propose a strategy, which, instead of selecting from pre-defined blocks, searches for a best match interpolated from the pre-defined blocks. Experiment results demonstrate a better accuracy and efficiency of this search method than some commonly-used methods for different kinds of motion.
This letter presents a new concatenated code and a new criterion for the new concatenated code in fast Rayleigh fading channel. The new concatenated code consists of the cascade of a new space-time trellis code (STTC) as an inner code and a new convolutional code as an outer code. The new criterion maximizes the minimum free distance for the new convolutional code and both the minimum trace and the average trace of distance matrix for the new STTC. The new concatenated code improves the frame error rate (FER) performance significantly with low complexity. The new STTC and convolutional code are designed so as to satisfy the new criterion for 4-state 4 phase shift keying (PSK). The results of the suggested concatenated code are obtained using two transmit antennas, and shown to be significantly superior to the new and existing STTCs. As the number of receive antennas increases, the performance of the new concatenated code significantly improves, for instance, reaches FER = 10-3 at signal-to-noise ratio (SNR) = 5.2 dB for four receive antennas. Note that the proposed concatenated code also improves significant FER performance by using only one receive antenna for high SNR.
Young-Hwan YOU Cheol-Hee PARK Dae-Ki HONG Min-Chul JU Sung-Jin KANG Jin-Woong CHO
In this letter, we present an adaptive hopping technique for a wireless personal area network (WPAN) system employing a frequency hop spread spectrum (FH/SS). Analytical results based on the closed-form solutions for the aggregate throughput show that the proposed hopping algorithm using two defined hopping criteria is more friendly towards all kinds of interferers and gives an enhanced throughput with a moderate computational complexity.
Lan ZHANG Masataka MORIYA Tadayuki KOBAYASHI Masashi MUKAIDA Toshinari GOTO
In-plane-aligned a-axis-oriented YBa2Cu3O7-δ (YBCO) thin films are attractive for the formation of planar intrinsic Josephson devices. In this study, these films were deposited by dc sputtering on LaSrGaO4 (LSGO) (100) substrates and the dependence of the characteristics on the deposition conditions was investigated. In-plane-aligned a-axis-oriented YBCO thin films were successfully grown in the substrate temperature range of 555-615. With the temperature gradient method, it was seen that the critical temperature of the film increased to 81 K. The current-voltage characteristic along the c-axis exhibited clear multibranch structures. These results indicate that ion-cleaning of the substrate surface broadens the growth temperature range of these films and planar intrinsic Josephson devices can be fabricated from these films.
In this paper, we consider a problem of global stabilization of a class of nonlinear systems which are approximately feedback linearizable. We propose a control law with the gain-scaling factor and analytically show the robust aspect of approximate feedback linearization in a more general framework.
In this paper, we propose a new counting scheme for m n contingency tables. Our scheme is a modification of Dyer and Greenhill's scheme for two rowed contingency tables. We can estimate not only the sizes of error, but also the sizes of the bias of the number of tables obtained by our scheme, on the assumption that we have an approximate sampler.
Hidetoshi IKEDA Kawori TAKAKUBO Hajime TAKAKUBO
Temperature dependence of drain current is analyzed in detail in terms of mobility and threshold voltage. From the analyses, it is proved that a point exists that the drain current is fixed without depending on temperature when the MOSFET operates in strong inversion. Applying this characteristic, a CMOS temperature-voltage converter operating in strong inversion with high linearity is proposed. SPICE simulation and experimental results are shown, and the corresponding performances are discussed.