A pipelined architecture is proposed for the normalized least mean square (NLMS) adaptive digital filter (ADF). Pipelined implementation of the NLMS has not yet been proposed. The proposed architecture is the first attempt to implement the NLMS ADF in the pipelined fashion. The architecture is based on an equivalent expression of the NLMS derived in this study. It is shown that the proposed architecture achieves a constant and a short critical path without producing output latency. In addition, it retains the advantage of the NLMS, i. e. , that the step size that assures the convergence is determined automatically. Computer simulation results that confirm that the proposed architecture achieves convergence characteristics identical to those of the NLMS.

In this letter, a new scheme of designing two-level minimum mean square error quantizer for image coding is proposed. Genetic algorithm is applied to achieve this goal. Comparisons of results with various methods have verified, the proposed method can reach nearly optimal quantization with only less iterations.

One of the most important problems in machine learning is to predict a binary value by observing a sequence of outcomes, up to the present time step, generated from some unknown source. Vovk and Cesa-Bianchi et al. independently proposed an on-line prediction model where prediction algorithms are assumed to be given a collection of prediction strategies called experts and hence be allowed to use the predictions they make. In this model, no assumption is made about the way the sequence of bits to be predicted is generated, and the performance of the algorithm is measured by the difference between the number of mistakes it makes on the bit sequence and the number of mistakes made by the best expert on the same sequence. In this paper we extend the model by introducing a notion of investment. That is, both the prediction algorithm and the experts are required to make bets on their predictions at each time step, and the performance of the algorithm is now measured with respect to the total money lost, rather than the number of mistakes. We analyze our algorithms in the particular situation where all the experts share the same amount of bets at each time step. In this shared bet model, we give a prediction algorithm that is in some sense optimal but impractical, and we also give an efficient prediction algorithm that turns out to be nearly optimal.

Real-time services, including constant bit rate (CBR) and real-time variable bit rate traffic (rt-VBR), have become increasingly important owing to the rapid proliferation of multimedia applications. A cell multiplexing method capable of handling real-time traffic should satisfy related quality of service (QoS) requirements, including cell transfer delay (CTD), cell delay variation (CDV) and cell loss ratio (CLR). In this paper, we present an efficient cell multiplexing method, called longest delay beyond expectation (LDBE), to schedule real-time and non-real-time traffic in ATM networks. For the real-time traffic, LDBE scheme can minimize the CDV, and reduce the CLR and CTD, particularly when different CDV tolerance (CDVT) values are applied at each node along the path of a connection. Simulation results demonstrate that the proposed LDBE performs better than other multiplexing methods regarding these CLR, CDV and CTD criteria for real-time traffic. Furthermore, the proposed LDBE is also suitable for scheduling non-real-time traffic by providing a low CLR for non-real-time variable bit rate (nrt-VBR) and minimizing the CTD for unspecified bit rate (UBR) traffic.

We apply two acceleration techniques for the backpropagation algorithm to an iterative gradient descent algorithm called the network inversion algorithm. Experimental results show that these techniques are also quite effective to decrease the number of iterations required for the detection of input vectors on the classification boundary of a multilayer perceptron.

We apply some variants of evolutionary computations to the fully-connected neural network model of associative memory. Among others, when we regard it as a parameter optimization problem, we notice that the model has some favorable properties as a test function of evolutionary computations. So far, many functions have been proposed for comparative study. However, as Whitley and his colleagues suggested, many of the existing common test functions have some problems in comparing and evaluating evolutionary computations. In this paper, we focus on the possibilities of using the fully-connected neural network model as a test function of evolutionary computations.

This paper proposes genetic algorithms (GAs) for path planning and trajectory planning of an autonomous mobile robot. Our GA-based approach has an advantage of adaptivity such that the GAs work even if an environment is time-varying or unknown. Therefore, it is suitable for both off-line and on-line motion planning. We first presents a GA for path planning in a 2D terrain. Simulation results on the performance and adaptivity of the GA on randomly generated terrains are shown. Then, we discuss an extension of the GA for solving both path planning and trajectory planning simultaneously.

Adaptive maximum likelihood differential detection implemented by a reduced state-transition Viterbi algorithm (called adaptive 3-state RSTVDD) is presented for adaptive reception of M-ary differential phase shift keying (DPSK) signals transmitted over additive white Gaussian noise (AWGN) and frequency-nonselective Rayleigh fading channels. The adaptive 3-state RSTVDD comprises 1DD, a differential encoder, and reverse modulator, followed by reduced-state (3-state) Viterbi DD (RSVDD) with adaptive phase reference estimation. The adaptive 3-state RSVDD detector estimates the sequence of phase errors of the 1DD output. The phase reference estimator is an adaptive least mean square (LMS) filter with a step-size that adapts to changing channel conditions. The final detected symbol sequence is the modulo-2π sum of the 1DD output phase sequence and the detected phase error sequence. The bit error rate (BER) performance of M-ary DPSK, M=4, 8, and 16, in the AWGN and Rayleigh fading channels is evaluated by computer simulation to show that adaptive 3-state RSTVDD can achieve almost the same BER performance as the previously developed adaptive M-state RSVDD. Since the number of trellis states is reduced to three irrespective of M, the adaptive 3-state RSTVDD has lower computation complexity and it is particularly useful for M-ary DPSK with M8.

In this paper, we present a priority scheduling algorithm at ATM switches with multi-class output buffers in which the service rate of each class buffer is dynamically adjusted. The service rate is computed periodically by a control scheme. We derive the design formulas of the control scheme to ensure that each class buffer occupancy converges to its desired operating point related to QoS requirement. Moreover, through dynamic service rate control in the proposed scheduling algorithm, the available channel capacity can be estimated exactly. It may be used for rate control of ABR traffic and call admission control of the other real-time traffic (CBR, VBR, etc. ).

The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. Comparing the quality of solution derived by the DAGA with the General Disk Modulo (GDM), BDM, and ECC methods through the simulation, shows that 1) the DAGA is superior to the GDM method in all the cases and 2) with the restrictions being placed on the number of disks, the average response time of the DAGA is always less than that of the BDM method and greater than that of the ECC method in the absence of data skew and 3) when data skew is considered, the DAGA performs better than or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.

The objective of thinning is to reduce the amount of information in image patterns to the minimum needed for recognition. Thinned image helps the extraction of important features such as end points, junction points, and connections from image patterns. The ultimate goal of parallel algorithms is to minimize the execution time while producing high quality thinned image. Though much research has been performed for parallel thinning algorithms, there has been no systematical approach for comparing the execution speed of parallel thinning algorithms. Several rough comparisons have been done in terms of iteration numbers. But, such comparisons may lead to wrong guides since the time required for iterations varies from one algorithm to the other algorithm. This paper proposes a formal method to analyze the performance of parallel thinning algorithms based on PRAM (Parallel Random Access Machine) model. Besides, the quality of skeletons, robustness to boundary noise sensitivity, and execution speed are considered. Six parallel algorithms, which shows relatively high performance, are selected, and analyzed based on the proposed analysis method. Experiments show that the proposed analysis method is sufficiently accurate to evaluate the performance of parallel thinning algorithms.

This paper presents a new compound constructive algorithm of neural networks whereby the fuzzy logic technique is explored as an efficient learning algorithm to implement an optimal network construction from an initial simple 3-layer network while the genetic algorithm is used to help design an improved network by evolutions. Numerical simulations on artificial life demonstrate that compared with the existing network design algorithms such as the constructive algorithms, the pruning algorithms and the fixed, static architecture algorithm, the present algorithm, called FuzGa, is efficient in both time complexity and network performance. The improved time complexity comes from the sufficiently small 3 layer design of neural networks and the genetic algorithm adopted partly because the relatively small number of layers facilitates an utilization of an efficient steepest descent method in narrowing down the solution space of fuzzy logic and partly because trappings into local minima can be avoided by genetic algorithm, contributing to considerable saving in time in the processing of network learning and connection. Compared with 54. 8 minutes of MLPs with 65 hidden neurons, 63. 1 minutes of FlexNet or 96. 0 minutes of Pruning, our simulation results on artificial life show that the CPU time of the present method reaching the target fitness value of 100 food elements eaten for the present FuzGa has improved to 42. 3 minutes by SUN's SPARCstation-10 of SuperSPARC 40 MHz machine for example. The role of hidden neurons is elucidated in improving the performance level of the neural networks of the various schemes developed for artificial life applications. The effect of population size on the performance level of the present FuzGa is also elucidated.

Since most digital phase-locked loops (DPLLs) used in digital data transmission receivers require both fast acquisition of input frequency and phase in the beginning and substantial jitter reduction in the steady-state, the DPLL loop bandwidth is preferred to being adjusted accordingly. In this paper, a bandwidth adjusting (adaptive) algorithm is presented, which allow both fast acquisition and significant jitter reduction for each different noise environment and hardware requirement. This algorithm, based on the recursive least squares (RLS) criterion, suggest an optimal sequence of control parameters for a dual-loop DPLL which achieves the fastest initial acquisition time by trying to minimize the jitter variance in any given time instant. The algorithm can be used for carrier recovery or clock recovery in mobile communications, local area networks and disk drivers that require a short initial preamble period.

In this paper, we consider the applicability of turbo code for future third generation (3G) mobile telecommunication systems. Futhermore, we propose a simple method of estimating the channel variance which is necessary for the MAP (Maximum A Posteriori) decoding algorithm. We compare the performance of turbo code with a known channel variance, conventional variance estimate and variance estimated by our proposed technique. We show that our variance estimation scheme is adequate for 3G WB-CDMA mobile systems without degradation of turbo code performance.

Retrieving the unknown parameters of scattering objects from measured field data is the subject of microwave imaging. This is naturally and usually posed as an optimization problem. In this paper, micro genetic algorithm coupled with deterministic method is applied to the shape reconstruction of perfectly conducting cylinders. The combined approach, with a very small population like the micro genetic algorithm, performs much better than the conventional large population genetic algorithms (GA's) in reaching the optimal region. In addition, we propose a criterion for switching the micro GA to the deterministic optimizer. The micro GA is utilized to effectively locate the vicinity of the global optimum, while the deterministic optimizer is employed to efficiently reach the optimum after inside this region. Therefore, the combined approach converges to the optimum much faster than the micro GA. The proposed approach is first tested by a function optimization problem, then applied to reconstruct perfectly conducting cylinders from both synthetic data and real data. Impressive and satisfactory results are obtained for both cases, which demonstrate the validity and effectiveness of the proposed approach.

Because of non-negligible ISI due to the Gaussian filter and delay spread in the GSM system, an equalizer is required. In this letter, a joint sliding window channel estimation and timing adjustment method is proposed for maximum likelihood sequence equalizer. And also a smoothing algorithm is presented in order to improve the equalizer performance. This smoothing scheme utilizes a variant of LMS algorithm to tune the channel coefficient estimates. Simulation results show that the proposed scheme is adequate for channel estimation of the adaptive equalizer.

In this paper, a new overload control strategy is proposed for a call control processor (CCP) in the base station controller (BSC) and processor utilization is measured. The proposed overload control strategy can regulate the call attempts by adopting measured processor utilization. A function, specifically a linear interpolation function based on Inverse Transform theory is used to convert controlled predictive average load rate in a call rejection rate. Then a call admission rate is obtained from the call rejection rate. Simulation shows that the proposed algorithm yields better performance than the conventional algorithm does under the heavy transient overload status in terms of call admission rate.

This paper proposes a scalable multiecho cancellation system based on multiple autonomic and distributed echo canceler units. The proposed system does not have any common control section. Distributed control sections are equipped with in multiple echo cancelers operating autonomically. Necessary information is transferred from one unit to the next one. When the number of echoes to be canceled is changed, the necessary number of echo canceler units, each of which may be realized on a single chip, are simply plugged in or unplugged. The proposed system also provides fast convergence thanks to the novel coefficient location algorithm which consists of flat-delay estimation and constrained tap-position control. The input signal is evaluated at each tap to determine when to terminate flat-delay estimation. The number of exchanged taps is selected larger in flat-delay estimation than in constrained tap-position control. The convergence time with a colored-signal input is reduced by approximately 50% over STWQ, and 80% over full-tap NLMS algorithm. With a real speech input, the proposed system cancels the echo by about 20 dB. Tap-positions have been shown to be controlled correctly.

Parallel multiple context-free grammar (PMCFG) and multiple context-free grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple context-free language (MCFL) and parallel multiple context-free language (PMCFL) can be solved in O(ne) time and O(ne+1) time, respectively, where e is a constant which depends only on a given MCFG or PMCFG. In this paper, we propose the following two algorithms. (1) An algorithm which reduces the recognition problem for MCFL to the boolean matrices multiplication problem. (2) An algorithm which reduces the recognition problem for PMCFL to the recognition problem for MCFL. The time complexity of these algorithms is O(ne-3i+1 M(ni)) where e and i are constants which depend only on a given MCFG or PMCFG, and M(k) is the time needed for multiplying two k k boolean matrices. The proposed algorithms are faster than the known fastest algorithms unless e=e, i=1 for MCFG, and e=e, i=0 for PMCFG.

This paper describes a new Artificial Neural Network (ANN), UNItary Decomposition ANN (UNIDANN), which can perform the unitary eigendecomposition of the synaptic weight matrix. It is shown both analytically and quantitatively that if the synaptic weight matrix is Hermitian positive definite, the neural output, based on the proposed dynamic equation, will converge to the principal eigenvectors of the synaptic weight matrix. Compared with previous works, the UNIDANN possesses several advantageous features such as low computation time and no synchronization problem due to the underlying analog circuit structure, faster convergence speed, accurate final results, and numerical stability. Some simulations with a particular emphasis on the applications to high resolution bearing estimation problems are also furnished to justify the proposed ANN.