SeongSik LEE Jeong Woo JWA HwangSoo LEE
We propose an improved orthogonal frequency division multiplexing (OFDM) signal detector which uses the minimum mean-square error (MMSE) noise feedback equalization (NFE). The input bit stream is trellis-coded to form OFDM signal blocks and the maximal ratio combining (MRC) is adopted at the receiver in order to improve the performance of the detector. As a result, we obtain significantly improved detection performance compared with the conventional OFDM receivers as follows. Using the proposed MMSE-NFE in the receiver, we can obtain the performance gain of about 1.5 dB to 2 dB in symbol energy to noise power spectral density (Es/No) for Doppler frequencies of fd=20 and 100 Hz, respectively, over the receiver with the MMSE linear equalization (LE) alone at symbol error rate (SER) of about 10-3. With MRC and trellis coding, the performance gain of about 11 dB in Es/No for fd=20 and 100 Hz at SER of about 10-3 is obtained.
Hideki MITSUBAYASHI Atsushi TAKAHASHI Yoji KAJITANI
The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.
In this paper, we introduce a computational mode of a tree transducer called a bi-stage transducer and study its properties. We consider a mapping on trees realized by composition of any sequence of top-down transducers and bottom-up transducers, and call such a mapping a multi-phase tree transformation. We think a multi-phase tree transformation is sufficiently powerful. It is shown that in the case of rank-preserving transducers, a multi-phase tree transformation is realized by a bi-stage transducer.
This paper discusses the largest common similar substructure (in short, LCSS) problem for trees. The problem is, for all pairs of "substructure of A and that of B," to find one of them, denoted by A and B', such that A is most similar to B' and the sum of the number of vertices of A and that of B' is largest. An algorithm for the LCSS problem for unrooted and unordered trees (in short, trees) and that for trees embedded in a plane (in short, Co-trees) are proposed. The time complexity of the algorithm for trees is O (max (ma, mb)2 NaNb) and that for CO-trees is O (mambNaNb), where, ma (mb) and Na (Nb) are the largest degree of a vertex of tree Ta (Tb) and the number of vertices of Ta (Tb), respectively. It is easy to modify the algorithms for enumerating all of the LCSSs for trees and CO-trees. The algorithms can be applied to structure-activity studies in chemistry and various structure comparison problems.
Kunihiko KOZARU Atsushi KINOSHITA Tomohisa WADA Yutaka ARITA Michihiro YAMADA
This paper presents Super-CMOS SRAM process technology that integrates bipolar and CMOS transistors in a chip while adding only one ion implantation step and no lithography mask steps to the conventional CMOS SRAM process. The Super-CMOS SRAM process therefore has the same process cost as the CMOS SRAMs, while it achieves higher access speeds. In order to demonstrate the Super-CMOS SRAM, we have developed a 3.3 V/5 V 256 kb SRAM using 0.4 µm Super-CMOS process technology. By applying bipolar transistors to the sense amplifier circuits, a high-speed access time of 5.8 ns with a 3.0 V power supply is successfully achieved.
A factorization method for a string polynomial called the constant method is proposed. This uses essentially three operations; classification of monomials, gcrd (greatest common right divisor), and lcrm (least common rigth multiple). This method can be applied to string polynomials except that their constants cannot be reduced to zeros by the linear transformation of variables. To factorize such excluded string polynomials, the naive method is also presented, which computes simply coefficients of two factors of a given polynomial, but is not efficient.
Qing-An ZENG Kaiji MUKUMOTO Akira FUKUDA
In this paper, we propose a handoff scheme with two-level priority for the reservation of handoff request calls in mobile cellular radio systems. We assume two types of mobile subscribers with different distributions of moving speed, that is, users with low average moving speed (e.g., pedestrians) and high average moving speed (e.g., people in moving cars). A fixed number of channels in each cell are reserved exclusively for handoff request calls. Out of these number of channels, some are reserved exclusively for the high speed handoff request calls. The remaining channels are shared by both the originating and handoff request calls. In the proposed scheme, both kinds of handoff request calls make their own queues. The system is modeled by a three-dimensional Markov chain. We apply the Successive Over-Relaxation (SOR) method to obtain the equilibrium state probabilities. Blocking probabilities of calls, forced termination probabilities and average queue length of handoff calls of each type are evaluated. We can make the forced termination probabilities of handoff request calls smaller than the blocking probability of originating calls. Moreover, we can make the forced termination probability of high speed handoff request calls smaller than that of the low speed ones. Necessary queue size for the two kinds of handoff request calls are also estimated.
In high performance compilers to process pointer-handling programs, precise pointer alias analysis is useful for the compilers to generate efficient object code. It is well known that most compiler techniques such as data flow analysis, dependence analysis, side effect analysis and optimizations are related to the alias problem. However, without data structure information, there is a limit on the precision of the alias analysis. Even though the automatic data structure detection problem is complex, when pointer manipulation satisfies some restrictions, some data structures can be detected automatically by compilers with some knowledge of aliases. In this paper, we propose an automatic data structure detection method for Pascal and Fortran 90. Linear list, tree and dag data structures are detected. Detected data structure information can be used not only for raising the precision of alias analysis but also for some optimizing techniques for pointer handling programs directly.
Hideharu YAHATA Yoji NISHIO Kunihiro KOMIYAJI Hiroshi TOYOSHIMA Atsushi HIRAISHI Yoshitaka KINOSHITA
A 167-MHz 1-Mbit CMOS synchronous cache SRAM was developed using 0.40-µm process technology. The floor plan was designed so that the address registers are located in the center of the chip, and high-speed circuits were developed such as the quasi latch (QL) sense amplifier and the one-shot control (OSC) output register. To maintain suitable setup and hold time margins, an equivalent margin (EM) design method was developed. 167-MHz operation was measured at a supply voltage of 2.5 V and an ambient temperature of 75. The same margins 1.1 ns of the setup time and hold time were measured for the specifications of a setup time of 2.0 ns and a hold time of 0.5 ns.
SCI (Scalable Coherent Interface) is pointerbased coherent directory scheme for massively parallel multiprocessors. Large message latency is one of the problems with SCI because of its linked list structure: the searching latency of messages could grow as a linear order of the number of processors. In this paper, we focus on a hierarchical architecture to propose a new schemeEST(Extending SCI-Tree), which may reduce the message traffic and also take the advantages of the topology property. Simulation results show that the EST scheme is effective in reducing message latency and communication cost when compared with other schemes.
Jordi CORTADELLA Michael KISHINEVSKY Alex KONDRATYEV Luciano LAVAGNO Alexandre YAKOVLEV
Petrify is a tool for (1) manipulating concurrent specifications and (2) synthesis and optimization of asynchronous control circuits. Given a Petri Net (PN), a Signal Transition Graph (STG), or a Transition System (TS) it (1) generates another PN or STG which is simpler than the original description and (2) produces an optimized net-list of an asynchronous controller in the target gate library while preserving the specified input-output behavior. An ability of back-annotating to the specification level helps the designer to control the design process. For transforming a specification petrify performs a token flow analysis of the initial PN and produces a transition system (TS). In the initial TS, all transitions with the same label are considered as one event. The TS is then transformed and transitions relabeled to fulfill the conditions required to obtain a safe irredundant PN. For synthesis of an asynchronous circuit petrify performs state assignment by solving the Complete State Coding problem. State assignment is coupled with logic minimization and speed-independent technology mapping to a target library. The final net-list is guaranteed to be speed-independent, i.e., hazard-free under any distribution of gate delays and multiple input changes satisfying the initial specification. The tool has been used for synthesis of PNs and PNs composition, synthesis and re-synthesis of asynchronous controllers and can be also applied in areas related with the analysis of concurrent programs. This paper provides an overview of petrify and the theory behind its main functions.
Toshiyuki MIYAMOTO Sadatoshi KUMAGAI
Signal Transition Graphs (STG's) are Petri nets, which were introduced to represent a behavior of asynchronous circuits. To derive logic functions from an STG, the reachability graph should be constructed. In the verification of STG's some method based on an Occurrence net (OCN) and its prefix, called an unfolding, has been proposed. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating sub state space of a given STG using the structural properties of OCN.
Alberto O. ADAN Toshio NAKA Seiji KANEKO Daizo URABE Kenichi HIGASHI Yasumori FUKUSHIMA Soshu TAKAMATSU Shogo HIDESHIMA Atsushi KAGISAWA
A 0.35 µm CMOS process for low-voltage, high-performance applications implemented in an ultra-thin-film SIMOX wafer: Shallow SIMOX, is described. Fully Depleted CMOS devices are realized in a 50 nm thick top Si film. Stable high speed, low-Vth transistors for low-voltage operation were developed by integrating a salicided dual gate process. Short-channel effects are suppressed by a novel channel-drain profile engineering. Low power consumption is achieved by the reduced diffusion capacitance of the SIMOX device and a thick, CMP planarized, intermetal dielectric to reduce metal interconnect capacitance's. Compared with the Bulk-Si CMOS devices, a factor of 1/5 reduction on power dissipation is achieved with this technology. A high ESD strength of 4 kV (HBM) demonstrates the applicability of this technology in advanced high-performance products.
In this paper, we give a concrete example of a 10-bit video rate ADC and introduce the effect of top-down design methodology with analog-HDL from the viewpoint of utilization techniques. First, we explain that analog top-down design methodology can improve chip performance by optimizing the architecture. Next, we concretely discuss the importance of modeling and verification. Verification of the full system does not require extracting all the information for each block at the transistor level in detail. The flexible verification method that we propose can provide good and fast full chip verification. We think analog top-down disign methodology will become increasingly more important from now on because "system-on-chip" requires one chip mixed-signal system LSIs.
Akihiko YASUOKA Kazutami ARIMOTO
The key circuit technologies for future giga-bit/low voltage operating high performance SOI-DRAM is described. Emphasis is made especially on the considerations for ways to overcome floating-body effects in order to obtain very long static/dynamic data retention time. A new scheme called a super body synchronous sensing scheme is proposed for low voltage operation at 1 V.
Jae-won YANG Shigemasa TAKAI Toshimitsu USHIO Sadatoshi KUMAGAI Shinzo KODAMA
This paper studies stabilization of timed discrete event systems with forcible events. We present an algorithm for computing the region of weak attraction for legal states.
This paper proposes a synthesis method to obtain speed-independent asynchronous circuits directly from signal transition graph (STG) specifications with single cycle signals which can be non-persistent and have free-choice operations. The resulting circuits are implemented with basic gates and asynchronous latches, and operate correctly under finite but unbounded gate delays and the zero wire delay assumptions. The proposed method introduces 5 types of lock relations to implement a non-persistent STG. A non-persistent STG can be implemented if every non-persistent signal to a signal t is super-locked with t. The resulting circuits are optimized by extracting of literals, mapping onto asymmetric C-elements, etc. Experimental results show that the proposed synthesis method outperforms the existing synthesis systems such as SYN and SIS.
Toshiaki IWAMATSU Takashi IPPOSHI Yasuo YAMAGUCHI Kimio UEDA Koichiro MASHIKO Shigeto MAEGAWA Yasuo INOUE Tadashi HIRAO Tdashi NISHIMURA Akihiko YASUOKA
A high-speed silicon-on-insulator (SOI) of a 1/8 frequency divider and a 64-bit adder were realized using an optimized gate-overlapped LDD and a self-aligned titanium silicide (TiSi2) source-drain structure. The advantages of the delay time and power consumption were analyzed by circuit simulation. The maximum operation frequency of the SOI divider is 2.9 GHz at 3.3 V. The SOI divider operates about 1.6 times faster than the bulk-Si divider. The power consumption of the SOI divider at the maximum operating frequency is about 60% of that of the bulk divider. On the other hand, the speed of the SOI adder is 1.9 nsec at 3.3 V. The SOI adder speed is about 1.3 times faster than the bulk adder. The power consumption of the SOI adder is about 80% of that of the bulk divider. It was found that the high speed, low power features of the SOI divider were due to the pass transistor which had low junction capacitance and little substrate bias effects, in addition to the low wiring capacitance and low fanout capacitance compared to the bulk adder. As a result, it is suggested that SOI circuits using pass transistor have a potential for GHz level systems and it is expected they will be applied to handy communication systems and portable computers used in the multimedia era.
Peifang ZHOU Oliver W. W. YANG
This paper investigates the problem of constructing a logical multicasting tree which dispatches data to multiple destinations according to their bandwidth requirements. An optimization problem is formulated to minimize the maximum delay between a sender and multiple receivers. An algorithm of finding the optimum branching locations is presented. Performance analysis from the closed queueing network theory is given to evaluate a multicasting tree network based on this proposed algorithm.
The reconstruction of 3-D moving images from transmitted parameters describing position, attitude and shape variation of objects in a virtual 3-D space has been studied as an application of three dimensional (3-D) image communication. The shape information was obtained from a database that was built in advance. Since an appropriate database of 3-D object shapes needs to be developed, efficient storage of the shape data of the actual objects might become a key technology. This paper proposes an efficient entropy coding method of voxel map data obtained with shape measuring equipment. The proposed method converts the voxel map data into an octree and encodes their node information with conditional probability on the state of neighbor nodes sequentially, beginning with the upper hierarchy level. This method has the property of being able to extract information up to a given arbitrary hierarchy level because of its hierarchical characteristic. For implementation, two methods are proposed for reducing the large number of contexts, one uses 3-D isotropism, the other uses sample statistics. The experimental coding results using several sample data sets show that the proposed method can reduce the information volume by about 20% in comparison to the ordinary method using unconditional entropy. The binary voxel map of 512512512 can be represented by approximately 680 kbits.