Masato NAKAZATO Satoshi OHTAKE Kewal K. SALUJA Hideo FUJIWARA
In this paper, we propose a method of accelerating test generation for sequential circuits by using the knowledge about the availability of state justification sequences, the bound on the length of state distinguishing sequences, differentiation between valid and invalid states, and the existence of a reset state. We also propose a method of synthesis for testability (SfT) which takes the features of our test generation method into consideration to synthesize sequential circuits from given FSM descriptions. The SfT method guarantees that the test generator will be able to find a state distinguishing sequence. The proposed method extracts the state justification sequence from the FSM produced by the synthesizer to improve the performance of its test generation process. Experimental results show that the proposed method can achieve 100% fault efficiency in relatively short test generation time.
Koichi HARADA Hidekazu USUI Koichiro NISHI
We propose the extended Bezier spiral in this paper. The spiral is useful for both design purposes and improved aesthetics. This is because the spiral is one of the Bezier curves, which play an important role in interactive curve design, and because the assessment of the curve is based on the human reception of the curve. For the latter purpose we utilize the logarithmic distribution graph that quantifies the designers' preferences. This paper contributes the unification of the two different curve design objectives (the interactive operation and so called "eye pleasing" result generation); which have been independently investigated so far.
We investigate the enhancement of the optical nonlinearity and the limit of the improvement of the response speed in CdSxSe1-x microcrystallites by measuring the effective optical nonlinear cross section (σeff), the energy decay time (T1) and the dephasing time in two kinds of semiconductor microcrystallites of CdS0.12Se0.8 microcrystallites embedded in alkaline multi-component glasses (CdSSeMs) and CdSe microcrystallites embedded in SiO2 thin film (CdSeMs). As the average radius of CdSSeMs decreases from 10 to 1 nm, the values of σeff and T1 gradually change from 2.610-16 to 1.110-16 cm2 and from dozens picoseconds to 4 psec, respectively. The size dependence of CdSSEMs shows that the energy level structure in the microcrystallite with a radius of less than a few nanometers is a two-level system, in which σeff is proportional to T2. The carrier recombination time (τ) of CdSSeMs with the average radius of 1 nm is estimated to 2 psec. As the average radius of a CdS0.12Se0.8 microcrystallite decreases from 9 to 3 nm, the values of T2 gradually change from 640 to 230 fsec at 18 K, respectively. The size and temperature dependences of T2 for the CdSSeMs show that there is the discrepancy between the theory and the measured T2. The discrepancy showes the presence of the acoustic-phonon-assisted relaxation processes other than the pure-dephasing processes. It is indicated that T2 becomes long by reducing the excessive acoustic-phonon-assisted relaxation processes, and that the longer T2 might enhance σeff. We investigate the enhancement of σeff in CdSeMs by making T2 longer. The τ, σeff, and T2 of CdSeM an average radius of 3 nm are 40 psec, 4.510-15 cm2, and 150 fsec at room temperature. The σeff is ten times as large as that of CdSSeM sample at the same average radius and the enhancement of σeff can be considered to be caused by the longer T2.
Shunji NAKATA Yoshitada KATAGIRI
This paper considers a more generalized capacitor that can decrease its width using its own electrical force. We consider a model in which the capacitor with plate distance d is coupled with repulsive mechatronical potential energy, which is proportional to 1/dn. In the conventional case, n is considered to be approximately very large. In our capacitor model, there is a stable point between attractive electrical force and repulsive mechatronical force. In this system, electrostatic energy is equal to the sum of mechatronical potential energy and energy dissipation. Moreover, the mechatronical potential energy is 1/n times smaller than the electrostatic energy. All energies, including the electrostatic energy, potential energy, and energy dissipation, are proportional not to ordinary value V2, but to V2/(n-1)+2, where V is the power supply voltage. This means the voltage dependence of energy is unusual. It is strongly dependent on the capacitor matter, i.e., on the characteristics of the mechatronical system. In addition, the energy dissipation of the system can be reduced to zero using the adiabatic charging process.
In this letter, a 1.25-Gb/s 0.18-µm CMOS half-rate burst-mode clock and data recovery (CDR) circuit is presented. The CDR contains a fast-locking clock recovery circuit (CRC) using a realigned oscillation technique to recover the desired clock. To reduce the power dissipation, the CRC uses a two-stage ring structure and a current-reused concept to merge with an edge detector. The recovered clock has a peak-to-peak jitter of 34.0 ps at 625 MHz and the retimed data has a peak-to-peak jitter of 44.0 ps at 625 Mb/s. The occupied die area of the CDR is 1.41.4 mm2, and power consumption is 32 mW under a 1.8-V supply voltage.
Kai CAI Rongquan FENG Zhiming ZHENG
Sequences with good correlation properties are widely used in engineering applications, especially in the area of communications. Among the known sequences, cyclotomic families have the optimal autocorrelation property. In this paper, we decide the cross-correlation function of the known cyclotomic sequences completely. Moreover, to get our results, the relations between the multiplier group and the decimations of the characteristic sequence are also established for an arbitrary difference set.
David GAVILAN Hiroki TAKAHASHI Suguru SAITO Masayuki NAKAJIMA
A method for evaluating image segmentation methods is proposed in this paper. The method is based on a perception model where the drawing act is used to represent visual mental percepts. Each segmented image is represented by a minimal set of features and the segmentation method is tested against a set of sketches that represent a subset of the original image database, using the Mahalanobis distance function. The covariance matrix is set using a collection of sketches drawn by different users. The different drawings are demonstrated to be consistent across users. This evaluation method can be used to solve the problem of parameter selection in image segmentation, as well as to show the goodness or limitations of the different segmentation algorithms. Different well-known color segmentation algorithms are analyzed with the proposed method and the nature of each one is discussed. This evaluation method is also compared with heuristic functions that serve for the same purpose, showing the importance of using users' pictorial knowledge.
Lijie WANG Takahiko HORIUCHI Hiroaki KOTERA
Adaptation process of retina helps human visual system to see a high dynamic range scene in real world. This paper presents a simple static local adaptation method for high dynamic range image compression based on a retinal model. The proposed simple model aims at recreating the same sensations between the real scene and the range compressed image on display device when viewed after reaching steady state local adaptation respectively. Our new model takes the display adaptation into account in relation to the scene adaptation based on the retinal model. In computing local adaptation, the use of nonlinear edge preserving bilateral filter presents a better tonal rendition in preserving the local contrast and details while avoiding banding artifacts normally seen in local methods. Finally, we demonstrate the effectiveness of the proposed model by estimating the color difference between the recreated image and the target visual image obtained by trial and error method.
Preeyakorn TIPWAI Suthep MADARASMI
We present the use of a Modified Generalized Hough Transform (MGHT) and deformable contours for image data retrieval where a given contour, gray-scale, or color template image can be detected in the target image, irrespective of its position, size, rotation, and smooth deformation transformations. Potential template positions are found in the target image using our novel modified Generalized Hough Transform method that takes measurements from the template features by extending a line from each edge contour point in its gradient direction to the other end of the object. The gradient difference is used to create a relationship with the orientation and length of this line segment. Potential matching positions in the target image are then searched by also extending a line from each target edge point to another end along the normal, then looking up the measurements data from the template image. Positions with high votes become candidate positions. Each candidate position is used to find a match by allowing the template to undergo a contour transformation. The deformed template contour is matched with the target by measuring the similarity in contour tangent direction and the smoothness of the matching vector. The deformation parameters are then updated via a Bayesian algorithm to find the best match. To avoid getting stuck in a local minimum solution, a novel coarse-and-fine model for contour matching is included. Results are presented for real images of several kinds including bin picking and fingerprint identification.
Taiji SASAOKA Hideyuki KAWABATA Toshiaki KITAMURA
Parallel programs for distributed memory machines are not easy to create and maintain, especially when they involve sparse matrix computations. In this paper, we propose a program translation system for generating parallel sparse matrix computation codes utilizing PSBLAS. The purpose of the development of the system is to offer the user a convenient way to construct parallel sparse code based on PSBLAS. The system is build up on the idea of bridging the gap between the easy-to-read program representations and highly-tuned parallel executables based on existing parallel sparse matrix computation libraries. The system accepts a MATLAB program with annotations and generates subroutines for an SPMD-style parallel program which runs on distributed-memory machines. Experimental results on parallel machines show that the prototype of our system can generate fairly efficient PSBLAS codes for simple applications such as CG and Bi-CGSTAB programs.
Nobuyuki SUGIO Hiroshi AONO Sadayuki HONGO Toshinobu KANEKO
This paper proposes novel calculuses of linearizing attack that can be applied to higher order differential attack. Higher order differential attack is a powerful and versatile attack on block ciphers. It can be roughly summarized as follows: (1) Derive an attack equation to estimate the key by using the higher order differential properties of the target cipher, (2) Determine the key by solving an attack equation. Linearizing attack is an effective method of solving attack equations. It linearizes an attack equation and determines the key by solving a system of linearized equations using approaches such as the Gauss-Jordan method. We enhance the derivation algorithm of the coefficient matrix for linearizing attack to reduce computational cost (fast calculus 1). Furthermore, we eliminate most of the unknown variables in the linearized equations by making the coefficient column vectors 0 (fast calculus 2). We apply these algorithms to an attack of the five-round variant of KASUMI and show that the attack complexity is equivalent to 228.9 chosen plaintexts and 231.2 KASUMI encryptions.
A one dimensional (1-D) based tree structure algorithm is proposed for estimating the 2D-DOAs of the signals impinging on a uniform rectangular array. The key idea of the proposed algorithm is to successively utilize the 1-D MUSIC algorithm several times, in tree structure, to estimate the azimuth and the elevation angles independently. Subspace projectors are exploited in conjunction with the 1-D MUSIC algorithms to decompose the received signal into several signals each coordinated by its own 2D-DOA. The pairing of the azimuth estimates and the associated elevation estimates is naturally determined due to the tree structure of the algorithm.
This paper introduces a new graph problem to find an Optimal Euler Circuit (OEC) in an Euler graph. OEC is defined as the Euler circuit that maximizes the sum of contiguous costs along it, where the contiguous cost is assigned for each of the two contiguous edges incident to a vertex. We prove that the OEC problem is NP-complete. A polynomial time algorithm will be presented for the case of a graph without vertex of degree greater than 4, and for the general case, a 1/4-approximation polynomial time algorithm will be proposed.
The UWB (ultra-wideband) pulse radar is a promising candidate as an environment measurement method for rescue robots. Radar imaging to locate a nearby target is known as an ill-posed inverse problem, on which various studies have been done. However, conventional algorithms require long computational time, which makes it difficult to apply them to real-time operations of robots. We have proposed a fast radar imaging algorithm, the SEABED algorithm, for UWB pulse radars. This algorithm is based on a reversible transform, BST (Boundary Scattering Transform), between the target shape and the observed data. This transform enables us to estimate target shapes quickly and accurately in a noiseless environment. However, in a noisy environment the image estimated by the SEABED algorithm is degraded because BST utilizes differential operations. We have also proposed an image stabilization method, which utilizes the upper bound of the smoothness of received data. This method can be applied only to convex objects, not to concave ones. In this paper, we propose a fractional BST, which is obtained by expanding the conventional BST, and an image stabilization method by using the fractional BST. We show that the estimated image can be stabilized regardless of the shape of target.
Youngjoo SUH Hoirin KIM Minsoo HAHN Yongju LEE
In this letter, a new segment-level speech/nonspeech classification method based on the Poisson polling technique is proposed. The proposed method makes two modifications from the baseline Poisson polling method to further improve the classification accuracy. One of them is to employ Poisson mixture models to more accurately represent various segmental patterns of the observed frequencies for frame-level input features. The other is the soft counting-based frequency estimation to improve the reliability of the observed frequencies. The effectiveness of the proposed method is confirmed by the experimental results showing the maximum error reduction of 39% compared to the segmentally accumulated log-likelihood ratio-based method.
Toshiki KANAMOTO Shigekiyo AKUTSU Tamiyo NAKABAYASHI Takahiro ICHINOMIYA Koutaro HACHIYA Atsushi KUROKAWA Hiroshi ISHIKAWA Sakae MUROMOTO Hiroyuki KOBAYASHI Masanori HASHIMOTO
In this letter, we discuss the impact of intrinsic error in parasitic capacitance extraction programs which are commonly used in today's SoC design flows. Most of the extraction programs use pattern-matching methods which introduces an improvable error factor due to the pattern interpolation, and an intrinsically inescapable error factor from the difference of boundary conditions in the electro-magnetic field solver. Here, we study impact of the intrinsic error on timing and crosstalk noise estimation. We experimentally show that the resulting delay and noise estimation errors show a scatter which is normally distributed. Values of the standard deviations will help designers consider the intrinsic error compared with other variation factors.
Shunsuke SAITO Yasuyuki TANAKA Mitsunobu KUNISHI Yoshifumi NISHIDA Fumio TERAOKA
Recently, the number of multi-homed hosts is getting large, which are equipped with multiple network interfaces to support multiple IP addresses. Although there are several proposals that aim at bandwidth aggregation for multi-homed hosts, few of them support mobility. This paper proposes a new framework called AMS: Aggregate-bandwidth Multi-homing Support. AMS provides functions of not only bandwidth aggregation but also mobility by responding to the changes of the number of connections during communication without the support of underlying infrastructure. To achieve efficient data transmission, AMS introduces a function called address pairs selection to select an optimal combination of addresses of the peer nodes. We implemented AMS in the kernel of NetBSD and evaluated it in our test network, in which dummynet was used to control bandwidth and delay. The measured results showed that AMS achieved ideal bandwidth aggregation in three TCP connections by selecting optimal address pairs.
Shinobu NAGAYAMA Tsutomu SASAO Jon T. BUTLER
This paper presents an architecture and a synthesis method for compact numerical function generators (NFGs) for trigonometric, logarithmic, square root, reciprocal, and combinations of these functions. Our NFG partitions a given domain of the function into non-uniform segments using an LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Experimental results show that: 1) our NFGs require, on average, only 4% of the memory needed by NFGs based on the linear approximation with non-uniform segmentation; 2) our NFG for 2x-1 requires only 22% of the memory needed by the NFG based on a 5th-order approximation with uniform segmentation; and 3) our NFGs achieve about 70% of the throughput of the existing table-based NFGs using only a few percent of the memory. Thus, our NFGs can be implemented with more compact FPGAs than needed for the existing NFGs. Our automatic synthesis system generates such compact NFGs quickly.
One of the critical issues in MTCMOS design is how to estimate a circuit delay quickly. In MTCMOS circuit, voltage on virtual ground fluctuates due to a discharge current of a logic cell. This event affects to the cell delay and makes static timing analysis (STA) difficult. In this paper, we propose a delay modeling and static STA methodology targeting at MTCMOS circuits. In the proposed method, we prepare a delay look-up table (LUT) consisting of the input slew, the output load capacitance, the virtual ground length, and a power-switch size. Using this LUT, we compute a circuit delay for each logic cell by applying the linear interpolation. This technique enables to calculate the cell delay considering the delay increase by the voltage fluctuation of virtual ground line. Experimental results show that the proposed methodology enables to estimate the cell delay and the critical path delay within 8% errors compared with SPICE simulation.
Heng-Chou CHEN Oscal T.-C. CHEN
The probability associated with population fitness in a Genetic Algorithm (GA) is studied using the concept of average Euclidean distance. Based on the probability derived from population fitness, the GA can effectively terminate its evolution operations to mitigate the total computational load. Simulation results verify the feasibility of the derived probability used for the GA's termination strategy.