Shogo USAMI Tsuyoshi Sasaki USUDA Ichi TAKUMI Masayasu HATA
Recently, the quantum information theory attracts much attention. In quantum information theory, the existence of superadditivity in capacity of a quantum channel was foreseen conventionally. So far, some examples of codes which show the superadditivity in capacity have been clarified. However in present stage, characteristics of superadditivity are not still clear up enough. The reason is as follows. All examples were shown by calculating the mutual information by quantum combined measurement, so that one had to solve the eigenvalue and the eigenvector problems. In this paper, we construct a simplification algorithm to calculate the mutual information by using square-root measurement as decoding process of quantum combined measurement. The eigenvalue and the eigenvector problems are avoided in the algorithm by using group covariancy of binary linear codes. Moreover, we derive the analytical solution of the mutual information for parity check codes with any length as an example of applying the simplification algorithm.
Katsumi SAKAKIBARA Ritsuko IWASA Yoshiharu YUBA
We prove that binary images of irreducible cyclic codes C over GF(2m) and binary concatenated codes of C and a binary [m+1,m,2] even-parity code are optimal (in the sense that they meet the Griesmer bound with equality) and proper, if a root of the check polynomial of C is primitive over GF(2m) or its extensions.
This paper addresses the problem of learning Bayesian belief networks (BBN) based on the minimum description length (MDL) principle. First, we give a formula of description length based on which the MDL-based procedure learns a BBN. Secondly, we point out that the difference between the MDL-based and Cooper and Herskovits procedures is essentially in the priors rather than in the approaches (MDL and Bayesian), and recommend a class of priors from which the formula is obtained. Finally, we show as a merit of using the formula that a modified version of the Chow and Liu algorithm is obtained. The modified algorithm finds a set of trees rather than a spanning tree based on the MDL principle.
Masahide NAKAMURA Tohru KIKUNO
Feature interaction detection determines whether interactions occur or not between the new and existing telecommunication services. Most of conventional detection methods on state transition model utilize an exhaustive search. The exhaustive search is fundamentally very powerful in the sense that all interactions are exactly detected. However, it may suffer from the state explosion problem due to the exponential growth of the number of states in the model when the number of users and the number of features increase. In order to cope with this problem, we propose a new detection method using a state reduction technique. By means of a symmetric relation, called permutation symmetry, we succeed in reducing the size of the model while preserving the necessary information for the interaction detection. Experimental evaluation shows that, for practical interaction detection with three users, the proposed method achieves about 80% reduction in space and time, and is more scalable than the conventional ones especially for the increase of the number of users in the service.
Masayuki GOTOH Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
We analyze the extended stochastic complexity (ESC) which has been proposed by K. Yamanishi. The ESC can be applied to learning algorithms for on-line prediction and batch-learning settings. Yamanishi derived the upper bound of ESC satisfying uniformly for all data sequences and that of the asymptotic expectation of ESC. However, Yamanishi concentrates mainly on the worst case performance and the lower bound has not been derived. In this paper, we show some interesting properties of ESC which are similar to Bayesian statistics: the Bayes rule and the asymptotic normality. We then derive the asymptotic formula of ESC in the meaning of almost sure and mean convergence within an error of o(1) using these properties.
In this paper we propose a heterogeneous agents model that represents speculative dynamics by using the synergetic approach. We consider the markets for three securities (a stock, a bond, and a foreign currency). Each market consists of two typical types of investors: fundamentalists and bandwagon traders. We show the characteristic patterns of speculative prices (speculative bubbles and speculative chaos) which are generated by trading between the fundamentalists and bandwagon traders.
Toshiya NAKAGUCHI Kenya JIN'NO Mamoru TANAKA
We propose a hysteresis neural network system solving NP-Hard optimization problems, the N-Queens Problem. The continuous system with binary outputs searches a solution of the problem without energy function. The output vector corresponds to a complete solution when the output vector becomes stable. That is, this system does never become stable without satisfying the constraints of the problem. Though it is very hard to remove limit cycle completely from this system, we can propose a new method to reduce the possibility of limit cycle by controlling time constants.
Yasuo TACHIBANA Yoshinori SUZUKI
This paper deals with a method of estimating the parameters and the order of a linear system using differential digital filters and the resultant. From the observed signals of the input and output of an objective system, we extract the differential signals from the zero order to an appropriate high order with the same phase characteristics, using several digital filters. On the assumption that the system order is known, we estimate the parameters of the transfer function and evaluate the estimation error bounds. We propose a criterion function generated by the product of the highest order coefficients and the resultant of the numerator and denominator of the estimated transfer function. Applying this criterion function, we can estimate the order of the objective system. The threshold corresponding to this criterion function is evaluated from the deviation in the frequency characteristics of the used differential filters and the error bound of the estimated parameters. In order to demonstrate the propriety of the proposed method, some numerical simulations are presented.
Bao-Yu SONG Makoto FURUIE Yukihiro YOSHIDA Takao ONOYE Isao SHIRAKAWA
An NMOS 4-phase dynamic logic scheme is described, which is intended to achieve low-power consumption in the deep submicron design. In this scheme, the short-circuit current is eliminated, and moreover, the voltage swing of transition signals is reduced, resulting in enhancing power reduction effectively. First, distinctive features of this 4-phase dynamic logic are specified, as compared with the static CMOS logic and dynamic domino CMOS logic. Then, power simulations are attempted for the 4-phase dynamic logic, static CMOS logic, dynamic CMOS logic, and pass-transistor logic, by using a number of logic modules, which demonstrate that the NMOS 4-phase dynamic logic is the most power-efficient. Moreover, through the gate delay simulation, the capability of how many transistors can be packed in a logic block is also discussed.
In literature, many methods have been presented for enumerating binary trees (full binary trees) and regular k-ary trees, while no one for enumerating arbitrary trees or arbitrary k-ary trees. It is proposed in 1997 using a context-free grammar GBT (GFBT) to code binary trees (full binary trees) for enumerating them. In this paper, we use another grammar GT (GTk) to code arbitrary trees (arbitrary k-ary trees) for enumerating them. The properties of words of Ln(GT) (Ln(GTk)) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ln(GT) (Ln(GTk)), and efficient algorithms are given and analyzed for the enumeration of words of Ln(GT) (Ln(GTk)).
Takashi HIRAYAMA Goro KODA Yasuaki NISHITANI Kensuke SHIMIZU
It is known that AND-EXOR two-level networks obtained by AND-EXOR expressions with positive literals are easily testable. They are based on the single-rail-input logic, and require (n+4) tests to detect their single stuck-at faults, where n is the number of the input variables. We present three-level networks obtained from single-rail-input OR-AND-EXOR expressions and propose a more easily testable realization than the AND-EXOR networks. The realization is an OR-AND-EXOR network which limits the fan-in of the AND and OR gates to n/r and r respectively, where r is a constant (1 r n). We show that only (r+n/r) tests are required to detect the single stuck-at faults by adding r extra variables to the network.
Takashi HISAKADO Kohshi OKUMURA
This paper presents the several bifurcation phenomena generated in nonlinear three-phase circuit with symmetry. The circuit consists of delta-connected nonlinear inductors, capacitors and three-phase symmetrical voltage sources. Particular attention is paid to the subharmonic oscillations of order 1/2. We analyze the bifurcations of the oscillations from both theoretical and experimental points. As a tool of analysis, we use the homotopy method. Additionally, by comparing with single-phase and single-phase-like circuits, the special feature of the three-phase circuit is revealed.
Shigeo KINOSHITA Takashi MORIE Makoto NAGATA Atsushi IWATA
This paper proposes non-volatile analog memory circuits using pulse-width modulation (PWM) methods. The conventional analog memory using floating gate device has a trade-off between programming speed and precision because of the constant width of write pulses. The proposed circuits attain high programming speed with high precision by using PWM write pulses. Three circuits are proposed and their performance is evaluated using SPICE simulation. The simulation results show that fast programming time less than 20 µs, high updating resolution of 11 bits, and high precision more than 7 bits are achieved.
When we have a singular Cab curve with many rational points, we had better to construct linear codes on its normalization rather than the original curve. The only obstacle to construct linear codes on the normalization is finding a basis of L( Q) having pairwise distinct pole orders at Q, where Q is the unique place of the Cab curve at infinity. We present an algorithm finding such a basis from defining equations of the normalization of the original Cab curve.
Pao-Chi CHANG Jong-Tzy WANG Yu-Cheng LIN
The MPEG video coding is the most widely used video coding standard which usually generates variable bitrate (VBR) data streams. Although ATM can deliver VBR traffic, the burst traffic still has the possibility to be dropped due to network congestion. The cell loss can be minimized by using an enforced rate control method. However, the quality of the reproduced video may be sacrificed due to insufficient peak rate available. In this work, we propose an end-to-end quality adaptation mechanism for MPEG traffic over ATM. The adaptive quality control (AQC) scheme allocates a certain number of coding bits to each video frame based on the network condition and the type of next frame. More bits may be allocated if the network condition, represented by the connection-level, is good or the next frame is B-frame that usually consumes fewer bits. A high connection-level allows a relatively large number of tagged cells, which are non-guaranteed in delivery, for video frames with high peak rates. The connection-level adjustment unit at the encoder end adjusts the connection-level based on the message of the network condition from the quality monitoring unit at decoder. The simulation results show that the AQC system can effectively utilize the channel bandwidth as well as maintain satisfactory video quality in various network conditions.
Atsushi KAMO Hiroshi NINOMIYA Teru YONEYAMA Hideki ASAI
This paper describes an efficient simulator for state transition analysis of multivalued continuous-time neural networks, where the multivalued transfer function of neuron is regarded as a stepwise constant one. Use of stepwise constant method enables to analyse the state transition of the network without solving explicitly the differential equations. This method also enables to select the optimal timestep in numerical integration. The proposed method is implemented on the simulator and applied to the general neural network analysis. Furthermore, this is compared with the conventional simulators. Finally, it is shown that our simulator is drastically faster and more practical than the conventional simulators.
We analyze the dynamics of self-organizing cortical maps under the influence of external stimuli. We show that if the map is a contraction, then the system has a unique equilibrium which is globally asymptotically stable; consequently the system acts as a stable encoder of external input stimuli. The system converges to a fixed point representing the steady-state of the neural activity which has as an upper bound the superposition of the spatial integrals of the weight function between neighboring neurons and the stimulus autocorrelation function. The proposed theory also includes nontrivial interesting solutions.
Recently, many on-line control methods of partially observed discrete event systems(DES's) have been proposed. This paper proposes an algorithm for on-line control based on a supervisor under complete observation. It is shown that DES's controlled by the proposed on-line controller generate maximally controllable and observable sublanguages which include the supremal normal sublanguages. Moreover, computational complexity of the proposed algorithm is polynomial with respect to the numbers of the unobservable events and the state of the supervisor under complete observation.
Ernesto DAMIANI Valentino LIBERALI Andrea G. B. TETTAMANZI
An evolutionary algorithm is used to evolve a digital circuit which computes a simple hash function mapping a 16-bit address space into an 8-bit one. The target technology is FPGA, where the search space of the algorithm is made of the combinational functions computed by cells and of the interconnections among cells. The evolutionary technique has been applied to five different interconnection topologies, specified by neighbourhood graphs. This circuit is readily applicable to the design of set-associative cache memories. Possible use of the evolutionary approach presented in the paper for on-line tuning of the function during cache operation is also discussed.
This paper describes the design of a scalable pipelined memory buffer for a shared scalable buffer ATM switch. The memory architecture provides high speed and scalability, and eliminates the restriction of memory cycle time in a shared buffer ATM switch. It provides versatile performance in a shared buffer ATM switch using its scalability. The architecture consists of a 2-D array configuration of small memory banks. Increasing the array configuration enlarges the entire memory capacity. Maximum cycle time of a designed scalable memory is 4 ns. The designed memory is embedded in the prototype chip of a shared scalable buffer ATM switch with 4 4 configuration of 4160-bit SRAM memory banks. It is integrated in 0.6 µm double-metal single-poly CMOS technology.