Tran Ha NGUYEN Kiyohide NAKAUCHI Masato KAWADA Hiroyuki MORIKAWA Tomonori AOYAMA
Layered multicast approach enables IP multicast to adapt to heterogeneous networks. In layered multicast, each layer of a session is sent to separate multicast groups. These layers will be transmitted on the same route, or on different routes. However, traditional congestion control schemes of layered multicast do not consider the case when layers of a session are transmitted on different routes. In this paper, at first we show that in sparse-mode routing protocols like PIM-SM and CBT, layers of a session can be mapped to different Rendezvous Points or cores due to the bootstrap mechanism. It means that layers of a session can be transmitted on different routes. We then show that traditional congestion control schemes of layered multicast do not work properly in sparse-mode routing regions. At last we introduce Rendezvous Point based Layered Multicast (RPLM), a novel congestion control scheme suitable for sparse-mode routing regions, and show that RPLM works efficiently in regions using sparse mode routing protocols. RPLM uses per-RP packet loss rate instead of the overall one to detect congestion on each route, and can react to congestion quickly by dropping the highest layer on the congested route. In addition, RPLM simultaneously drops all the layers those are useless in quality's improvement to prevent bandwidth waste.
Wavelength converters are usually used for improving the performance of WDM optical networks. From the viewpoint of network economics and current technologies, the wavelength converters with a limited conversion range are necessary to be used sparsely in real applications. However, there have been little efforts for developing wavelength assignment algorithm that achieves a guaranteed high performance with either limited or sparse wavelength conversion. In this paper, we propose a new wavelength assignment algorithm that can be applied to both sparse and limited wavelength conversion. Through the results of simulation program, we show that the proposed algorithm outperforms other ones presented until now.
Hiromitsu SHIINA Shigeru MASUYAMA
This paper proposes the UGLR parser as an extension of the GLR parser. A UGLR parser is powerful enough to parse deterministically any phrase structure language if it is in the class of recursive languages and can parse any context free language as fast as the conventional GLR parser. Natural language processing often requires a parser for languages belonging to classes larger than that of context free languages, and the proposed parser is useful for this purpose.
The conventional synthesis procedure of discrete time sparsely interconnected neural networks (DTSINNs) for associative memories may generate the cells with only self-feedback due to the sparsely interconnected structure. Although this problem is solved by increasing the number of interconnections, hardware implementation becomes very difficult. In this letter, we propose the DTSINN system which stores the 2-dimensional discrete Walsh transforms (DWTs) of memory patterns. As each element of DWT involves the information of whole sample data, our system can associate the desired memory patterns, which the conventional DTSINN fails to do.
Akihiko SUGIYAMA Kenji ANZAI Hiroshi SATO Akihiro HIRANO
This paper proposes a scalable multiecho cancellation system based on multiple autonomic and distributed echo canceler units. The proposed system does not have any common control section. Distributed control sections are equipped with in multiple echo cancelers operating autonomically. Necessary information is transferred from one unit to the next one. When the number of echoes to be canceled is changed, the necessary number of echo canceler units, each of which may be realized on a single chip, are simply plugged in or unplugged. The proposed system also provides fast convergence thanks to the novel coefficient location algorithm which consists of flat-delay estimation and constrained tap-position control. The input signal is evaluated at each tap to determine when to terminate flat-delay estimation. The number of exchanged taps is selected larger in flat-delay estimation than in constrained tap-position control. The convergence time with a colored-signal input is reduced by approximately 50% over STWQ, and 80% over full-tap NLMS algorithm. With a real speech input, the proposed system cancels the echo by about 20 dB. Tap-positions have been shown to be controlled correctly.
Chi H.CHAN Chien Min LIN Leung TSANG Yiu Fung LEUNG
In this paper, we illustrate the analysis of microstrip structures with a large number of unknowns using the sparse-matrix/canonical grid method. This fast Fourier thansform (FFT) based iterative method reduces both CPU time and computer storage memory requirements. We employ the Mixed-Potential Integral Equation (MPIE) formulation in conjunction with the RWG triangular discretization. The required spatial-domain Green's functions are obtained efficiently and accurately using the Complex Image Method (CIM). The impedance matrix is decomposed into a sparse matrix which corresponds to near interactions and its complementary matrix which corresponds to far interactions among the subsectional current elements on the microstrip structures. During the iterative process, the near-interaction portion of the matrix -vector multiplication is computed directly as the conventional MPIE formulation. The far-interaction portion of the matrix-vector multiplication is computed indirectly using fast Fourier transforms (FFTs). This is achieved by a Taylor series expansion of the Green's function about the grid points of a uniformly-spaced canonical grid overlaying the triangular discretization.
Hiroto SHINGAI Hiroyuki MATSUNAGA Kiichi URAHAMA
A method based on clustering is presented for restoring and segmenting gray scale images. An optimum clustering obtained by a gradient method gives an image with gray scale values which vary smoothly in each segmented region. The method is also applied to restoration from sparsely sampled data.
Akitoshi KATAOKA Sachiko KURIHARA Shinji HAYASHI Takehiro MORIYA
A trained sparse conjugate codebook is proposed for improving the speech quality of CELP-based coding in a noisy environment. Although CELP coding provides high quality at a low bit rate in a silent environment (creating clean speech), it cannot provide a satisfactory quality in a noisy environment because the conventional fixed codebook is designed to be suitable for clean speech. The proposed codebook consists of two sub-codebooks; each sub-codebook consists of a random component and a trained component. Each component has excitation vectors consisting of a few pulses. In the random component, pulse position and amplitude are determined randomly. Since the radom component does not depend on the speech characteristics, it handles noise better than the trained one. The trained component maintains high quality for clean speech. Since excitation vector is the sum of the two sub-excitation vectors, this codebook handles various speech conditions by selecting a sub-vector from each component. This codebook also reduces the computational complexity of a fixed codebook search and memory requirements compared with the conventional codebook. Subjective testing (absolute category rating (ACR) and degradation category rating (DCR)) indicated that this codebook improves speech quality compared with the conventional trained codebook for noisy speech. The ACR test showed that the quality of the 8 kbit/s CELP coder with this codebook is equivalent to that of the 32 kbit/s ADPCM for clean speech.
This paper describes an error-correcting parser (ec-parser) for context-free languages that is an extension of the Leiss's parser. Since the ec-parser uses precomputed informations and a pruning technique by lookahead, the ec-parser is always faster than the Lyon's parser. Several examples are shown.
We consider an asymptotically sparsely encoded associative memory. Patterns are encoded by n-dimensional vectors of 1 and 1 generated randomly by a sequence of biased Bernoulli trials and stored in the network according to Hebbian rule. Using a heuristic argument we derive the following capacities:c(n)ne/4k log n'C(n)ne/4k(1e)log n'where, 0e1 controls the degree of sparsity of the encoding scheme and k is a constant. Here c(n) is the capacity of the network such that any stored pattern is a fixed point with high probability, whereas C(n) is the capacity of the network such that all stored patterns are fixed points with high probability. The main contribution of this technical paper is a theoretical verification of the above results using the Poisson limit theorems of exchangeable events.
Masaaki NAGATA Tsuyoshi MORIMOTO
A unification-based Japanese parser has been implemented for an experimental Japanese-to-English spoken language translation system (SL-TRANS). The parser consists of a unification-based spoken-style Japanese grammar and an active chart parser. The grammar handles the syntactic, semantic, and pragmatic constraints in an integrated fashion using HPSG-based framework in order to cope with speech recognition errors. The parser takes multiple sentential candidates from the HMM-LR speech recognizer, and produces a semantic representation associated with the best scoring parse based on acoustic and linguistic plausibility. The unification-based parser has been tested using 12 dialogues in the conference registration domain, which include 261 sentences uttered by one male speaker. The sentence recognition accuracy of the underlying speech recognizer is 73.6% for the top candidate, and 83.5% for the top three candidates, where the test-set perplexity of the CFG grammar is 65. By ruling out erroneous speech recognition results using various linguistic constraints, the parser improves the sentence recognition accuracy up to 81.6% for the top candidate, and 85.8% for the top three candidates. From the experiment result, we found that the combination of syntactic restriction, selectional restriction and coordinate structure restriction can provide a sufficient restriction to rule out the recognition errors between case-marking particles with the same vowel, which are the type of errors most likely to occur. However, we also found that it is necessary to use pragmatic information, such as topic, presupposition, and discourse structure, to rule out the recognition errors involved with topicalizing particles and sentence final particles.
Akito NAGAI Shigeki SAGAYAMA Kenji KITA Hideaki KIKUCHI
This paper discusses three approaches for combining an efficient LR parser and phoneme-context-dependent HMMs and compares them through continuous speech recognition experiments. In continuous speech recognition, phoneme-context-dependent allophonic models are considered very helpful for enhancing the recognition accuracy. They precisely represent allophonic variations caused by the difference in phoneme-contexts. With grammatical constraints based on a context free grammar (CFG), a generalized LR parser is one of the most efficient parsing algorithms for speech recognition. Therefore, the combination of allophonic models and a generalized LR parser is a powerful scheme enabling accurate and efficient speech recognition. In this paper, three phoneme-context-dependent LR parsing algorithms are proposed, which make it possible to drive allophonic HMMs. The algorithms are outlined as follows: (1) Algorithm for predicting the phonemic context dynamically in the LR parser using a phoneme-context-independent LR table. (2) Algorithm for converting an LR table into a phoneme-context-dependent LR table. (3) Algorithm for converting a CFG into a phoneme-context-dependent CFG. This paper also includes discussion of the results of recognition experiments, and a comparison of performance and efficiency of these three algorithms.
We investigate the relationship between two different notions of reducibility among prediction (learning) problems within the distribution-free learning model of Valiant (PAC learning model). The notions of reducibility we consider are the analogues for prediction problems of the many-one reducibility and of the Turing reducibility. The former is the notion of prediction preserving reducibility developed by Pitt and Warmuth, and its generalization. Concerning these two notions of reducibility, we show that there exist a pair of prediction problems A and B, whose membership problems are polynomial time solvable, such that A is reducible to B with respect to the Turing reducibility, but not with respect to the prediction preserving reducibility. We show this result by making use of the notion of a class of polynomially sparse variants of a concept representation class. We first show that any class A of polynomially sparse variants of another class B is reducible to B with respect to the Turing reducibility'. We then prove the existence of a prediction problem R and a class R of polynomially sparse variants of R, such that R does not reduce to R with respect to the prediction preserving reducibility.