Hiroshi SAWADA Yasuhiko TAKENAGA Shuzo YAJIMA
Binary decision diagrams (BDD's) are graph representations of Boolean functions, and at the same time they can be regarded as a computational model. In this paper, we discuss relations between BDD's and other computational models and clarify the computational power of BDD's. BDD's have the property that each variable is examined only once according to a total order of the variables. We characterize families of BDD's by on-line deterministic Turing machines and families of permutations. To clarify the computational power of BDD's, we discuss the difference of the computational power with respect to the way of reading inputs. We also show that the language TADGAP (Topologically Arranged Deterministic Graph Accessibility Problem) is simultaneously complete for both of the class U-PolyBDD of languages accepted by uniform families of polynomial-size BDD's and the clas DL of languages accepted by log-space bounded deterministic Turing machines. From the results, we can see that the problem whether U-PolyBDD U-NC1 is equivalent to a famous open problem whether DL U-NC1, where U-NC1 is the class of languages accepted by uniform families of log-depth constant fan-in logic circuits.
Pitch frequency is a basic characteristic of human voice, and pitch extraction is one of the most important studies for speech recognition. This paper describes a simple but effective technique to obtain correct pitch frequency from candidates (pitch candidates) extracted by the short-range autocorrelation function. The correction is performed by a neural network in consideration of the time coutinuation that is realized by referring to pitch candidates at previous frames. Since the neural network is trained by the back-propagation algorithm with training data, it adapts to any speaker and obtains good correction without sensitive adjustment and tuning. The pitch extraction was performed for 3 male and 3 female announcers, and the proposed method improves the percentage of correct pitch from 58.65% to 89.19%.
A simple method for separating the dissipation factors associated with both conductor losses and dielectric losses of printed circuit boards in microwave frequencies is presented. This method utilizes the difference in dependence of two dissipation factors on the dimensions of bounded stripline resonators using a single printed circuit board specimen as a center strip conductor. In this method, the separation is made through a procedure involving the comparison of the measured values of the total dissipation factor with those numerically calculated for the resonators. A method, which is based on a TEM wave approximation and uses Green's function and a variational principle, is used for the numerical calculation. Both effective conductivity for three kinds of industrial copper conductor supported with a substrate of polymide film and dielectric loss tangent of the substrates are determined using this method from the values of the unloaded Q measured at the 10 GHz region. Radiation losses from the resonator affecting the accuracy of the separation are discussed, as well as the values of the effective conductivity of metals on the polyimide substrate which is calculated using the above method. The resulting values of the effective conductivity agree with those using the triplateline method within 10%.
Yuzo OHTA Lei GONG Hiromasa HANEDA
Data of system parameters of real systems have some uncertainty and they should be given by sets (or intervals) rather than fixed values. To analyze and design systems contaning such uncertain parameters, it is required to represent and treat uncertainty in data of parameters, and to compute value sets of characteristic polynomials and transfer functions. Interval arithmetic is one of the most powerful tools to perform such subjects. In this paper, Polygon Interval Arithmetic (PIA) on the set of polygons in the complex plane is considered, and the data structure and algorithms to execute PIA efficiently is proposed. Moreover, practical examples are shown to demonstrate how PIA is useful to compute the evaluation of value sets.
Kenichi NAKASHI Hiroyuki SHIRAHAMA Kenji TANIGUCHI Osamu TSUKAHARA Tohru EZAKI
In order to investigate the jitter characteristics of PLLs for practical applications, we have developed a computer simulation program of PLL, which can deal with arbitrary patterns both of data and jitters, as well as a conceivable nonlinearity of the circuit performance. We used a time-domain method, namely, we solved the state equation of a charge pump type PLL with a constant time step. The jitter transfer characteristics of a conventional PLL were calculated for periodic input data patterns with sinusoidal jitters. The result agreed fairly well with the corresponding experiments. And we have revealed that an ordinary PD (Phase Detector), which detects the phase difference between input and VCO signals at only rising edges, shows the folded jitter transfer characteristics at the half of the equivalent frequency of the input signal. This folded jitter characteristics increases the total jitter for long successive '1' or '0' data patterns, because of their low equivalent sampling frequency, and might increase the jitter even for the random data patterns. Based on simulation results, we devised an improved phase detector for PLL having a low jitter characteristics. And we also applied the simulation to an FDD (Frequency Difference Detector) type fast pull-in PLL which we have proposed recently, and obtained that the jitter of it was smaller than that of a conventional PLL by 25% for PRBS (pseudo random bit sequence) NRZ code.
Junghyun HWANG Yoshiteru OOI Shinji OZAWA
An approach to estimate the information of moving objects is described in terms of their kinetic and static properties such as 2D velocity, acceleration, position, and the size of each object for the features of motion snd shape. To obtain the information of motion/shape of multiple objects, an advanced contour matching scheme is developed, which includes the synthesis of edge images and the analysis of object shape with a high matching confidence as well as a low computation cost. The scheme is composed of three algorithms: a motion estimation by an iterative triple cross-correlation, an image synthesis by shifting and masking the object, and a shape analysis for determining the object size. Implementing fuzzy membership functions to the object shape, the scheme gets improved in accuracy of capturing motion and shape of multiple moving objects. Experimental result shows that the proposed method is valid for several walking men in real scene.
Vijaya Gopal BANDI Hideki ASAI
A new efficient waveform relaxation technique based on dynamically overlapped partitioning scheme is presented. This overlapped partitioning method enables the application of waveform relaxation technique to bipolar VLSI circuits. Instead of fixed overlapping, we select the depth of overlapping dynamically based on the sensitivity criteria. By minimizing the overlapped area, we could reduce the additional computational overhead which results from overlapping the partitions. This overlapped waveform relaxation method has better convergence properties due to smaller error introduced at each step compared with standard relaxation techniques. When overlapped partitioning is used in the case of digital circuits, the waveforms obtained after first iteration are nearly accurate. Therefore, by using these waveforms as initial guess waveforms for the second iterations we can reduce Newton-Raphson iterations at each time point.
Masaki ISHIDA Koichi HAYASHI Masakatsu NISHIGAKI Hideki ASAI
This paper describes the relaxation-based algorithms with the dynamic partitioning technique for bipolar circuit analysis. In this technique, a circuit is partitioned dynamically based on the consideration of the operating region of specified bipolar devices. This technique has been used already in the waveform relaxation method. In this paper, the dynamic circuit partitioning technique is implemented in the Iterated Timing Analysis (ITA). First, the dynamic partitioning method and its validity are described. Next, the present ITA is applied to the transient simulation of several digital bipolar circuits and compared with the waveform relaxation method.
This paper presents an optimal filtering algorithm using the covariance information in linear continuous distributed parameter systems. It is assumed that the signal is observed with additive white Gaussian noise. The autocovariance function of the signal, the variance of white Gaussian noise, the observed value and the observation matrix are used in the filtering algorithm. Then, the current filter has an advantage that it can be applied to the case where a partial differential equation, which generates the signal process, is unknown.
This paper discusses a common channel signaling system in which multiple micro-switching systems can converse as though configured like a conventional centralized switching system. A micro-switching system is a switching system whose main functions are integrated on a chip, like a microprocessor. Progress in MOS technology will soon make micro-switching systems possible, and their small scale and economy will allow subscriber switching systems to be distributed closer to subscribers. This will allow shorter subscriber loops, so subscriber networks will be able to reuse existing metallic lines as H1 (1.544/2.048Mb/s)-class subscriber loops. Economical micro-switching systems and reuse of existing network resources will contribute to the establishment H0 (384kb/s)-ISDN, so that every subscriber will be able to enjoy multimedia communications through HO-calls as simply as using present telephones. Four alternative signaling network architectures are examined, classified by arrangement of their signaling transfer junctions and signaling links, and a new signaling system featuring cell-based transfer functions is proposed. This is suitable for a distributed micro-switching-system network in order to minimize the figures of merit, which collectively estimate network cost and signaling delay.
Shigeki AISAWA Kazuhiro NOGUCHI Masafumi KOGA Takao MATSUMOTO Yoshihito AMEMIYA
A very-high-speed ten-neuron analog neural network LSI chip is fabricated for the first time using super self-aligned Si bipolar process technology. The LSI consists of ten neurons and 100 electrically modifiable synaptic weights. The neural network nonlinear mapping function to solve the four-bit parity problem is successfully demonstrated at 150 mega-patterns/sec. The operation speed of this neural network is, to the best of the authors, knowledge, the fastest yet reported.
Masaji YAMASHITA Koichi SHIMIZU Goro MATSUMOTO
To study the biological effects of the ion-current commonly found under ultra-high voltage DC transmission lines, a technique was developed to evaluate the human exposure to the ion-current field. This technique is based on numerical analysis using the boundary element method. The difficulty of handling the space charge in the calculation was overcome by assuming a lumped source ion-current. This technique is applicable to a three-dimensionally complex object such as a human body. In comparison with theoretical values, the accuracy of this technique was evaluated to be satisfactory for our purposes. It was then applied to a human body in an ion-current field. The distribution of the electric field along the body surface was obtained. The general characteristics of the field distribution were essentially the same as in those without space charges. However, it was found that the strength of the field concentration was significantly enhanced by the space charges. Further, the field exposure when a human body was charged by an ion-current was evaluated. As the charged voltage increases, the position of the field concentration moves from a human's head toward his legs. But the shock of micro spark increases. This technique provides a useful tool for the study of biological effects and safety standards of ion-current fields.
This paper presents a mathematical formulation of a data path allocation and floorplanning problem using the mixed integer linear programming, and shows some experimental results. We assume that a data flow graph and the scheduled result are given in advance. The chip area and total wire length are used for the quality measures of the solution for the problem. This method is applied to some examples, and compared with the other method reported previously in the points of the solution and computation time.
Takashi SHIMOTORI Yoshio NIKAWA Shinsaku MORI
A semicylindrical microstrip applicator system is proposed and designed, both for microwave heating and for noninvasive temperature estimation, in application to hyperthermia treatment. The experimental results showed that the system functions both as a heating device and as a means of noninvasive temperature estimation. Therefore, electrical switching of these two functions makes the system realize both heating and temperature estimation. These functions reduce the pain of hyperthermia therapy for patients. The system is constructed of a water-loaded cylindrical applicator. Thus, the whole system can be made compact compared to conventional applicators. This improvement allows for various merits, such as realizing a surface cooling effect and decreased leakage of electromagnetic (EM) waves. When the applicator is set as an array arrangement, the system can be used as a microwave heating device. The penetration depth can be varied by adjusting phases of the EM wave radiated from each applicator. The experimental results at 430 MHz showed that semicylindrical microstrip applicators can be expected to be valid for tumor heating at depths within 55 mm. Moreover, by measuring transmission power between the two applicators, the system can be used to estimate temperature inside the medium. The transmission power which was measured in the frequency domain was converted in the time domain. By such a method, temperature distribution was calculated by solving simple simultaneous primary equations. The results of the temperature estimation show that the number of estimated temperature segments which have an error within 0.5 is 28 out of 36. The system can be easily used as a temperature measuring applicator as well as a heating applicator.
Kazuhiko SHIMADA Keisuke NAKANO Masakazu SENGOKU Takeo ABE
In cellular mobile systems, an alternative approach for a Dynamic Channel Assignment problem is presented. It adaptively assigns the channels considering the cochannel interference level. The Dynamic Channel Assignment problem is modeled on the different cellular system from the conventional one. In this paper, we formulate the rearrangement problem in the Dynamic Channel Assignment and propose a novel strategy for the problem. The proposed algorithm is based on an artificial neural network as a specific dynamical system, and is successfully applied to the cellular system models. The computer simulation results show that the algorithm utilized for the rearrangement is an effective strategy to improve the traffic characteristics.
C-V and I-V characteristics of an n-MOSFET with Si-implanted gate-SiO2 of 50 nm are analyzed by using a test device with large equal channel width and length of 100 µm, and discussed for realizing a large hysteresis window of threshold voltage. Interface trap densities change logarithmically from 31010 to 11012cm2eV1 as the Si-dose at 25 keV increases from zero to 31016cm2. Threshold-voltage changes caused by 25 keV implantaions are as high as 0.2 V. Effective mobilities (subthreshold swings) change from 600 (0.10) to 100 cm2/V
Yasuhiko TAKENAGA Shuzo YAJIMA
An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC1-reducible to REACHABILITY. That is, both of the problems belong to NC2. In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC1-reducible to REACHBILITY.
Hsiao-Jing CHEN Yoshiaki SHIRAI
A method is presented to perform image segmentation by accumulatively observing apparent motion in a long image sequence of a dynamic scene. In each image in the sequence, locations are grouped into small patches of approximately uniform optical flow. To reduce the noise in computed flow vectors, a local image motion vector of each patch is computed by averaging flow vectors in the corresponding patches in several images. A segment contains patches belonging to the same 3-D plane in the scene. Initial segments are obtained in the image, and then an attempt to merge or split segments is iterated to update the segments. In order to remove inherent ambiguities in motion-based segmentation, temporal coherence between the local image motion of a patch and the apprent motion of every plane is investigated over long time. In each image, a patch is grouped into the segment of the plane whose apparent motion is temporally most coherent with the local image motion of the patch. When apparent motions of two planes are temporally incoherent, segments of the planes are retained as individual ones.
Makoto SAKAMOTO Katsushi INOUE Itsuo TAKANAMI
There have been several interesting investigations on the space functions constructed by one-dimensional or two-dimensional Turing machines. On the other hand, as far as we know, there is no investigation about the space functions constructed by three-dimensional Turing machines. In this paper, we investigate about space constructibility by three-dimensional deterministic Turing machines with cubic inputs, and show that the functions log*n and log(k)n, k1, are fully space constructible by these machines.
Mitsuyoshi SUZUKI Hideichi SASAOKA
This paper studies the effect of frequency re-using patterns on the channel capacity in the forward link of orthogonal code division multiple access (CDMA) cellular systems. The received carrier-to-interference ratio (CIR) determined by computer simulation shows that re-using the same frequency channel on every third sector (3-sector layout) provides superior channel capacity than does every-sector re-use (1-sector layout).