We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions A and B (denoted by A B) as the relation that some distributed algorithm can compute B on any network satisfying A. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions k-LEADER and k-COLOR. k-LEADER denotes the initial condition that gives special condition only to k vertices. k-COLOR denotes the initial condition that divides the vertices into k groups. Then we investigate the property of the relation among these initial conditions.
Numerous scientific and engineering fields extensively utilize optimization techniques for finding appropriate parameter values of models. Various optimization methods are available for practical use. The optimization algorithms are classified primarily due to the rates of convergence. Unfortunately, it is often the case in practice that the particular optimization method with specified convergence rates performs substantially differently on diverse optimization tasks. Theoretical classification of convergence rates then lacks its relevance in the context of the practical optimization. It is therefore desirable to formulate a novel classification framework relevant to the theoretical concept of convergence rates as well as to the practical optimization. This article introduces such classification framework. The proposed classification framework enables specification of optimization techniques and optimization tasks. It also underlies its inherent relationship to the convergence rates. Novel classification framework is applied to categorizing the tasks of optimizing polynomials and the problem of training multilayer perceptron neural networks.
Naotake KAMIURA Teijiro ISOKAWA Yutaka HATA Nobuyuki MATSUI Kazuharu YAMATO
To enhance fault tolerance ability of the feedforward neural networks (NNs for short) implemented in hardware, we discuss the learning algorithm that converges without adding extra neurons and a large amount of extra learning time and cycles. Our algorithm modified from the standard backpropagation algorithm (SBPA for short) limits synaptic weights of neurons in range during learning phase. The upper and lower bounds of the weights are calculated according to the average and standard deviation of them. Then our algorithm reupdates any weight beyond the calculated range to the upper or lower bound. Since the above enables us to decrease the standard deviation of the weights, it is useful in enhancing fault tolerance. We apply NNs trained with other algorithms and our one to a character recognition problem. It is shown that our one is superior to other ones in reliability, extra learning time and/or extra learning cycles. Besides we clarify that our algorithm never degrades the generalization ability of NNs although it coerces the weights within the calculated range.
Yuansheng TANG Toru FUJIWARA Tadao KASAMI
An algorithm for finding the optimal sectionalization for sectionalized trellises with respect to distinct optimality criterions was presented by Lafourcade and Vardy. In this paper, for linear block codes, we give a direct method for finding the optimal sectionalization when the optimality criterion is chosen as the total number |E| of the edges, the expansion index |E|-|V|+1, or the quantity 2|E|-|V|+1, only using the dimensions of the past and future sub-codes. A more concrete method for determining the optimal sectionalization is given for the Reed-Muller codes with the natural lexicographic coordinate ordering.
This article addresses two issues. Firstly, the convergence property of conjugate gradient (CG) algorithm is investigated by a Chebyshev polynomial approximation. The analysis result shows that its convergence behaviour is affected by an acceleration term over the steepest descent (SD) algorithm. Secondly, a new CG algorithm is proposed in order to boost the tracking capability for time-varying parameters. The proposed algorithm based on re-initialising forgetting factor shows a fast tracking ability and a noise-immunity property when it encounters an unexpected parameter change. A fast tracking capability is verified through a computer simulation in a system identification problem.
Tatsuhiro TSUCHIYA Yusuke TOKUDA Tohru KIKUNO
A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.
Yuichi KAJI Ryujiro SHIBUYA Toru FUJIWARA Tadao KASAMI Shu LIN
New algorithms for the MAP (also known as the APP) decoding and the MAX-LogMAP decoding of linear block codes are presented. The algorithms are devised based on the structural properties of linear block codes, and succeeds in reducing the decoding complexity without degrading the error performance. The proposed algorithms are suitable for the parallel and pipeline processing which improves the throughput of the decoder. To evaluate the decoding complexity of the proposed algorithms, simulation results for some well-known codes are presented. The results show that the algorithms are especially efficient than the conventional BCJR-based algorithms for codes whose rate are relatively low.
A new method is introduced for sequential estimation of TDOA (time delay of arrival) and FDOA (frequency delay of arrival) in a two sensor array. The proposed scheme is basically a two step algorithm utilizing 1-dimensional slice functions of the third order cumulants between two signal measurements, and is capable of suppressing the effect of correlated Gaussian measurement noises. It is demonstrated that the proposed algorithm outperforms existing TDOA/FDOA estimation algorithms from the viewpoint of computational burden and in the sense of mean squared error as well.
Hiroyoshi MATSUI Michiko INOUE Toshimitsu MASUZAWA Hideo FUJIWARA
We investigate possibility of fault-tolerant and self-stabilizing protocols (ftss protocols) using an unreliable failure detector. Our main contribution is (1) to newly introduce k-accuracy of an unreliable failure detector, (2) to show that k-accuracy of a failure detector is necessary for any ftss k-group consensus protocol, and (3) to present three ftss k-group consensus protocols using a k-accurate and weakly complete failure detector under the read/write daemon on complete networks and on (n-k+1)-connected networks, and under the central daemon on complete networks.
Atsuo OZAKI Masakazu FURUICHI Nobuo NISHI Etsuji KURODA
Although a number of car-traffic simulators have been developed for various purposes, none of the existing simulators enhance the simulation accuracy using sensor data or allow the system structure to re-configure the system structure depending on the application. Our goal was to develop a highly accurate, highly modular, flexible, and scalable micro-model car-traffic simulation system. The HLA (High Level Architecture) was applied to every system module as a standard interface between each module. This allows an efficient means for evaluating and validating a variety of micro-model simulation schemes. Our ongoing projects consist of running several identical simulations concurrently, with different parameter sets. By sending the results of these simulations to a manager module, which analyzes both the parameter sets and the simulated results, the manager module can evaluate the best-simulated results and determine the next action by comparing these results with the sensor data. In this system, the sensor data or the statistical data on the flow of traffic, obtained by monitoring real roads, is used to improve the simulation accuracy. Future systems are being planned to employ real time sensor data, where the input of the data occurs at almost real time speed. In this paper, we discuss the design of a HLA-based car-traffic simulation system and the construction of a sensor-data fusion algorithm. We also discuss our preliminary evaluation of the results obtained with this system. The results show that the proposed fusion algorithm can adjust the simulation accuracy to the logged sensor data within a difference of 5% (minimum 1.5%) in a specific time period. We also found that simulations with 500 different parameter sets can be executed within 5 minutes using 8 simulator modules.
Tetsuya SHIMAMURA Tomoyuki TAKADA Jouji SUZUKI
In this paper, we propose an adaptive IIR equalizer based on prefiltering techniques. The proposed equalizer has a cascade structure of an ARMA prefilter and an adaptive FIR equalizer. The ARMA prefilter is designed based on the transfer function estimated by the gradient-type instrumental variable algorithm. Simulation results are shown to confirm the performance of the proposed adaptive IIR equalizer.
Ahmad CHELDAVI Gholamali REZAI-RAD
Based on genetic algorithm (GA) in this paper we present a simple method to extract distributed circuit parameters of a multiple coupled nonuniform microstrip transmission lines from it's measured or computed S-parameters. The lines may be lossless or lossy, with frequency dependent parameters. First a sufficient amount of information about the system is measured or computed over an specified frequency range. Then this information is used as an input for a GA to determine the inductance and capacitance matrices of the system. The theory used for fitness evaluation is based on the steplines approximation of the nonuniform transmission lines and quasi-TEM assumptions. Using steplines approximation the system of coupled nonuniform transmission lines is subdivided into arbitrary large number of coupled uniform lines (steplines) with different characteristics. Then using modal decomposition method the system of coupled partial differential equations for each step is decomposed to a number of uncoupled ordinary wave equations which are then solved in frequency-domain.
Kwame Osei BOATENG Hiroshi TAKAHASHI Yuzo TAKAMATSU
In this paper, we consider the design for testability of a multiplier based on the modified Booth Algorithm. First, we present a basic array implementation of the multiplier. Next, we introduce testability considerations to derive two C-testable designs. The first of the designs is C-testable under the single stuck-at fault model (SAF) with 10 test patterns. And, the second is C-testable under the cell fault model (CFM) with 33 test patterns.
Masato TAJIMA Keiji TAKIDA Zenshiro KAWASAKI
Both Viterbi decoding with labels (i.e., the Yamamoto-Itoh scheme) and the soft-output Viterbi algorithm (SOVA) evaluate the metric difference between the maximum-likelihood (ML) path and the discarded path at each level in the trellis. Noting this fact, we show that the former scheme also provides information about the reliability values for decoded information bits.
Kei SAKAGUCHI Jun-ichi TAKADA Kiyomichi ARAKI
An optimization of the smoothing preprocessing for the correlated signal parameter estimation was considered. Although the smoothing factor (the number of subarrays) is a free parameter in the smoothing preprocessing, a useful strategy to determine it has not yet been established. In this paper, we investigated thoroughly about the smoothing factor and also proposed a new scheme to optimize it. The proposed method, using the smoothed equivalent diversity profile (SED profile), is able to evaluate the effect of smoothing preprocessing without any a priori information. Therefore, this method is applicable in the real multipath parameter estimation.
Jacir L. BORDIM JiangTao CUI Tatsuya HAYASHI Koji NAKANO Stephan OLARIU
The main contribution of this work is to propose energy-efficient randomized initialization protocols for ad-hoc radio networks (ARN, for short). First, we show that if the number n of stations is known beforehand, the single-channel ARN can be initialized by a protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. We then go on to address the case where the number n of stations in the ARN is not known beforehand. We begin by discussing, an elegant protocol that provides a tight approximation of n. Interestingly, this protocol terminates, with high probability, in O((log n)2) time slots and no station has to be awake for more than O(log n) time slots. We use this protocol to design an energy-efficient initialization protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. Finally, we design an energy-efficient initialization protocol for the k-channel ARN that terminates, with high probability, in O(n/k+log n) time slots, with no station being awake for more than O(log n) time slots.
Hai LIN Mohammad Reza ASHARIF Katsumi YAMASHITA
The purpose of this letter is to modify the correlation least mean squares algorithm using a sum of the lagged squared errors as the cost function and extend the modified CLMS algorithm to two-dimensional domain. The effectiveness of the proposed algorithm is shown by the computer simulation.
Hee-Bong PARK Seung-Hoon HWANG Keum-Chan WHANG
In this letter, a new rapid converging method based on orthogonalization is proposed. Our approach is to find the near-optimum coefficient values during training period, and then use them as the initial values of the LMS algorithm. The numerical results show that the rapid convergence speed of the proposed scheme does not depend on the eigenvalue spread.
Wonsik LEE Sunghan LEE Beomhee LEE Youngdae LEE
In this paper, as a practical application, we focus on the genetic algorithm (GA) for multi-head surface mounting machines which are used to populate printed circuit boards (PCBs). Although there have been numerous studies on the surface mounting machine, studies on the multi-head case are rare because of its complexity. The multi-head surface mounting machine can pick multiple components simultaneously in one pickup operation and this operation can reduce much portion of the assembly time. Hence we try to minimize the assembly time by maximizing the number of simultaneous pickups, resulting in reduction of PCB production cost. This research introduces a partial-link GA method for the single-head case. Then, we apply this method to the multi-head case by regarding a reel-group as one reel and a component-cluster as one component. The results of computer simulation show that our genetic algorithm is greatly superior to the heuristic algorithm that is currently used in industry.
In this paper, a new set of difference equations is derived for transient analysis of the convergence of adaptive FIR filters using the Sign-Sign Algorithm with Gaussian reference input and additive Gaussian noise. The analysis is based on the assumption that the tap weights are jointly Gaussian distributed. Residual mean squared error after convergence and simpler approximate difference equations are further developed. Results of experiment exhibit good agreement between theoretically calculated convergence and that of simulation for a wide range of parameter values of adaptive filters.