Distributed algorithms that entail successive rounds of message exchange are called decentralized consensus protocols. Several consensus protocols use a finite projective plane as a communication structure and require 4nn messages in two rounds, where n is the number of nodes. This paper presents an efficient communication structure that uses a finite projective plane with a duality of indices. The communication structure requires 2nn messages in two rounds, and can therefore halve the number of messages. It is shown that a finite projective plane with a duality can be constructed from a difference set, and that the presented communication structure has two kinds of symmetry.
This paper discusses a common channel signaling system in which multiple micro-switching systems can converse as though configured like a conventional centralized switching system. A micro-switching system is a switching system whose main functions are integrated on a chip, like a microprocessor. Progress in MOS technology will soon make micro-switching systems possible, and their small scale and economy will allow subscriber switching systems to be distributed closer to subscribers. This will allow shorter subscriber loops, so subscriber networks will be able to reuse existing metallic lines as H1 (1.544/2.048Mb/s)-class subscriber loops. Economical micro-switching systems and reuse of existing network resources will contribute to the establishment H0 (384kb/s)-ISDN, so that every subscriber will be able to enjoy multimedia communications through HO-calls as simply as using present telephones. Four alternative signaling network architectures are examined, classified by arrangement of their signaling transfer junctions and signaling links, and a new signaling system featuring cell-based transfer functions is proposed. This is suitable for a distributed micro-switching-system network in order to minimize the figures of merit, which collectively estimate network cost and signaling delay.
Yuzo OHTA Lei GONG Hiromasa HANEDA
Data of system parameters of real systems have some uncertainty and they should be given by sets (or intervals) rather than fixed values. To analyze and design systems contaning such uncertain parameters, it is required to represent and treat uncertainty in data of parameters, and to compute value sets of characteristic polynomials and transfer functions. Interval arithmetic is one of the most powerful tools to perform such subjects. In this paper, Polygon Interval Arithmetic (PIA) on the set of polygons in the complex plane is considered, and the data structure and algorithms to execute PIA efficiently is proposed. Moreover, practical examples are shown to demonstrate how PIA is useful to compute the evaluation of value sets.
Mitsuyoshi SUZUKI Hideichi SASAOKA
This paper studies the effect of frequency re-using patterns on the channel capacity in the forward link of orthogonal code division multiple access (CDMA) cellular systems. The received carrier-to-interference ratio (CIR) determined by computer simulation shows that re-using the same frequency channel on every third sector (3-sector layout) provides superior channel capacity than does every-sector re-use (1-sector layout).
A new design methodology is proposed and analyzed for the design of ternary logic systems. In the new ternary logic systems, no conversions among radices are required and only the two-state ternary literals associated with the ternary signals are transmitted in the whole system. With the new design methodology, the ternary systems can be realized by the dynamic CMOS logic circuits which are simple and fully compatible with those of the conventional binary logic circuits in process, power supply, and logic levels. A new dynamic differential logic called the CMOS Redundant Differential Logic (CRDL) is also developed to increase the logic flexibility and the circuit performance. Using the new design methodology and the CRDL circuits, the multiplier with redundant binary addition tree is designed in both non-pipelined and pipelined systems. The experimental chip has been fabricated and measured, which successfully verifies the correctness of the logic functions and the speed performance of the designed circuits.
A design of an Ada IPC (Inter-Program Communication) interface is proposed, through which a designer of distributed systems can (a) specify arbitrary data types needed for inter-program communication and (b) use parallel programming features to build highly parallel systems; a test simulator was built for execution of the IPC interface and a multi-window system was realized as an application of the interface on the simulator; the interface was found to be useful, making description of inter-program communication simpler and easier.
Takashi YAHAGI Md.Kamrul HASAN
In many applications involving the processing of noisy signals, it is desired to know the noise variance. This paper proposes a new method for estimating the noise variance from the signals of autoregressive (AR) and autoregressive moving-average (ARMA) systems corrupted by additive white noise. The method proposed here uses the low-order Yule-Walker (LOYW) equations and the lattice filter (LF) algorithm for the estimation of noise variance from the noisy output measurements of AR and ARMA systems, respectively. Two techniques are proposed here: iterative technique and recursive one. The accuracy of the methods depends on SNR levels, more specifically on the inherent accuracy of the Yule-Walker and lattice filter methods for signal plus noise system. The estimated noise variance is used for the blind indentification of AR and ARMA systems. Finally, to demonstrate the effectiveness of the method proposed here many numerical results are presented.
Miki HASEYAMA Nobuo NAGAI Hideo KITAJIMA
In this paper, the relationship between the recursive least square (RLS) method with a U-D decomposition algorithm and ARMA lattice filter realization algorithm is presented. Both the RLS method and the lattice filter realization algorithm are used for the same applications, such as model identification, etc., therefore, it is expected that the lattice filter algorithm is in some ways related to the RLS. Though some of the proposed lattice filter algorithms have been derived by the RLS method, they do not express the relationship between RLS snd ARMA lattice filter realization algorithm. In order to describe the relation clearly, a new structure of ARMA lattice filter is proposed. Further, based on the relationship, a method of model identification with frequency weighting (MIFW), which is different from a previous method, is derived. The new MIFW method modifies the lattice parameters which are acquired without a frequency weighting and obtain the parameters of an ARMA model, which is identified with frequency weighting. The proposed MIFW method has the following restrictions: (1) The used frequency weighting is FIR filter with a low order. (2) By using the parameters of the ARMA lattice filter with ARMA (N,M) order and the frequency weighting with L order, the new ARMA parameter with the frequency weignting is with ARMA(N-L,M-L) order. By using the proposed MIFW method, the ARMA parameters estimated with the frequency weighting can be obtained without starting the computation again.
Hiroyasu ISHIKAWA Hideo KOBAYASHI
The performance of selection diversity combined with decision feedback equalizer for reception of TDMA carriers is investigated in this paper. The second generation digital land mobile communication systems standardized in the U.S., Japan, and Europe employ TDMA carriers at transmission bit rates up to several hundreds kbit/s. In order to provide higher quality of mobile communications services to the user with employing TDMA carriers, the systems would require both diversity and equalization techniques to combat attenuation of received signal power level due to Rayleigh fading and intersymbol interference resulting from time-variant multipath fading, respectively. This paper proposes a novel integration method of selection diversity and decision feedback equalization techniques which provides the better bit error rate performance than that for the conventional selection diversity method with decision feedback equalizer. The feature of proposed method is that selection diversity and decision feedback equalization techniques are integrated so as to interwork each other. We call the proposed method by the Decision Feedback Diversity with Decision Feedback Equalizer. The detailed algorithm of the proposed method is first presented, and then the system parameters for the method are evaluated based on the computer simulation results. Finally the computer simulation results for the performance of the proposed method are presented and compared to those for the conventional Selection Diversity with Decision Feedback Equalizer and the conventional Dual Diversity Combining and Equalization method under the typical mobile radio environments, in order to demonstrate the validity of the proposed method.
Naohisa OTSUKA Hiroshi INABA Kazuo TORAICHI
It is an important problem whether or not we can reject the disturbances from distributed parameter circuit. In order to analyze this problem structurally, it is necessary to investigate the basic equation of distributed parameter circuit in the framework of state space. Since the basic equation has two parameters for time and space, the state value belongs to an infinite-dimensional space. In this paper, the disturbance-rejection problems with incomplete state feedback and/or incomplete state feedback and feedforward for infinite-dimensional systems are studied in the framework of geometric approach. And under certain assumptions, necessary and/or sufficient conditions for these problems to be solvable are proved.
Kiyohito TOKUDA Shinichi SATO Yuichi SHIRAKI Atsushi FUKASAWA
This paper describes the performance analysis of a distributed antenna system which includes space and path diversity with radio channel estimation. This system is used for CDMA personal communication systems. In this paper, the performance of a diversity system is analyzed precisely considering multipath and inter-antenna interference. In a diversity system, the adaptive RAKE receiver which estimates the characteristics of a radio channel adaptively has been used for diversity combining. In the adaptive RAKE, the time-variant characteristic has been approximated by a time function. In this paper, the estimation performance of the adaptive RAKE is analyzed in cases of time functions of 0-th, first and second degrees. The performances are evaluated and compared with the differential RAKE. The adaptive RAKE is found to improve the signal quality of more than 2dB in comparison with the differential RAKE. It is also found that the optimum parameter design can be achieved flexibly for radio channel estimation by using higher degree time functions.
We develop a convergence theory of the simple genetic algorithm (SGA) for two-bit problems (Type I TBP and Type II TBP). SGA consists of two operations, reproduction and crossover. These are imitations of selection and recombination in biological systems. TBP is the simplest optimization problem that is devised with an intention to deceive SGA into deviating from the maximum point. It has been believed that, empirically, SGA can deviate from the maximum point for Type II while it always converges to the maximum point for Type I. Our convergence theory is a first mathematical achievement to ensure that the belief is true. Specifically, we demonstrate the following. (a) SGA always converges to the maximum point for Type I, starting from any initial point. (b) SGA converges either to the maximum or second maximum point for Type II, depending upon its initial points. Regarding Type II, we furthermore elucidate a typical sufficient initial condition under which SGA converges either to the maximum or second maximum point. Consequently, our convergence theory establishes a solid foundation for more general GA convergence theory that is in its initial stage of research. Moreover, it can bring powerful analytical techniques back to the research of original biological systems.
Jun'ichi HORI Yoshiaki SAITOH Tohru KIRYU
When measuring the ejection fraction for the evaluation of the ventricular pumping function by means of the thermodilution technique, the slow response a conventional thermistor has caused it to be considered unsuitable, and fast thermistors have been proposed as an alternative. However, in this paper we propose improving the time-domain response of a conventional thermistor using a signal processing technique composed of a series of first-order high-pass filters which is known as the natural observation system. We considered the rise time of the thermistor in response to a step temperature change to effect correction for the measurement of the ejection fraction. The coefficients of the natural observation system were calculated by minimizing the square error between the step-response signal of the thermistor and the band-limited reference signal. In an experiment using a model ventricle, the thermodilution curve obtained from a conventional thermistor was improved using the proposed technique, thus enabling successful measurement of the ejection fraction of the ventricles.
This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.
This paper proposes using an adaptive array in a base station for signal reception and transmission in order to increase the spectral efficiency without decreasing the cell radius. The adaptive array controls the directivity pattern of the base station to reduce co-channel interference during reception; the same array pattern is applied during transmission to prevent unnecessary illumination. Computer simulation results show that the cluster size can be reduced to one with time division duplexing (TDD), indicating that we can reuse the same frequency group at all cells. Thus, the improvement in spectral efficiency is as much as 16 fold that of an omni-antenna. Moreover, load sharing, which is expected to improve the channel utilization for unbalanced load situations, is available by cell overlapping. Frequency division duplexing (FDD) requires a weight adjust function to be applied for transmission since the difference in frequency between signal reception and transmission causes null positioning error. However, simple LMS-adjusting can provide a cluster size of one as well as cell overlapping when the frequency deference is 5%.
Tomokazu MUGURUMA Eiichi TANAKA Sumio MASUDA
Many metrics between trees have been proposed. However, there is no research on a graph metric that can be applied to molecular graphs. And most of the reports on tree metrics have dealt with rooted and ordered trees. As the first step defining a graph metric for molecular graphs, this paper proposes a tree metric between unrooted and unordered trees. This metric is based on a mapping between trees that determines a transformation from one tree to another. The metric is the minimum weight among the weights of all possible transformations. The characteristics of the mapping are investigated. A top-down computing method is proposed using the characteristics of the mapping. The time and space complexities are OT(N 2aN 2b(N 3aN 3b)) and Os(N 2aN 2b), respectively, where Na and Nb are the numbers of vertices of the two trees. If the degrees of all vertices of the trees are bounded by a constant, the time complexity of the method is O (N 3aN 3b). The computing time to obtain the distance between a pair of molecular graphs using a computer (SUN SparcStation ELC) is 0.51 seconds on average for all the pairs of 111 molecular graphs that have 12.0 atoms on average. This methic can be applied to the clustering of molecular graphs.
We propose a large capacity broadband packet switch architecture using multiple optical star couplers and tunable devices whose tuning range is restricted. The proposed switch has the conventional three-stage switch structure. With the use of the generalized knockout principle and tunable lasers arranged in an appropriate manner, the switch becomes an output queueing system that yields the best possible delay/throughput performance. This switch requires minimal hardware at the cost of the increased number of wavelengths.
A novel pulse neural network model for sound localization has been proposed. Our model is based on the physiological auditory nervous system. Human beings can perceive the sound direction using inter-aural time difference (ILD) and inter-aural level difference (ILD) of two sounds. The model extracts these features using only pulse train information. The model is divided roughly into three sections: preprocessing for input signals; transforming continuous signals to pulse trains; and extracting features. The last section consists of two parts: ITD extractor and ILD extractor. Both extractors are implemented using a pulse neuron model. They have the same network structure, differing only in terms of parameters and arrangements of the pulse neuron model. The pulse neuron model receives pulse trains and outputs a pulse train. Because the pulses have only simple informations, their data structures are very simple and clear. Thus, a strict design is not required for the implementation of the model. These advantages are profitable for realizing this model by hardware. A computer simulation has demonstrated that time and level differences between two signals have been successfully extracted by the model.
Recent developments and case studies regarding VLSI device chip failure analysis are reviewed. The key failure analysis techniques reviewed include EMMS (emission microscopy), OBIC (optical beam induced current), LCM (liquid crystal method), EBP (electron beam probing), and FIB (focused ion beam method). Further, future possibilities in failure analysis, and some promising new tools are introduced.
In this paper, we show that the neural network can approximate the chaotic behavior in nonlinear dynamical system by experimental study. Chaotic neural activities have been reported in many respects including neural network field. On the contrary, can the neural network learn the chaotic behavior? There have been explored the neural network architecture for predicting successive elements of a sequence. Also there have been several studies related to learning algorithms for general recurrent neural networks. But they often require complicated procedure in time calculation. We use simple standard backpropagation for a kind of simple recurrent neural network. Two types of chaotic system, differential equation and difference equation, are examined to compare characteristics. In the experiments, Lorenz equation is used as an example of differential equation. One-dimensional logistic equation and Henon equation are used as examples of difference equation. As a result, we show the approximation ability of chaotic dynamics in difference equation, which is logistic equation and Henon equation, by neural network. To indicate the chaotic state, we use Lyapunov exponent which represents chaotic activity.