Hiroaki UCHIDA Toshimichi SAITO
This paper studies synchronization phenomena in a ring-coupled system of digital spiking neurons. The neuron consists of two shift registers connected by a wiring circuit and can generate various spike-trains. Applying a spike based connection, the ring-coupled system is constructed. The ring-coupled system can generate multi-phase synchronization phenomena of various periodic spike-trains. Using a simple dynamic model, existence and stability of the synchronization phenomena are analyzed. Presenting a FPGA based test circuit, typical synchronization phenomena are confirmed experimentally.
We studied complicated superstable periodic orbits (SSPOs) in a spiking neuron model with a rectangular threshold signal. The neuron exhibited SSPOs with various periods that changed dramatically when we varied the parameter space. Using a one-dimensional return map defined by the spike phase, we evaluated period changes and showed its complicated distribution. Finally, we constructed a test circuit to confirm the typical phenomena displayed by the mathematical model.
Qiuli CHEN Ming HE Fei DAI Chaozheng ZHU
The changes of temperature, salinity and ocean current in underwater environment, have adverse effects on the communication range of sensors, and make them become temporary failure. These temporarily misbehaving sensors are called dumb nodes. In this paper, an energy-efficient connectivity re-establishment (EECR) scheme is proposed. It can reconstruct the topology of underwater acoustic sensor networks (UASNs) with the existing of dumb nodes. Due to the dynamic of underwater environment, the generation and recovery of dumb nodes also change dynamically, resulting in intermittent interruption of network topology. Therefore, a multi-band transmission mode for dumb nodes is designed firstly. It ensures that the current stored data of dumb nodes can be sent out in time. Subsequently, a connectivity re-establishment scheme of sub-nodes is designed. The topology reconstruction is adaptively implemented by changing the current transmission path. This scheme does't need to arrange the sleep nodes in advance. So it can reduce the message expenses and energy consumption greatly. Simulation results show that the proposed method has better network performance under the same conditions than the classical algorithms named LETC and A1. What's more, our method has a higher network throughput rate when the nodes' dumb behavior has a shorter duration.
Rei HASEGAWA Keita KATAGIRI Koya SATO Takeo FUJII
Spectrum databases are required to assist the process of radio propagation estimation for spectrum sharing. Especially, a measurement-based spectrum database achieves highly efficient spectrum sharing by storing the observed radio environment information such as the signal power transmitted from a primary user. However, when the average received signal power is calculated in a given square mesh, the bias of the observation locations within the mesh strongly degrades the accuracy of the statistics because of the influence of terrain and buildings. This paper proposes a method for determining the statistics by using mesh clustering. The proposed method clusters the feature vectors of the measured data by using the k-means and Gaussian mixture model methods. Simulation results show that the proposed method can decrease the error between the measured value and the statistically processed value even if only a small amount of data is available in the spectrum database.
Xing CHEN Tianshuang QIU Cheng LIU Jitong MA
This paper mainly discusses the time-difference-of-arrival (TDOA) estimation problem of digital modulation signal under impulsive noise and cochannel interference environment. Since the conventional TDOA estimation algorithms based on the second-order cyclic statistics degenerate severely in impulsive noise and the TDOA estimation algorithms based on correntropy are out of work in cochannel interference, a novel signal-selective algorithm based on the generalized cyclic correntropy is proposed, which can suppress both impulsive noise and cochannel interference. Theoretical derivation and simulation results demonstrate the effectiveness and robustness of the proposed algorithm.
Hidefumi HIRAISHI Hiroshi IMAI Yoichi IWATA Bingkai LIN
Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
Minsu KIM Kunwoo LEE Katsuhiko GONDOW Jun-ichi IMURA
The main purpose of Codemark is to distribute digital contents using offline media. Due to the main purpose of Codemark, Codemark cannot be used on digital images. It has high robustness on only printed images. This paper presents a new color code called Robust Index Code (RIC for short), which has high robustness on JPEG Compression and Resize targeting digital images. RIC embeds a remote database index to digital images so that users can reach to any digital contents. Experimental results, using our implemented RIC encoder and decoder, have shown high robustness on JPEG Comp. and Resize of the proposed codemark. The embedded database indexes can be extracted 100% on compressed images to 30%. In conclusion, it is able to store all the type of digital products by embedding indexes into digital images to access database, which means it makes a Superdistribution system with digital images realized. Therefore RIC has the potential for new Internet image services, since all the images encoded by RIC are possible to access original products anywhere.
Yi LIU Qingkun MENG Xingtong LIU Jian WANG Lei ZHANG Chaojing TANG
Electronic payment protocols provide secure service for electronic commerce transactions and protect private information from malicious entities in a network. Formal methods have been introduced to verify the security of electronic payment protocols; however, these methods concentrate on the accountability and fairness of the protocols, without considering the impact caused by timeliness. To make up for this deficiency, we present a formal method to analyze the security properties of electronic payment protocols, namely, accountability, fairness and timeliness. We add a concise time expression to an existing logical reasoning method to represent the event time and extend the time characteristics of the logical inference rules. Then, the Netbill protocol is analyzed with our formal method, and we find that the fairness of the protocol is not satisfied due to the timeliness problem. The results illustrate that our formal method can analyze the key properties of electronic payment protocols. Furthermore, it can be used to verify the time properties of other security protocols.
Hidefumi HIRAISHI Sonoko MORIYAMA
We investigate excluded minor characterizations of two fundamental classes of matroids: orientable matroids and representable matroids. We prove (i) for any fixed field F, there exist infinitely many excluded minors of rank 3 for the union of the class of orientable matroids and the class of F-representable matroids, and (ii) for any fixed field F with characteristic 0, there exist infinitely many orientable excluded minors of rank 3 for intersection of the class of orientable matroids and the class of F-representable matroids. We show these statements by explicitly constructing infinite families of excluded minors.
Satsuya OHATA Takahiro MATSUDA Goichiro HANAOKA Kanta MATSUURA
The concept of threshold public key encryption (TPKE) with the special property called key re-splittability (re-splittable TPKE, for short) was introduced by Hanaoka et al. (CT-RSA 2012), and used as one of the building blocks for constructing their proxy re-encryption scheme. In a re-splittable TPKE scheme, a secret key can be split into a set of secret key shares not only once, but also multiple times, and the security of the TPKE scheme is guaranteed as long as the number of corrupted secret key shares under the same splitting is smaller than the threshold. In this paper, we show several new constructions of a re-splittable TPKE scheme by extending the previous (ordinary) TPKE schemes. All of our proposed schemes are based on discrete logarithm (DL)-type assumptions. Therefore, our results suggest that key re-splittability is a very natural property for DL-type TPKE schemes.
Hiroaki SUTO Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI
The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2kn2)-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.
Nobukazu TSUKIJI Yasunori KOBORI Haruo KOBAYASHI
We propose a method to derive the loop gain from the open-loop and closed-loop output impedances in a dc-dc buck converter with voltage mode and current mode controls. This enables the loop gain to be measured without injecting a signal into the feedback loop, i.e. without breaking the feedback loop; hence the proposed method can be applied to the control circuits implemented on an IC. Our simulation and experiment show that the loop gain determined by the proposed method closely matches that yielded by the conventional method, which has to break the feedback loop. These results confirm that the proposed method can accurately estimate the phase margin.
Fara ASHIKIN Masaki HASHIZUME Hiroyuki YOTSUYANAGI Shyue-Kung LU Zvi ROTH
A design-for-testability method and an electrical interconnect test method are proposed to detect open defects occurring at interconnects among dies and input/output pins in 3D stacked ICs. As part of the design method, an nMOS and a diode are added to each input interconnect. The test method is based on measuring the quiescent current that is made to flow through an interconnect to be tested. The testability is examined both by SPICE simulation and by experimentation. The test method enabled the detection of open defects occurring at the newly designed interconnects of dies at experiments test speed of 1MHz. The simulation results reveal that an open defect generating additional delay of 279psec is detectable by the test method at a test speed of 200MHz beside of open defects that generate no logical errors.
Zhijian HUANG Yong Jun WANG Jing LIU
The rising systems programming language Rust is fast, efficient and memory safe. However, improperly dereferencing raw pointers in Rust causes new safety problems. In this paper, we present a detailed analysis into these problems and propose a practical hybrid approach to detecting unsafe raw pointer dereferencing behaviors. Our approach employs pattern matching to identify functions that can be used to generate illegal multiple mutable references (We define them as thief function) and instruments the dereferencing operation in order to perform dynamic checking at runtime. We implement a tool named UnsafeFencer and has successfully identified 52 thief functions in 28 real-world crates*, of which 13 public functions are verified to generate multiple mutable references.
Hidetaka ITO Hiroomi HIKAWA Yutaka MAEDA
This letter proposes a numerical method for approximating the location of and dynamics on a class of chaotic saddles. In contrast to the conventional strategy of maximizing the escape time, our proposal is to impose a zero-expansion condition along transversely repelling directions of chaotic saddles. This strategy exploits the existence of skeleton-forming unstable periodic orbits embedded in chaotic saddles, and thus can be conveniently implemented as a variant of subspace Newton-type methods. The algorithm is examined through an illustrative and another standard example.
A lot of vision systems have been embedded in devices around us, like mobile phones, vehicles and UAVs. Many of them still need interactive operations of human users. However, specifying accurate object information could be a challenging task due to video jitters caused by camera shakes and target motions. In this paper, we first collect practical hand drawn bounding boxes on real-life videos which are captured by hand-held cameras and UAV-based cameras. We give a deep look into human-computer interactive operations on unstable images. The collected data shows that human input suffers heavy deviations which are harmful to interaction accuracy. To achieve robust interactions on unstable platforms, we propose a target-focused video stabilization method which utilizes a proposal-based object detector and a tracking-based motion estimation component. This method starts with a single manual click and outputs stabilized video stream in which the specified target stays almost stationary. Our method removes not only camera jitters but also target motions simultaneously, therefore offering an comfortable environment for users to do further interactive operations. The experiments demonstrate that the proposed method effectively eliminates image vibrations and significantly increases human input accuracy.
Jingjie YAN Bei WANG Ruiyu LIANG
In this paper, we establish a novel bimodal emotion database from physiological signals and facial expression, which is named as PSFE. The physiological signals and facial expression of the PSFE database are respectively recorded by the equipment of the BIOPAC MP 150 and the Kinect for Windows in the meantime. The PSFE database altogether records 32 subjects which include 11 women and 21 man, and their age distribution is from 20 to 25. Moreover, the PSFE database records three basic emotion classes containing calmness, happiness and sadness, which respectively correspond to the neutral, positive and negative emotion state. The general sample number of the PSFE database is 288 and each emotion class contains 96 samples.
Abu Hena Al MUKTADIR Kenji FUJIKAWA Hiroaki HARAI Lixin GAO
This paper proposes route advertisement policies (RAP) and an inbound traffic engineering (ITE) technique for a multihomed autonomous system (AS) employing the Border Gateway Protocol (BGP) and provider aggregatable (PA) addressing. The proposed RAP avail the advantage of address aggregation benefit of PA addressing. If multiple address spaces are allocated to each of the ASes that are multihomed to multiple upstream ASes, reduction of the forwarding information base (FIB) and quick convergence are achieved. However, multihoming based on PA addressing raises two issues. First, more specific address information is hidden due to address aggregation. Second, multiple allocated address spaces per AS does not provide the capability of ITE. To cope with these two limitations, we propose i) RAP to ensure connectivity among ASes with fewer routes installed in the FIB of each top-tier AS, and ii) an ITE technique to control inbound routes into multihomed ASes. Our ITE technique does not increase the RIB and FIB sizes in the Internet core. We implement the proposed RAP in an emulation environment with BGP using the Quagga software suite and our developed Hierarchical Automatic Number Allocation (HANA) protocols. We use HANA as a tool to automatically allocate hierarchical PA addresses to ASes. We confirm that with our proposed policies the FIB and RIB (routing information base) sizes in tier-1 ASes do not change with the increase of tier-3 ASes, and the number of BGP update messages exchanged is reduced by up to 69.9% from that achieved with conventional BGP RAP. We also confirmed that our proposed ITE technique, based on selective prefix advertisement, can indeed control inbound traffic into a multihomed AS employing PA addressing.
Hiroyuki ASAHARA Takuji KOUSAKA
In this research, we propose an effective stability analysis method to impacting systems with periodically moving borders (periodic borders). First, we describe an n-dimensional impacting system with periodic borders. Subsequently, we present an algorithm based on a stability analysis method using the monodromy matrix for calculating stability of the waveform. This approach requires the state-transition matrix be related to the impact phenomenon, which is known as the saltation matrix. In an earlier study, the expression for the saltation matrix was derived assuming a static border (fixed border). In this research, we derive an expression for the saltation matrix for a periodic border. We confirm the performance of the proposed method, which is also applicable to systems with fixed borders, by applying it to an impacting system with a periodic border. Using this approach, we analyze the bifurcation of an impacting system with a periodic border by computing the evolution of the stable and unstable periodic waveform. We demonstrate a discontinuous change of the periodic points, which occurs when a periodic point collides with a border, in the one-parameter bifurcation diagram.
Liaoruo HUANG Qingguo SHEN Zhangkai LUO
Bandwidth reservation is an important way to guarantee deterministic end-to-end service quality. However, with the traditional bandwidth reservation mechanism, the allocated bandwidth at each link is by default the same without considering the available resource of each link, which may lead to unbalanced resource utilization and limit the number of user connections that network can accommodate. In this paper, we propose a non-uniform bandwidth reservation method, which can further balance the resource utilization of network by optimizing the reserved bandwidth at each link according to its link load. Furthermore, to implement the proposed method, we devise a flexible and automatic bandwidth reservation mechanism based on meter table of Openflow. Through simulations, it is showed that our method can achieve better load balancing performance and make network accommodate more user connections comparing with the traditional methods in most application scenarios.