Takafumi NAKANO Tadashi WADAYAMA
This paper studies the zero error capacity of the Nearest Neighbor Error (NNE) channels with a multilevel alphabet. In the NNE channels, a transmitted symbol is a d-tuple of elements in {0,1,2,...,l-1}. It is assumed that only one element error to a nearest neighbor element in a transmitted symbol can occur. The NNE channels can be considered as a special type of limited magnitude error channels, and it is closely related to error models for flash memories. In this paper, we derive a lower bound of the zero error capacity of the NNE channels based on a result of the perfect Lee codes. An upper bound of the zero error capacity of the NNE channels is also derived from a feasible solution of a linear programming problem defined based on the confusion graphs of the NNE channels. As a result, a concise formula of the zero error capacity is obtained using the lower and upper bounds.
Zhuo ZHANG Yan LEI Qingping TAN Xiaoguang MAO Ping ZENG Xi CHANG
Fault localization is essential for solving the issue of software faults. Aiming at improving fault localization, this paper proposes a deep learning-based fault localization with contextual information. Specifically, our approach uses deep neural network to construct a suspiciousness evaluation model to evaluate the suspiciousness of a statement being faulty, and then leverages dynamic backward slicing to extract contextual information. The empirical results show that our approach significantly outperforms the state-of-the-art technique Dstar.
Toru FUJITA Koji NAKANO Yasuaki ITO Daisuke TAKAFUJI
The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.
The purpose of this study is to investigate the effects of device size on non-visual icon search using a touch interface with voice output. We conducted an experiment in which twelve participants searched for the target icons with four different-sized touchscreen devices. We analyzed the search time, search strategies and subjective evaluations. As a result, mobile devices with a screen size of 4.7 inches had the shortest search time and obtained the highest subjective evaluation among the four devices.
Minkyu SHIN Seongkyu MUN David K. HAN Hanseok KO
In this paper, a multichannel speech enhancement system which adopts a denoising auto-encoder as part of the beamformer is proposed. The proposed structure of the generalized sidelobe canceller generates enhanced multi-channel signals, instead of merely one channel, to which the following denoising auto-encoder can be applied. Because the beamformer exploits spatial information and compensates for differences in the transfer functions of each channel, the proposed system is expected to resolve the difficulty of modelling relative transfer functions consisting of complex numbers which are hard to model with a denoising auto-encoder. As a result, the modelling capability of the denoising auto-encoder can concentrate on removing the artefacts caused by the beamformer. Unlike conventional beamformers, which combine these artefacts into one channel, they remain separated for each channel in the proposed method. As a result, the denoising auto-encoder can remove the artefacts by referring to other channels. Experimental results prove that the proposed structure is effective for the six-channel data in CHiME, as indicated by improvements in terms of speech enhancement and word error rate in automatic speech recognition.
Tso-Cho CHEN Erl-Huei LU Chia-Jung LI Kuo-Tsang HUANG
In this paper, a weighted multiple bit flipping (WMBF) algorithman for decoding low-density parity-check (LDPC) codes is proposed first. Then the improved WMBF algorithm which we call the efficient weighted bit-flipping (EWBF) algorithm is developed. The EWBF algorithm can dynamically choose either multiple bit-flipping or single bit-flipping in each iteration according to the log-likelihood ratio of the error probability of the received bits. Thus, it can efficiently increase the convergence speed of decoding and prevent the decoding process from falling into loop traps. Compared with the parallel weighted bit-flipping (PWBF) algorithm, the EWBF algorithm can achieve significantly lower computational complexity without performance degradation when the Euclidean geometry (EG)-LDPC codes are decoded. Furthermore, the flipping criterion does not require any parameter adjustment.
Tadahiro FURUKAWA Mitsuhiro KODEN
Novel roll-to-roll (R2R) deposition and patterning of ITO on ultra-thin glass were developed with no photolithography and applied to flexible organic light emitting diodes (OLEDs). The developed deposition consists of low temperature sputtering and annealing. The developed patterning utilizes an etching paste printed by novel R2R screen printing.
Chenxi LI Lei CAO Xiaoming LIU Xiliang CHEN Zhixiong XU Yongliang ZHANG
As an important method to solve sequential decision-making problems, reinforcement learning learns the policy of tasks through the interaction with environment. But it has difficulties scaling to large-scale problems. One of the reasons is the exploration and exploitation dilemma which may lead to inefficient learning. We present an approach that addresses this shortcoming by introducing qualitative knowledge into reinforcement learning using cloud control systems to represent ‘if-then’ rules. We use it as the heuristics exploration strategy to guide the action selection in deep reinforcement learning. Empirical evaluation results show that our approach can make significant improvement in the learning process.
Akitoshi ITAI Arao FUNASE Andrzej CICHOCKI Hiroshi YASUKAWA
This paper describes the background noise estimation technique of the tensor product expansion with absolute error (TPE-AE) to estimate multiple sources. The electroencephalogram (EEG) signal produced by the saccadic eye movement is adopted to analyze relationship between a brain function and a human activity. The electrooculogram (EOG) generated by eye movements yields significant problems for the EEG analysis. The denoising of EOG artifacts is important task to perform an accurate analysis. In this paper, the two types of TPE-AE are proposed to estimates EOG and other components in EEG during eye movement. One technique estimates two outer products using median filter based TPE-AE. The another technique uses a reference signal to separate the two sources. We show that the proposed method is effective to estimate and separate two sources in EEG.
Toshihiko WAKAHARA Toshitaka MAKI Noriyasu YAMAMOTO Akihisa KODATE Manabu OKAMOTO Hiroyuki NISHI
The Life Intelligence and Office Information System (LOIS) Technical Committee of the Institute of Electronics, Information and Communication Engineers (IEICE) dates its origin to May 1986. This Technical Committee (TC) has covered the research fields of the office related systems for more than 30 years. Over this time, this TC, under its multiple name changes, has served as a forum for research and provided many opportunities for not only office users but also ordinary users of systems and services to present ideas and discussions. Therefore, these advanced technologies have been diffused from big enterprises to small companies and home users responsible for their management and operation. This paper sums up the technology trends and views of the office related systems and services covered in the 30 years of presentations of the LOIS Technical Committees by using the new literature analysis system based on the IEICE Knowledge Discovery system (I-Scover system).
Batbayar KHANDISH Hyun PARK Jung-Bong SUK
The IEEE 802.15.4 standard enables a short range, low data rate and low power communication between devices in wireless sensor networks (WSNs). In IEEE 802.15.4, a slotted carrier sensing multiple access with collision avoidance (CSMA/CA) algorithm is employed to coordinate a large number of sensor devices. Unlike IEEE 802.11 wireless LAN (WLAN), energy consumption requirements enable it to use fewer number of backoffs, which adversely increase collisions, resulting in degradation of energy consumption. In this letter, we devise an adaptive backoff scheme in WSN whose backoff range is adjusted depending on the contention level, and present its Markov model for mathematical analysis. The proposed scheme is analyzed and its efficiency is validated by ns-2 simulation in respect to network throughput and energy consumption. Its performance is also compared with the standard and previous works, showing that it outperforms them for a whole range of arrival rate.
Toshihiro YAMAUCHI Yuta IKEGAMI Yuya BAN
Recently, there has been an increase in use-after-free (UAF) vulnerabilities, which are exploited using a dangling pointer that refers to a freed memory. In particular, large-scale programs such as browsers often include many dangling pointers, and UAF vulnerabilities are frequently exploited by drive-by download attacks. Various methods to prevent UAF attacks have been proposed. However, only a few methods can effectively prevent UAF attacks during runtime with low overhead. In this paper, we propose HeapRevolver, which is a novel UAF attack-prevention method that delays and randomizes the timing of release of freed memory area by using a memory-reuse-prohibited library, which prohibits a freed memory area from being reused for a certain period. The first condition for reuse is that the total size of the freed memory area is beyond the designated size. The threshold for the conditions of reuse of the freed memory area can be randomized by HeapRevolver. Furthermore, we add a second condition for reuse in which the freed memory area is merged with an adjacent freed memory area before release. Furthermore, HeapRevolver can be applied without modifying the target programs. In this paper, we describe the design and implementation of HeapRevolver in Linux and Windows, and report its evaluation results. The results show that HeapRevolver can prevent attacks that exploit existing UAF vulnerabilities. In addition, the overhead is small.
Junlin TANG Kaida XU Yuan ZENG Guangrong YUE Shaoqian LI
Beamforming technology is an effective method to build a robust link. The commonly used digital beamforming is an expensive and power consuming approach to realizing millimeter-wave transmission. This makes radio frequency(RF) beamforming, which has low cost and low power consumption due to its use of phase shifters the more feasible approach to creating stable links in the millimeter-wave band. Unfortunately, the performance of RF processing is degraded by the limited precision of digital phase shifters. In this paper, we analyze the gain loss caused by the limited precision of phase shifter in millimeter wave single stream beam steering. We deduce a theoretical relationship between the array gain loss and variance of phase error. The theoretical results are validated by the Monte Carlo simulations, which indicate that gain loss could be reduced by the increased precision of phase shifter. In practical applications, 4-bit phase shifters provide sufficient accuracy for single stream beam steering.
Takafumi HAYASHI Yodai WATANABE Takao MAEDA Shinya MATSUFUJI
The present paper introduces a novel construction of structured ternary sequences having a zero-correlation zone (ZCZ) for both periodic and aperiodic correlation functions. The cross-correlation function and the side lobe of the auto-correlation function of the proposed sequence set are zero for phase shifts within the ZCZ. The proposed ZCZ sequence set can be generated from an arbitrary Hadamard matrix of order n. The sequence set of order 0 is identical to the r-th row of the Hadamard matrix. For m≥0, the sequence set of order (m+1) is constructed from the sequence set of order m by sequence concatenation and interleaving. The sequence set of order m has 2m subsets of size n. The length of the sequence is equal to n4m+2m+1(2m-1); The phase shift of the ZCZ for the whole sequence set is from -(2m-1) to (2m-1). The sequence set of order 0 is coincident with the rows of the given Hadamard sequence with no ZCZ. The subsets can be associated with a perfect binary tree of height m with 2m leaves. The r-th sequence subset consists of from the nr-th sequence to the ((n+1)r-1)-th sequence. The r-th subset is assigned to the r-th leaf of the perfect binary tree. For a longer distance between the corresponding leaves to the r-th and s-th sequences, the ZCZ of the r-th and s-th sequences is wider. This tree-structured width of ZCZ of a pair of the proposed sequences enables flexible design in applications of the proposed sequence set. The proposed sequence is suitable for a heterogeneous wireless network, which is one of the candidates for the fifth generation of radio access networks.
Qiong WANG Mohamed EL-HADEDY Kevin SKADRON Ke WANG
Motif searching, i.e., identifying meaningful patterns from biological data, has been studied extensively due to its importance in the biomedical sciences. In this work, we seek to improve the performance of Weeder, a widely-used tool for automatic de novo motif searching. Weeder consists of several functions, among which we find that the function oligo_scan, which handles the pattern matching, is the bottleneck, especially when dealing with large datasets. Motivated by this observation, we adopt the Micron Automata Processor (AP) to accelerate the pattern-matching stage of Weeder. The AP is a massively-parallel, non-von-Neumann semiconductor architecture that is purpose-built for symbolic pattern matching. Relying on the fact that AP is capable of performing matching for thousands of patterns in parallel, we develop an AP-accelerated Weeder implementation in this work. In particular, we describe how to map Weeder's pattern matching to the AP chip and use the high-end FPGA on the AP board to postprocess the output from AP. Our experiment shows that the AP-accelerated Weeder achieves 751x speedup on pattern matching, compared to a single-threaded CPU implementation.
Yuki YAMAGISHI Kazuo AOYAMA Kazumi SAITO Tetsuo IKEDA
This paper presents an efficient similarity search method utilizing as an index a complete binary tree (CBT) based on optimized pivots for a large-scale and high-dimensional data set. A similarity search method, in general, requires high-speed performance on both index construction off-line and similarity search itself online. To fulfill the requirement, we introduce novel techniques into an index construction and a similarity search algorithm in the proposed method for a range query. The index construction algorithm recursively employs the following two main functions, resulting in a CBT index. One is a pivot generation function that obtains one effective pivot at each node by efficiently maximizing a defined objective function. The other is a node bisection function that partitions a set of objects at a node into two almost equal-sized subsets based on the optimized pivot. The similarity search algorithm employs a three-stage process that narrows down candidate objects within a given range by pruning unnecessary branches and filtering objects in each stage. Experimental results on one million real image data set with high dimensionality demonstrate that the proposed method finds an exact solution for a range query at around one-quarter to half of the computational cost of one of the state-of-the-art methods, by using a CBT index constructed off-line at a reasonable computational cost.
Jou-Ming CHANG Hung-Yi CHANG Hung-Lung WANG Kung-Jui PAI Jinn-Shyong YANG
Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.
Haruki MIYAGAWA Junya SEKIKAWA
Arc runners are fixed on silver electrical contacts. Break arcs are generated between the contacts in a 450VDC circuit. Break arcs are magnetically blown-out and air is blown to the break arcs. The air flow was not used to our previous reports with runners. Circuit current when contacts are closed is 10A. Flow rate of air Q is changed from 1 to 10L/min. Supply voltage E is changed from 200V to 450V. The following results are shown. Arc duration D tends to decrease with increasing flow rate Q. The number of reignitions N increases with increasing supply voltage E for each flow rate Q. The number of reignitions is the least when the flow rate Q is 2L/min.
Break arcs are rotated with a radial magnetic field formed by a permanent magnet embedded in a fixed contact. The break arcs are generated in a 48VDC resistive circuit. The circuit current is 10A when the contacts are closed. The polarity of the fixed contact in which the magnet is embedded is changed. The rotational radius and the difference of position between the cathode and anode spots are investigated. The following results are obtained. The cathode spot is moved more easily than the anode spot by the radial magnetic field. The rotational radius of the break arcs is affected by the Lorentz force that is caused by the circumferential component of the arc current and the axial component of the magnetic field. The circumferential component of the arc current is caused by the difference of the positions of the rotating cathode and anode spots.
Eiji OKI Naoya WADA Satoru OKAMOTO Naoaki YAMANAKA Ken-ichi SATO
This paper presents past and recent trends of optical networks and addresses the future directions. First, we describe path networks with the historical backgrounds and trends. path networks have advanced by using various multiplexing technologies. They include time-division multiplexing (TDM), asynchronous transfer mode (ATM), and wavelength-division multiplexing (WDM). ATM was later succeeded to multi-protocol label switching (MPLS). Second, we present generalized MPLS technologies (GMPLS). In GMPLS, the label concept of MPLS is extended to other labels used in TDM, WDM, and fiber networks. GMPLS enables network operators to serve networks deployed by different technologies with a common protocol suite of GMPLS. Third, we describe multi-layer traffic engineering and a path computation element (PCE). Multi-layer traffic engineering designs and controls networks considering resource usages of more than one layer. This leads to use network resources more efficiently than the single-layer traffic engineering adopted independently for each layer. PCE is defined as a network element that computes paths, which are used for traffic engineering. Then, we address software-defined networks, which put the designed network functions into the programmable data plane by way of the management plane. We describe the evaluation from GMPLS to software defined networking (SDN) and transport SDN. Fifth, we describe the advanced devices and switches for optical networks. Finally, we address advances in networking technologies and future directions on optical networking.