Masahiro FUJII Tadashi MAEDA Yasuo OHNO Masatoshi TOKUSHIMA Masaoki ISHIKAWA Muneo FUKAISHI Hikaru HIDA
A high speed and low power consumption SCFL circuit design with low supply voltage is proposed. Focusing on the relationship between logic swing and supply voltage, the lower limit for the supply voltage is presented. Theoretical analysis and circuit simulation indicates that the logic swing needs to be optimized to maintain high average gm within the swing. An SCFL D-FF fabricated using a 0.25 µm n-AlGaAs/i-InGaAs HJFET process operates at up to 10 Gbps with power consumption as low as 19 mW at a supply voltage of 1.3 V.
Kiyotaka ATSUMI Shigeru MASUYAMA
We propose a parallel parsing algorithm based on Earley's method, which works in O(log2n) time using O(n4.752) processors on CREW PRAM. This algorithm runs with less number of precessors compared with previously proposed W. Rytter's algorithm.
With increases in the speed of semiconductor devices and integrated circuits, the importance of internal testing with sufficient temporal resolution has been growing. This paper describes recently established electro-optic testing technologies based on pulse lasers and electro-optic crystal probes. Practicability, limitation and future issues are discussed.
This paper presents a parallel move generation of a Chess machine system for achieving the purpose of reducing the number of move generation cycles. The parallel system is composed of five move generation modules which share the move generating cycles to reduce the time of building a game tree. Simulation results show that the proposed parallel move generation architecture takes about half of the number of move generation cycles to build a game tree that is the same as the one built by a sequential move generation module.
Masaki KUMANOYA Toshiyuki OGAWA Yasuhiro KONISHI Katsumi DOSAKA Kazuhiro SHIMOTORI
Various kinds of new architectures have been proposed to enhance operating performance of the DRAM. This paper reviews these architectures including EDO, SDRAM, RDRAM, EDRAM, and CDRAM. The EDO slightly modifies the output control of the conventional DRAM architecture. Other innovative architectures try to enhance the performance by taking advantage of DRAM's internal multiple bits architecture with internal pipeline, parallel-serial conversion, or static buffers/on-chip cache. A quantitative analysis based on an assumption of wait cycles was made to compare PC system performance with some architectures. The calculation indicated the effectiveness of external or on-chip cache. Future trends cover high-speed I/O interface, unified memory architecture, and system integrated memory. The interface includes limited I/O swing such as HSTL and SSTL to realize more than 100MHz operation. Also, Ramlink and SyncLink are briefly reviewed as candidates for next generation interface. Unified memory architecture attempts to save total memory capacity by combining graphics and main memory. Advanced device technology enables system integration which combine system logic and memory. It suggests one potential direction towards system on a chip in the future.
For the purpose of automatic speech recognition, language models (LMs) are used to predict possible succeeding words for a given partial word sequence and thereby to reduce the search space. In this paper several kinds of stochastic language models (SLMs) are evaluated-bigram, trigram, hidden Markov model (HMM), bigram-HMM, stochastic context-free grammar (SCFG) and hand-written Bunsetsu Grammar. To compare the predictive power of these SLMs, the evaluation was conducted from two points of views: (1) relationship between the number of model parameters and entropy, (2) predictive rate of succeeding part of speech (POS) and succeeding word. We propose a new type of bigram-HMM and compare it with the other models. Two kinds of approximations are tried and examined through experiments. Results based on both of English Brown-Corpus and Japanese ATR dialog database showed that the extended bigram-HMM had better performance than the others and was more suitable to be a language model.
Jianliang XU Katsushi INOUE Yue WANG Akira ITO
This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.
Seiichiro TANI Kiyoharu HAMAGUCHI Shuzo YAJIMA
An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.
Hiroyoshi YAMADA Yoshio YAMAGUCHI Masakazu SENGOKU
A new superresolution technique is proposed for high-resolution estimation of the scattering analysis. For complicated multipath propagation environment, it is not enough to estimate only the delay-times of the signals. Some other information should be required to identify the signal path. The proposed method can estimate the frequency characteristic of each signal in addition to its delay-time. One method called modified (Root) MUSIC algorithm is known as a technique that can treat both of the parameters (frequency characteristic and delay-time). However, the method is based on some approximations in the signal decorrelation, that sometimes make problems. Therefore, further modification should be needed to apply the method to the complicated scattering analysis. In this paper, we propose to apply a time-domain null filtering scheme to reduce some of the dominant signal components. It can be shown by a simple experiment that the new technique can enhance estimation accuracy of the frequency characteristic in the Root-MUSIC algorithm.
The coupling response of an external transient electromagnetic field to a transmission line is considered. An experiment has been conducted to verify the line equations for a transmission line excited externally by a transient near field. The model field is generated by a monopole antenna installed in the vicinity of the transmission line and driven by a step waveform. The waveform is analyzed into discrete spectrum components using a Fourier transform. The frequency-domain field components affecting the transmission line are estimated by the moment method, and then the induced frequency-domain voltage at the terminal load is converted into a time-domain voltage using an inverse Fourier transform. Comparison between the measured and the computed values provides verification of the line equations. The coupling mechanism is discussed from the experimental results. It seems equivalently that the transmission line picks up the field, generated at the feed point and the top point of the monopole antenna, at both terminal ends.
Zheng TANG Yuichi SHIRATA Okihiko ISHIZUKA Koichi TANNO
A calibrating analog-to digital (A/D) converter employing a T-Model neural network is described. The T-Model neural-based A/D converter architecure is presented with particular emphasis on the elimination of local minimum of the Hopfield neural network. Furthermore, a teacher forcing algorithm is presented and used to synthesize the A/D converter and correct errors of the converter due to offset and device mismatch. An experimental A/D converter using standard 5-µm CMOS discrete IC circuits demonstrates high-performance analog-to-digital conversion and calibrating.
It has become very important to study the lightning surges that flow into telecommunications equipment because of the increased use of circuits susceptible to excess voltage. This paper reports for the first time simultaneous measurements of distributed lightning current at many positions in a mountain-top radio relay station caused by natural direct lightning strikes. More than 90% of the direct lightning current flowed from the lightning rod to the ground through building structural components such as antenna tower legs, waveguides, and so on, with the high frequency components of the lightning current tending to flow into the outside parts of those structural components. And then, 25 to 43 % of the lightning current flowed out again to outside telecommunications cables and power lines because the lightning current raised the station's ground potential. Based on these measurements, to help predict lightning current which is dangerous to telecommunications equipment, lightning current occurrence probabilities at the waveguide and cables were estimated by analyzing the distribution ratios between the current in those components.
This paper proposes a mutual exclusion method that is unified for the parallel and distributed systems. The method partially serializes requests into partial queues of requests, which are next totally serialized into a main queue. A request in the main queue is authorized to enter the critical section (CS) when the request receives the privilege token from the previous request in the queue. In the distributed system of N sites that each is a parallel system, mutual exclusion is performed by cooperation of two algorithms based on the same method. The algorithm for the distributed system works on a logical network (that is a directed tree) of S ( N) sites. The algorithm for each site produces a local-main queue of requests. The chunk of requests in the local queue is concatenated at a time to the partial queue of the distributed system. The the cost of mutual exclusion -- the number of intersite messages required per CS entry -- is reduced to O(1) (between 0 and 3).
Eiji OKAMOTO Wayne AITKEN George Robert BLAKLEY
Polynomials are called permutation polynomials if they induce bijective functions. This paper investigates algebraic properties of permutation polynomials over a finite field, especially properties associated with permutation cycles. A permutation polynomial has a simple structure but good randomness properties suitable for applications. The cycle structure of permutations are considered to be related to randomness. We investigate the algebraic structure from the viewpoint of randomness. First we show the relationship between polynomials and permutations using a matrix equation. Then, we give a general form of a permutation polynomial corresponding to a product C1C2
Qian Ping GU Satoshi OKAWA Shietung PENG
In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s1,
A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees Ta and Tb are OT (N2aN2a), OT(maNaN2b) and OT(mambNaNb), respectively, where Na(Nb) and ma(mb) are the number of vertices in tree Ta(Tb)and the maximum degree of a vertex in Ta(Tb), respectively. The space complexities of these methods are OS(NaNb).
Over the past few years, many industrial processes have switched to electrical processes from conventional fossil fuel as a primary energy source, since electricity can be transmitted more economically than the transport of fossil fuels, as well as less pollution problems and labour- and spacesaving nature. For the environmental protections, ozone generation for water treatments, and decomposition of pollution gases such as SOx, NOx, COx, etc., by high pressure gas discharge processes become an important research subject. However, due to the early stage of development, the EMC problem is not yet well considered. In this review, we try to address the EMC problem in the various atmospheric pressure gas discharge processing techniques and identify future needs of research.
Nobuo FUNABIKI Seishi NISHIKAWA
A clique of a graph G(V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time energy-descent optimization algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that RaCLIQUE, the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.
Induced noises from breaking contact arc discharge and sliding contact discharge of dc motor are measured by pick up coil and current probe. Statistical properties, amplitude distribution probability (APD), of induced noise waveform are analyzed by simple method using intermediate frequency of spectrum analyzer. It is shown that APD characteristics can be used to estimate statistical characteristics and peak value of induced noise. Simulation model of the noise made by the combination of Gaussian noise is mentioned. The model called the composite noise generator (CNG) can be good fit to the real characteristics of both noises from breaking arc and dc motor. Applications of the CNG for noise filter using toroidal coil shows that the CNG is useful to realize the test of noise suppression characteristics. What parameters of the CNG should be considered is described for further applications.
Toshiaki KOIZUMI Kumio TAKAHASHI Shun SUZUKI Hideaki SONE Yoshiaki NEMOTO
This paper discusses the design of a small sensing device for EMI measurement which has equivalent characteristics to the absorbing clamp method, and reports the results on evaluation of the device. The device can be applied to the inspection apparatus for products such as power tools to examine conformance to EMI regulations of electromagnetic radiation spectrum. For reducing the scale of the EMI inspection apparatus, new matching circuit being replaced with the absorbing clamp method is adopted in the sensing device. Length of the sensing device is smaller than one twelfth of a wavelength of the measuring frequency in order to regard the sensing device as a concentrated constant circuit. The matching circuit is a resonant circuit which consists of a coaxial coupled transformer and a variable capacitor, and the transformer is a spiral copper tube in which a pair of AC power line wires passes. Resonant frequency of the circuit is tuned to the measuring frequency by adjusting the variable capacitor so that the circuit would terminate the power line by impedance zero. Thus interference current propagating along the power line from a product is absorbed, and observed by means of a VHF current probe which is settled in the matching circuit. A simple circuit for measurement of noise amplitude distribution (NAD) of interference current was developed as well as an equation to estimate quasi-peak value from the NAD. Result of measurement by the sensing device and proposed procedure confirmed good correlation with the standard absorbing clamp method, and deviation was within 3dB. Measurement time was reduced to 25 s per product, and the in-line EMI checker with new sensing device can be employed in a mass production line.