HyunJin KIM Hong-Sik KIM Jung-Hee LEE Jin-Ho AHN Sungho KANG
This paper proposes a hardware-based parallel pattern matching engine using a memory-based bit-split string matcher architecture. The proposed bit-split string matcher separates the transition table from the state table, so that state transitions towards the initial state are not stored. Therefore, total memory requirements can be minimized.
Jie JIA Daeil YOON Hae Kwang KIM
Context-based adaptive variable length coding (CAVLC) is an entropy coding scheme employed in H.264/AVC for transform coefficient compression. The CAVLC encodes levels of nonzero-valued coefficients. Then indicates their positions with run_before which is number of zeros preceding each nonzero coefficient in scan order. In H.264, the run_before is coded using lookup tables depending on number of zero-valued coefficients that have not been coded. This paper presents an improved run_before coding method which encodes run_before using tables taking both zero-valued and nonzero-valued coefficients into consideration. Simulation results report that the proposed method yields an average of 4.40% bit rate reduction for run_before coding over H.264 baseline profile with intra-only coding structure. It corresponds to 0.52% bit rate saving over total bit rate on average.
We propose a surface profiling algorithm by white-light interferometry that extends sampling interval to twice of the widest interval among those used in conventional algorithms. The proposed algorithm uses a novel function called an in-phase component of an interferogram to detect the peak of the interferogram, while conventional algorithms used the squared-envelope function or the envelope function. We show that the in-phase component has the same peak as the corresponding interferogram when an optical filter has a symmetric spectral distribution. We further show that the in-phase component can be reconstructed from sampled values of the interferogram using the so-called quadrature sampling technique. Since reconstruction formulas used in the algorithm are very simple, the proposed algorithm requires low computational costs. Simulation results show the effectiveness of the proposed algorithm.
Kan WATANABE Masaru FUKUSHI Susumu HORIGUCHI
This paper presents a proposal of an expected-credibility-based job scheduling method for volunteer computing (VC) systems with malicious participants who return erroneous results. Credibility-based voting is a promising approach to guaranteeing the computational correctness of VC systems. However, it relies on a simple round-robin job scheduling method that does not consider the jobs' order of execution, thereby resulting in numerous unnecessary job allocations and performance degradation of VC systems. To improve the performance of VC systems, the proposed job scheduling method selects a job to be executed prior to others dynamically based on two novel metrics: expected credibility and the expected number of results for each job. Simulation of VCs shows that the proposed method can improve the VC system performance up to 11%; It always outperforms the original round-robin method irrespective of the value of unknown parameters such as population and behavior of saboteurs.
Huanfei MA Zhihao WU Haibin KAN
This letter investigates the space-time block codes from quasi-orthogonal design as a tradeoff between high transmission rate and low decoding complexity. By studying the role orthogonality plays in space-time block codes, upper bound of transmission rate and lower bound of decoding complexity for quasi-orthogonal design are claimed. From this point of view, novel algorithms are developed to construct specific quasi-orthogonal designs achieving these bounds.
In the present paper, we propose an evolutionary P2P networking technique that dynamically and adaptively optimizes several P2P network topologies, in which all of the nodes are included at the same time, in an evolutionary manner according to given evaluation criteria. In addition, through simulations, we examine whether the proposed evolutionary P2P networking technique can provide reliable search capability in dynamic P2P environments. In simulations, we assume dynamic P2P environments in which each node leaves and joins the network with its own probability and in which search objects vary with time. The simulation results show that topology reconstruction by the evolutionary P2P networking technique is better than random topology reconstruction when only a few types of search objects are present in the network at any moment and these search objects are not replicated. Moreover, for the scenario in which the evolutionary P2P networking technique is more effective, we show through simulations that when each node makes several links with other nodes in a single network topology, the evolutionary P2P networking technique improves the reliable search capability. Finally, the number of links that yields more reliable search capability appears to depend on how often nodes leave and join the network.
Keisuke IKUSHIMA Ryou SOUGEN Osanori KOYAMA Makoto YAMADA Yutaka KATSUYAMA
A novel fiber jacket removing system by a CO2 laser has been proposed to realize compact packaging of optical components. It has been clarified experimentally that excess-fiber-free MT connectorization is possible for 4-fiber ribbon.
Dai YAMAMOTO Jun YAJIMA Kouichi ITOH
This paper proposes a compact hardware (H/W) implementation for the MISTY1 block cipher, which is one of the ISO/IEC 18033-3 standard encryption algorithms. In designing the compact H/W, we focused on optimizing the implementation of FO/FI/FL functions, which are the main components of MISTY1. For this optimization, we propose three new methods; reducing temporary registers for the FO function, shortening the critical path for the FI function, and merging the FL/FL-1 functions. According to our logic synthesis on a 0.18-µm CMOS standard cell library based on our proposed methods, the gate size is 3.4 Kgates, which is the smallest as far as we know.
Osamu SHIMADA Akihiko SUGIYAMA Toshiyuki NOMURA
This paper proposes a low complexity noise suppressor with hybrid filterbanks and adaptive time-frequency tiling. An analysis hybrid filterbank provides efficient transformation by further decomposing low-frequency bins after a coarse transformation with a short frame size. A synthesis hybrid filterbank also reduces computational complexity in a similar fashion to the analysis hybrid filterbank. Adaptive time-frequency tiling reduces the number of spectral gain calculations. It adaptively generates tiling information in the time-frequency plane based on the signal characteristics. The average number of instructions on a typical DSP chip has been reduced by 30% to 7.5 MIPS in case of mono signals sampled at 44.1 kHz. A Subjective test result shows that the sound quality of the proposed method is comparable to that of the conventional one.
This paper proposes a novel crest factor reduction (CFR) algorithm applicable to currently deployed W-CDMA base stations. The peak-to-average ratio (PAR) reduction of the multiple carrier mixed signal, namely CFR, has been an issue in order to convey the benefit of using low-cost power amplifiers. The simple final clipping method (SFCM) as a conventional method has been widely utilized due to its simplicity and effectiveness. However, the SFCM degrades the adjacent channel leakage ratio (ACLR) characteristic as well as the signal quality indicated by either the error vector magnitude (EVM) or the peak code domain error (PCDE). Conventionally, in order to alleviate this undesired deterioration, extra channel filtering and signal quality enhancement followed by CFR might be processed in an open-loop style. Alternatively, to perform CFR by maintaining the PAR as low as possible subject to satisfying the prescribed ACLR and EVM/PCDE performance, this paper introduces the prediction filter dependent peak reduction (PFDPR) process collaboratively working with dynamic waterfilling-based code domain compensation (DWCDC). To verify the superiority of the proposed CFR algorithm, tentative simulations are conducted while maintaining the rules of legitimate W-CDMA base station test specifications.
Maki YOSHIDA Shigeo MITSUNARI Toru FUJIWARA
This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.
Kohei MIYASE Xiaoqing WEN Hiroshi FURUKAWA Yuta YAMATO Seiji KAJIHARA Patrick GIRARD Laung-Terng WANG Mohammad TEHRANIPOOR
At-speed scan testing is susceptible to yield loss risk due to power supply noise caused by excessive launch switching activity. This paper proposes a novel two-stage scheme, namely CTX (Clock-Gating-Based Test Relaxation and X-Filling), for reducing switching activity when a test stimulus is launched. Test relaxation and X-filling are conducted (1) to make as many FFs as possible inactive by disabling corresponding clock control signals of clock-gating circuitry in Stage-1 (Clock-Disabling), and (2) to equalize the input and output values in Stage-2 of as many remaining active FFs as possible (FF-Silencing). CTX effectively reduces launch switching activity and thus yield loss risk even when only a small number of don't care (X) bits are present (as in test compression) without any impact on test data volume, fault coverage, performance, or circuit design.
Anis UZZAMAN Brion KELLER Brian FOUTZ Sandeep BHATIA Thomas BARTENSTEIN Masayuki ARAI Kazuhiko IWASAKI
This paper describes a simple means to enable direct diagnosis by bypassing MISRs on a small set of tests (MISR-bypass test mode) while achieving ultimate output compression using MISRs for the majority of tests (MISR-enabled test mode.) By combining two compression schemes, XOR and MISRs in the same device, it becomes possible to have high compression and still support compression mode volume diagnostics. In our experiment, the MISR-bypass test was first executed and at 10% of the total test set the MISR-enabled test was performed. The results show that compared with MISR+XOR-based compression the proposed technique provides better volume diagnosis with slightly small (0.71 X to 0.97 X) compaction ratio. The scan cycles are about the same as the MISR-enabled mode. A possible application to partial good chips is also shown.
Luis GRACIA Carlos PEREZ-VIDAL
In this research a new prediction algorithm based on a Fuzzy Mix of Filters (FMF) is developed. The use of a fuzzy mix is a good solution because it makes intuitive the difficult design task of combining several types of filters, so that the outputs of the filters that work closer to their optimal behavior have higher influence in the predicted values. Therefore the FMF adapts, according to the motion of the tracked object or target, the filter weights to reduce the estimation error. The paper develops the theory about the FMF and uses it for applications with hard real-time requirements. The improvement of the proposed FMF is shown in simulation and an implementation on a parallel processor (FPGA) is presented. As a practical application of the FMF, experimental results are provided for a visual servoing task.
Trung Thanh NGO Yuichiro KOJIMA Hajime NAGAHARA Ryusuke SAGAWA Yasuhiro MUKAIGAWA Masahiko YACHIDA Yasushi YAGI
For fast egomotion of a camera, computing feature correspondence and motion parameters by global search becomes highly time-consuming. Therefore, the complexity of the estimation needs to be reduced for real-time applications. In this paper, we propose a compound omnidirectional vision sensor and an algorithm for estimating its fast egomotion. The proposed sensor has both multi-baselines and a large field of view (FOV). Our method uses the multi-baseline stereo vision capability to classify feature points as near or far features. After the classification, we can estimate the camera rotation and translation separately by using random sample consensus (RANSAC) to reduce the computational complexity. The large FOV also improves the robustness since the translation and rotation are clearly distinguished. To date, there has been no work on combining multi-baseline stereo with large FOV characteristics for estimation, even though these characteristics are individually are important in improving egomotion estimation. Experiments showed that the proposed method is robust and produces reasonable accuracy in real time for fast motion of the sensor.
Cong-Nguyen BUI Hae-Yeoun LEE Jeong-Chun JOO Heung-Kyu LEE
A secure method for steganography is proposed. Pixel-value differencing (PVD) steganography and bit-plane complexity segmentation (BPCS) steganography have the weakness of generating blocky effects and noise in smooth areas and being detectable with steganalysis. To overcome these weaknesses, a secure bit-plane based steganography method on the spatial domain is presented, which uses a robust measure to select noisy blocks for embedding messages. A matrix embedding technique is also applied to reduce the change of cover images. Given that the statistical property of cover images is well preserved in stego-images, the proposed method is undetectable by steganalysis that uses RS analysis or histogram-based analysis. The proposed method is compared with the PVD and BPCS steganography methods. Experimental results confirm that the proposed method is secure against potential attacks.
Minoru MORI Minako SAWAKI Junji YAMATO
This paper describes an adaptive feature extraction method that exploits category-specific information to overcome both image degradation and deformation in character recognition. When recognizing multiple fonts, geometric features such as directional information of strokes are often used but they are weak against the deformation and degradation that appear in videos or natural scenes. To tackle these problems, the proposed method estimates the degree of deformation and degradation of an input pattern by comparing the input pattern and the template of each category as category-specific information. This estimation enables us to compensate the aspect ratio associated with shape and the degradation in feature values and so obtain higher recognition accuracy. Recognition experiments using characters extracted from videos show that the proposed method is superior to the conventional alternatives in resisting deformation and degradation.
Meiling ZHANG Weiguo ZHANG Jingmei LIU Xinmei WANG
Impossible differential attack (IDA) uses impossible differential characteristics extracted from enough plaintext pairs to retrieve subkeys of the first and the last several rounds of AES. In this paper, a general IDA on 7-round AES is proposed. Such attack takes the number of all-zero columns of the 7th and the 6th round as parameters (α,β). And a trade-off relation between the number of plaintexts and times of encryptions in the process of the attack is derived, which makes only some values of (α,β) allowed in the attack for different key length.
A method was developed for deriving the approximate global optimum of a nonlinear objective function with multiple local optimums. The objective function is expanded into a linear wave coefficient equation, so the problem of maximizing the objective function is reduced to that of maximizing a quadratic function with respect to the wave coefficients. Because a wave function expressed by the wave coefficients is used in the algorithm for maximizing the quadratic function, the algorithm is equivalent to a full search algorithm, i.e., one that searches in parallel for the global optimum in the whole domain of definition. Therefore, the global optimum is always derived. The method was evaluated for various objective functions, and computer simulation showed that a good approximation of the global optimum for each objective function can always be obtained.
Hiroyuki YOTSUYANAGI Masayuki YAMAMOTO Masaki HASHIZUME
In this paper, the scan chain ordering method for BIST-aided scan test for reducing test data and test application time is proposed. In this work, we utilize the simple LFSR without a phase shifter as PRPG and configure scan chains using the compatible set of flip-flops with considering the correlations among flip-flops in an LFSR. The method can reduce the number of inverter codes required for inverting the bits in PRPG patterns that conflict with ATPG patterns. The experimental results for some benchmark circuits are shown to present the feasibility of our test method.