A large memory is typically designed with multiple identical memory blocks for reducing delay and power. The circuit verification of individual memory blocks can be effectively handled by the Symbolic Trajectory Evaluation (STE) approach. However, if multiple memory blocks are integrated into a single system, the STE approach cannot verify it economically. This paper introduces algorithms for verifying block-level connectivity of memories. The verification time of a large memory can be reduced drastically by using bottom-up verification scheme. That is, a memory block is first verified thoroughly, and then only the interconnection between memory blocks of the large memory needs to be verified. The proposed verification algorithms require (3n+2(log2n+1)+3log2m) Read/Write operations for a 2nm-bit memory, where n and m are the address width and data width, respectively. Also, the algorithms can verify 100% of the inter-port and intra-port signal misplaced faults of the address, data input, and data output ports.
Joon-Hyuk CHANG Nam Soo KIM Sanjit K. MITRA
In this letter, we propose an approach to incorporate a statistical model for the voiced/unvoiced (V/UV) speech decision under background noise environments. Our approach consists of splitting the input noisy speech into two separate bands and applying a statistical model for each band. We compute and compare the likelihood ratio (LR) for each band based on the statistical model and estimated noise statistics for the V/UV decision. According to the simulation test, the proposed V/UV decision shows a better performance compared with the selectable mode vocoder (SMV) V/UV decision algorithm, particularly in clean and white noise environments.
Nae-Joung KWAK Wun-Mo YANG Jae-Hyuk HAN Jae-Hyeong AHAN
Digital halftoning is used to quantize a grayscale image to a binary image. Error diffusion halftoning generates a high-quality binary image, but also generates some defects such as the warm effect, sharpening, and so forth. To reduce these defects, Kite proposed a modified threshold modulation method that utilizes a multiplicative parameter for controlling sharpening. Nevertheless, some degradation was observed near the edges of objects with a large luminance change. In this paper, we propose a method of controlling the multiplicative parameter in proportion to the magnitude of the local edge slope. The results of computer simulation show a greater reduction of sharpening in the halftone image. In particular, there is a great improvement in the quality of the edges of objects with a large luminance change.
Tetsuya IIZUKA Makoto IKEDA Kunihiro ASADA
This paper proposes a cell layout synthesis method via Boolean Satisfiability (SAT). Cell layout synthesis problems are first transformed into SAT problems by our formulations. Our method realizes a high-speed layout synthesis for CMOS logic cells and guarantees to generate the minimum-width cells with routability under our layout styles. It considers complementary P-/N-MOSFETs individually during transistor placement, and can generate smaller width layout compared with pairing the complementary P-/N-MOSFETs case. To demonstrate the effectiveness of our SAT-based cell synthesis, we present experimental results which compare it with the 0-1 ILP-based transistor placement method and a commercial cell generation tool. The experimental results show that our SAT-based method can generate minimum-width placements in much shorter run time than the 0-1 ILP-based transistor placement method, and can generate the cell layouts of 32 static dual CMOS logic circuits in 54% run time compared with the commercial tool. Area increase of our method without compaction is only 3% compared with the commercial tool with compaction.
So-Young PARK Yong-Jae KWAK Joon-Ho LIM Hae-Chang RIM
In this paper, we propose a probabilistic feature-based parsing model for head-final languages, which can lead to an improvement of syntactic disambiguation while reducing the parsing cost related to lexical information. For effective syntactic disambiguation, the proposed parsing model utilizes several useful features such as a syntactic label feature, a content feature, a functional feature, and a size feature. Moreover, it is designed to be suitable for representing word order variation of non-head words in head-final languages. Experimental results show that the proposed parsing model performs better than previous lexicalized parsing models, although it has much less dependence on lexical information.
Youhua SHI Shinji KIMURA Masao YANAGISAWA Tatsuo OHTSUKI
Test data volume and power consumption for scan-based designs are two major concerns in system-on-a-chip testing. However, test set compaction by filling the don't-cares will invariably increase the scan-in power dissipation for scan testing, then the goals of test data reduction and low-power scan testing appear to be conflicted. Therefore, in this paper we present a selective scan chain reconfiguration method for test data compression and scan-in power reduction. The proposed method analyzes the compatibility of the internal scan cells for a given test set and then divides the scan cells into compatible classes. After the scan chain reconfiguration a dictionary is built to indicate the run-length of each compatible class and only the scan-in data for each class should be transferred from the ATE to the CUT so as to reduce test data volume. Experimental results for the larger ISCAS'89 benchmarks show that the proposed approach overcomes the limitations of traditional run-length coding techniques, and leads to highly reduced test data volume with significant power savings during scan testing in all cases.
The problem of signal restoration in the presence of observation space noise has been tackled extensively. However, restoration of degraded signals in the presence of signal space noise leads to considerable complexity because it becomes difficult to distinguish between the original signal and the noise. In this paper, a partial projection filter has been devised for the restoration of signals degraded by both the signal space and the observation space noises. A closed form of the proposed filter has been derived and its performance has been verified experimentally.
Keiji KIDA Xiaoke ZHU Changwen ZHUANG Yasuhiro TAKASHIMA Shigetoshi NAKATAKE
This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.
Katsuhiko DEGAWA Takafumi AOKI Tatsuo HIGUCHI Hiroshi INOKAWA Yasuo TAKAHASHI
This paper presents a model-based study of SET (Single-Electron-Transistor) logic gate family for synthesizing binary, MV (Multiple-Valued) and mixed-mode logic circuits. The use of SETs combined with MOS transistors allows compact realization of basic logic functions that exhibit periodic transfer characteristics. The operation of basic SET logic gates is successfully confirmed through SPICE circuit simulation based on the physical device model of SETs. The proposed SET logic gates are useful for implementing binary logic circuits, MV logic circuits and binary-MV mixed-mode logic circuits in a highly flexible manner. As an example, this paper describes design of various parallel counters for carry-propagation-free arithmetic, where MV signals are effectively used to achieve higher functionality with lower hardware complexity.
Charoenchai BOWORNTUMMARAT Lunchakorn WUTTISITTIKULKIJ Sak SEGKHOONTHOD
In this paper, we consider the problem of multicast routing and wavelength assignment (MC-RWA) in multi-fiber all-optical WDM networks. Two main network design system comprehensively investigated here are mesh and multi-ring designs. Given the multicast traffic demands, we present new ILP formulations to solve the MC-RWA problem with an objective to determine the minimal number of fibers needed to support the multicast requests. Unlike previous studies, our ILP formulations are not only capable of finding the optimal multicast routing and wavelength assignment pattern to the light-trees, but also finding the optimal light-tree structures simultaneously. Since broadcast and unicast communications are special cases of multicast communications, our ILP models are actually the generalized RWA mathematical models of optical WDM networks. In addition to proposing the ILP models, this paper takes two main issues affecting the network capacity requirement into account, that is, the splitting degree level of optical splitters and techniques of wavelength assignment to the light-trees. Three multicast wavelength assignment techniques studied in this paper are Light-Tree (LT), Virtual Light-Tree (VLT) and Partial Virtual Light-Tree (PVLT) techniques. Due to the NP-completeness of the MC-RWA problem, the ILP formulations can reasonably cope with small and moderate networks. To work with large networks, this paper presents alternative MC-RWA ILP-based heuristic algorithms for the PVLT and LT networks and develops lower bound techniques to characterize the performance of our algorithms. Using existing large backbone networks, numerical results are reported to analyze such aspects as multiple fiber systems, the benefits of using optical splitters and wavelength converters, and the capacity difference between the mesh and multi-ring designs. Finally, this paper provides an analysis of the influence of network connectivity on the network implementation under the constraints of mesh and multi-ring design schemes.
Hideki HASEGAWA Seiya KASAI Taketomo SATO
A new approach for ultra-low-power LSIs based on quantum devices is presented and its present status and critical issues are discussed with a brief background review on the semiconductor nanotechnology. It is a hexagonal binary decision diagram (BDD) quantum logic circuit approach suitable for realization of ultra-low-power logic/memory circuits to be used in new applications such as intelligent quantum (IQ) chips embedded in the ubiquitous network environment. The basic concept of the approach, circuit examples showing its feasibility, growth of high density nanostructure networks by molecular beam epitaxy (MBE) for future LSI implementation, and the key processing issues including the device isolation issue are addressed.
Izumi MASUBUCHI Seiji YABUKI Tokihisa TSUJI
This paper provides a computational method to construct a Lyapunov function to prove a stability of hybrid automata that can have nonlinear vector fields. Algebraic inequalities and equations are formulated, which are solved via LMI optimization. Numerical examples are presented to illustrate the proposed method.
Jau-Ji SHEN Iuon-Chang LIN Min-Shiang HWANG
Recently, a new light-weight version of the secure electronic transaction protocol was proposed. The protocol can achieve two goals. One goal is that the security level is the same as the SET protocol. The other goal is to reduce the computational time in message generation and verification, and reduce the communication overhead. However, the protocol has a weakness, which is that non-repudiation is acquired, but confidentiality is lost. In this paper, we point out the weakness of the protocol. We also propose an improvement to the protocol to overcome this weakness.
Luis Fortino CISNEROS-SINENCIO Alejandro DIAZ-SANCHEZ Jaime RAMIREZ-ANGULO
Reconfigurable logic circuitry has special importance because the popularity of Field Programmable Gate Arrays (FPGA) based applications. A reconfigurable logic based on FGMOS transistors, where a single stage can perform binary operations as well as state machines, is presented. The use of the proposed logic allows the integration of several stages into a single chip because their small area requirement, low voltage and low power characteristics.
Liang DONG Say-Wei FOO Yong LIAN
The Hidden Markov Model (HMM) is a popular statistical framework for modeling and analyzing stochastic signals. In this paper, a novel strategy is proposed that makes use of level-building algorithm with a chain of AdaBoost HMM classifiers to model long stochastic processes. AdaBoost HMM classifier belongs to the class of multiple-HMM classifier. It is specially trained to identify samples with erratic distributions. By connecting the AdaBoost HMM classifiers, processes of arbitrary length can be modeled. A probability trellis is created to store the accumulated probabilities, starting frames and indices of each reference model. By backtracking the trellis, a sequence of best-matched AdaBoost HMM classifiers can be decoded. The proposed method is applied to visual speech processing. A selected number of words and phrases are decomposed into sequences of visual speech units using both the proposed strategy and the conventional level-building on HMM method. Experimental results show that the proposed strategy is able to more accurately decompose words/phrases in visual speech than the conventional approach.
Kan TAKEUCHI Kazumasa YANAGISAWA Kazuko SAKAMOTO Teruya TANAKA
The optimum tier architectures for ASICs are investigated by using a methodology for predicting packing efficiency of a logic block (the ratio of total cell area to the block area including space regions between cells). In the methodology based on Rent's rule, (1) the empirical parameters required for the prediction are derived from the results of our ASIC products. (2) The concept of logic distance, which is expressed in units of the number of cells rather than the absolute net length, is introduced. (3) Not only performance constraints but also reliability constraints are incorporated. These allow us to make a quantitative comparison of the packing efficiency between various cell and tier structures. It is found that, for mega-cell blocks, all minimum-pitch layer architecture with buffer insertion is expected to give more than 20% reduction in block areas compared to the minimum-pitch + bi-pitch architecture, while satisfying the performance and reliability constraints.
Vikas RANA Ryoichi ISHIHARA Yasushi HIROSHIMA Daisuke ABE Satoshi INOUE Tatsuya SHIMODA Wim METSELAAR Kees BEENAKKER
Location control of grains by µ-Czochralski process with excimer-laser is a powerful tool for realizing high performance single-crystalline Si TFTs (c-Si TFTs). This study reports the behavior of p-channel single-crystalline Si TFTs fabricated inside a location-controlled grain by µ-Czochralski method. Self-aligned p-channel single-crystalline Si TFTs is fabricated with a top gate structure having ECR-PECVD SiO2 as gate insulator. The field effect hole mobility of 250 cm2/Vs and subthreshold swing of 0.29 V/dec. are obtained successfully. Effects of active Si thickness and boron channel doping on the characteristics of the c-Si TFTs were studied.
A reaction-diffusion computer is a large-scale array of elementary processors, micro-volumes of chemical medium, which act, change their states determined by chemical reactions, concurrently and interact locally, via local diffusion of chemical species; it transforms data to results, both represented by concentration profiles of chemical species, by traveling and colliding waves in spatially extended chemical media. We show that reaction-diffusion processors, simulated or experimental, can solve a variety of tasks, including computational geometry, robot navigation, logics and arithmetics.
Masaru HONJO Satoshi MAKIDO Takaya YAMAZATO Hiraku OKADA Masaaki KATAYAMA Akira OGAWA
We propose a novel hierarchical transmission method of DCT coefficients using multi-code DS/SS modulation. For low resolution image transmission over noisy channel, an error resilient and graceful degradation technique is necessary. Here, the DCT coefficients are divided into each stratum (a branch of multi-code DS/SS) and transmitted simultaneously through a noisy channel. By assigning an appropriate transmission energy that corresponds to their source energy variances, energy assignment, it is possible to maintain picture quality effectively even in a noisy channel. Analysis of this method was performed using an image data model, 2-D Gauss-Markov random field, which showed that picture quality is maintained even in the noisy channel condition.
Takafumi KAMIMURA Kazuhiko MATSUMOTO
The carbon nanotube field-effect transistors show the hysteresis characteristic in their electrical characteristics owing to the amorphous carbon around the carbon nanotube. It is shown here the reduction of the hysteresis characteristic by the refining process applied repeatedly to the carbon nanotube. Moreover, after the refining processes, the transconductance of carbon nanotube field-effect transistor becomes 2.0 µS the ten times larger than before the refining process. Almost all carbon nanotubes without the refining processes, grown by thermal chemical vapor deposition, show the p type semiconductor characteristics. After the refining processes on the other hand, almost all carbon nanotube show the ambipolar type semiconductor characteristics.