In this paper, we study the following problem: given two graphs G, H and an isomorphism φ between an induced subgraph of G and an induced subgraph of H, compute the number of isomorphisms between G and H that do not contradict φ. We show that this problem can be solved in O(((k+1)(k+1)!)2n3) time when the input graphs are restricted to chordal graphs with clique number at most k+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in O(n3) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between G and H can be efficiently computed by use of the tree model.

In this paper, a novel method of clock feedthrough reduction in CMOS autozeroed operational amplifiers with three-phase clock operation is presented. The operational amplifiers in the method are configured by two autozeroed-gain stages. The differential input stage and the second output gain stage are autozeroed individually by a three-phase clock for autozeroing. The three-phase clock is provided so as to finish the compensation period of the input stage earlier than the end of the second stage compensation period. This operation makes it possible to absorb affection of clock feedthrough in the input stage with the second stage. As a result, residual error of offset compensation is much reduced by the voltage gain of the first stage. The effect of the two-stage autozeroing has been confirmed with SPICE simulation and fabricated CMOS circuit. The results of SPICE simulation showed that the two-stage autozeroed operational amplifier has significant advantage as compared to conventional configuration. Affection of clock feedthrough is reduced to about 1/50 in the two-stage configuration. Fabricated CMOS circuit also showed high potential of the two-stage autozeroed operational amplifier for feedthrough reduction. It has been proven experimentally that the two-stage autozeroing is an effective design approach to reduce clock feedthrough error in CMOS autozeroed operational amplifiers.

A noise suppression algorithm with high speech quality based on weighted noise estimation and MMSE STSA is proposed. The proposed algorithm continuously updates the estimated noise by weighted noisy speech in accordance with an estimated SNR. The spectral gain is modified with the estimated SNR so that it can better utilize the improvement in noise estimation. With a better noise estimate, a more correct SNR is obtained resulting in the enhanced speech with low distortion. Subjective evaluation results show that five-grade mean opinion scores of the new algorithm with and without a speech codec are improved by as much as 0.35 and 0.40 respectively, compared with either the original MMSE STSA or the EVRC noise suppression algorithm.

This paper presents a comparison of the throughput performance employing hybrid automatic repeat request (HARQ) with packet combining, such as Type-I with packet combining (simply Chase combining hereafter) and Type-II (Incremental redundancy hereafter), using turbo coding in a multipath fading channel in high speed downlink packet access (HSDPA). We apply a multipath interference canceller (MPIC) to remove the influence of severe multipath interference. Link level simulation results show that the maximum throughput using Incremental redundancy with 64QAM is improved by approximately 5-8% compared to that using Chase combining, and that the required average received signal energy of 12 code channels per chip-to-background noise spectrum density (Ec/N0) at the throughput of 4 Mbps with Incremental redundancy is decreased by approximately 1.0 dB rather than that with Chase combining when the vehicular speed is higher than approximately 30 km/h. Furthermore, we elucidate based on the system level simulation that although no improvement is obtained in a slow mobility environment such as the average vehicular speed of 3 km/h, the achieved throughput of Incremental redundancy is increased by approximately 5-6% and 13% for the average vehicular speed of 30 km/h and 120 km/h, respectively, compared to that with Chase combining.

In this paper, we propose topic extraction models based on statistical relevance scores between topic words and words in articles, and report results obtained in topic extraction experiments using continuous speech recognition for Japanese broadcast news utterances. We attempt to represent a topic of news speech using a combination of multiple topic words, which are important words in the news article or words relevant to the news. We assume a topic of news is represented by a combination of words. We statistically model mapping from words in an article to topic words. Using the mapping, the topic extraction model can extract topic words even if they do not appear in the article. We train a topic extraction model capable of computing the degree of relevance between a topic word and a word in an article by using newspaper text covering a five-year period. The degree of relevance between those words is calculated based on measures such as mutual information or the χ2-method. In experiments extracting five topic words using a χ2-based model, we achieve 72% precision and 12% recall for speech recognition results. Speech recognition results generally include a number of recognition errors, which degrades topic extraction performance. To avoid this, we employ N-best candidates and likelihood given by acoustic and language models. In experiments, we find that extracting five topic words using N-best candidate and likelihood values achieves significantly improved precision.

A plane drawing of a graph is called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at most n faces. The algorithm uses O(n) space and generates such floorplans in O(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactly n faces in O(1) time per floorplan. Also we can generate without duplications all (non-based) floorplans having exactly n faces in O(n) time per floorplan.

This paper reviews the advantages of the silicon three-dimensional MMIC technology such as low loss transmission lines, high integration level, and high Q-factor on-chip inductors. Coupled to the masterslice concept, this technology also offers simple design procedure, short turn-around-time, low cost, and potential integration with LSI circuits. A K-band amplifier and an up-converter demonstrate the high frequency operation and low-power consumption benefits of the Si 3-D MMIC technology. A C-band Si-bipolar single-chip transceiver is proposed to illustrate the high integration level offered by the masterslice concept. Finally, the recent advances we achieved toward high Q-factor on-chip inductors provide the design of the S-band low noise amplifier presented in this paper.

In this letter, we consider one-to-all broadcast on distributed memory parallel computers based on message-passing, such as cluster of WSs or PCs. We present an efficient broadcast algorithm, called overlapped-two-phase broadcast (O2PB), that is an enhanced version of two-phase broadcast (2PB). The O2PB algorithm is compared with other algorithms, such as linear broadcast, tree broadcast and 2PB algorithms. According to our theoretical and experimental results, when the size of message to be broadcasted is large, the O2PB algorithm is fastest among all the algorithms. The O2PB algorithm is approximately 20% faster than the 2PB algorithm.

This paper discusses a new type of semi-supervised document clustering that uses partial supervision to partition a large set of documents. Most clustering methods organizes documents into groups based only on similarity measures. In this paper, we attempt to isolate more semantically coherent clusters by employing the domain-specific knowledge provided by a document analyst. By using external human knowledge to guide the clustering mechanism with some flexibility when creating the clusters, clustering efficiency can be considerably enhanced. Experimental results show that the use of only a little external knowledge can considerably enhance the quality of clustering results that satisfy users' constraint.

The multicast ATM switch has been developed for the purpose of the point-to-multipoint cell transmission. The basic structure of conventional multicast ATM switches is mainly based on a T. T. Lee's multicast switch, since it has a very simple and expandable structure. However, in spite of these benefits, it requires excessive hardware for the loss-free cell transmission, since it employs the blocking network, i.e., the banyan network as a copy network and a routing network. In this paper, we propose a new network for the multicast ATM switching. In proposed copy network, we adopt a new structure, the parallel broadcast banyan network with bypass links between switch planes, to offer the maximum cell transmission capacity and the fault tolerance. All conflict cells, which are blocked during the cell routing process, are bypassed to the next switch plane through bypass links and try to be routed. And to support the highly efficient cell transmission, we propose Alternate Path Scheme (APS) and copy-number (CN) comparator in the proposed copy network. APS is a kind of cell transmission schemes and guarantees multicasting capability to achieve a high performance. To estimate the performance of a proposed copy network, we provide several simulation results.

In this paper, we discuss the applicability of H filtering algorithm for a decision feedback equalizer (DFE) in mobile communications environments. A comparison of bit error rate (BER) performance between a H2 filtering (recursive least squares) algorithm-based and an a priori H filtering algorithm-based fractionally-tap-spaced DFEs in various fading channels is presented. Against, our results are rather pessimistic of the H equalizer, namely, as compared with the H2 equalizer, at most the same or a little better BER performance of the H equalizer is obtained only when the ratio of the average received energy per bit to the white noise power spectral density and the normalized fading rate are large enough, especially in Rician fading channels. Moreover, the H equalizer has the problems of how to choose an appropriate prescribed positive value and computational complexity, therefore it may not be considered as an attractive alternative to the H2 equalizer for wireless communications systems.

In this paper, a Turbo codec with reduced number of iterations is proposed. By inserting an even parity-check bit every six information bit, the coder can increase the minimum distance of the codewords and the number of iterations is reduced. Furthermore, this codec accommodates automatic repeat request (ARQ) scheme easily.

The problem of finding a path with two additive constraints, in particular finding a path that satisfies both the cost and the delay constraints, is called multi-constrained path (MCP) problem in the literature. In this paper, we explore the MCP problem based on the idea of single mixed weight --a mixed weight for each link is first obtained by combining its delay and cost, and then Dijkstra's algorithm is used to find the corresponding shortest path. Given two infeasible paths, it can be theoretically proved that a better path can possibly be found if we choose an appropriate parameter to construct the mixed weight. An approximate algorithm is thus proposed to solve the MCP problem. Theoretical analysis demonstrates that this algorithm can make a correct judgment whether there is a feasible path or not with a very high probability even in the strict case where the delay bound is between the delays of the least delay path and the least cost path, while the cost bound is between the costs of the two paths. On the other hand, the time complexity of this algorithm is very small since it only needs to execute Dijkstra's algorithm a limited number of times. The excellent performance of the proposed algorithm is verified by a large number of experiments on networks of different sizes.

In this paper, a rotman lens of multi-beam feed that can be applied to a car collision avoidance radar is designed using nonradiative dielectric (NRD) guide appropriate to the millimeter wave frequency. For the optimum condition, NRD guide at the transmission lines of input and output ports is designed to obtain low loss, small coupling between the transmission lines, and dominant mode operation. The rotman lens is also optimized so as to minimize sidelobe of array factor. To prevent beam pattern from being distorted, multiple-reflection from sidewall has been eliminated by corrugated sidewall.

In this paper, we propose a simplified transform-based and variable-rate vocoder, which is evolved from the code-excited linear prediction (CELP) coding structure. With pre-emphasis and de-emphasis filters, the transformed-based CELP vocoder incorporates a long-term predictor, a discrete cosine transform (DCT), and pre-filters and postfilters for achieving perceptually weighted quantization. The proposed transform-based vocoder requires less computational complexity with slightly worse quality than the CELP coders. Furthermore, the proposed DCT-based coding structure easily figured with additional DCT coefficients could simultaneously offer low, middle, and high bit rates to adapt the variation of bandwidth for modern Internet or wireless communications.

In this letter, we propose high-speed binary to residue converters for moduli 2n, 2n 1 without using look-up table. For integration of residue arithmetic circuit using a signed-digit (SD) number representation with ordinary binary system, the proposed circuits carry out the efficient conversion. Using SD adders instead of ordinary adders that are used in conventional binary to residue converter, the high-speed conversion without the carry propagation can be achieved. Thus, the proposed converter is independent of the size of modulus and can speed up the binary to residue conversion. On the simulation, the conversion delay times are 1.78 ns for modulus 210-1 and 1.73 ns for modulus 210+1 under the condition of 0.6 µm CMOS technology, respectively. The active area of the proposed converter for moduli 210 1 is 335 µm325 µm.

A novel delta-sigma modulator that utilizes a resonant-tunneling diode (RTD) quantizer is proposed and its operation is investigated by HSPICE simulations. In order to eliminate the signal-to-noise-and-distortion ratio (SINAD) degradation caused from the poor isolation of a single-stage quantizer (1SQ), a three-stage quantizer (3SQ), which consists of three cascoded RTD quantizers, is introduced. At a sample rate of 10 Gsps (samples per a second) and a signal bandwidth of 40 MHz (oversampling ratio of 128), the modulator demonstrates a SINAD of 56 dB, which corresponds to the effective number of bits of 9.3.

In this paper we introduce a bottom-up pushdown tree transducer (b-PDTT) which is a bottom-up tree transducer with pushdown storage (where the pushdown storage stores the trees) and may be considered as a dual concept of the top-down pushdown tree transducer (t-PDTT). After proving some fundamental properties of b-PDTT, for example, any b-PDTT can be realized by a linear stack with single state and converted into G-type normal form which corresponds to Greibach normal form in a context-free grammar, and so on, we compare the translational capability of a b-PDTT with that of a t-PDTT.

In this paper, we propose an efficient dual-tree-based multicasting scheme with three destination-switch partition strategies on irregular switch-based networks. The dual-tree-based routing scheme supports adaptive, distributed, and deadlock-free multicast on irregular networks with double channels. We first describe a dual-tree structure constructed from the irregular networks and prove that the multicasting based on such a structure is deadlock-free. Then, an efficient multicast routing algorithm with three destination-switch partition strategies: source-switch-based partition, destination-switch-based partition, and all-switches-based partition, is proposed. Finally, we perform simulations to evaluate our proposed algorithm under various impact parameters: system size, message length, and startup time. The experimental results show that the improved tree-based multicasting scheme outperforms the usual tree-based multicasting scheme. The dual-tree-based multicasting scheme with destination-switch-based partition is shown to be the best for all situations.

In this paper the authors propose a method for designing the Virtual Private Network (VPN) that guarantees a strict Quality of Service (QoS) over IP networks. The assumed QoS metric is PLP (Packet Loss Probability), and it is guaranteed probabilistically by the provision of an appropriate equivalent bandwidth. We consider two network architectures for constructing VPN, the customer pipe scheme and the Hose scheme, and we present an analytic model to compute the amount of the required bandwidth for the two schemes. Finally, we investigate the validity of the proposition via numerical experiments.