Shunta TERUI Katsuhisa YAMANAKA Takashi HIRAYAMA Takashi HORIYAMA Kazuhiro KURITA Takeaki UNO
We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.
In recent years, microwave wireless power transfer (WPT) has attracted considerable attention due to the increasing demand for various sensors and Internet of Things (IoT) applications. Microwave WPT requires technology that can detect and avoid human bodies in the transmission path. Using a phantom is essential for developing such technology in terms of standardization and human body protection from electromagnetic radiation. In this study, a simple and lightweight phantom was developed focusing on its radar cross-section (RCS) to evaluate human body avoidance technology for use in microwave WPT systems. The developed phantom's RCS is comparable to that of the human body.
The expansion of the communication area is expected for Beyond-5G/6G networks using the High Altitude Platform Station (HAPS), Internet of Things (IoT), and sensor devices. Beyond-5G/6G networks constitute the vast amounts of devices that require the latest power utilization system. We expect Microwave Power Transfer (MPT) plays a role in the wireless power supply to HAPS, IoT, and sensors in this network. This work discusses the link design and techniques of MPT for the newest power utilization system required on Beyond-5G/6G networks.
We studied whether a statement similar to the Ghouila-Houri's theorem might hold for alternating orientations of cocomparability graphs. In this paper, we give the negative answer. We prove that it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. Hence, cocomparability graphs with an acyclic alternating orientation form a proper subclass of alternately orientable cocomparability graphs. We also provide a separating example, that is, an alternately orientable cocomparability graph such that no alternating orientation is acyclic.
TaiYu CHENG Yutaka MASUDA Jun NAGAYAMA Yoichi MOMIYAMA Jun CHEN Masanori HASHIMOTO
Reducing power consumption is a crucial factor making industrial designs, such as mobile SoCs, competitive. Voltage scaling (VS) is the classical yet most effective technique that contributes to quadratic power reduction. A recent design technique called activation-aware slack assignment (ASA) enhances the voltage-scaling by allocating the timing margin of critical paths with a stochastic mean-time-to-failure (MTTF) analysis. Meanwhile, such stochastic treatment of timing errors is accepted in limited application domains, such as image processing. This paper proposes a design optimization methodology that achieves a mode-wise voltage-scalable (MWVS) design guaranteeing no timing errors in each mode operation. This work formulates the MWVS design as an optimization problem that minimizes the overall power consumption considering each mode duration, achievable voltage lowering and accompanied circuit overhead explicitly, and explores the solution space with the downhill simplex algorithm that does not require numerical derivation and frequent objective function evaluations. For obtaining a solution, i.e., a design, in the optimization process, we exploit the multi-corner multi-mode design flow in a commercial tool for performing mode-wise ASA with sets of false paths dedicated to individual modes. We applied the proposed design methodology to RISC-V design. Experimental results show that the proposed methodology saves 13% to 20% more power compared to the conventional VS approach and attains 8% to 15% gain from the conventional single-mode ASA. We also found that cycle-by-cycle fine-grained false path identification reduced leakage power by 31% to 42%.
Yiyang JIA Jun MITANI Ryuhei UEHARA
Folding an m×n square grid pattern along the edges of a grid is called map folding. We consider a decision problem in terms of whether a partial overlapping order of the squares aligning on the boundary of an m×n map is valid in a particular fold model called simple fold. This is a variation of the decision problem of valid total orders of the map in a simple fold model. We provide a linear-time algorithm to solve this problem, by defining an equivalence relation and computing the folding sequence sequentially, either uniquely or representatively.
Jung-Hyun KIM Min Kyu SONG Hong-Yeop SONG
In this paper, we investigate how to obtain binary locally repairable codes (LRCs) with good locality and availability from binary Simplex codes. We first propose a Combination code having the generator matrix with all the columns of positive weights less than or equal to a given value. Such a code can be also obtained by puncturing all the columns of weights larger than a given value from a binary Simplex Code. We call by block-puncturing such puncturing method. Furthermore, we suggest a heuristic puncturing method, called subblock-puncturing, that punctures a few more columns of the largest weight from the Combination code. We determine the minimum distance, locality, availability, joint information locality, joint information availability of Combination codes in closed-form. We also demonstrate the optimality of the proposed codes with certain choices of parameters in terms of some well-known bounds.
Li WANG Xiaoan TANG Junda ZHANG Dongdong GUAN
Feature visualization is of great significances in volume visualization, and feature extraction has been becoming extremely popular in feature visualization. While precise definition of features is usually absent which makes the extraction difficult. This paper employs probability density function (PDF) as statistical property, and proposes a statistical property guided approach to extract features for volume data. Basing on feature matching, it combines simple liner iterative cluster (SLIC) with Gaussian mixture model (GMM), and could do extraction without accurate feature definition. Further, GMM is paired with a normality test to reduce time cost and storage requirement. We demonstrate its applicability and superiority by successfully applying it on homogeneous and non-homogeneous features.
Kun JIANG Yuexiang YANG Qinghua ZHENG
The growth in the amount of information available on the Internet and thousands of user queries per second brings huge challenges to the index update and query processing of search engines. Index compression is partially responsible for the current performance achievements of existing search engines. The selection of the index compression algorithms must weigh three factors, i.e., compression ratio, compression speed and decompression speed. In this paper, we study the well-known Simple-9 compression, in which exist many branch operations, table lookup and data transfer operations when processing each 32-bit machine word. To enhance the compression and decompression performance of Simple-9 algorithm, we propose a successive storage structure and processing metric to compress two successive Simple-9 encoded sequence of integers in a single data processing procedure, thus the name Successive Simple-9 (SSimple-9). In essence, the algorithm shortens the process of branch operations, table lookup and data transfer operations when compressing the integer sequence. More precisely, we initially present the data storage format and mask table of SSimple-9 algorithm. Then, for each mode in the mask table, we design and hard-code the main steps of the compression and decompression processes. Finally, analysis and comparison on the experimental results of the simulation and TREC datasets show the compression and decompression efficiency speedup of the proposed SSimple-9 algorithm.
Qiusheng WANG Xiaolan GU Yingyi LIU Haiwen YUAN
Multiple notch filters are used to suppress narrow-band or sinusoidal interferences in digital signals. In this paper, we propose a novel optimization design technique of an infinite impulse response (IIR) multiple notch filter. It is based on the Nelder-Mead simplex method. Firstly, the system function of the desired notch filter is constructed to form the objective function of the optimization technique. Secondly, the design parameters of the desired notch filter are optimized by Nelder-Mead simplex method. A weight function is also introduced to improve amplitude response of the notch filter. Thirdly, the convergence and amplitude response of the proposed technique are compared with other Nelder-Mead based design methods and the cascade-based design method. Finally, the practicability of the proposed notch filter design technique is demonstrated by some practical applications.
Jun SONODA Keimei KAINO Motoyuki SATO
The finite-difference time-domain (FDTD) method has been widely used in recent years to analyze the propagation and scattering of electromagnetic waves. Because the FDTD method has second-order accuracy in space, its numerical dispersion error arises from truncated higher-order terms of the Taylor expansion. This error increases with the propagation distance in cases of large-scale analysis. The numerical dispersion error is expressed by a dispersion relation equation. It is difficult to solve this nonlinear equation which have many parameters. Consequently, a simple formula is necessary to substitute for the dispersion relation error. In this study, we have obtained a simple formula for the numerical dispersion error of 2-D and 3-D FDTD method in free space propagation.
Yuichi SAWAHARA Yuya IKUTA Yangjun ZHANG Toshio ISHIZAKI Ikuo AWAI
The authors propose “Disk-repeater” as a new structure alternative to the conventional resonator repeater. Disk-repeater has a simple structure comprised of just copper plates and wire, non-resonant structure. First, coupling coefficients are measured as functions of disk diameter and wire length to characterize the basic performance of Disk-repeater. It is explained by several experimental evidences that Disk-repeater and resonator are not magnetically coupled but electrically coupled. It is also shown that the transmission distance extends dramatically longer than that of conventional resonator repeater. Further, two-dimensional arrangement, where multiple disks are connected, shows very high efficiency and uniform transmission characteristic regardless of positions of receiving resonator. Disk-repeater gives possibility of unprecedented versatile application with the simple structure.
Hajime UNO Sho ENDO Naofumi HOMMA Yu-ichi HAYASHI Takafumi AOKI
Electromagnetic analysis (EMA) against public-key cryptographic software on an embedded OS is presented in this paper. First, we propose a method for finding an observation point for EMA, where the EM radiation caused by cryptographic operations can be observed with low noise. The basic idea is to find specific EM radiation patterns produced by cryptographic operations given specific input pattern. During the operations, we scan the surface of the target device(s) with a micro magnetic probe. The scan is optimized in advanced using another compatible device that has the same central processing unit (CPU) and OS as the target device. We demonstrate the validity of the proposed EMAs through some EMA experiments with two types of RSA software on an embedded OS platform. The two types of RSA software have different implementations for modular multiplication algorithms: one is a typical and ready-made implementation using BigInteger class on Java standard library, and another is a custom-made implementation based on the Montgomery multiplication algorithm. We conduct experiments of chosen-message EMA using our scanning method, and show such EMAs successfully reveal the secret key of RSA software even under the noisy condition of the embedded OS platform. We also discuss some countermeasures against the above EMAs.
We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.
Hirofumi SANADA Megumi TAKEZAWA Hiroki MATSUZAKI
This paper describes how to design matching structures to improve the frequency characteristics of one-dimensional finite periodic structures. In particular, it deals with one-dimensional finite superlattices. A downhill simplex method is used to determine some of the structural parameters of the matching structure. Numerical examples show that this method is effective in improving the frequency characteristics of finite superlattices.
Kazumitsu SAKAMOTO Ken HIRAGA Tomohiro SEKI Tadao NAKAGAWA Kazuhiro UEHARA
A Simple decoding method for short-range MIMO (SR-MIMO) transmission can reduce the power consumption for MIMO decoding, but the distance between the transceivers requires millimeter-order accuracy in order to satisfy the required transmission quality. In this paper, we propose a phase difference control method between each propagation channel to alleviate the requirements for the transmission distance accuracy. In the proposed method, the phase difference between each propagation channel is controlled by changing the transmission (or received) power ratio of each element of sub-array antennas. In millimeter-wave broadband transmission simulation, we clarified that when sub-array antenna spacing is set to 6.6 mm and element spacing of sub-array antenna is set to 2.48mm, the proposed method can extend the transmission distance range satisfying the required transmission quality, which is that bit error rate (BER) before error correction is less than 10-2 from 9∼29mm to 0∼50mm in QPSK, from 15∼19mm to 0∼30mm in 16QAM, and from only 15mm to 4∼22mm in 64QAM.
Chien-Ning CHEN Sung-Ming YEN SangJae MOON
Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an n-bit NAF recoded scalar is n/3, and an exhaustive search among the 2n/3 candidates is required. This paper shows that in a left-to-right NAF recoded or a left-to-right 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2n/3 to 22n/9 and 20.19n respectively for the cases of NAF and sliding window method.
Young Ik SON Goo-Jong JEONG In Hyuk KIM
Disturbance attenuation for a class of time-delay systems is performed by a combined simple adaptive control (SAC) with a new configuration of disturbance observer (DOB). The nominal system results from the Pade approximation, which is in the form of a non-minimum phase LTI system. For the implementation of SAC and DOB, two parallel feedforward compensators (PFC) are designed with the inverses of PD- and PID-controller, respectively. Simulation results show the effectiveness of the proposed controller to compensate the disturbance response and uncertain delay time.
Mun-Kyu LEE Jeong Eun SONG Dooho CHOI Dong-Guk HAN
The NTRU cryptosystem is a public key system based on lattice problems. While its theoretical security has been well studied, little effort has been made to analyze its security against implementation attacks including power analysis attacks. In this paper, we show that a typical software implementation of NTRU is vulnerable to the simple power analysis and the correlation power analysis including a second-order power attack. We also present novel countermeasures to prevent these attacks, and perform experiments to estimate the performance overheads of our countermeasures. According to our experimental results, the overheads in required memory and execution time are only 8.17% and 9.56%, respectively, over a Tmote Sky equipped with an MSP430 processor.
Tetsuhiro SASAGAWA Shinya WATANABE Osamu HASHIMOTO Toshifumi SAITO Hiroshi KURIHARA
In this paper, first the temperature distribution of the pyramidal EM-wave absorber is calculated in the coupled method. Next, the injected power to the EM-wave absorber is changed to estimate the maximum power density that the EM-wave absorber can resist. As a result, the limitation of the injecting power density to a pyramidal EM-wave absorber is achievable.