Jun KURIHARA Shinsaku KIYOMOTO Kazuhide FUKUSHIMA Toshiaki TANAKA
In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.
Sang Hyuk KANG Min Young CHUNG Bara KIM
In this letter, we propose a video traffic model based on a class of stochastic processes, which we call truncated GeoY/G/∞ input processes. Group of picture (GOP) size traces are modeled by truncated GeoY/G/∞ input process with gamma-distributed batch sizes Y and Weibull-like autocorrelation function. With full-length MPEG-4 video traces in QCIF, we run simulations to show that our proposed model estimates packet loss ratios at various traffic loads more accurately than existing modeling methods.
Ming-Der SHIEH Tai-Ping WANG Chien-Ming WU
We present a systematic and efficient way of managing the path metric memory and simplifying its connection network to the add_compare_select unit (ACSU) for Viterbi decoder (VD) design. Using the derived equations for memory partition and add-compare-select (ACS) arrangement together with the extended in-place scheduling scheme proposed in this work, we can increase the memory bandwidth for conflict-free path metric accesses with hardwired interconnection between the path metric memory and ACSU. Compared with the existing work, the developed architecture possesses the following advantages: (1) Each partitioned memory bank can be treated as a local memory of a specific processing element, inside the ACSU, with hardwired interconnection, so that the interconnect complexity is reduced significantly. (2) The partitioned memory banks can be merged into only two pseudo-banks regardless of the number of adopted ACS processing elements. This not only greatly simplifies the design of address generation unit, but also makes smaller the physical size of required memory. (3) The implementation can be accomplished in a systematic way with regular and simple controlling circuitry. Experimental results demonstrate the effectiveness of the developed architecture and the benefit will be more apparent for convolutional codes with large memory order.
Modern microprocessors achieve high application performance at the acceptable level of power dissipation. In terms of power to performance trade-off, the instruction window is particularly important. This is because enlarging the window size achieves high performance but naive scaling of the conventional instruction window can severely increase the complexity and power consumption. In this paper, we propose low-power instruction window techniques for contemporary microprocessors. First, the small reorder buffer (SROB) reduces power dissipation by deferred allocation and early release. The deferred allocation delays the SROB allocation of instructions until their all data dependencies are resolved. Then, the instructions are executed in program order and they are released faster from the SROB. This results in higher resource utilization and low power consumption. Second, we replace a conventional issue queue by a direct lookup table (DLT) with an efficient tag translation technique. The translation scheme resolves the instruction dependency, especially for the case of one producer to multiple consumers. The efficiency of the translation scheme stems from the fact that the vast majority of instruction dependency exists within a basic block. Experimental results show that our proposed design reduces the power consumption significantly for SPEC2000 benchmarks.
In this paper, we shall describe about a fuzzy estimation theory based on the concept of set-valued operators, suitable for available operation of extremely complicated large-scale network systems. Fundamental conditions for availability of system behaviors of such network systems are clarified in a form of β-level fixed point theorem for system of fuzzy-set-valued operators. Here, the proof of this theorem is accomplished in a weak topology introduced into the Banach space.
Akira UTAGAWA Tetsuya ASAI Tetsuya HIROSE Yoshihito AMEMIYA
We present on-chip oscillator arrays synchronized by random noises, aiming at skew-free clock distribution on synchronous digital systems. Nakao et al. recently reported that independent neural oscillators can be synchronized by applying temporal random impulses to the oscillators [1],[2]. We regard neural oscillators as independent clock sources on LSIs; i.e., clock sources are distributed on LSIs, and they are forced to synchronize through the use of random noises. We designed neuron-based clock generators operating at sub-RF region (< 1 GHz) by modifying the original neuron model to a new model that is suitable for CMOS implementation with 0.25-µm CMOS parameters. Through circuit simulations, we demonstrate that i) the clock generators are certainly synchronized by pseudo-random noises and ii) clock generators exhibited phase-locked oscillations even if they had small device mismatches.
We consider a problem of global asymptotic stabilization of a class of nonlinear systems that have the unknown linear growth rate. While the existing results only deal with one specified form of nonlinear systems, our proposed method includes both forms of triangular and feedforward nonlinear systems in a unified framework. The proposed controller has a dynamic gain mechanism which is selectively engaged based on the given nonlinear form. Then, the dynamic gain is adaptively tuned depending on the unknown linear growth rate.
Geng HU Hong WANG Shiyuan YANG
Testing is a critical stage in integrated circuits production in order to guarantee reliability. The complexity and high integration level of mixed-signal ICs has put forward new challenges to circuit testing. This paper describes an oscillation-based combined self-test strategy for the analog portion and analog-to-digital converters (ADCs) in integrated mixed-signal circuits. In test mode, the analog portion under test is reconfigured into an oscillator, generating periodic signals as the test stimulus of ADC. By analyzing the A/D conversion results, a histogram test of ADC can be performed, and the oscillation frequency as well as amplitude can be checked, and in this way the oscillation test of the analog portion is realized simultaneously. For an analog benchmark circuit combined with an ADC, triangle oscillation and sinusoid oscillation schemes are both given to test their faults. Experimental results show that fault coverage of the analog portion is 92.2% and 94.3% in the two schemes respectively, and faults in the ADC can also be tested.
In networked control systems, uncontrollable events may unexpectedly occur in a plant before a proper control action is applied to the plant due to communication delays. In the area of supervisory control of discrete event systems, Park and Cho [5] proposed the notion of delay-nonconflictingness for the existence of a supervisor achieving a given language specification under communication delays. In this paper, we present the algebraic properties of delay-nonconflicting languages which are necessary for solving supervisor synthesis problems under communication delays. Specifically, we show that the class of prefix-closed and delay-nonconflicting languages is closed under intersection, which leads to the existence of a unique infimal prefix-closed and delay-nonconflicting superlanguage of a given language specification.
Isao NAKANISHI Hiroyuki SAKAMOTO Yoshio ITOH Yutaka FUKUI
In on-line signature verification, complexity of signature shape can influence the value of the optimal threshold for individual signatures. Writer-dependent threshold selection has been proposed but it requires forgery data. It is not easy to collect such forgery data in practical applications. Therefore, some threshold equalization method using only genuine data is needed. In this letter, we propose three different threshold equalization methods based on the complexity of signature. Their effectiveness is confirmed in experiments using a multi-matcher DWT on-line signature verification system.
Masako FUJII Koji NII Hiroshi MAKINO Shigeki OHBAYASHI Motoshige IGARASHI Takeshi KAWAMURA Miho YOKOTA Nobuhiro TSUDA Tomoaki YOSHIZAWA Toshikazu TSUTSUI Naohiko TAKESHITA Naofumi MURATA Tomohiro TANAKA Takanari FUJIWARA Kyoko ASAHINA Masakazu OKADA Kazuo TOMITA Masahiko TAKEUCHI Shigehisa YAMAMOTO Hiromitsu SUGIMOTO Hirofumi SHINOHARA
We propose a new large-scale logic test element group (TEG), called a flip-flop RAM (FF-RAM), to improve the total process quality before and during initial mass production. It is designed to be as convenient as an SRAM for measurement and to imitate a logic LSI. We implemented a 10 Mgates FF-RAM using our 65-nm CMOS process. The FF-RAM enables us to make fail-bit maps (FBM) of logic cells because of its cell array structure as an SRAM. An FF-RAM has an additional structure to detect the open and short failure of upper metal layers. The test results show that it can detect failure locations and layers effortlessly using FBMs. We measured and analyzed it for both the cell arrays and the upper metal layers. Their results provided many important clues to improve our processes. We also measured the neutron-induced soft error rate (SER) of FF-RAM, which is becoming a serious problem as transistors become smaller. We compared the results of the neutron-induced soft error rate to those of previous generations: 180 nm, 130 nm, and 90 nm. Because of this TEG, we can considerably shorten the development period for advanced CMOS technology.
Performance properties of list scheduling algorithms under various dynamic assumptions are analyzed. The focus is on bounds for scheduling directed acyclic graphs with arbitrary precedence constrains and arbitrary task processing times subject to minimizing the makespan. New performance bounds are derived and compared with known results.
Abhay GHATPANDE Hidenori NAKAZATO Olivier BEAUMONT Hiroshi WATANABE
Divisible Load Theory (DLT) is an established mathematical framework to study Divisible Load Scheduling (DLS). However, traditional DLT does not address the scheduling of results back to source (i.e., result collection), nor does it comprehensively deal with system heterogeneity. In this paper, the DLSRCHETS (DLS with Result Collection on HETerogemeous Systems) problem is addressed. The few papers to date that have dealt with DLSRCHETS, proposed simplistic LIFO (Last In, First Out) and FIFO (First In, First Out) type of schedules as solutions to DLSRCHETS. In this paper, a new polynomial time heuristic algorithm, SPORT (System Parameters based Optimized Result Transfer), is proposed as a solution to the DLSRCHETS problem. With the help of simulations, it is proved that the performance of SPORT is significantly better than existing algorithms. The other major contributions of this paper include, for the first time ever, (a) the derivation of the condition to identify the presence of idle time in a FIFO schedule for two processors, (b) the identification of the limiting condition for the optimality of FIFO and LIFO schedules for two processors, and (c) the introduction of the concept of equivalent processor in DLS for heterogeneous systems with result collection.
IEEE 802.16 broadband wireless access (BWA) technology is suitable for providing multimedia applications without accessing the wired networks directly. Although IEEE 802.16 standard well defines the quality of service (QoS) framework, it makes no specific recommendation with regard to the bandwidth allocation. In this paper, we propose an algorithm for allocating bandwidth in response to dynamic changes in the arrival rate such that the total bandwidth is efficiently utilized.
Junya SEKIKAWA Takayoshi KUBONO
Motion of break arcs driven by external magnetic field is observed using a high-speed camera. The magnetic field is applied with a permanent magnet. Experimental circuit is DC42 V-10 A resistive circuit. Material of electrical contacts is silver. Following results are shown. The break arcs are driven in the direction according to Lorentz force. The arc duration decreases with decrease of the distance between the electrical contacts and the magnet. When the external magnetic-flux density at the position of the break arc is lower than a certain value, the effect of the magnetic field to drive the break arc becomes ineffective to shorten the arc duration. The result is explained with a relationship between the motion of break arc and the distribution of the external magnetic field.
Juichi KOSAKAYA Hideyuki TADOKORO Yasuhiro INAZUMI
Introducing multi-agent (MA) technology into a SCADA (Supervisory Control and Data Acquisition) system can improve the serviceability and enhance maintenance-free operation with the inter-terminal parameter (ITP) method. In addition, the system's distributed intelligent field terminals (IFTs) use a common algorithm that is unaffected by any changes to the system specifications. As a result of these innovations, the proposed system has much better serviceability because it is much easier to make modifications compared to that of conventional systems. This system has been implemented for practical purposes at over 60 sites.
In this paper, we design an adaptive mobility-supporting MAC (AM-MAC) protocol for mobile sensor networks. In our protocol, as in S-MAC [1], each virtual cluster that consists of a subset of sensor nodes has its own listen-sleep schedule. Hence, when a mobile sensor node moves into a new virtual cluster, it needs to adapt to the listen-sleep schedule of the corresponding virtual cluster in a timely and energy efficient manner. To this end, in our protocol, we utilize schedule information on border nodes between virtual clusters. This allows us to implement fast and energy efficient listen-sleep schedule adaptation for mobile nodes, which consists of two main functions: energy efficient secondary listen period and smart scheduling adaptation. Simulation results show that our protocol can provide fast schedule adaptation while achieving energy efficiency.
Yoshitada WATANABE Yuichi HIRAKAWA
This paper reports on the effect of switching action on the contact surfaces of earthquake disaster prevention relays. Large-scale earthquakes occur frequently in Japan and bring extensive damage with them, and fire caused by electrical equipments is one example of the serious damage which can occur. Earthquake sensors capable of maintaining a high level of reliability when earthquakes occur play an important role as a means of minimizing this damage. For this reason, we carried out observations by focusing on samples which had either been subjected to an electric current of 10 mA or 0.1 A. The samples of 10 mA exhibited low and constant contact resistance despite the addition of seismic motion, while the samples of 0.1 A samples exhibited varying contact resistance and damage on their contact spots resulting from the addition of seismic motion. The sample surfaces were then observed using an atomic force microscope (AFM) in tapping mode and a surface potential microscope (SPoM). As a result, we found that even the unused earthquake disaster prevention relay (standard sample) which had a surface lined with asperities on its parallel striations formed by irregular protrusions due to dust and other deposits. In addition, scanning the contact surface with the SPoM at the same potential revealed the occurrence of differences in surface potential which varied in response to the asperities on the striations.
Junya SEKIKAWA Naoki MORIYAMA Takayoshi KUBONO
In a D.C.42 V-10A resistive circuit, break arcs are generated between electrical contact pairs. The materials of the contact pairs are Ag, Ag/C 2wt%, Ag/SnO2 12wt%, and Ag/ZnO 12wt%. The arc spectral intensities are measured by a time-resolved spectroscopic temperature measurement system. The arc temperature is calculated from the spectral intensities by using the method of relative intensities of two spectra. The experimental results are as follows. The arc temperature gradually decreases with increase of the gap of electrical contacts. The ranges of arc temperature for Ag, Ag/C 2wt%, Ag/SnO2 12wt%, and Ag/ZnO 12wt% contacts pairs are 4500-11000 K, 4000-6000 K, 4000-7000 K, and 4000-11000 K, respectively.
Sung-Chang LIM Dae-Yeon KIM Yung-Lyul LEE
In this paper, an alternative transform based on the correlation of the residual block is proposed for the improvement of the H.264/AVC coding efficiency. A discrete sine transform is used alternately with a discrete cosine transform in order to greatly compact the energy of the signal when the correlation coefficients of the signal are in the range of -0.5 to 0.5. Therefore, the discrete sine transform is suggested to be used in conjunction with the discrete cosine transform in H.264/AVC. The alternative transform selecting the optimal transform between two transforms by using rate-distortion optimization shows a coding gain compared with H.264/AVC. The proposed method achieves a PSNR gain of up to 1.0 dB compared to JM 10.2 at relatively high bitrates.