The recursive least-squares filter and fixed-point smoother are designed in linear discrete-time systems. The estimators require the information of the system matrix, the observation vector and the variances of the state and white Gaussian observation noise in the signal generating model. By appropriate choices of the observation vector and the state variables, the state-space model corresponding to the ARMA (autoregressive moving average) model of order (n,m) is introduced. Here,some elements of the system matrix consist of the AR parameters. This paper proposes modified iterative technique to the existing one regarding the estimation of the variance of observation noise based on the estimation methods of ARMA parameters in Refs. [2],[3]. As a result, the system matrix, the ARMA parameters and the variances of the state and observation noise are estimated from the observed value and its sampled autocovariance data of finite number. The input noise variance of the ARMA model is estimated by use of the autocovariance data and the estimates of the AR parameters and one MA parameter.
We describe a formal verification algorithm for pipelined processors. This algorithm proves the equivalence between a processor's design and its specifications by using rewriting of recursive functions and a new type of mathematical induction: extended recursive induction. After the user indicates only selectors in the design, this algorithm can automatically prove processors having more than 10(1010) states. The algorithm is manuary applied to benchmark processors with pipelined control, and we discuss how data width, memory size, and the numbers of pipeline stages and instructions influence the computation cost of proving the correctness of the processors. Further, this algorithm can be used to generate a pipeline invariant.
Jianming LU Takashi YAHAGI Jianting CAO
This letter presents new estimation algorithm of ARMAX systems which do not always satisfy the strictly positive real (SPR) condition. We show how estimated parameters can converge to their true values based on the overparameterized system. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.
In this paper we investigate the learnability of relations in Inductive Logic Programming, by using equality theories as background knowledge. We assume that a hypothesis and an observation are respectively a definite program and a set of ground literals. The targets of our learning algorithm are relations. By using equality theories as background knowledge we introduce tree structure into definite programs. The structure enable us to narrow the search space of hypothesis. We give pairs of a hypothesis language and a knowledge language in order to discuss the learnability of relations from the view point of inductive inference and PAC learning.
Although consistent learning is sufficient for PAC-learning, it has not been found what strategy makes learning more efficient, especially on the sample complexity, i.e., the number of examples required. For the first step towards this problem, classes that have consistent learning algorithms with one-sided error are considered. A combinatorial quantity called maximal particle sets is introduced, and an upper bound of the sample complexity of consistent learning with one-sided error is obtained in terms of maximal particle sets. For the class of n-dimensional axis-parallel rectangles, one of those classes that are consistently learnable with one-sided error, the cardinality of the maximal particle set is estimated and O(d/ε1/ε log 1/δ) upper bound of the learning algorithm for the class is obtained. This bound improves the bounds due to Blumer et al. and meets the lower bound within a constant factor.
Masayuki KASHIMA Ryouichi WATANABE Ryouhei KONUMA Hiroshi INOUE Yoshikatsu SHIRAISHI
Various approaches on optical network systems using wavelength-division multiplexing (WDM) technique have been proposed. It is difficult to make a scale of WDM network larger since a number of the optical wavelength which can be used is limited. In order to make easily larger scale of network, multi-hop WDM network have been proposed. We have studied 2-hop network: RookNet which has simple routing algorithm and high network throughput. Nodes in RookNet are divided into row groups and column groups and are placed in a mesh form. Packets are transferred between nodes over 1-hop or 2-hops. The 2-hop transfer means that a source node sends packets to a destination node via a relay node. When 2-hop traffic increases, relay processing time in a relay node is increasing. This is the reason that network throughput becomes low. To solve this problem is very important. In this paper, we show RookNet rearrangement algorithm which replaces location of node within group so as to decrease the 2-hop traffic and to maintain high network throughput. Proposed rearrangement algorithm can achieve improvement of 10 percent in terms of throughput. We also propose RookNet configuration which discriminates optical wavelength and subcarrier effectively in order to decrease the relay processing time.
Hirofumi YOKOI Shigeo SHIODA Hiroshi SAITO Jun MATSUDA
We investigated performance of routing schemes in B-ISDN, for heterogeneous traffic flows under various bandwidths. In particular, we compared the simulated performance of these schemes by evaluating their blocking probabilities. To achieve high performance, these schemes use special kinds of routing algorithm, one which is pre-selection algorithm and one which is cyclic algorithm. We investigated the efficiency of the pre-selection algorithm and the robustness of the cyclic algorithm for nonuniform traffic and network resources. We found that these routing algorithm schemes can compensate for errors in resource design.
Hiroyuki YAMAUCHI Hironori AKAMATSU Tsutomu FUJITA
A low power bus architecture with Local and Global Charge-Recycling Bus (Local-CRB and Global-CRB) techniques, featuring virtual stacking of the individual bus-capacitance and the dummy capacitor into a series configuration between supply voltage and ground, has been proposed. These Local and Global CRB schemes make it possible to reduce not only each bus-swing but also a total equivalent bus-capacitance of the ultra multi-bit buses running in parallel. The voltage swing of each bus is given by the recycled charge-supplying from the upper adjacent bus capacitance or the dummy capacitor, instead of the power line. The dramatical power reduction was verified by the simulated and measured data. According to these data, if employing the combination of those CRB schemes in a practical chip, the ultra-high data rate of 25 Gb/s can be achieved while maintaining the power dissipation to be less than 300 mW at Vcc3.6 V for the bus width of 512 bit with the bus-capacitance of 14 pF per bit operating at 50 MHz.
Ryoichi KAWAHARA Takuya ASAKA Shuichi SUMITA
This paper reports an overload control method for the Intelligent Network (IN). The IN, which is being investigated as a future communication network, facilitates both rapid introduction of new services and easy modification of existing services. In the IN, the call processing functions and data needed to achieve IN services are distributed over several nodes. Therefore, traffic demand for the various services may cause varying patterns of node overloads. It is therefore important to develop effective overload control methods and to evaluate their characteristics. We propose an overload control method and evaluate its characteristics in comparison with other methods under various overload traffic patterns with a network simulator that models all nodes and their relationships in the IN. In particular, we focus on three aspects of overload control: how can high throughput be maintained, how can an overloaded node be stabilized, and how can fair access be guaranteed.
This paper proposes a novel updating technique, dynamically updating, for achieving extension or modification of functions in a distributed system. Usual updating technique requires synchronous suspension for multiple processes for avoiding unspecified reception caused by the conflict of different versions of processes. Thus, this technique needs very high overhead and it must restrict the types of distributed systems, to which it can be applied, to RPC (remote procedure call) type or client-server type. Using the proposed dynamically updating technique, updating management can be invoked asynchronously by each process with assurance of correct execution of the system, i.e., the system can cope with the effect of unspecified reception caused by mixture of different version processes. Therefore, low overhead updating can be achieved in partner type distributed systems, that is more general type including communications systems or computer networks. Dynamically updating technique is implemented by using a novel distributed algorithm that consists of group communication, checkpoint setting, and rollback recovery. By using the algorithm proposed in this paper, rollback recovery can be achieved with the lowest overhead, i.e., a set of checkpoint determines the last global state for consistent rollback recovery and a set of processes that need to rollback simultaneously is the smallest one. This paper also proves the correctness of the proposed algorithm.
This paper describes an O(log3n) time O(n/log n) processors parallel algorithm for determining the congruence (exact matching) of two point sets in three-dimensions on a CREW PRAM, where n is the maximum size of the input point sets. Although optimal O(n log n) time sequential algorithms were developed for this problem, no efficient parallel algorithm was known previously. In the algorithm, the original problem is reduced to the two-dimensional congruence problem by computing a three-dimensional point set cps(S) for each input point set S, where cps(S) satisfies the following conditions: 0|cps(S)|12; cps(T(S))T(cps(S)) for all isometric transformations T. The two-dimensional problem can be solved efficiently in parallel using a parallel version of a previously-known sequential algorithm. cps(S) is computed recursively in the following way: the size of a point set is reduced by a constant factor in each recursive step. To reduce the size of a point set, a convex hull is constructed and then it is regarded as a planar graph, so that combinatorial properties of a planar graph are used effectively. A sequential version of the algorithm works in O(n log n) time, so that this paper gives another optimal sequential algorithm. The presented algorithm can be applied for graphs such that each vertex corresponds to a point and each edge corresponds to a line segment connecting its endpoints. Moreover, the algorithm can be modified for computing the canonical form of a point set or a graph.
Seiichi SERIKAWA Teruo SHIMOMURA
A new gloss-extracting method is proposed in this study. A spatial filter with variable resolution is used for the extraction of glossiness. Various spheres and cylinders with curvature radii from 4 to mm are used as the specimens. In all samples, a strong correlation, with a correlation coefficient of more than 0.98, has been observed between psychological glossiness Gph perceived by the human eye and glossiness Gfm extracted by this method. This method is useful for plane specimens as well as spherical and cylindrical ones.
Kimihide MATSUMOTO Satoshi NOJO
We propose a new concept of network dimensioning, which is based not only on the grade of service but also on profit. In traditional network dimensioning methodology, the number of circuits on links is designed under a cost-minimization concept with grade of service constraints. Recently, telecommunication markets have become very large and competitive; therefore, we believe that a profit viewpoint is now essential. However, it is difficult to calculate profit in almost all the dimensioning methods currently used, because they mainly employ peak-hour traffic data, while profit depends on all the hourly traffic data which contain both peak and off-peak data. In this paper, we propose using all the hourly traffic data in network dimensioning. From these data and telephone charges for each hour, revenues will be estimated. On the other hand, facility costs will be estimated from the number of circuits. Finally, we can estimate profit from the difference between revenues and facility costs. Focusing on both quality and profits in network dimensioning leads to more advanced quality management and quality control in telecommunications networks than with traditional methodology. This paper outlines a dimensioning method based on profit, and describes its properties, some applications of it, and summarizes further studies.
Kazunobu MATSUMOTO Akira KAWAKAMI
With the development in portable electronic equipment, the demand for secondary batteries of high energy density is increasing. Recently, nickel metal hydride secondary batteries (Ni/MH) are expanding the market, and lithium ion secondary batteries have been newly developed and commercialized. This paper describes in detail Ni/MH and lithium ion secondary batteries, and reports on their development state and characteristics.
Paulo LORENZO Munehiro GOTO Arthur J. CATTO
The Manchester Dataflow Machine (MDFM) works with tasks of size equal to one single instruction. This fine granularity aims at exploring all parallelism at the instruction level. However, this project decision increases the instruction communication cost, which ends up to jam the interconnection network and reduces the system performance. One way to skirt this problem is to adopt variable size tasks instead of working with such small task size. In this paper, in order to study whether or not the usage of such variable size tasks in the MDFM architecture contributes to the improvement of the performance, some simulations by toy programs take place. In the simulation, variable size tasks are realized by packing the sequential instruction stretches into one task. To manage this packing, the Sequential Block (SB) technique is developed. The simulation of those packed and unpacked programs give an outline of advantages and disadvantages of working with variable size tasks, and how the SB technique should be implemented in the system.
Takeshi NISHIDA Kunihiro TANIGUCHI
Over the last decade, the Internet has been extremely successful by distinguishing between overlaying applications and underlying networking technologies. This approach allows rapid and independent improvement in both networking and application technologies. The internetworking layer that divides applications and the network enables the Internet to function as a general and evolving infrastructures for data communications. The current Internet architecture offers only best-effort data delivery. However, recent emerging computer and networking technologies, demand the Internet guaranteed performance. In particular, audio and video applications have more rigid delay requirement than those applications which the current Internet supports. To offer guaranteed services in addition to best-effort services, both a new service model and a new architecture are necessary in the Internet architecture. The paper surveys researches and experiments conducted in the Internet community to accommodate a wide variety of qualities of services.
Circuit design techniques for linearizing adaptively biased differential pairs are described. An emitter-and source-coupled pair is adaptively biased by a squaring circuit to linearize its transconductance, one of whose inputs is divided by resistors. An input signal for a differential pair or a squaring circuit is set to an adequate amplitude by a resistive divider without sacrificing linearity. Therefore, a differential pair is biased by the output current of a squaring circuit and they are coupled directly. There are three design techniques for squaring circuits. One is the transistor-size unbalance technique. Another is the bias offset technique. A third is the multitail technique. The bipolar and MOS squaring circuits discussed in this paper were proposed by the author previously, and consist of transistor-pairs with different transistor size (i.e., the emitter areas or gate W/L values are different), transistor-pairs with the same bias offset, or a multitail cell(i.e., a triple-tail cell or quadritail cell). Several kinds of squaring circuits consisting of such transistor-pairs are applied to produce the quadratic bias currents for compensating the nonlinearity of an emitter-and source-coupled pair. Therefore, four circuits using emitter-coupled pairs with adaptive-biasing current and four circuits using source-coupled pairs with adaptive-biasing current are proposed and analyzed in depth. Furthermore, a circuit configuration for low voltage operation is also introduced and verified with bipolar transistor-arrays on a breadboard.
Atsushi TAKAHASHI Shuichi UENO Yoji KAJITANI
A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family Fkn of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph Fkn is at least Ω(kn log(n/k)). Next, we construct a universal graph for Fkn with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for Fkn is Θ(kn log(n/k)) .
Switched-capacitor chaotic neurons fabricated in a full-custom integrated circuit are used to investigate the behavior of 2- and 3-neuron chaotic neural networks. Various sets of parameters are used to visualize the dynamical responses of the networks. Hysteresis of the network is also demonstrated. Lyapunov exponents are approximated from the measured data to characterize the state of each neuron. The effect of the finite length of data and the rounding effect of data acquisition system to the computation of Lyapunov exponents are briefly discussed.
Device models for a laser diode, photodetector, MESFET, HEMT, bipolar transistor, diode, and resistor are proposed and are implemented in a commercial mixed-signal simulator along with models for an optical fiber, an external optical modulator, and a pulse pattern generator. The validity of the models is confirmed by comparing simulated and experimental results. The performance of a mixed photonic/electronic circuit, which is determined by a large-signal waveform and the device noises, is estimated by the present analysis method.