Song-Hyon KIM Kyong-Ha LEE Inchul SONG Hyebong CHOI Yoon-Joon LEE
We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.
Hiroyuki YOTSUYANAGI Hiroyuki MAKIMOTO Takanobu NIMIYA Masaki HASHIZUME
This paper proposes a method for testing delay faults using a boundary scan circuit in which a time-to-digital converter (TDC) is embedded. The incoming transitions from the other cores or chips are captured at the boundary scan circuit. The TDC circuit is modified to set the initial value for a delay line through which the transition is propagated. The condition for measuring timing slacks of two or more paths is also investigated since the overlap of the signals may occur in the delay line of the TDC in our boundary scan circuit. An experimental IC with the TDC and boundary scan is fabricated and is measured to estimate the delay of some paths measured by the TDC embedded in boundary scan cells. The simulation results for a benchmark circuit with the boundary scan circuit are also shown for the case that timing slacks of multiple paths can be observed even if the signals overlap in the TDC.
The conventional hybrid STBC schemes can achieve less BER performance for STBC detection schemes than conventional STBC schemes since SM symbols interfere with STBC symbols. Therefore, this letter proposes the improved scheme for hybrid STBC systems. STBC and SM schemes are combined for the hybrid space-time block code system. Our approach effectively obtains both diversity gain and spectral efficiency gain. The proposed scheme offers improved BER performance since it uses iterative detection. Moreover, it increases the data rate effectively with a little performance loss.
Chun WANG Zhongyuan LAI Hongyuan WANG
In this paper, we propose the Perceptual Shape Decomposition (PSD) to detect fingers for a Kinect-based hand gesture recognition system. The PSD is formulated as a discrete optimization problem by removing all negative minima with minimum cost. Experiments show that our PSD is perceptually relevant and robust against distortion and hand variations, and thus improves the recognition system performance.
Junya SEKIKAWA Katsuyoshi MIYAJI
Break arcs are generated in a DC48V resistive circuit. The circuit current is varied from 1A to 6A. The contact resistance distribution on the anode surfaces eroded by break arcs is investigated. The following results are shown. When the current is 2A, 3A and 6A, the contact resistance at the center region of the anode surface is higher than that around the center region. The contact resistance around the center region decreases with the decrease of the circuit current. When the current is 1A, the contact resistance is very low at all positions on the contact surface. The lower contact resistance may be caused by the occurrence of the short arc that is extinguished in the metallic phase arc.
Kensuke SAITO Daijiro ISHIBASHI Nobuhiro KUGA
In this letter, we propose a partial impedance-matching method using a two-strip resonator for noncontact Passive Intermodulation (PIM) measurements using a coaxial tube. It is shown that the strip closer to the inner tube of the coaxial tube is dominant in the observed PIM characteristics while both strips are excited equally. The ideal efficiency of power to each strip is 50%, which is a significant improvement in comparison with conventional methods.
John W. McBRIDE Chamaporn CHIANRABUTRA Liudi JIANG Suan Hui PU
Multi-Walled CNT (MWCNT) are synthesized on a silicon wafer and sputter coated with a gold film. The planar surfaces are mounted on the tip of a piezo-electric actuator and mated with a gold coated hemispherical surface to form an electrical contact. These switching contacts are tested under conditions typical of MEMS relay applications; 4V, with a static contact force of 1mN, at a low current between 20-50mA. The failure of the switch is identified by the evolution of contact resistance which is monitored throughout the switching cycles. The results show that the contact resistance can be stable for up to 120 million switching cycles, which are 106 orders of higher than state-of-the-art pure gold contact. Bouncing behavior was also observed in each switching cycle. The failing mechanism was also studied in relation to the contact surface changes. It was observed that the contact surfaces undergo a transfer process over the switching life time, ultimately leading to switching failure the number of bounces is also related to the fine transfer failure mechanism.
Diancheng WU Yu LIU Hao ZHU Donghui WANG Chengpeng HAO
This paper presents a novel data compression method for testing integrated circuits within the framework of pattern run-length coding. The test set is firstly divided into 2n-length patterns where n is a natural number. Then the compatibility of each pattern, which can be an external type, or an internal type, is analyzed. At last, the codeword of each pattern is generated according to its analysis result. Experimental results for large ISCAS89 benchmarks show that the proposed method can obtain a higher compression ratio than existing ones.
Shinichi MIYAMOTO Seiichi SAMPEI Wenjie JIANG
To enhance the throughput while satisfying the quality of service (QoS) requirements of wireless local area networks (WLANs), this paper proposes a distributed coordination function-based (DCF-based) medium access control (MAC) protocol that realizes centralized radio resource management (RRM) for a basic service set. In the proposed protocol, an access point (AP) acts as a master to organize the associated stations and attempts to reserve the radio resource in a conventional DCF-manner. Once the radio resource is successfully reserved, the AP controls the access of each station by an orthogonal frequency division multiple access (OFDMA) scheme. Because the AP assigns radio resources to the stations through the opportunistic two-dimensional scheduling based on the QoS requirements and the channel condition of each station, the transmission opportunities can be granted to the appropriate stations. In order to reduce the signaling overhead caused by centralized RRM, the proposed protocol introduces a station-grouping scheme which groups the associated stations into clusters. Moreover, this paper proposes a heuristic resource allocation algorithm designed for the DCF-based MAC protocol. Numerical results confirm that the proposed protocol enhances the throughput of WLANs while satisfying the QoS requirements with high probability.
Dan NIU Xiao WU Zhou JIN Yasuaki INOUE
Finding DC operating points of nonlinear circuits is an important and difficult task. The Newton-Raphson method adopted in the SPICE-like simulators often fails to converge to a solution. To overcome this convergence problem, homotopy methods have been studied from various viewpoints. However, the previous studies are mainly focused on the bipolar transistor circuits. Also the efficiencies of the previous homotopy methods for MOS transistor circuits are not satisfactory. Therefore, finding a more efficient homotopy method for MOS transistor circuits becomes necessary and important. This paper proposes a Newton fixed-point homotopy method for MOS transistor circuits and proposes an embedding algorithm in the implementation as well. Moreover, the global convergence theorems of the proposed Newton fixed-point homotopy method for MOS transistor circuits are also proved. Numerical examples show that the efficiencies for finding DC operating points of MOS transistor circuits by the proposed MOS Newton fixed-point homotopy method with the two embedding types can be largely enhanced (can larger than 50%) comparing with the conventional MOS homotopy methods, especially for some large-scale MOS transistor circuits which can not be easily solved by the SPICE3 and HSPICE simulators.
A.K.M. Mahfuzul ISLAM Hidetoshi ONODERA
This paper proposes the use of on-chip monitor circuits to detect process shift and process spread for post-silicon diagnosis and model-hardware correlation. The amounts of shift and spread allow test engineers to decide the correct test strategy. Monitor structures suitable for detection of process shift and process spread are discussed. Test chips targeting a nominal process corner as well as 4 other corners of “slow-slow”, “fast-fast”, “slow-fast” and “fast-slow” are fabricated in a 65nm process. The monitor structures correctly detects the location of each chip in the process space. The outputs of the monitor structures are further analyzed and decomposed into the process variations in threshold voltage and gate length for model-hardware correlation. Path delay predictions match closely with the silicon values using the extracted parameter shifts. On-chip monitors capable of detecting process shift and process spread are helpful for performance prediction of digital and analog circuits, adaptive delay testing and post-silicon statistical analysis.
Spectrum sensing is one of the main functions in cognitive radio networks. To improve the sensing performance and increase spectrum efficiency, a number of cooperative spectrum sensing methods have been proposed. However, most of these methods focused on a single-channel environment. In this letter, we present a novel cooperative spectrum sensing method based on cooperator selection in a multi-channel cognitive radio network. Using reinforcement learning, a cognitive radio user can select reliable and robust cooperators, without any a priori knowledge. Using the proposed method, a cognitive radio user can achieve better sensing capability and overcome performance degradation problems due to malicious users or erratic user behavior. Numerical results show that the proposed method can achieve excellent performance.
Song JIA Li LIU Xiayu LI Fengfeng WU Yuan WANG Ganggang ZHANG
Information security has been seriously threatened by the differential power analysis (DPA). Delay-based dual-rail precharge logic (DDPL) is an effective solution to resist these attacks. However, conventional DDPL convertors have some shortcomings. In this paper, we propose improved convertor pairs based on dynamic logic and a sense amplifier (SA). Compared with the reference CMOS-to-DDPL convertor, our scheme could save 69% power consumption. As to the comparison of DDPL-to-CMOS convertor, the speed and power performances could be improved by 39% and 54%, respectively.
Yoshiki KAYANO Kazuaki MIYANAGA Hiroshi INOUE
Arc discharge at breaking electrical contact is considered as a main source of not only degradation of the electrical property but also an undesired electromagnetic (EM) noise. In order to clarify the effect of holder temperature on the bridge and arc-duration, opening-waveforms at slowly separating silver-tin dioxide contact with different holder temperature are measured and discussed experimentally in this paper. Firstly, as opening-waveforms, the contact voltage, the contact current and the movement of moving contact related to the gap length are measured simultaneously. Secondly, the relationship between temperature of the holder and duration of the arc was quantified experimentally. It was revealed that as the initial temperature of the holder becomes higher, arc-duration becomes slightly longer. More importantly, the holder temperature dependencies of percentage of each-phase (metallic and gaseous-phases) are different with different closed-current.
Yoshihiko SUSUKI Ryoya KAZAOKA Takashi HIKIHARA
This paper proposes the physical architecture of an electric power system with multiple homes. The notion of home is a unit of small-scale power system that includes local energy source, energy storage, load, power conversion circuits, and control systems. An entire power system consists of multiple homes that are interconnected via a distribution network and that are connected to the commercial power grid. The interconnection is autonomously achieved with a recently developed technology of grid-connected inverters. A mathematical model of slow dynamics of the power system is also developed in this paper. The developed model enables the evaluation of steady and transient characteristics of power systems.
Kun-Lin TSAI I-Jui TUNG Feipei LAI
Content addressable memory is widely used for fast lookup table data searching, but it often consumes considerable power. Moreover, designing the suitable content addressable memory architecture for a specific application also consumes lots of time, since the behavioral simulation is often done in the transistor level. SystemC is a system-level modeling language and simulation platform, providing high simulation efficiency for hardware software co-design. Unfortunately, SystemC does not provide the function for estimating power dissipation of a structure design. In this paper, a SystemC-based fast content addressable memory power estimation method is presented for estimating the power dissipation of the match-line circuit, the search-line circuit, and the storage cell array of content addressable memory in the early design stage. The mathematical equations and behavioral patterns are used as the inputs of power estimation model. The simulation results based on 10 Mibench benchmarks show that the simulation time of the proposed method is in average 1233 times faster than that of HSPICE simulator with only 3.51% error rate.
A specification for digital cinema systems which deal with movies digitally from production to delivery as well as projection on the screens is recommended by DCI (Digital Cinema Initiative), and the systems based on this specification have already been developed and installed in theaters. The parameters of the systems that play an important role in determining image quality include image resolution, quantization bit depth, color space, gamma characteristics, and data compression methods. This paper comparatively discusses a relation between required bit depth and gamma quantization using both of a human visual system for grayscale images and two color difference models for color images. The required bit depth obtained from a contrast sensitivity function against grayscale images monotonically decreases as the gamma value increases, while it has a minimum value when the gamma is 2.9 to 3.0 from both of the CIE 1976 L* a* b* and CIEDE2000 color difference models. It is also shown that the bit depth derived from the contrast sensitivity function is one bit greater than that derived from the color difference models at the gamma value of 2.6. Moreover, a comparison between the color differences computed with the CIE 1976 L* a* b* and CIEDE2000 leads to a same result from the view point of the required bit depth for digital cinema systems.
Joji WATANABE Tadaaki HOSAKA Takayuki HAMAMOTO
For source camera identification, we propose a method to reconstruct the sensor pattern noise map from a size-reduced query image by minimizing an objective function derived from the observation model. Our method can be applied to multiple queries, and can thus be further improved. Experiments demonstrate the superiority of the proposed method over conventional interpolation-based magnification algorithms.
Yoshiya KOMATSU Masanori HARIYAMA Michitaka KAMEYAMA
This paper presents a novel architecture of an asynchronous FPGA for handshake-component-based design. The handshake-component-based design is suitable for large-scale, complex asynchronous circuit because of its understandability. This paper proposes an area-efficient architecture of an FPGA that is suitable for handshake-component-based asynchronous circuit. Moreover, the Four-Phase Dual-Rail encoding is employed to construct circuits robust to delay variation because the data paths are programmable in FPGA. The FPGA based on the proposed architecture is implemented in a 65 nm process. Its evaluation results show that the proposed FPGA can implement handshake components efficiently.
Hiroto SAIGO Hisashi KASHIMA Koji TSUDA
Apriori-based mining algorithms enumerate frequent patterns efficiently, but the resulting large number of patterns makes it difficult to directly apply subsequent learning tasks. Recently, efficient iterative methods are proposed for mining discriminative patterns for classification and regression. These methods iteratively execute discriminative pattern mining algorithm and update example weights to emphasize on examples which received large errors in the previous iteration. In this paper, we study a family of loss functions that induces sparsity on example weights. Most of the resulting example weights become zeros, so we can eliminate those examples from discriminative pattern mining, leading to a significant decrease in search space and time. In computational experiments we compare and evaluate various loss functions in terms of the amount of sparsity induced and resulting speed-up obtained.