Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. An optimal parallel algorithm for finding a spanning tree on the trapezoid graph is given by Bera et al., it takes O(log n) time with O(n/log n) processors on the EREW (Exclusive-Read Exclusive-Write) PRAM. Bera et al.'s algorithm is very simple and elegant. Moreover, it can correctly construct a spanning tree when the graph is connected. However, their algorithm can not accept a disconnected graph as an input. Applying their algorithm to a disconnected graph, Concurrent-Write occurs once for each connected component, thus this can not be achieved on EREW PRAM. In this paper we present an O(log n) time parallel algorithm with O(n/log n) processors for constructing a spanning forest on trapezoid graph G on EREW PRAM even if G is a disconnected graph.

Finite impulse response (FIR) filtering is the most computationally intensive operation in the channelizer of a wireless communication receiver. Higher order FIR channel filters are needed in the channelizer to meet the stringent adjacent channel attenuation specifications of wireless communications standards. The computational cost of FIR filters is dominated by the complexity of the coefficient multipliers. Even though many methods for reducing the complexity of filter multipliers have been proposed in literature, these works focused on lower order filters. This paper presents a coefficient-partitioning-based binary subexpression elimination method for realizing low power FIR filters. We show that the FIR filters implemented using proposed method consume less power and achieve speed improvement compared to existing filter implementations. Design examples of the channel filters employed in the Digital Advanced Mobile Phone System (D-AMPS) and Personal Digital Cellular (PDC) receivers show that the proposed method achieved 23% average reductions of full adder and power consumption and 23.3% reduction of delay over the best existing method. Synthesis results show that the proposed method offers average area reduction of 8% and power reduction of 22% over the best known method in literature.

We have previously proposed a diffusion-type flow control mechanism as a solution for severely time-sensitive flow control required for high-speed networks. In this mechanism, each node in a network manages its local traffic flow using the basis of only the local information directly available to it, by using predetermined rules. In addition, the implementation of decision-making at each node can lead to optimal performance for the whole network. Our previous studies show that our flow control mechanism with certain parameter settings works well in high-speed networks. However, to apply this mechanism to actual networks, it is necessary to clarify how to design a parameter in our control mechanism. In this paper, we investigate the range of the parameter and derive its optimal value enabling the diffusion-type flow control to work effectively.

We developed a method for extracting feature patterns from multivariate data using a network of coupled phase oscillators subject to an analogue of the Kuramoto model for collective synchronization. Our method may be called data synchronization. We applied data synchronization to the care-needs-certification data, provided by Otsu City as a historical old city near Kyoto City, in the Japanese public long-term care insurance program to find the trend of the major patterns of the aging process for elderly people needing nursing care.

Autonomous Decentralized System (ADS) has been making progress in these 31 years since it was proposed in 1977. During these long years in the rapidly advancing computer and communication technologies, the ADS concept has not been changed but its technologies have been growing in accordance with the change and diversity of the social, economical and personal requirements and through the globalization of the market and the restructuring organizations. The ADS technologies are systematized to cover all processes of system design, operation, maintenance and modification. This paper reviews the work done in fields of ADS in past 31 years from not only technological perspectives, but it also encompasses users requirements and value, system design, industrial activity, academic activity and standardization [1]-[26]. Moreover the new directions of the ADS are suggested.

We study the synchronization of dynamical systems induced by common additional external colored noise. In particular, we consider the special case that the external input noise is generated by a linear second-order differential equation forced by Gaussian white noise. So the frequency spectrum of this noise is not constant. In the case that noise-free dynamics is chaotic, we find examples where the synchronization is enhanced when the peak of the input noise is close to the peak of the noise-free dynamics in frequency space. In the case that noise-free dynamics is non-chaotic, we do not observe this phenomenon.

In this paper, we shall describe about a fuzzy estimation theory based on the concept of set-valued operators, suitable for available operation of extremely complicated large-scale network systems. Fundamental conditions for availability of system behaviors of such network systems are clarified in a form of β-level fixed point theorem for system of fuzzy-set-valued operators. Here, the proof of this theorem is accomplished in a weak topology introduced into the Banach space.

In a codebook based precoding MIMO system, the precoding codebook significantly determines the system performance. Consequently, it is crucial to design the precoding codebook, which is related to the channel fading, antenna number, spatial correlation etc. So specific channel conditions correspond to respective optimum codebooks. In this paper, in order to obtain the optimum codebooks, a universal unitary space vector quantization (USVQ) codebook design criterion is provided, which can design the optimum codebooks for various fading and spatial correlated channels with arbitrary antenna configurations. Furthermore, the unitary space K-mean (USK) algorithm is also proposed to generate the USVQ codebook, which is iterative and convergent. Simulations show that the capacities of the precoding MIMO schemes using the USVQ codebooks are very close to those of the ideal precoding cases and outperform those of the schemes using the traditional Grassmannian codebooks and the 3GPP LTE DFT (discrete Fourier transform) codebooks.

We present on-chip oscillator arrays synchronized by random noises, aiming at skew-free clock distribution on synchronous digital systems. Nakao et al. recently reported that independent neural oscillators can be synchronized by applying temporal random impulses to the oscillators [1],[2]. We regard neural oscillators as independent clock sources on LSIs; i.e., clock sources are distributed on LSIs, and they are forced to synchronize through the use of random noises. We designed neuron-based clock generators operating at sub-RF region (< 1 GHz) by modifying the original neuron model to a new model that is suitable for CMOS implementation with 0.25-µm CMOS parameters. Through circuit simulations, we demonstrate that i) the clock generators are certainly synchronized by pseudo-random noises and ii) clock generators exhibited phase-locked oscillations even if they had small device mismatches.

In this paper we analytically investigate the generalization performance of learning using correlated inputs in the framework of on-line learning with a statistical mechanical method. We consider a model composed of linear perceptrons with Gaussian noise. First, we analyze the case of the gradient method. We analytically clarify that the larger the correlation among inputs is or the larger the number of inputs is, the stricter the condition the learning rate should satisfy is, and the slower the learning speed is. Second, we treat the block orthogonal projection learning as an alternative learning rule and derive the theory. In a noiseless case, the learning speed does not depend on the correlation and is proportional to the number of inputs used in an update. The learning speed is identical to that of the gradient method with uncorrelated inputs. On the other hand, when there is noise, the larger the correlation among inputs is, the slower the learning speed is and the larger the residual generalization error is.

Two phase detectors (PD) are proposed to minimize the phase offset and deadzone when used in DLL or PLL. With the shortest symmetrical racing paths from both inputs, the binary PD achieves fast latch operation and theoretical elimination of the setup time. In contrast to the conventional PDs whose offsets are around 10 ps with large sensitivity to sizing, the proposed binary PD shows an offset of less than 1 ps with a reduction of 30-percent delay time. The proposed latch-type binary phase detection is also expanded to form a linear PD by the addition of a reset-generating circuit.

A QoS management technique based on an autonomous decentralized mobility system, which is an autonomous decentralized system enhanced to provide mobile stations with information about urgent roadway situations, is proposed in this paper. This technique enables urgent messages to be flexibly and quickly transmitted to mobile stations by multiple decentralized base stations using dedicated short range communication. It also supports the easy addition of additional base stations. Each station autonomously creates information-delivery communities based on the urgency of the messages it receives through the roadside network and the distances between the senders and receivers. Each station dynamically determines the urgency of messages according to the message content and the speed of the mobile stations. Evaluation of this technique applied to the Smart Gateway system, which provides driving-assistance services to mobile stations through dedicated short-range communication, demonstrated its effectiveness and that it is suitable for actual systems.

We consider a problem of global asymptotic stabilization of a class of nonlinear systems that have the unknown linear growth rate. While the existing results only deal with one specified form of nonlinear systems, our proposed method includes both forms of triangular and feedforward nonlinear systems in a unified framework. The proposed controller has a dynamic gain mechanism which is selectively engaged based on the given nonlinear form. Then, the dynamic gain is adaptively tuned depending on the unknown linear growth rate.

This letter proposes a novel scheme of joint antenna combination and symbol detection in multi-input multi-output (MIMO) systems, which simultaneously determines the antenna combination coefficients to lower the RF chains and designs the minimum bit error rate (MBER) detector to mitigate the interference. The joint decision statistic, however, is highly nonlinear and the particle swarm optimization (PSO) algorithm is employed to reduce the computational overhead. Simulations show that the new approach yields satisfactory performance with reduced computational overhead compared with pervious works.

In this paper, a robust sound source localization approach is proposed. The approach retains good performance even when model errors exist. Compared with previous work in this field, the contributions of this paper are as follows. First, an improved broad-band and near-field array model is proposed. It takes array gain, phase perturbations into account and is based on the actual positions of the elements. It can be used in arbitrary planar geometry arrays. Second, a subspace model errors estimation algorithm and a Weighted 2-Dimension Multiple Signal Classification (W2D-MUSIC) algorithm are proposed. The subspace model errors estimation algorithm estimates unknown parameters of the array model, i.e., gain, phase perturbations, and positions of the elements, with high accuracy. The performance of this algorithm is improved with the increasing of SNR or number of snapshots. The W2D-MUSIC algorithm based on the improved array model is implemented to locate sound sources. These two algorithms compose the robust sound source approach. The more accurate steering vectors can be provided for further processing such as adaptive beamforming algorithm. Numerical examples confirm effectiveness of this proposed approach.

This work addresses the issue on the robustness performance in M-ary quantization watermarking. If the encoded messages are arranged in the order of Gray Code such that adjacent messages differ at only one bit, this work demonstrates the robustness will be substantially improved in low DNR scenarios. Furthermore, the two-bit quantization watermarking can outperform the LUT approach which also provides the robustness improvement in the high-noisy environments.

In this paper, we propose new joint transport and MAC protocols for ad hoc wireless networks based on an optimization framework. To overcome the practical and efficiency limitations of previous research, we develop a different framework based on independent sets and propose an implementable heuristic algorithm. We address the implementation issues of the proposed algorithm. Simulation results confirm the efficiency and fairness of our protocols.

In this letter, we propose a new histogram equalization method to compensate for acoustic mismatches mainly caused by corruption of additive noise and channel distortion in speech recognition. The proposed method employs an improved test cumulative distribution function (CDF) by more accurately smoothing the conventional order statistics-based test CDF with the use of window functions for robust feature compensation. Experiments on the AURORA 2 framework confirmed that the proposed method is effective in compensating speech recognition features by reducing the averaged relative error by 13.12% over the order statistics-based conventional histogram equalization method and by 58.02% over the mel-cepstral-based features for the three test sets.

In this paper, we propose a new localization algorithm and improve the DV-Hop algorithm by using a differential error correction scheme that is designed to reduce the location error accumulated over multiple hops. This scheme needs no additional hardware support and can be implemented in a distributed way. The proposed method can improve location accuracy without increasing communication traffic and computing complexity. Simulation results show the performance of the proposed algorithm is superior to that of the DV-Hop algorithm.

This paper studies two kinds of simple switched dynamical systems with piecewise constant characteristics. The first one is based on the single buck converter whose periodic/chaotic dynamics are analyzed precisely using the piecewise linear phase map. The second one is based on a paralleled system of the buck converters for lower voltages with higher current capabilities. Referring to the results of the single system, it is clarified that stable multi-phase synchronization is always possible by the proper use of the switching strategies and adjustment of the clock period. Presenting a simple test circuit, typical operations are confirmed experimentally.