Kiyotaka KOHNO Mitsuru KAWAMOTO Asoke K. NANDI Yujiro INOUYE
The present letter deals with the blind equalization problem of a single-input single-output infinite impulse response (SISO-IIR) channel with additive Gaussian noise. To solve the problem, we propose a new criterion for maximizing constrainedly a fourth-order cumulant. The algorithms derived from the criterion have such a novel property that even if Gaussian noise is added to the output of the channel, an effective zero-forcing (ZF) equalizer can be obtained with as little influence of Gaussian noise as possible. To show the validity of the proposed criterion, some simulation results are presented.
Katsuhisa YAMANAKA Shin-ichi NAKANO
A naive coding of floorplans needs 2m bits for each floorplan. In this paper we give a new simple coding of floorplans, which needs only 5m/3 bits for each floorplan.
Naoto KOBAYASHI Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
We propose transformation of a parity-check matrix of any low-density parity-check code. A code with transformed parity-check matrix is an equivalent of a code with the original parity-check matrix. For the binary erasure channel, performance of a message-passing algorithm with a transformed parity-check matrix is better than that with the original matrix.
Noboru KUNIHIRO Wataru ABE Kazuo OHTA
Maurer and Yacobi proposed an ID-Based key distribution scheme in 1991. In this scheme, the private key for each user is generated by solving discrete logarithm problem. We examine the realizability of this scheme. We show that this scheme can be practical by appropriate parameter setting.
Kazuo MUROTA Ken'ichiro TANAKA
The concept of M-convex functions has recently been generalized for functions defined on constant-parity jump systems. The b-matching problem and its generalization provide canonical examples of M-convex functions on jump systems. In this paper, we propose a steepest descent algorithm for minimizing an M-convex function on a constant-parity jump system.
Satoshi TAOKA Kazuya WATANABE Toshimasa WATANABE
Let G = (D ∪ S,E) be an undirected graph with a vertex set D ∪ S and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set D and a supply vertex set S. We assume that D ≠
Recently, various decoding algorithms with Low Density Parity Check (LDPC) codes have been proposed. Most algorithms can be divided into a hard decision algorithm and a soft decision algorithm. The Weighted Bit Flipping (WBF) algorithm that is between a hard decision and a soft decision algorithms has been proposed. The Bootstrapped WBF and Modified WBF algorithms have been proposed to improve the error rate performance and decoding complexity of the WBF algorithm. In this letter, we apply the Bootstrap step to the Modified WBF algorithm. We show that the Bootstrapped modified WBF algorithm outperforms the WBF, Bootstrapped WBF, and Modified WBF algorithms. Moreover, we show that the Bootstrapped modified WBF algorithm has the lowest decoding complexity.
Yoshitaka OHTAKI Naoki WAKAMIYA Masayuki MURATA Makoto IMASE
Ants-based routing algorithms have attracted the attention of researchers because they are more robust, reliable, and scalable than other conventional routing algorithms. Since they do not involve extra message exchanges to maintain paths when network topology changes, they are suitable for mobile ad-hoc networks where nodes move dynamically and topology changes frequently. As the number of nodes increases, however, the number of ants (i.e., mobile agents or control messages) also increases, which means that existing algorithms have poor scalability. In this paper, we propose a scalable ant-based routing algorithm that keeps the overhead low while keeping paths short. Our algorithm uses a multistep TTL (Time To Live) scheme, an effective message migration scheme, and an efficient scheme for updating the probability of packet forwarding. Simulation experiments have confirmed that our proposed algorithm can establish shorter paths than the conventional ant-based algorithm with the same signaling overhead.
Shyue-Horng SHIAU Chang-Biau YANG
The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.
Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. Choosing an appropriate representation of candidate solutions to the problem is the essential issue for applying GAs to solve real world network design problems, since the encoding and the interaction of the encoding with the crossover and mutation operators have strongly influence on the success of GAs. In this paper, we investigate a new encoding crossover and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improve predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. The proposed crossover and mutation operators offer locality, heritability, and computational efficiency. We compare with the approach to others that encode candidate spanning trees via the Pr?fer number-based encoding, edge set-based encoding, and demonstrate better results on larger instances for the communication spanning tree design problems.
Temperature-tracking is becoming of paramount importance in modern electronic design automation tools. In this paper, we present a deterministic thermal placement algorithm for standard cell based layout which can lead to a smooth temperature distribution over the die. It is mainly based on Fiduccia-Mattheyses partition scheme and a former substrate thermal model that can convert the known temperature constraints into the corresponding power distribution constraints. Moreover, a kind of force-directed heuristic based on cells' power consumption is introduced in the above process. Experimental results demonstrate a comparatively uniform temperature distribution and show a reduction of the maximal temperature on the die.
Kazunori SHIMIZU Tatsuyuki ISHIKAWA Nozomu TOGAWA Takeshi IKENAGA Satoshi GOTO
In this paper, we propose a partially-parallel LDPC decoder which achieves a high-efficiency message-passing schedule. The proposed LDPC decoder is characterized as follows: (i) The column operations follow the row operations in a pipelined architecture to ensure that the row and column operations are performed concurrently. (ii) The proposed parallel pipelined bit functional unit enables the column operation module to compute every message in each bit node which is updated by the row operations. These column operations can be performed without extending the single iterative decoding delay when the row and column operations are performed concurrently. Therefore, the proposed decoder performs the column operations more frequently in a single iterative decoding, and achieves a high-efficiency message-passing schedule within the limited decoding delay time. Hardware implementation on an FPGA and simulation results show that the proposed partially-parallel LDPC decoder improves the decoding throughput and bit error performance with a small hardware overhead.
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.
Xiuping GUO Genke YANG Zhiming WU Zhonghua HUANG
In this paper, we propose a hybrid fine-tuned multi-objective memetic algorithm hybridizing different solution fitness evaluation methods for global exploitation and exploration. To search across all regions in objective space, the algorithm uses a widely diversified set of weights at each generation, and employs a simulated annealing to optimize each utility function. For broader exploration, a grid-based technique is adopted to discover the missing nondominated regions on existing tradeoff surface, and a Pareto-based local perturbation is performed to reproduce incrementing solutions trying to fill up the discontinuous areas. Additional advanced feature is that the procedure is made dynamic and adaptive to the online optimization conditions based on a function of improvement ratio to obtain better stability and convergence of the algorithm. Effectiveness of our approach is shown by applying it to multi-objective 0/1 knapsack problem (MOKP).
Feng LIU Shaoqian LI Min LIANG Laizhao HU
A new wideband signal DOA estimation algorithm based on modified quantum genetic algorithm (MQGA) is proposed in the presence of the errors and the mutual coupling between array elements. In the algorithm, the narrowband signal subspace fitting method is generalized to wideband signal DOA finding according to the character of space spectrum of wideband signal, and so the rule function is constructed. Then, the solutions is encoded onto chromosomes as a string of binary sequence, the variable quantum rotation angle is defined according to the distribution of optimization solutions. Finally, we use the MQGA algorithm to solve the nonlinear global azimuths optimization problem, and get optimization azimuths by fitness values. The computer simulation results illustrated that the new algorithm have good estimation performance.
Hye-Mi CHOI Ji-Hoon KIM In-Cheol PARK
As turbo decoding is a highly memory-intensive algorithm consuming large power, a major issue to be solved in practical implementation is to reduce power consumption. This paper presents an efficient reverse calculation method to lower the power consumption by reducing the number of memory accesses required in turbo decoding. The reverse calculation method is proposed for the Max-log-MAP algorithm, and it is combined with a scaling technique to achieve a new decoding algorithm, called hybrid log-MAP, that results in a similar BER performance to the log-MAP algorithm. For the W-CDMA standard, experimental results show that 80% of memory accesses are reduced through the proposed reverse calculation method. A hybrid log-MAP turbo decoder based on the proposed reverse calculation reduces power consumption and memory size by 34.4% and 39.2%, respectively.
ChenGuang ZHOU Kui MENG ZuLian QIU
In order to improve the efficiency and speed of match seeking in fractal compression, this paper presents an Average-Variance function which can make the optimal choice more efficiently. Based on it, we also present a fast optimal choice fractal image compression algorithm and an optimal method of constructing data tree which greatly improve the performances of the algorithm. Analysis and experimental results proved that it can improve PSNR over 1 dB and improve the coding speed over 30-40% than ordinary optimal choice algorithms such as algorithm based on center of gravity and algorithm based on variance. It can offer much higher optimal choice efficiency, higher reconstructive quality and rapid speed. It's a fast fractal encoding algorithm with high performances.
This paper presents a personal identification method based on BMME and LDA for images acquired at anterior and posterior occlusion expression of teeth. The method consists of teeth region extraction, BMME, and pattern recognition for the images acquired at the anterior and posterior occlusion state of teeth. Two occlusions can provide consistent teeth appearance in images and BMME can reduce matching error in pattern recognition. Using teeth images can be beneficial in recognition because teeth, rigid objects, cannot be deformed at the moment of image acquisition. In the experiments, the algorithm was successful in teeth recognition for personal identification for 20 people, which encouraged our method to be able to contribute to multi-modal authentication systems.
Pino CABALLERO-GIL Candelaria HERNANDEZ-GOYA
This work addresses the critical problem of authentication in mobile ad hoc networks. It includes a new approach based on the Zero-Knowledge cryptographic paradigm where two different security levels are defined. The first level is characterized by the use of an NP-complete graph problem to describe an Access Control Protocol, while the highest level corresponds to a Group Authentication Protocol based on a hard-on-average graph problem. The main goal of the proposal is to balance security strength and network performance. Therefore, both protocols are scalable and decentralized, and their requirements of communication, storage and computation are limited.
Tetsuji OGAWA Tetsunori KOBAYASHI
A discriminative modeling is applied to optimize the structure of a Partly-Hidden Markov Model (PHMM). PHMM was proposed in our previous work to deal with the complicated temporal changes of acoustic features. It can represent observation dependent behaviors in both observations and state transitions. In the formulation of the previous PHMM, we used a common structure for all models. However, it is expected that the optimal structure which gives the best performance differs from category to category. In this paper, we designed a new structure optimization method in which the dependence of the states and the observations of PHMM are optimally defined according to each model using the weighted likelihood-ratio maximization (WLRM) criterion. The WLRM criterion gives high discriminability between the correct category and the incorrect categories. Therefore it gives model structures with good discriminative performance. We define the model structure combination which satisfy the WLRM criterion for any possible structure combinations as the optimal structures. A genetic algorithm is also applied to the adequate approximation of a full search. With results of continuous lecture talk speech recognition, the effectiveness of the proposed structure optimization is shown: it reduced the word errors compared to HMM and PHMM with a common structure for all models.