In this paper we consider a parallel and distributed computation of genetic algorithms on loosely-coupled multiprocessor systems. Loosely-coupled ones are more suitable for massively parallel processing and also more easily VLSI implementation than tightly-coupled ones. However, communication overhead on parallel processing is more serious for loosely-coupled ones. We propose in this paper a parallel and distributed execution method of genetic algorithm on loosely-coupled multiprocessor systems of fixed network topologies in which each processor element carries out genetic operations on its own chromosome set and communicates with only the neighbors in order to save communication overhead. We evaluate the proposed method on the multiprocessor systems with ring, torus, and hypercube topologies for benchmark problem instances. From the results, we find that the ring topology is more suitable for the proposed parallel and distributed execution since variety of chromosomes in the ring is kept much more than that in the others. Moreover, we also propose a new network topology called cone which is a hierarchical connection of ring topologies. We show its effectiveness by experimental evaluation.

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.

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.

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).

A new numerical approach for the analysis of electromagnetic scattering from a body moving in an arbitrary direction is described. A time dependent grid generation is applied to solve these problems. We are treating this method for a quasi-stationary field. Some numerical results are compared with the exact ones and excellent agreement between them is obtained.

In this paper, we compare the performance of evolutionary digital filters (EDFs) for IIR adaptive digital filters (ADFs) in terms of convergence behavior and stability, and discuss their advantages. The authors have already proposed the EDF which is controlled by adaptive algorithm based on the evolutionary strategies of living things. This adaptive algorithm of the EDF controls and changes the coefficients of inner digital filters using the cloning method or the mating method. Thus, the adaptive algorithm of the EDF is of a non-gradient and multi-point search type. Numerical examples are given to demonstrate the effectiveness and features of the EDF such that (1) they can work as adaptive filters as expected, (2) they can adopt various error functions such as the mean square error, the absolute sum error, and the maximum error functions, and (3) the EDF using IIR filters (IIR-EDF) has a higher convergence rate and smaller adaptation noise than the LMS adaptive digital filter (LMS-ADF) and the adaptive digital filter based on the simple genetic algorithm (SGA-ADF) on a multiple-peak surface.

In an iterative decoding algorithm, such as Chase Type-II decoding algorithm and its improvements, candidate codewords for a received vector are generated for test based on a bounded-distance decoder and a set of test error patterns. It is desirable to remove useless test error patterns in these decoding algorithms. This paper presents a sufficient condition for ruling out some useless test error patterns. If this condition holds for a test error patterns e, then e can not produce a candidate codeword with a correlation metric larger than those of the candidate codewords generated already and hence e is useless. This significantly reduces the decoding operations in Chase type-II decoding algorithm or decoding iterations in its improvements.

Although ATM networks support various traffic requirements, but many data applications are unable to precisely specify traffic parameters such as bit rate. These applications generally require a dynamic share of the available bandwidth among all active connections, they are called available-bit-rate (ABR) service. Due to bursty and unpredictable pattern of an ABR data stream, its traffic control is more challenging than other services. In this paper, we present an improved ABR traffic control approach, called Offset Proportional Rate Control Algorithm (OPRCA). The proposed approach achieves high link utilization, low delay and weighted fair sharing among contenting sources according to the predefined OPR. The implementation is much simpler than that of existing schemes. OPRCA combines an end-to-end rate control with link-by-link feedback control, and employs a buffering scheme that avoids Head-of-Line (HOL) blocking. It can dynamically regulate the transmission rate of source traffic and maintain the real fairness among all active connections. Simulation results have shown the effectiveness of OPRCA in several performance aspects.

This paper describes a method for analyzing active impedance, i. e. equivalent resistance and equivalent reactance, of a narrow-band transistor Colpitts crystal oscillator. This oscillator, employing an AT-cut resonator filter, has a very narrow-band width and an achievement of extremely low phase-noise characteristics is expected. The analysis proposed is based on an algebraic formula, which employs a nonlinear approximation for transistor gm, and a simplified circuit model. Calculated results are compared with the experimental results in the frequency characteristics of the oscillator active impedance with changing the driving signal current. Good agreement between the calculation and experimental results shows that the proposed technique is suitable for designing Colpitts crystal oscillators with resonator filters. In addition we apply this technique to the analysis of dual-mode crystal oscillators.

In a recent paper, Yang proposes an integer labeling algorithm for determining whether an arbitrary simplex P in Rn contains an integer point or not. The problem under consideration is a very difficult one in the sense that it is NP-complete. The algorithm is based on a specific integer labeling rule and a specific triangulation of Rn. In this paper we discuss a practical implementation of the algorithm and present a computer program (ILIN) for solving integer programming using integer labeling algorithm. We also report on the solution of a number of tested examples with up to 500 integer variables. Numerical results indicate that the algorithm is computationally simple, flexible, efficient and stable.

In this paper we newly define a generalized edge-ranking of a graph G as follows: for a positive integer c, a c-edge-ranking of G is a labeling (ranking) of the edges of G with integers such that, for any label i, deletion of all edges with labels >i leaves connected components, each having at most c edges with label i. The problem of finding an optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n2log Δ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T. Our algorithm is faster than the best algorithm known for the case c=1.

This paper presents the results of the best differential characteristic search of FEAL. The search algorithm for the best differential characteristic (best linear expression) was already presented by Matsui, and improvements on this algorithm were presented by Moriai et al. We further improve the speed of the search algorithm. For example, the search time for the 7-round best differential characteristic of FEAL is reduced to about 10 minutes (Pentium/166 MHz), which is about 212. 6 times faster than Matsui's algorithm. Moreover, we determine all the best differential characteristics of FEAL for up to 32 rounds assuming all S-boxes are independent. As a result, we confirm that the N-round (7N32) best differential characteristic probability of FEAL is 2-2N, which was found by Biham. For N=6, we find 6-round differential characteristics with a greater probability, 2-11, than that previously discovered, 2-12.

An adaptive infinite impulse response (IIR) filter implemented using an allpass and a minimum phase system has an advantage of its poles converging to the poles of the unknown system when the input is a white signal. However, when the input signal is colored, convergence speed deteriorates considerably, even to the point of lack of convergence for certain colored signals. Furthermore with a colored input signal, there is no guarantee that the poles of the adaptive digital filter (ADF) will converge to the poles of the unknown system. In this paper we propose a method which uses a linear predictor filter to whiten the input signal so as to improve the convergence characteristic. Computer simulation results confirm the increase in convergence speed and the convergence of the poles of the ADF to the poles of the unknown system even when the input is a colored signal.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.

In this paper, a dynamic constructive algorithm for fault tolerant feedforward neural network, called DCFTA, is proposed. The algorithm starts with a network with single hidden neuron, and a new hidden unit is added dynamically to the network whenever it fails to converge. Before inserting the new hidden neuron into the network, only the weights connecting the new hidden neuron to the other neurons are trained (i. e. , updated) until there is no significant reduction of the output error. To generate a fault tolerant network, the relevance of each synaptic weight is estimated in each cycle, and only the weights which have their relevance less than a specified threshold are updated in that cycle. The loss of a connections between neurons (which are equivalent to stuck-at-0 faults) are assumed. The simulation results indicate that the network constructed by DCFTA has a significant fault tolerance ability.

In this paper, a new nonlinear integrator with positive phase shifts is proposed. Results of the digital simulation show that the nonlinear integrator has a better performance than the conventional one in a control system.

A genetic algorithm is presented for the blind-deconvolution problem of image restoration without any a priori information about object image or blurring function. The restoration problem is modeled as an optimization problem, whose cost function is to be minimized based on mechanics of natural selection and natural genetics. The applicability of GA for blind-deconvolution problem was demonstrated.

In this paper, three issues concerning the linear adaptive receiver using the LMS algorithm for single-user demodulation in direct-sequence/code-division multiple-access (DS/CDMA) systems are considered. First, the convergence rate of the LMS algorithm in DS/CDMA environment is considered theoretically. Both upper and lower bounds of the eigenvalue spread of the autocorrelation matrix of receiver input signals are derived. It is cleared from the results that the convergence rate of the LMS algorithm becomes slow when the signal power of interferer is large. Second, fast converging technique using a prefilter is considered. The LMS based adaptive receiver using an adaptive prefilter adjusted by a Hebbian learning algorithm to decorrelate the input signals is proposed. Computer simulation results show that the proposed receiver provides faster convergence than the LMS based receiver. Third, the complexity reduction of the proposed receiver by prefiltering is considered. As for the reduced complexity receiver, it is shown that the performance degradation is little as compared with the full complexity receiver.

Subtrellises for low-weight codewords of binary linear block codes have been recently used in a number of trellis-based decoding algorithms to achieve near-optimum or suboptimum error performance with a significant reduction in decoding complexity. An algorithm for purging a full code trellis to obtain a low-weight subtrellis has been proposed by H.T. Moorthy et al. This algorithm is effective for codes of short to medium lengths, however for long codes, it becomes very time consuming. This paper investigates the structure and complexity of low-weight subtrellises for binary linear block codes. A construction method for these subtrellises is presented. The state and branch complexities of low-weight subtrellises for Reed-Muller codes and some extended BCH codes are given. In addition, a recursive algorithm for searching the most likely codeword in low-weight subtrellis-based decoding algorithm is proposed. This recursive algorithm is more efficient than the conventional Viterbi algorithm.

The approach presented in this paper was intended for extending conventional Markov random field (MRF) models to a more practical problem: the unsupervised and adaptive segmentation of gray-level images. The "unsupervised" segmentation means that all the model parameters, including the number of image classes, are unknown and have to be estimated from the observed image. In addition, the "adaptive" segmentation means that both the region distribution and the image feature within a region are all location-dependent and their corresponding parameters must be estimated from location to location. We estimated local parameters independently from multiple small windows under the assumption that an observed image consists of objects with smooth surfaces, no texture. Due to this assumption, the intensity of each region is a slowly varying function plus noise, and the conventional homogeneous hidden MRF (HMRF) models are appropriate for these windows. In each window, we employed the EM algorithm for maximum-likelihood (ML) parameter estimation, and then, the estimated parameters were used for "maximizer of the posterior marginals" (MPM) segmentation. To keep continuous segments between windows, a scheme for combining window fragments was proposed. The scheme comprises two parts: the programming of windows and the Bayesian merging of window fragments. Finally, a remerging procedure is used as post processing to remove the over-segmented small regions that possibly exist after the Bayesian merging. Since the final segments are obtained from merging, the number of image classes is automatically determined. The use of multiple parallel windows makes our algorithm to be suitable for parallel implementation. The experimental results of real-world images showed that the surfaces (objects) consistent with our reasonable model assumptions were all correctly segmented as connected regions.