We designed multilayer wavelength-selective reflector films by stacking thin-films of transparent polymer. The optimum structure of the multilayer is determined using a combination of characteristic matrix method and a version of genetic algorithm. Such multilayer films can be used in LCD devices to enhance the color saturation of the display.
Warin WATTANAPORNPROM Prabhas CHONGSTITVATANA
This article introduces the Coincidence Algorithm (COIN) to solve several multimodal puzzles. COIN is an algorithm in the category of Estimation of Distribution Algorithms (EDAs) that makes use of probabilistic models to generate solutions. The model of COIN is a joint probability table of adjacent events (coincidence) derived from the population of candidate solutions. A unique characteristic of COIN is the ability to learn from a negative sample. Various experiments show that learning from a negative example helps to prevent premature convergence, promotes diversity and preserves good building blocks.
Natsuki AIZAWA Shogo MURAMATSU Masahiro YUKAWA
A directional lapped orthogonal transform (DirLOT) is an orthonormal transform of which basis is allowed to be anisotropic with the symmetric, real-valued and compact-support property. Due to its directional property, DirLOT is superior to the existing separable transforms such as DCT and DWT in expressing diagonal edges and textures. The goal of this paper is to enhance the ability of DirLOT further. To achieve this goal, we propose a novel image restoration technique using multiple DirLOTs. This paper generalizes an image denoising technique in [1], and expands the application of multiple DirLOTs by introducing linear degradation operator P. The idea is to use multiple DirLOTs to construct a redundant dictionary. More precisely, the redundant dictionary is constructed as a union of symmetric orthonormal discrete wavelet transforms generated by DirLOTs. To select atoms fitting a target image from the dictionary, we formulate an image restoration problem as an l1-regularized least square problem, which can efficiently be solved by the iterative-shrinkage/thresholding algorithm (ISTA). The proposed technique is beneficial in expressing multiple directions of edges/textures. Simulation results show that the proposed technique significantly outperforms the non-subsampled Haar wavelet transform for deblurring, super-resolution, and inpainting.
Kazi OBAIDULLAH Constantin SIRITEANU Shingo YOSHIZAWA Yoshikazu MIYANAGA
Genetic algorithm (GA) is now an important tool in the field of wireless communications. For multiple-input/multiple-output (MIMO) wireless communications system employing spatial multiplexing transmission, we evaluate the effects of GA parameters value on channel parameters in fading channels. We assume transmit-correlated Rayleigh and Rician fading with realistic Laplacian power azimuth spectrum. Azimuth spread (AS) and Rician K-factor are selected according to the measurement-based WINNER II channel model for several scenarios. Herein we have shown the effects of GA parameters and channel parameters in different WINNER II scenarios (i.e., AS and K values) and rank of the deterministic components. We employ meta GA that suitably selects the population (P), generation (G) and mutation probability (pm) for the inner GA. Then we show the cumulative distribution function (CDF) obtain experimentally for the condition number C of the channel matrix H. It is found that, GA parameters depend on the channel parameters, i.e., GA parameters are the functions of the channel parameters. It is also found that for the poorer channel conditions smaller GA parameter values are required for MIMO detection. This approach will help to achieve maximum performance in practical condition for the lower numerical complexity.
Many applications of wireless sensor networks (WSNs) require secure communication. The tree-based key management scheme, which is a symmetric key scheme, provides backward and forward secrecy. The sensor nodes in the communication group share a secret key for encrypting messages. When the sensor nodes are added to or evicted from the group, the group key has to be updated by sending rekeying messages. In this paper, we propose a method of key tree structure (KTS) generation by considering the addition and eviction ratio of sensor nodes to reduce the number of rekeying messages, which is influenced by the structure of the tree. For this, we define an extension of an existing tree structure such as a binary or ternary tree and generate KTS using an A* algorithm. To reduce the energy consumed by the message transmission, we also exploit genetic algorithm (GA) to build a secure communication group by considering the KTS. In the paper, we show the effectiveness of the proposed method compared with the existing structure via the simulation in terms of memory usage, the number of rekeying messages and energy consumption.
Gaosheng LI Peiguo LIU Yan LI Zhonghao LU Dongming ZHOU Yujian QIN
Regular on-site testing is an elementary means to obtain real-time data and state of Electromagnetic Compatibility (EMC) of electronics systems. Nowadays, there is a lot of measured EMC data while the application of the data is insufficient. So we put forward the concept of EMC model synthesis. To carry out EMC data mining with measured electromagnetic data, we can build or modify models and synthesize variation rules of electromagnetic parameters of equipment and EMC performance of systems and platforms, then realize the information synthesis and state prediction. The concept of EMC reliability is brought forward together with the definition and description of parameters such as invalidation rate and EMC lifetime. We studied the application of statistical algorithms and Artificial Neural Network (ANN) in model synthesis. Operating flows and simulation results as well as measured data are presented. Relative research can support special measurement, active management and predictive maintenance and replenishment in the area of EMC.
Ryota KOUZUKI Toshimichi SAITO
This paper studies the simple dynamic binary neural network characterized by the signum activation function, ternary weighting parameters and integer threshold parameters. The network can be regarded as a digital version of the recurrent neural network and can output a variety of binary periodic orbits. The network dynamics can be simplified into a return map, from a set of lattice points, to itself. In order to store a desired periodic orbit, we present two learning algorithms based on the correlation learning and the genetic algorithm. The algorithms are applied to three examples: a periodic orbit corresponding to the switching signal of the dc-ac inverter and artificial periodic orbit. Using the return map, we have investigated the storage of the periodic orbits and stability of the stored periodic orbits.
WonHee LEE Samuel Sangkon LEE Dong-Un AN
Clustering methods are divided into hierarchical clustering, partitioning clustering, and more. K-Means is a method of partitioning clustering. We improve the performance of a K-Means, selecting the initial centers of a cluster through a calculation rather than using random selecting. This method maximizes the distance among the initial centers of clusters. Subsequently, the centers are distributed evenly and the results are more accurate than for initial cluster centers selected at random. This is time-consuming, but it can reduce the total clustering time by minimizing allocation and recalculation. Compared with the standard algorithm, F-Measure is more accurate by 5.1%.
Discrete structures are foundational material for computer science and mathematics, which are related to set theory, symbolic logic, inductive proof, graph theory, combinatorics, probability theory, etc. Many problems solved by computers can be decomposed into discrete structures using simple primitive algebraic operations. It is very important to represent discrete structures compactly and to execute efficiently tasks such as equivalency/validity checking, analysis of models, and optimization. Recently, BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale combinational logic data, which are the basic discrete structures in various fields of application. Although a quarter of a century has passed since Bryant's first idea, there are still a lot of interesting and exciting research topics related to BDD and ZDD. BDD/ZDD is based on in-memory data processing techniques, and it enjoys the advantage of using random access memory. Recent commodity PCs are equipped with gigabytes of main memory, and we can now solve large-scale problems which used to be impossible due to memory shortage. Thus, especially since 2000, the scope of BDD/ZDD methods has increased. This survey paper describes the history of, and recent research activity pertaining to, techniques related to BDD and ZDD.
Jinyi ZHOU Shutao XIA Yong JIANG Haitao ZHENG Laizhong CUI
In a multihop wireless network, wireless interference is a crucial factor in the maximum multiflow (MMF) problem, which studies the maximum throughput between multiple pairs of sources and sinks with a link schedule to support it. In this paper, we observe that network coding could help to decrease the impact of wireless interference, and thus propose a framework to study the MMF problem for multihop wireless networks with network coding. Firstly, a network model is established to describe the new conflict relations and schedulability modified by network coding. Next, we formulate the MMF problem to compute the maximum throughput of multiple unicast flows supported by the multihop wireless network with network coding, and show that its capacity region could be enlarged by performing network coding. Finally, we show that determining the capacity region of a multihop wireless network with network coding is an NP-hard problem, and thus propose a greedy heuristic algorithm, called coding-first collecting (CFC), to determine a capacity subregion of the network. We also show that finding an optimal hyperarc schedule to meet a given link demand function is NP-hard, and propose a polynomial algorithm, called coding-first scheduling (CFS), to find an approximate fractional hyperarc schedule in the multihop wireless network with network coding. A numerical analysis of a grid wireless network and a random wireless network is presented to demonstrate the efficiencies of the CFC algorithm and the CFS algorithm based on the framework.
Jiachen HUANG Changyong PAN Kewu PENG Liwen FAN Jian SONG
Amplitude phase shift keying (APSK) constellation with Gray mapping was proposed recently. Inspired by the simplified soft demapping for regular Gray-QAM, a simplified soft demapping algorithm for Gray-APSK is proposed in this paper. Compared with conventional soft demapping schemes, its complexity is greatly reduced with only a little SNR loss, which is validated by the complexity analysis and FPGA compilation results.
Qian ZHAO Yukikazu NAKAMOTO Shimpei YAMADA Koutaro YAMAMURA Makoto IWATA Masayoshi KAI
Wireless sensor nodes are becoming more and more common in various settings and require a long battery life for better maintainability. Since most sensor nodes are powered by batteries, energy efficiency is a critical problem. In an experiment, we observed that when peak power consumption is high, battery voltage drops quickly, and the sensor stops working even though some useful charge remains in the battery. We propose three off-line algorithms that extend battery life by scheduling sensors' execution time that is able to reduce peak power consumption as much as possible under a deadline constraint. We also developed a simulator to evaluate the effectiveness of these algorithms. The simulation results showed that one of the three algorithms dramatically can extend battery life approximately three time as long as in simultaneous sensor activation.
Given a binary image I and a threshold t, the size-thresholded binary image I(t) defined by I and t is the binary image after removing all connected components consisting of at most t pixels. This paper presents space-efficient algorithms for computing a size-thresholded binary image for a binary image of n pixels, assuming that the image is stored in a read-only array with random-access. With regard to the problem, there are two cases depending on how large the threshold t is, namely, Relatively large threshold where t = Ω(), and Relatively small threshold where t = O(). In this paper, a new algorithmic framework for the problem is presented. From an algorithmic point of view, the problem can be solved in O() time and O() work space. We propose new algorithms for both the above cases which compute the size-threshold binary image for any binary image of n pixels in O(nlog n) time using only O() work space.
Chao DONG Li GAO Ying HONG Chengpeng HAO
Dichotomous coordinate descent (DCD) iterations method has been proposed for adaptive feedback cancellation, which uses a fixed number of iterations and a fixed amplitude range. In this paper, improved DCD algorithms are proposed, which substitute the constant number of iterations and the amplitude range with a variable number of iterations(VI) and/or a variable amplitude range(VA). Thus VI-DCD, VA-DCD and VIA-DCD algorithms are obtained. Computer simulations are used to compare the performance of the proposed algorithms against original DCD algorithm, and simulation results demonstrate that significant improvements are achieved in the convergence speed and accuracy. Another notable conclusion by further simulations is that the proposed algorithms achieve superior performance with a real speech segment as the input.
Shin-ichi NAKANO Katsuhisa YAMANAKA
A rectangular drawing is a plane drawing of a graph in which every face is a rectangle. Rectangular drawings have an application for floorplans, which may have a huge number of faces, so compact code to store the drawings is desired. The most compact code for rectangular drawings needs at most 4f-4 bits, where f is the number of inner faces of the drawing. The code stores only the graph structure of rectangular drawings, so the length of each edge is not encoded. A grid rectangular drawing is a rectangular drawing in which each vertex has integer coordinates. To store grid rectangular drawings, we need to store some information for lengths or coordinates. One can store a grid rectangular drawing by the code for rectangular drawings and the width and height of each inner face. Such a code needs 4f-4 + f⌈log W⌉ + f⌈log H⌉ + o(f) + o(W) + o(H) bits*, where W and H are the maximum width and the maximum height of inner faces, respectively. In this paper we design a simple and compact code for grid rectangular drawings. The code needs 4f-4 + (f+1)⌈log L⌉ + o(f) + o(L) bits for each grid rectangular drawing, where L is the maximum length of edges in the drawing. Note that L ≤ max{W,H} holds. Our encoding and decoding algorithms run in O(f) time.
This paper presents an efficient algorithm for reporting all intersections among n given segments in the plane using work space of arbitrarily given size. More exactly, given a parameter s which is between Ω(1) and O(n) specifying the size of work space, the algorithm reports all the segment intersections in roughly O(n2/+ K) time using O(s) words of O(log n) bits, where K is the total number of intersecting pairs. The time complexity can be improved to O((n2/s) log s + K) when input segments have only some number of different slopes.
Hirotoshi HONMA Yoko NAKAJIMA Haruka AOSHIMA Shigeru MASUYAMA
Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/log n) processors on EREW PRAM computation model.
Satoshi TAOKA Daisuke TAKAFUJI Toshimasa WATANABE
A vertex cover of a given graph G = (V,E) is a subset N of V such that N contains either u or v for any edge (u,v) of E. The minimum weight vertex cover problem (MWVC for short) is the problem of finding a vertex cover N of any given graph G = (V,E), with weight w(v) for each vertex v of V, such that the sum w(N) of w(v) over all v of N is minimum. In this paper, we consider MWVC with w(v) of any v of V being a positive integer. We propose simple procedures as postprocessing of algorithms for MWVC. Furthremore, five existing approximation algorithms with/without the proposed procedures incorporated are implemented, and they are evaluated through computing experiment.
Ro-Yu WU Jou-Ming CHANG An-Hang CHEN Ming-Tat KO
A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where .
Masaki KAWABATA Takao NISHIZEKI
Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive number, called the supply or demand. Each demand vertex v must be supplied an amount of “power,” equal to the demand of v, from exactly one supply vertex through edges in T. Each edge is assigned a positive number called the capacity. One wishes to partition T into subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and the power flow through each edge is no more than capacity of the edge. The “partition problem” is a decision problem to ask whether T has such a partition. The “maximum partition problem” is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.