Kazushi IKEDA Youhua WANG Kenji NAKAYAMA
The numerical property of the recursive least squares (RLS) algorithm has been extensively, studied. However, very few investigations are reported concerning the numerical behavior of the predictor-based least squares (PLS) algorithms which provide the same least squares solutions as the RLS algorithm. In Ref. [9], we gave a comparative study on the numerical performances of the RLS and the backward PLS (BPLS) algorithms. It was shown that the numerical property of the BPLS algorithm is much superior to that of the RLS algorithm under a finite-precision arithmetic because several main instability sources encountered in the RLS algorithm do not appear in the BPLS algorithm. This paper theoretically shows the stability of the BPLS algorithm by error propagation analysis. Since the time-variant nature of the BPLS algorithm, we prove the stability of the BPLS algorithm by using the method as shown in Ref. [6]. The expectation of the transition matrix in the BPLS algorithm is analyzed and its eigenvalues are shown to have values within the unit circle. Therefore we can say that the BPLS algorithm is numerically stable.
In this paper a new class of single error-correcting fixed block-length (d, k) codes has been proposed. The correctable error types are peak-shift error, insertion or deletion error, symmetric error, etc. The basic technique to construct codes is a systematic construction algorithm of multilevel sequences with a constant Lee weight (TALG algorithm). The coding rate and efficiency are considerably good, and hence the proposed new codes will be very useful for improving the reliability of high density magnetic recording.
Tadao KASAMI Takuya KOUMOTO Toru FUJIWARA Hiroshi YAMAMOTO Yoshihisa DESAKI Shu LIN
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.
Tsuyoshi KAWAGUCHI Takeharu BABA Ryo-ichi NAGATA
The main defficulty in recognizing 3-D objects from 2-D images is matching 2-D information to the 3-D object representation. The multiple-view approach makes this problem easy to solve by reducing the problem to 2-D to 2-D matching problem. This approach models each 3-D object by a collection of 2-D views from various viewing angles and recognizes an object in the image by finding a 2-D view that has the best match to the image. However, if the size of the model database becomes large, the approach requires long time for the recognition of objects. In this paper we present a 3-D object recognition algorithm based on multiple-view approach. To reduce the recognition time, the proposed algorithm uses the coarse-to-fine process previously proposed by the authors and a genetic algorithm-based search scheme for the selection of a best matched model in the database. And, we could verify from the results of the experiments that the algorithm proposed in this paper is useful to speed up the recognition process in multiple-view based object recognition systems.
Mariko NAKANO-MIYATAKE Hector PEREZ-MEANA
In the last few years analog adaptive filters have been a subject of active research because they have the ability to handle in real time much higher frequencies, with a smaller size and lower power consumption that their digital counterparts. During this time several analog adaptive filter algorithms have been reported in the literature, almost all of them use the continuous time version of the least mean square (LMS) algorithm. However the continuous time LMS algorithm presents the same limitations than its digital counterpart, when operates in noisy environments, although their convergence rate may be faster than the digital versions. This fact suggests the necessity of develop analog versions of recursive least square (RLS) algorithm, which in known to have a very low sensitivity to additive noise. However a direct implementation of the RLS in analog way would require a considerable effort. To overcome this problem, we propose an analog RLS algorithm in which the adaptive filter coefficients vector is estimated by using a fully connected network that resembles a Hopfield network. Theoretical and simulations results are given which show that the proposed and conventional RLS algorithms have quite similar convergence properties when they operate with the same sampling rate and signal-to-noise ratio.
Toshiyuki KOHNOSU Toshihisa NISHIJIMA Shigeichi HIRASAWA
Concatenated codes have many remarkable properties from both the theoretical and practical viewpoints. The minimum distance of a concatenated code is at least the product of the minimum distances of an outer code and an inner code. In this paper, we shall examine some cases that the minimum distance of concatenated codes is beyond the lower bound and get the tighter bound or the true minimum distance of concatenated codes by using the complete weight enumerator of the outer code and the Hamming weight enumerator of the inner code. Furthermore we propose a new decoding method based on Reddy-Robinson algorithm by using the decoding method beyond the BCH bound.
Turbo codes have fascinated many coding researchers because of thier near-Shannon-limit error correction performance. In this paper, we discuss multi-dimensional turbo codes which are parallel concatenation of multiple constituent codes. The average upper bound to bit error probability of multidimensional turbo codes is derived. The bound shows that the interleaver gains of this kind of codes are larger than that of conventional two-dimensional turbo codes. Simplified structures of multi-dimensional turbo encoder and decoder are proposed for easier implementation. Simulation results show that for a given interleaver size, by increasing the dimension, great performance improvement can be obtained.
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.
Yao-Lin JIANG Wai-Shing LUK Omar WING
We present theoretical results on the convergence of iterative methods for the solution of linear differential-algebraic equations arising form circuit simulation. The iterative methods considered include the continuous-time and discretetime waveform relaxation methods and the Krylov subspace methods in function space. The waveform generalized minimal residual method for solving linear differential-algebraic equations in function space is developed, which is one of the waveform Krylov subspace methods. Some new criteria for convergence of these iterative methods are derived. Examples are given to verify the convergence conditions.
To implement the PGPS packet scheduling algorithm in high speed networks is more difficult since it is based on real time simulation of an equivalent fluid-model system leading to a higher implementation time complexity. A modified approach to PGPS is the SCFQ scheme. This scheme is easy to implement, but has an increasing end-to-end delay bound. The VC packet scheduling algorithm provides the same end-to-end delay bound as PGPS does, but has the disadvantage of unfairness. As SCFQ, SFQ is much easier to implement than PGPS and achieves the same fairness, but has a higher end-to-end delay bound than PGPS. We propose a new packet scheduling algorithm, called Minimum Starting-tag Fair Queueing (MSFQ), which assigns the virtual time to be the minimum starting tag over all backlogged connections. MSFQ is much easier to implement than PGPS and provides the same end-to-end delay bound for each connection and fairness as PGPS. In this paper, we will show the end-to-end delay bound and fairness of MSFQ and compare 5 rate-based packet scheduling algorithms including PGPS, VC, SCFQ, SFQ, and MSFQ focusing on end-to-end delay bound, fairness, and implementation time complexity.
Chotipat PORNAVALAI Goutam CHAKRABORTY Norio SHIRATORI
Distributed multimedia applications are often sensitive to the Quality of Service (QoS) provided by the communication network. They usually require guaranteed QoS service, so that real-time communication is possible. However, searching a route with multiple QoS constraints is known to be a NP-complete problem. In this paper, we propose a new simple and efficient distributed QoS routing algorithm, called "DQoSR," for supporting real-time communication in high-speed networks. It searches a route that could guarantee bandwidth, delay, and delay jitter requirements. Routing decision is based only on the modified cost, hop and delay vectors stored in the routing table at each node and its directly connected neighbors. Moreover, DQoSR is proved to construct loop-free routes. Its worst case message complexity is O(|V|2), where |V| is the number of nodes in the network. Thus DQoSR is fast and scales well to large networks. Finally, extensive simulations show that average rate of establishing successful connection of DQoSR is very near to optimum (the difference is less than 0.4%).
KyungHa LEE YongHoon KIM HyungJin CHOI
In this paper, we propose a novel algorithm for all-digital high speed symbol synchronization to be called the MBECM (Modified-Band Edge Component Maximization). The proposed algorithm has a structure based on the spectral line method. It simplifies and modifies the existing BECM algorithm to compensate for the timing offset caused by different phase characteristics of the BPF (band pass filter) at 1/2T and -1/2T. The algorithm is also independent of the carrier recovery and requires only two samples per symbol for its operation. Until now the timing detector's characteristics of the spectral line method including the M-BECM was not analyzed, particularly effect of the timing offset at convergence point. We analyze the timing detector's characteristics of the M-BECM and derive expressions for the timing detector's mean value (often called the S-curve) as a function of the normalized symbol-clock phase, the rolloff parameterand the bandwidth of the BPF. By using these expressions, the PDbias for eliminating the timing offset at an optimal convergence point are calculated. We also analyze and evaluate performance of the proposed algorithm in various ways such as jitter, timing detector output characteristics, etc. and suggest improvements. The proposed M-BECM is compared to the popular Gardner algorithm for high speed modem applications. The proposed algorithm has simpler structure than the Gardner algorithm and simulation results reveal that the proposed algorithm has better overall performance than the Gardner algorithm in narrow band.
Takayuki SAITO Yoshiyasu TAKEFUJI
The graph partitioning problem is a famous combinatorial problem and has many applications including VLSI circuit design, task allocation in distributed computer systems and so on. In this paper, a novel neural network for the m-way graph partitioning problem is proposed where the maximum neuron model is used. The undirected graph with weighted nodes and weighted edges is partitioned into several subsets. The objective of partitioning is to minimize the sum of weights on cut edges with keeping the size of each subset balanced. The proposed algorithm was compared with the genetic algorithm. The experimental result shows that the proposed neural network is better or comparable with the other existing methods for solving the m-way graph partitioning problem in terms of the computation time and the solution quality.
This paper first proposes a new approach to designing high-quality, low-diameter, small mean-internode-distance (MID), k-subcubic-connected cyclic networks. The approach is a modification of the k-cubic-connected cyclic (k-ccc) network in which there are N=k2k-1 instead of N=k2k nodes in the k-ccc network. The special features of this network are: (1) It fills the gap between the number of nodes in k-ccc and (k+1)-ccc networks, but retains a constant number of link (3) per node in the network, (2) it allows higher quality, smaller diameters and mean internode distances hypercube networks with the same numbers of nodes. A second novel approach consists of a k+-sccc network with the same number of nodes as the k-ccc but with smaller diameters and mean internode distances. A generalized k-ccc network formed by nodes N=k2m is introduced for n-cube and k-ccc (modified or normal) networks that allows minimum network quality to be obtained where m may or may not equal to k. A routing algorithm for 4-sccc is also presented.
Andrzej CICHOCKI Shun-ichi AMARI Jianting CAO
In this paper we develop a new family of on-line adaptive learning algorithms for blind separation of time delayed and convolved sources. The algorithms are derived for feedforward and fully connected feedback (recurrent) neural networks on basis of modified natural gradient approach. The proposed algorithms can be considered as generalization and extension of existing algorithms for instantaneous mixture of unknown source signals. Preliminary computer simulations confirm validity and high performance of the proposed algorithms.
This paper introduces a new recursive factorization of the polynomial, 1-zN, over the real numbers when N is an even composite integer. The recursive factorization is applied for efficient computation of the discrete Fourier transform (DFT) and the cyclic convolution of real sequences with highly composite even length.
Hiroki YOSHIMURA Tadaaki SHIMIZU Naoki ISU Kazuhiro SUGATA
A noise reduction filter composed of a sandglass-type neural network (Sandglass-type Neural network Noise Reduction Filter: SNNRF) was proposed in the present paper. Sandglass-type neural network (SNN) has symmetrical layer construction, and consists of the same number of units in input and output layers and less number of units in a hidden layer. It is known that SNN has the property of processing signals which is equivalent to KL expansion after learning. We applied the recursive least square (RLS) method to learning of SNNRF, so that the SNNRF became able to process on-line noise reduction. This paper showed theoretically that SNNRF behaves most optimally when the number of units in the hidden layer is equal to the rank of covariance matrix of signal component included in input signal. Computer experiments confirmed that SNNRF acquired appropriate characteristics for noise reduction from input signals, and remarkably improved the SN ratio of the signals.
Yoshio KARASAWA Takashi SEKIGUCHI Takashi INOUE
Based on a recent remarkable development of digital beamforming (DBF) antenna technologies, we propose a new concept of kaleidoscopic antenna, we call it "software antenna," which is a more general one extending DBF schemes. The software antenna instantly reconfigures itself adapting its software and hardware to changes in the radio-environment. To realize the software antenna, the development of high-speed reconfigurable FPGAs is indispensable. As an intelligent antenna, we believe the software antenna could play a key role in the days of software radio having a function of mobile computing.
Fernando Gil V. RESENDE,Jr Paulo S.R. DINIZ Keiichi TOKUDA Mineo KANEKO Akinori NISHIHARA
A new cost function based on multi-band decomposition of the estimation error and application of a different step-size for each band is used in connection with the least-mean-square criterion to improve the fidelity of estimates as compared to those obtained with conventional least-mean-square adaptive algorithms. The basic new idea is to trade off time and frequency resolutions of the adaptive algorithm along the frequency domain by using different step-sizes in the analysis of distinct frequencies in accordance with the frequency-localized statistical behavior of the imput signal. The mathematical background for a stochatic approach to the multi-band decomposition-based scheme is presented and algorithms with fixed and variable step-sizes are derived. Computer experiments compare the performance of multiband and conventional least-mean-square methods when applied to system identification.
Barry SHACKLEFORD Etsuko OKUSHI Mitsuhiro YASUDA Hisao KOIZUMI Katsuhiko SEO Takashi IWAMOTO
Genetic algorithms were introduced by Holland in 1975 as a method of solving difficult optimization problems by means of simulated evolution. A major drawback of genetic algorithms is their slowness when emulated by software on conventional computers. Described is an adaptation of the original genetic algorithm that is advantageous to hardware implementation along with the architecture of a hardware framework that performs the functions of population storage, selection, crossover, mutation, fitness evaluation, and survival determination. Programming of the framework is illustrated with the set coverage problem that exhibits a 6,000 speed-up over software emulation on a 100 MHz workstation.