In this paper, we present a new state space-based approach for the two-dimensional (2-D) frequency estimation problem which occurs in various areas of signal processing and communication problems. The proposed method begins with the construction of a state space model associated with the noiseless data which contains a summation of 2-D harmonics. Two auxiliary Hankel-block-Hankel-like matrices are then introduced and from which the two frequency components can be derived via matrix factorizations along with frequency shifting properties. Although the algorithm can render high resolution frequency estimates, it also calls for lots of computations. To alleviate the high computational overhead required, a highly parallelizable implementation of it via the principle subband component (PSC) of some appropriately chosen transforms have been addressed as well. Such a PSC-based transform domain implementation not only reduces the size of data needed to be processed, but it also suppresses the contaminated noise outside the subband of interest. To reduce the computational complexity induced in the transformation process, we also suggest that either the transform of the discrete Fourier transform (DFT) or the Haar wavelet transform (HWT) be employed. As a consequence, such an approach of implementation can achieve substantial computational savings; meanwhile, as demonstrated by the provided simulation results, it still retains roughly the same performance as that of the original algorithm.

The stable marriage problem is one of the basic problems proposed in 1962. In this paper, we consider a distributed stable marriage problem. This problem is applicable to cooperative works of autonomous robots in distributed environments. We show a Gale-Shapley based protocol to obtain stable matching and introduce autonomous mechanism for exchanging partners, called divorce process, in distributed environments. We report some interesting results of matching games by computer simulation.

A noble blind equalization algorithm (BEA) using a single/multilevel modulus is proposed. According to the residual intersymbol interference (ISI) level of the equalizer output, the new algorithm adopts relevantly a single modulus or a multilevel modulus to form its cost function. Moreover, since the proposed approach separates complex two-dimensional signal into in-phase and quadrature components, and forms the error signals for each component, it has inherently the capability of phase recovery. Hence, it improves the performances of steady-state and recovers the phase rotation without any degradation of transient property. Simulation results confirm the effectiveness of the new approach.

The technique of common-multiplicand multiplication, CMM, is modified and the similar approach is utilized to enhance the performance of a recently proposed fast exponentiation algorithm by exponent decomposition. On average, the improved exponentiation, its original version, and the traditional right to left binary exponentiation algorithm take 1.292m+11,1.375m+3, and 1.5m multiplications, respectively where m is the bit length of the exponent. Finally, it is shown how to improve the overall performance of an exponentiation by employing the improved exponentiation algorithm, the improved CMM algorithm , and any general purpose fast multiplication algorithm.

An optical array imaging system has been presented in previous articles. In this system, first, the object is illuminated with laser light sequentially from each of the array elements and the reflected field is detected as interferogram. The interferograms obtained are then spatially heterodyne-detected on a computer to extract the signal components, that is, array data. Then, the eigenvector of the largest eigenvalue is derived by applying the power method to the array data and it is beam-steered to get images of the object. The algorithm gives good images for most objects, but it fails to work for some objects. It was shown that using a subset of the array data may solve the problem, but that finding the corresponding optimum subaperture is quite time-consuming. In this paper, first, the integral equation describing the system is solved for a general class of object, to make clear the conditions for the eigenvector to form a sharp beam. Second, the imaging algorithm is sped up to a great degree by optimizing only the illuminating aperture in a coarse fashion. Third, the rate of convergence of the power method is adaptively estimated in the algorithm to make the eigenvector derivation reliable. Finally the improved algorithm is investigated using both computer-generated and experimentally obtained array data.

A pipelined adaptive digital filter (ADF) architecture based on a two-dimensional least mean square algorithm is proposed. This architecture enables the ADF to be operated at a high clock rate and reduction of the required amount of hardware. To achieve this reduction we introduce a new building unit, called a block, and propose implementing the pipelined ADF using the block, Since the number of blocks in a cell is adjustable, we derive a condition for satisfying given specifications. We show the smallest number of blocks and the corresponding delay can be determined by using the proposed method.

In OSI management, we utilize a scope parameter in Common Management Information Service (CMIS) that enables us to operate multiple Managed Objects (MOs) at one CMIS operation, so that we may reduce the number of communications between a manager and an agent. The more the number of MOs increases, the harder it is to find optimal combinations of scopes. In an existing approximation algorithm for finding optimal combinations of scopes, there are restrictions on the structure of a naming tree for the algorithm to work efficiently and the lower bound of its approximation ratio, n/4, grows in proportion to the number of MOs, n. This paper proposes a new approximation algorithm that removes the restriction on the structure of a naming tree and significantly improves the approximation ratio to (1 + ln n) in the upper bound, by keeping the same time complexity as the existing algorithm.

In this paper, we give a new lower bound for the dimension of subfield subcodes. This bound improves the lower bound given by Stichtenoth. A BCH code and a subfield subcode of algebraic geometric code on a hyper elliptic curve are discussed as special cases.

Approximate maximum likelihood (ML) detection implemented by a reduced state Viterbi algorithm (VA), called the reduced state Viterbi coherent detection (RSVCD) algorithm in this paper, is described for the reception of uncoded M-ary PSK (MPSK) signals transmitted over additive white Gaussian noise (AWGN) channels. An M-state trellis, each state representing one of M signal constellation points, is used. The RSVCD algorithm performs parallel channel estimation based on the per-survivor processing principle (PSPP). Simple decision feedback CD (DFCD) is deduced as a special case of RSVCD. Unified BER expressions are derived for RSVCD, DFCD, and approximate ML detection implemented as an ML-state Viterbi algorithm (referred to as VACD) [6] as well as ideal CD and differential detection (DD). Computer simulation results are also presented and compared with theoretical results.

It is usual to set single-point noise controller at each point in order to cancel noises at multiple cancelling points. How should we adapt controllers in such a case? The easiest way is to let them work individually, though it is possible to use all the error signals for one controller. In this case, there is a promblem that the controllers do not necessarily converge. In this paper, we consider the conditions of the paths under which the controllers converge when they work individually.

The filtered-x algorithm, which is widely applied to active noise control system, requires setting a small step gain. Such a small step gain reduces the noise reduction effect when the alogrithm is implemented by fixed point processing. This paper presents an experimental result that the 'polarized-g' individually normalized least mean square (INLMS) algorithm can provide almost the same noise reduction effect even in the fixed point processing of 16 bits as that in floating point processing.

The numerical properties of the recursive least squares (RLS) algorithm and its fast versions have been extensively studied. However, very few investigations are reported concerning the numerical behavior of the predictor based least squares (PLS) algorithms that provide the same least squares solutions as the RLS algorithm. This paper presents a comparative study on the numerical performances of the RLS and the backward PLS (BPLS) algorithms. Theoretical analysis of three main instability sources reported in the literature, including the overrange of the conversion factor, the loss of symmetry and the loss of positive definiteness of the inverse correlation matrix, has been done under a finite-precision arithmetic. Simulation results have confirmed the validity of our analysis. The results show that three main instability sources encountered in the RLS algorithm do not exist in the BPLS algorithm. Consequently, the BPLS algorithm provides a much more stable and robust numerical performance compared with the RLS algorithm.

In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t1,...,tk} of k nodes in a k-connected graph G, find k node-disjoint paths s ti, 1 i k. We give an O(n2) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs Gn which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(Gn) + 1 for n 4,6 and at most d(Gn) + 2 for n = 4,6, where d(Gn) = 3(n-1)/2 is the diameter of Gn. d(Gn) + 1 and d(Gn) + 2 are also the lower bounds on the length of the paths for the above problem in Gn for n 4,6 and n = 4,6, respectively.

We describe our implementation of the Hypercube variation of the Multiple Polynomial Quadratic Sieve (HMPQS) integer factorization algorithm on a Parsytec GC computer with 128 processors. HMPQS is a variation on the Quadratic Sieve (QS) algorithm which inspects many quadratic polynomials looking for quadratic residues with small prime factors. The polynomials are organized as the nodes of an n-dimensional cube. We report on the performance of our implementations on factoring several large numbers for the Cunningham Project.

In the adaptive lattice estimation process, it is well known that the convergence speed of the successive stage is affected by the estimation errors of reflection coefficients in its preceding stages. In this paper, we propose block estimation methods of two-dimensional (2-D) adaptive lattice filter. The convergence speed of the proposed algorithm is significantly enhanced by improving the adaptive performance of preceding stages. Furthermore, this process can be simply realized. The modeling of 2-D AR field and texture image are demonstrated through computer simulations.

In this paper the design of systolic array processors for computing 2-dimensional Discrete Fourier Transform (2-D DFT) is considered. We investigated three different computational schemes for designing systolic array processors using systematic approach. The systematic approach guarantees to find optimal systolic array processors from a large solution space in terms of the number of processing elements and I/O channels, the processing time, topology, pipeline period, etc. The optimal systolic array processors are scalable, modular and suitable for VLSI implementation. An application of the designed systolic array processors to the prime-factor DFT is also presented.

In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions ui(I) on I, and define an optimization problem of finding the interval I maximizing f(I) subject to ui(I) > Ki for given real numbers Ki (i = 1, 2, , h). We propose efficient alogorithms to solve the above optimization problem if the objective function is either additive or quotient, and the conditional functions are additive, where a function f is additive if f(I) = ΣiIf^(i) extending a function f^ on U, and quotient if it is represented as a quotient of two additive functions. We use computational-geometric methods such as convex hull, range searching, and multidimensional divide-and-conquer.

The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.

A modified error correction/detection scheme based on the scheme by Yi and Lee is proposed. Algebraic decoding is used to perform error correction. Error detection is performed by an absolute value test. It is shown that the proposed scheme bridges the performance gap between Yi and Lee's scheme and Forney's optimal scheme.

This paper discusses the largest common similar substructure (in short, LCSS) problem for trees. The problem is, for all pairs of "substructure of A and that of B," to find one of them, denoted by A and B', such that A is most similar to B' and the sum of the number of vertices of A and that of B' is largest. An algorithm for the LCSS problem for unrooted and unordered trees (in short, trees) and that for trees embedded in a plane (in short, Co-trees) are proposed. The time complexity of the algorithm for trees is O (max (ma, mb)2 NaNb) and that for CO-trees is O (mambNaNb), where, ma (mb) and Na (Nb) are the largest degree of a vertex of tree Ta (Tb) and the number of vertices of Ta (Tb), respectively. It is easy to modify the algorithms for enumerating all of the LCSSs for trees and CO-trees. The algorithms can be applied to structure-activity studies in chemistry and various structure comparison problems.