The ultrasonic wave is widely used for acquiring perceptual information necessary for indoor/outdoor navigation of mobile robots, where the system is implemented as a sound navigation and ranging system (sonar). A robot equipped with multiple ultrasonic sonars is likely to exhibit undesirable operation due to erroneous measurements resulting from cross-talk among the sonars. Each sonar transmits and receives a pulse-modulated ultrasonic wave for measuring the range and identifying its own signal. We propose a technique for generating pulse patterns for multiple concurrently operated ultrasonic sonars. The approach considers pulse-pattern generation as a combinatorial optimization problem which can be solved by a genetic algorithm (GA). The aim is to acquire a pulse pattern satisfying certain conditions in order to avoid cross-talk or keep the probability of erroneous measurement caused by cross-talk low. We provide a method of genotype coding for the generation of the pulse pattern. Furthermore, in order to avoid a futile search encountered when the conventional technique is used, we propose an improved genotype coding technique that yields considerably different results from those of the conventional technique.

This paper proposes a fast algebraic codebook search for DSVD applications. In this method, the codebook search is simplified by reducing the number of possible position combinations using a mean-based track threshold multiplied by heuristically determined optimum threshold factor. And, to guarantee a complexity requirement of DSVD, the maximum number of searching position combinations is limited to 320. The proposed method reduced computational complexity considerably, compared with G.729 with a slight degradation of SNR. Particularly, it shows better speech quality with lower complexity than G.729A.

This paper introduces a new approach based on the geographic nearest neighbors for constructing the Delaunay triangulation (a dual of the Voronoi diagram) of a set of n sites in the plane under the L1 metric. In general, there is no inclusion relationship between the Delaunay triangulation and the octant neighbor graph. We however find that under the L1 metric the octant neighbor graph contains at least one edge of each triangle in the Delaunay triangulation. By using this observation and employing a range tree scheme, we design an algorithm for constructing the Delaunay triangulation (thus the Voronoi diagram) in the L1 metric. This algorithm takes O(n log n) sequential time for constructing the Delaunay triangulation in the L1 metric. This algorithm can easily be parallelized, and takes O(log n) time with O(n) processors on a CREW-PRAM.

In this paper we propose a learning algorithm to enhance the fault tolerance of feedforward neural networks (NNs for short) by manipulating the gradient of sigmoid activation function of the neuron. We assume stuck-at-0 and stuck-at-1 faults of the connection link. For the output layer, we employ the function with the relatively gentle gradient to enhance its fault tolerance. For enhancing the fault tolerance of hidden layer, we steepen the gradient of function after convergence. The experimental results for a character recognition problem show that our NN is superior in fault tolerance, learning cycles and learning time to other NNs trained with the algorithms employing fault injection, forcible weight limit and the calculation of relevance of each weight to the output error. Besides the gradient manipulation incorporated in our algorithm never spoils the generalization ability.

Conventional adaptive array antenna processing must access signals on all of the array antenna elements. However, because the low-cost electronically steerable passive array radiator (ESPAR) antenna only has a single-port output, all of the signals on the antenna elements cannot be observed. In this paper, a technique for adaptively controlling the loaded reactances on the passive radiators, thus forming both beam and nulls, is presented for the ESPAR antenna. The adaptive algorithm is based on the steepest gradient theory, where the reactances are sequentially perturbed to determine the gradient vector. Simulations show that the ESPAR antenna can be adaptive. The statistical performance of the output SIR of the ESPAR antenna is also given.

This paper proposes a 2.6 GHz low cost DBF array antenna system and reports its evaluation based on our experimental results. The proposed system is partially constructed by digital devices for the simplification of hardware, and employs some techniques for improving the resolution. The system is evaluated through the DOA estimation by the MUSIC algorithm inside a radio anechoic chamber. As a result, we found that the proposed system estimates the DOA with the highest accuracy at which MUSIC algorithm can perform. Moreover, this paper discusses the estimation errors. We also found that the estimation error is particularly affected from the inaccurate element interval.

Constant Modulus Algorithm (CMA) is a method that has been widely known as blind adaptive beamforming because it requires no knowledge about the signal except that the transmitted signal waveform has a constant envelope. Although CMA has the merit of this blind operation, it possesses problems in its convergence property. In this paper, problems that are inherent to this algorithm is resolved using a combination of CMA and another major adaptive algorithm SMI (Sample Matrix Inversion). The idea is to use SMI to determine the initial weights for CMA operation. Although the benefit of CMA being a blind algorithm is not fully taken advantage of, good aspects of both SMI and CMA can be introduced. By using this approach, two major problems in convergence properties of CMA can be solved. One of these problems is the reliability and this relates to the convergence performance in certain cases. When the interfering signal is stronger than the desired signal, the algorithm tends to come up with the wrong solution by capturing the interfering signal which has the stronger power. Also, the convergence time of this algorithm is slow, limiting its application in dynamic environment, although the slow convergence time of CMA has been studied previously and several methods have been proposed to overcome this defect. Using the proposed method, the deterioration due to both of these problems can be mitigated. Simulation results are shown to confirm the theory. Furthermore, evaluations are done concerning the fading characteristics. It is also confirmed from the simulation that the tracking performance of this method can be regarded as sufficient in personal mobile communication.

In this paper, we propose a multi-level block matching algorithm using motion information in blocks. In the proposed algorithm, the block-level is decided by the motion degree in the block before motion searching procedure, and then adequate motion searching performs according to the block-level. Which improves computational efficiency by eliminating an unnecessary searching process in no motion or low motion regions, and brings more accurate estimation results by deepening motion searching process in high motion regions. Simulation results show that the proposed algorithm brings the lower estimation error--about 20% MSE reduction--with the fewer blocks per frame and the lower computational loading--about 98% operational amount reduction--than full search block matching algorithm with constant block size.

We describe a simplified receiver structure having several receiving antennas (i.e., an adaptive array antenna system) and using time-division-multiplexing (TDM) signal processing. Three simplified receiver structures were investigated for use in the antenna system. To confirm the feasibility of using a TDM receiver, both a TDM receiver and a conventional adaptive array receiver were constructed for testing. In our proposed system, several repetitions of the constant modulus algorithm (CMA) are used to reduce co-channel interference (CCI). The frame format used for both receivers was the same as that of the personal handy phone system in Japan. The laboratory testing was done using a fading simulator to enable measurement of the bit error rate. The results are very promising and show the feasibility of the TDM receiver.

This paper presents a genetic algorithm for designing at minimum cost a two-connected network topology such that the shortest cycle (referred to as a ring) to which each edge belongs does not exceed a given maximum number of hops. The genetic algorithm introduces a solution representation in which constraints such as connectivity and ring constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided thus resulting in increased efficiency. Experimental evaluation shows the effectiveness of the proposed GA.

Multi-level divide-and-conquer (MDC) is a generalized divide-and-conquer technique, which consists of more than one division step organized hierarchically. In this paper, we investigate the paradigm of the MDC and show that it is an efficient technique for designing parallel algorithms. The following parallel algorithms are used for studying the MDC: finding the convex hull of discs, finding the upper envelope of line segments, finding the farthest neighbors of a convex polygon and finding all the row maxima of a totally monotone matrix. The third and the fourth algorithms are newly presented. Our discussion is based on the EREW PRAM, but the methods discussed here can be applied to any parallel computation models.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.

A digit-recurrence algorithm for cube rooting is proposed. In cube rooting, the digit-recurrence equation of the residual includes the square of the partial result of the cube root. In the proposed algorithm, the square of the partial result is kept, and the square, as well as the residual, is updated by addition/subtraction, shift, and multiplication by one or two digits. Different specific versions of the algorithm are possible, depending on the radix, the digit set of the cube root, and etc. Any version of the algorithm can be implemented as a sequential (folded) circuit or a combinational (unfolded) circuit, which is suitable for VLSI realization.

In this paper, we present deterministic parallel algorithms for the convex hull of sorted points and their application to a related problem. The algorithms are proposed for the coarse grained multicomputer (CGM) model. We first propose a cost optimal parallel algorithm for computing the problem with a constant number of communication rounds for n/p p2, where n is the size of an input and p is the number of processors. Next we propose a cost optimal algorithm, which is more complicated, for n/p pε, where 0 < ε < 2. From the above two results, we can compute the convex hull of sorted points with O(n/p) computation time and a constant number of communication rounds for n/p pε, where ε > 0. Finally we show an application of our convex hull algorithms. We solve the convex layers for d lines in O((n log n)/p) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

In order to compute gcd of polynomials, the Euclidean algorithm is used. We estimate the complexities of known Euclidean algorithms. Further, we propose a heuristic Euclidean algorithm. This is faster than ordinary methods under some special conditions by the use of the recurrent Karatsuba multiplication.

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k nε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k nε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O((n α(n) log3 n)/p) time using p processors, where 1 p n1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

The uniform switching system is the family of non-linear n m binary arrays constrained such that all columns are from the constant weight k vectors and all rows have weights divisible by p > 0. For this system, we present a cardinality formula and an enumerative algorithm.

This paper presents the outline of the systolic array recursive least-squares (RLS) processor prototyped primarily with the aim of broadband mobile communication applications. To execute the RLS algorithm effectively, this processor uses an orthogonal triangularization technique known in matrix algebra as QR decomposition for parallel pipelined processing. The processor board comprises 19 application-specific integrated circuit chips, each with approximately one million gates. Thirty-two bit fixed-point signal processing takes place in the processor, with which one cycle of internal cell signal processing requires approximately 500 nsec, and boundary cell signal processing requires approximately 80 nsec. The processor board can estimate up to 10 parameters. It takes approximately 35 µs to estimate 10 parameters using 41 known symbols. To evaluate signal processing performance of the prototyped systolic array processor board, processing time required to estimate a certain number of parameters using the prototyped board was comapred with using a digital signal processing (DSP) board. The DSP board performed a standard form of the RLS algorithm. Additionally, we conducted minimum mean-squared error adaptive array in-lab experiments using a complex baseband fading/array response simulator. In terms of parameter estimation accuracy, the processor is found to produce virtually the same results as a conventional software engine using floating-point operations.

In recent years, the study of the security of Elliptic Curve Cryptosystems (ECCs) have been received much attention. The MOV algorithm, which reduces the elliptic curve discrete log problem (ECDLP) to the discrete log problem in finite fields with the Weil pairing, is a representative attack on ECCs. Recently Kanayama et al. observed a realization of the MOV algorithm for non-supersingular elliptic curves under the weakest condition. Shikata et al. independently considered a realization of the MOV algorithm for non-supersingular elliptic curves and proposed a generalization of the MOV algorithm. This short note explicitly shows that, under a usual cryptographical condition, we can apply the MOV algorithm to non-supersingular elliptic curves by using the multiplication by constant maps as in the case of supersingular. Namely, it is explicitly showed that we don't need such a generalization in order to realize the MOV algorithm for non-supersingular elliptic curves under a usual cryptographical condition.

This paper addresses the problem of detecting digital line components in a given binary image consisting of n black dots arranged over N N integer grids. The most popular method in computer vision for this purpose is the one called Hough Transform which transforms each black point to a sinusoidal curve to detect digital line components by voting on the dual plane. We start with a definition of a line component to be detected and present several different algorithms based on the definition. The one extreme is the conventional algorithm based on voting on the subdivided dual plane while the other is the one based on topological walk on an arrangement of sinusoidal curves defined by the Hough transform. Some intermediate algorithm based on half-planar range counting is also presented. Finally, we discuss how to incorporate several practical conditions associated with minimum density and restricted maximality.