Shin-ichiro KAWANO Shin-ichi NAKANO
In this paper we give a simple algorithm to generate all partitions of {1,2,,n} into k non-empty subsets. The number of such partitions is known as the Stirling number of the second kind. The algorithm generates each partition in constant time without repetition. By choosing k = 1,2,,n we can also generate all partitions of {1,2,,n} into subsets. The number of such partitions is known as the Bell number.
Seikoh YOSHIDA Nariaki IKEDA Jiang LI Takahiro WADA Hironari TAKEHARA
We propose a novel Schottky barrier diode with a dual Schottky structure combined with an AlGaN/GaN heterostructure. The purpose of this diode was to lower the on-state voltage and to maintain the high reverse breakdown voltage. An AlGaN/GaN heterostructure was grown using a metalorganic chemical vapor deposition (MOCVD). The Schottky barrier diode with a dual Schottky structure was fabricated on the AlGaN/GaN heterostructure. As a result, the on-voltage of the diode was below 0.1 V and the reverse breakdown voltage was over 350 V.
This paper newly proposes a method to automatically decompose real scene images into multiple object-oriented component regions. First, histogram patterns of a specific image feature, such as intensity or hue value, are estimated from image sequence and stored up. Next, Gaussian distribution parameters which correspond to object components involved in the scene are estimated by applying the EM algorithm to the accumulated histogram. The number of the components is simultaneously estimated by evaluating the minimum value of Bayesian Information Criterion (BIC). This method can be applied to a variety of computer vision issues, for example, the color image segmentation and the recognition of scene situation transition. Experimental results applied for indoor and outdoor scenes showed the effectiveness of the proposed method.
Takanori FUKUOKA Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z+{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.
We propose source coding algorithms that use the randomness of a past sequence. The proposed algorithms solve the problems of multi-terminal source coding, rate-distortion source coding, and source coding with partial side information at the decoder. We analyze the encoding rate and the decoding error rate in terms of almost-sure convergence.
Morikazu NAKAMURA Naruhiko YAMASHIRO Yiyuan GONG Takashi MATSUMURA Kenji ONAGA
This paper proposes an iterative parallel genetic algorithm with biased initial population to solve large-scale combinatorial optimization problems. The proposed scheme employs a master-slave collaboration in which the master node manages searched space of slave nodes and assigns seeds to generate initial population to slaves for their restarting of evolution process. Our approach allows us as widely as possible to search by all the slave nodes in the beginning period of the searching and then focused searching by multiple slaves on a certain spaces that seems to include good quality solutions. Computer experiment shows the effectiveness of our proposed scheme.
Koji GODA Toshinori YAMADA Shuichi UENO
This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.
Shoichi MASUI Kenji MUKAIDA Masahiko TAKENAKA Naoya TORII
High-speed, area-efficient, and low-power Montgomery modular multipliers for RSA algorithm have been developed for digital signature and user authentication in high-speed network systems and smart card LSIs. The multiplier-accumulators (MAC) in the developed Montgomery modular multipliers have a non-identical multiplicand/multiplier word length organization. This organization can eliminate the bandwidth bottleneck associated with a data memory, and enables to use a single-port memory for area and power reductions. The developed MAC is faster than the conventional identical word length organization due to the shortened critical path. For smart card applications, an area-efficient architecture with 42 kgates can produce 1.2 digital signatures in a second for 2,048-bit key length with the power consumption of 6.8 mW.
Anycast refers to the transmission of data from a source node to (any) one member in the group of designed recipients in a network. When the physical network and the set of anycast requests are given, the WDM anycast routing problem (WARP) is to find a set of light-paths, one for each source, for anycasting messages to one of the member in the anycast destination group such that not any path using the same wavelength passes through the same link. The goal of the WARP is to minimize the number of used wavelengths. In this paper, the WARP is formulated and studied, since WARP is NP-hard, several heuristic algorithms and a hybrid method which combines heuristic and simulated annealing techniques are proposed to solve it. These algorithms are used to find the close-to-optimal solution. Simulated results show that the proposed algorithms are able to achieve good performance.
Takatoshi JITSUHIRO Satoshi NAKAMURA
We propose a new method both for automatically creating non-uniform, context-dependent HMM topologies, and selecting the number of mixture components based on the Variational Bayesian (VB) approach. Although the Maximum Likelihood (ML) criterion is generally used to create HMM topologies, it has an over-fitting problem. Recently, to avoid this problem, the VB approach has been applied to create acoustic models for speech recognition. We introduce the VB approach to the Successive State Splitting (SSS) algorithm, which can create both contextual and temporal variations for HMMs. Experimental results indicate that the proposed method can automatically create a more efficient model than the original method. We evaluated a method to increase the number of mixture components by using the VB approach and considering temporal structures. The VB approach obtained almost the same performance as the smaller number of mixture components in comparison with that obtained by using ML-based methods.
Energy-efficient operations are essential to prolonging the lifetime of wireless sensor networks. Clustering sensor nodes is one approach that can reduce energy consumption by aggregating data, controlling transmission power levels, and putting redundant sensor nodes to sleep. To distribute the role of a cluster head, clustering approaches should be based on efficient cluster configuration schemes. Therefore, low overhead in the cluster configuration process is one of the key constraints for energy-efficient clustering. In this paper, we present an autonomous clustering approach using a coverage estimation-based self-pruning algorithm. Our strategy for clustering is to allow the best candidate node within its own cluster range to declare itself as a cluster head and to dominate the other nodes in the range. This same self-declaration strategy is also used in the active sensor election process. As a result, the proposed scheme can minimize clustering overheads by obviating both the requirements of collecting neighbor information beforehand and the iterative negotiating steps of electing cluster heads. The proposed scheme allows any type of sensor network application, including spatial query execution or periodic environment monitoring, to operate in an energy-efficient manner.
This paper presents a method of searching for the shortest route via the most designated points with the length not exceeding the preset upper bound. The proposed algorithm can obtain the quasi-optimum route efficiently and its effectiveness is verified by applying the algorithm to the actual map data.
Takahiro MURAKAMI Tetsuya HOYA Yoshihisa ISHIDA
This paper presents a novel algorithm for spectral subtraction (SS). The method is derived from a relation between the spectrum obtained by the discrete Fourier transform (DFT) and that by a subspace decomposition method. By using the relation, it is shown that a noise reduction algorithm based on subspace decomposition is led to an SS method in which noise components in an observed signal are eliminated by subtracting variance of noise process in the frequency domain. Moreover, it is shown that the method can significantly reduce computational complexity in comparison with the method based on the standard subspace decomposition. In a similar manner to the conventional SS methods, our method also exploits the variance of noise process estimated from a preceding segment where speech is absent, whereas the noise is present. In order to more reliably detect such non-speech segments, a novel robust voice activity detector (VAD) is then proposed. The VAD utilizes the spread of eigenvalues of an autocorrelation matrix corresponding to the observed signal. Simulation results show that the proposed method yields an improved enhancement quality in comparison with the conventional SS based schemes.
Won-Gi HONG Young-Ro KIM Tae-Myoung OH Sung-Jea KO
Recently, many algorithms have been proposed for fast full search motion estimation. Among them, successive elimination algorithm (SEA) and its modified algorithms significantly speed up the performance of the full search algorithm. By introducing the inequality equation between the norm and the mean absolute difference (MAD) of two matching blocks, the SEA can successively eliminate invalid candidate blocks without any loss in estimation accuracy. In this paper, we propose a partial norm based early rejection algorithm (PNERA) for fast block motion estimation. The proposed algorithm employs the sum of partial norms from several subblocks of the block. Applying the sum of partial norms to the inequality equation, we can significantly reduce the computational complexity of the full search algorithm. In an attempt to reduce the computational load further, the modified algorithms using partial norm distortion elimination (PNDE) and subsampling methods are also proposed. Experimental results show that the proposed algorithm is about 4 to 9 times faster than the original exhaustive full search, and is about 3 to 4 times faster than the SEA.
Hirohisa GAMBE Yoshinori TANAKA Kazuhisa OHBUCHI Teruo ISHIHARA Jifeng LI
Thanks to the possibility of being able to implement them in decoders in relatively simple ways, turbo codes are being applied to various areas of engineering. Wireless communications is one of the most important applications, where various types of data communications are required and the speed of information and data capacity need to be changed with different rates of parity bit puncturing being adopted to obtain highly efficient transmission. In such applications, adaptation to various turbo-coding specifications on a real-time basis is needed as well as good bit-error-rate performance. We present a new concept for simplifying metric computation and programmable circuit configurations that focuses on the convolutional decoder, which occupies a significant portion of allocated hardware, and we fundamentally treat a simplified log-domain version of the maximum a posteriori (MAP) algorithm, usually know as the Max-Log-MAP (MLM), as a base algorithm. The sliding window method provides an attractive way of computing metric values for the Max-Log-MAP. However, this algorithm does cause degradation, especially when a high rate code is used, generated by bit puncturing. We propose a new means of avoiding this problem and demonstrate that the sliding window, and a modified version as well as other methods, should be flexibly selected to utilize hardware resources depending on turbo specifications. We demonstrated that our proposed methods provide almost the same BER performance as MLM even when a high rate puncturing rate of 5/6 is applied. Finally, we describe the new hardware architecture that we invented to cope with these programmability issues. We show that a turbo-decoding circuit can be implemented in the processor core and its associated unit to configure an LSI macro circuit. The proposed unit has about 60-K gates. We demonstrate that this architecture can be applied to about the 1.5-Mbps information bit throughput of turbo decoding with a 200-MHz clock cycle, which is achievable with today's advanced CMOS technologies.
Yohei ITAYA Heiga ZEN Yoshihiko NANKAKU Chiyomi MIYAJIMA Keiichi TOKUDA Tadashi KITAMURA
This paper investigates the effectiveness of the DAEM (Deterministic Annealing EM) algorithm in acoustic modeling for speaker and speech recognition. Although the EM algorithm has been widely used to approximate the ML estimates, it has the problem of initialization dependence. To relax this problem, the DAEM algorithm has been proposed and confirmed the effectiveness in artificial small tasks. In this paper, we applied the DAEM algorithm to practical speech recognition tasks: speaker recognition based on GMMs and continuous speech recognition based on HMMs. Experimental results show that the DAEM algorithm can improve the recognition performance as compared to the standard EM algorithm with conventional initialization algorithms, especially in the flat start training for continuous speech recognition.
Hideki TODE Makoto WADA Kazuhiko KINOSHITA Toshihiro MASAKI Koso MURAKAMI
A flooding algorithm is an indispensable and fundamental network control mechanism for achieving some tasks, such notifying all nodes of some information, transferring data with high reliability, getting some information from all nodes, or to reserve a route by flooding the messages in the network. In particular, the flooding algorithm is greatly effective in the heterogeneous and dynamic network environment such as so-called ubiquitous networks, whose topology is indefinite or changes dynamically and whose nodal function may be simple and less intelligent. Actually, it is applied to grasp the network topology in a sensor network or an ad-hoc network, or to retrieve content information by mobile agent systems. A flooding algorithm has the advantages of robustness and optimality by parallel processing of messages. However, the flooding mechanism has a fundamental disadvantages: it causes the message congestion in the network, and eventually increases the processing time until the flooding control is finished. In this paper, we propose and evaluate methods for producing a more efficient flooding algorithm by adopting the growth processes of primitive creatures, such as molds or microbes.
Wei-Tsong LEE Kuo-Chi CHU Kun-Chen CHUNG Jen-Yi PAN Pau-Choo CHUNG
The multi-channel Hybrid Fiber Coaxial (HFC) network is essentially a shared medium with multi-channels. Its operation requires the use of a scheduling algorithm to manage the data transmission within each channel. The Data-Over-Cable Service Interface Specification (DOCSIS) protocol is an important standard for HFC networks. Since this protocol does not explicitly specify the scheduling algorithm to be used, many alternative algorithms have been proposed. However, none of these algorithms are applicable to the scheduling of non-Unsolicited Grant Service (UGS) data in multi-channel HFC networks. Accordingly, the present study develops a multi-channel scheduling algorithm which optimizes the scheduling delay time of each transmitted non-UGS request. This algorithm manages the amount of data transmission in each upstream channel according to the overall network load and the bandwidth available in each channel. This study constructs a mathematical model of the algorithm and then uses this model as the basis for a series of simulations in which the performance of the scheduling algorithm is evaluated.
Vicent PLA Jorge MARTINEZ Vicente CASARES-GINER
In this paper we propose a new algorithm for computing the optimal configuration of the Multiple Fractional Guard Channel (MFGC) admission policy in multiservice mobile wireless networks. The optimal configuration maximizes the offered traffic that the system can handle while meeting certain QoS requirements. The proposed algorithm is shown to be more efficient than previous algorithms appeared in the literature.
Junji KAWATA Yuichi TANJI Yoshifumi NISHIO Akio USHIDA
In this paper, we propose a new algorithm for calculating the exact poles of the admittance matrix of RLCG interconnects. After choosing dominant poles and corresponding residues, each element of the exact admittance matrix is approximated by partial fraction. A procedure to obtain the residues that guarantee the passivity is also provided, based on experimental studies. In the procedure the residues are calculated by using the least squares method so that the partial fraction matches each element of the exact admittance matrix in the frequency-domain. From the partial fraction representation, the asymptotic equivalent circuit models which can be easily simulated with SPICE are synthesized. It is shown that an efficient model-order reduction is possible for short-length interconnects.