Nobuhiko SUGINO Satoshi IIMURO Akinori NISHIHARA Nobuo FUJII
In this paper, DSPs, of which memory addresses are pointed by special purpose registers (address registers: ARs), are assumed, and methods to derive an efficient memory access pattern for those DSPs proposed. In such DSPs, programmers must take care for efficient allocation of memory space as well as effective use of registers, in order to derive an efficient program in the sense of execution period. In this paper, memory addresses and AR update operations are modeled by an access graph, and a novel memory allocation method is presented. This method removes cycles and forks in a given access graph, and decides an address location of variables in memory space with less overhead. In order to utileze multiple ARs, methods to assign variables into ARs are investigated. The proposed methods are applied to the compiler for DSP56000 and are proved to be effective by generated codes for several examples.
This paper proposes a fast timing recovery method with a decision feedback equalizer for baudrate sampling. The proposed method features two special techniques. The first one is for coarse estimation of the sampling phase. Internal signals of the oversampled analog-to-digital converter at different phases are directly taken out for parallel evaluation. The second technique provides fine tuning with a phase-modification stepsize which is adaptively controlled by the residual intersymbol interference. Simulation results by a full-duplex digital transmission system with a multilevel line code show superiority of the proposed method. The coarse timing estimation and the fine tuning reduce 75% and 40% of the time required by the conventional method,respectively. The overall saving in timing recovery is almost 60% over the conventional method. The proposed method could easily be extended to other applications with a decision feedback equalizer.
Fabrizio LOMBARDI Nohpill PARK Susumu HORIGUCHI
This paper proposes new algorithms for diagnosing (detection, identification and location) baseline multistage interconnection networks (MIN) as one of the basic units in a massively parallel system. This is accomplished in the presence of single and multiple faults under a new fault model. This model referred to as the geometric fault model, considers defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a fault corresponds to a physical bridge fault between two connections). It is shown that this type of fault affects the correct geometry of the network, thus requiring a different testing approach than previous methods. Initially, an algorithm which detects the presence of bridge faults (both in the single and multiple fault cases), is presented. For a single bridge fault, the proposed algorithm locates the fault except in an unique pathological case under which it is logically impossible to differentiate between two equivalent locations of the fault (however, the switching element affected by this fault is uniquely located). The proposed algorithm requires log2 N test vectors to diagnose the MIN as fault free (where N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 log2 N tests and terminates when multiple bridge faults are detected. Subsequently, an algorithm which locates all bridge faults is given. The number of required test vectors is O(N). Fault location of each bridge fault is accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are given.
Yoshinobu GAMACHI Tomoaki OHTSUKI Hideyuki UEHARA Iwao SASASE
The performance of direct-detection optical synchronous code-division multiple-access (CDMA) systems using pulse position modulation (PPM) signaling (PPM/CDMA) with interference canceller is analyzed. In optical CDMA systems, it is known that the maximum number of simultaneous users in CDMA systems is limited by the maximum tolerable interference among users. If the receiver is able to estimate this interference and cancel or reduce its effect, the capacity of CDMA systems can be increased and the system performance can be improved. There are some ways to increase the system performance, that is, using PPM and interference canceller. However, the system using both PPM and interference canceller has not been analyzed. In this paper, the upper bound on the bit error probability of optical synchronous PPM/CDMA systems with interference canceller is derived, and the bit error probability of optical synchronous PPM/CDMA systems is evaluated under the assumption of number-state light field where the background noise is negligible. We compare the bit error probability of the optical synchronous PPM/CDMA systems with interference canceller to that of the optical synchronous PPM/CDMA systems without interference canceller and to those of optical synchronous OOK/CDMA systems with and without interference canceller. We show that optical synchronous PPM/CDMA systems with interference canceller have better bit error probability performance.
Yasuyoshi HORIBATA Hiroshi OIKAWA
Several major aircraft accidents have been attributed to low-altitude wind shears, which are normally caused by microbursts or gust fronts. Terminal Doppler Weather Radar (TDWR) systems are being installed near major airports for the detection of low-altitude wind shears. In order to develop a TDWR system further, low-altitude wind shears were numerically simulated in this study. The basic equations, which contain prognostic equations for air velocity, pressure, temperature, water vapor, and rainwater, were solved using a finite difference scheme. A terrain-following coordinate transformation was employed to simulate terrain effects. The simulation results are presented in this paper.
Sadayuki OHKUMA Hiroshi ICHIKAWA Seigo YUKUTAKE Hitoshi ENDO Shuichi KUBOUCHI
A GTL/LV-CMOS interfaced 1 M bit(32k words 36bits/64k words18bits) BiCMOS cache SRAM is designed within a 5.65 10.54mm2 chip size. The process is 0.4µm BiCMOS with 4 poly-Si layers, 3 Metal layers, and TFT memory cells(2.66 4.94µm2). The late write operation is newly adopted. The late write operation method improvements make the fast access time 6 ns and the shorter cycle time 5 ns.
Toru WAKAHARA Akira SUZUKI Naoki NAKAJIMA Sueharu MIYAHARA Kazumi ODAKA
This paper describes an on-line Kanji character recognition method that solves the one-to-one stroke correspondence problem with both the stroke-number and stroke-order variations common in cursive Japanese handwriting. We propose two kinds of complementary algorithms: one dissolves excessive mapping and the other dissolves deficient mapping. Their joint use realizes stable optimal stroke correspondence without combinatorial explosion. Also, three kinds of inter-stroke distances are devised to deal with stroke concatenation or splitting and heavy shape distortion. These new ideas greatly improve the stroke matching ability of the selective stroke linkage method reported earlier by the authors. In experiments, only a single reference pattern for each of 2,980 Kanji character categories is generated by using training data composed of 120 patterns written carefully with the correct stroke-number and stroke-order. Recognition tests are made using the training data and two kinds of test data in the square style and in the cursive style written by 36 different people; recognition rates of 99.5%, 97.6%, and 94.1% are obtained, respectively. Moreover, comparative results obtained by the current OCR technique as applied to bitmap patterns of on-line character data are presented. Finally, future work for enhancing the stroke matching approach to cursive Kanji character recognition is discussed.
Yukihiro HAMADA Feng BAO Aohan MEI Yoshihide IGARASHI
A directed graph G = (V,E) is called the n-rotator graph if V = {a1a2
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,
Tadao KASAMI Toru FUJIWARA Yoshihisa DESAKI
In this paper cosets of the second order Reed-Muller code of length 2m, denoted RMm,2, in the third order Reed-Muller code of the same length, denoted RMm,3, are studied. The set of cosets, RMm,3/RMm,2 is partitioned into blocks. Two cosets are in the same block, if and only if there is a transformation in the general linear group by which one coset is transformed into the other. Two cosets in the same block have the same weight distribution. For the code length less than or equal to 128, the representative coset leader of each block is presented and the weight distribution of cosets in the block is computed. By using these results, the extended code of a cyclic code of length 128 between RM7,2 and RM7,3 can be decomposed into a set of cosets in RM7,3/RM7,2, and its weight distribution can be derived. Several cyclic codes to length 127 are shown to be equivalent and some new linear unequal error protection codes are found.
Masahiro GESHIRO Toshiaki KITAMURA Tadashi YOSHIKAWA Shinnosuke SAWA
A two-waveguide tapered velocity coupler is presented for a variable divider of optical beams. The coupler consists of one tapered slab waveguide in dimension and the other slab waveguide with a constant film thickness. It is assumed that the device is fabricated on a LiNbO3 substrate, with a push/pull external electric field parallel with the optic axis applied only in the film regions of the coupler. Various numerical simulations through the finite difference beam propagation analysis show that a wide range of dividing ratios from - 15 dB to 15 dB or more can be achieved with considerably small values of driving-voltage electrode-length product and that the dividing characteristics are stable over a wide range of frequencies.
In this paper, we give an algorithm which, given a set F of at most (n - 1) - k faulty nodes, and two sets S = {s1,..., sk} and T = {t1,..., tk}, 1 k n - 1, of nonfaulty nodes in n-dimensional star graphs Gn, finds k fault-free node disjoint paths si tji, where (j1,..., jk) is a permutation of (1,..., k), of length at most d(Gn) + 5 in O(kn) optimal time, where d(Gn) = 3(n-1)/2 is the diameter of Gn.
Yoshimichi WATANABE Takehiro TOKUDA
We present two efficient attribute evaluator construction methods for a wide subclass of L-attributed grammars by enumeration of attributed items during one-pass bottom-up parsing. We have already proposed a construction method of a parser/evaluator for the subclass of L-attributed grammar. However the evaluator produced by our previous method uses a great number of attributed items to evaluate all attributes of a given input string. In this paper we propose two generalized methods to reduce the number of attributed itmes used in attribute evaluation. Our methods allow us to evaluate all attributes taking advantage of the use of available lookahead information.
Shousei YOSHIDA Akihisa USHIROKAWA
This paper describes a CDMA cellular system based on adaptive interference cancellation (CDMA-AIC) with a large capacity. In the CDMA-AIC, each base station employs a single-user type adaptive interference canceller (AIC), which consists of a fractionally chip-spaced code-orthogonalizing filter (COF) and a coherent detector. The AIC adaptively removes power-dominant multiple-access interferences (MAIs) in the cellular system, regardless of whether they are intra-cell interferences or inter-cell interferences, without any information about them, such as spreading codes, signal received timings and channel parameters. Evaluation under the multiple-cell environment demonstrates that the reverse link capacity of the CDMA-AIC with QPSK modulation is 3.6 times as large as the capacity of the CDMA without MAI cancellation. Further, the capacity is less sensitive to transmission power control errors than that of the conventional CDMA systems.
Hidekazu MURATA Atsushi FUJIWARA Susumu YOSHIDA
Co-channel interference is a major factor limiting spectral efficiency of a cellular radio system. The trellis-coded co-channel interference canceller (TCC) leading to the significant increase of traffic capacity of a cellular system has been proposed. In this scheme, a maximum-likelihood sequence estimation implemented with the Viterbi algorithm is extended to estimate both desired signal and co-channel interference, and combined with trellis-coded modulation to enhance the co-channel interference cancelling capability. The complexity of TCC grows exponentially with the channel memory and the constraint length of the trellis encoder. In this paper, two reduced-state sequence estimation algorithms, namely, the delayed decision feedback sequence estimation and the M-algorithm, are applied to TCC and their performance is compared. In addition, effective trellis coded modulation schemes to reduce the computational complexity are proposed. The performance of these schemes is examined through simulations, and compared to that of a conventional interference canceller.
Kiyoyasu MARUYAMA Chawalit BENJANGKAPRASERT Nobuaki TAKAHASHI Tsuyoshi TAKEBE
An adaptive algorithm for a single sinusoid detection using IIR bandpass filter with parallel block structure has been proposed by Nishimura et al. However, the algorithm has three problems: First, it has several input frequencies being impossible to converge. Secondly, the convergence rate can not be higher than that of the scalar structure. Finally, it has a large amount of computation. In this paper, a new algorithm is proposed to solve these problems. In addition, a new structure is proposed to reduce the amount of computation, in which the adaptive control signal generator is realized by the paralel block structure. Simulation results are given to illustrate the performance of the proposed algorithm.
Fujihiko MATSUMOTO Yukio ISHIBASHI
According as the fine LSI process technique develops, the technique to reduce power dissipation of high-frequency integrated analog circuits is getting more important. This paper describes a design of high-frequency integrator with low power dissipation for monolithic leapfrog filters. In the design of the conventional monolithic integrators, there has been a great dfficulty that a high-frequency integrator which can operate at low supply voltage cannot be realized without additional circuits, such as unbalanced-to-balanced conversion circuits and common-mode feedback circuits. The proposed integrator is based on the Miller integrator. By a PNP current mirror circuit, high CMRR is realized. However, the high-frequency characteristic of the integrator is independent of PNP transistors. In addition, it can operate at low supply voltage. The excess phase shift of the integrator is compensated by insertion of the compensation capacitance. The effectiveness of the proposed technique is confirmed by PSPICE simulation. The simulation results of the integrator shows that the common-mode gain is efficiently low and the virtual ground is realized, and that moderate phase compensation can be achieved. The simulation results of the 3rd-order leapfrog filter using the integrator shows that the 50 MHz-cutoff frequency filter is obtained. Its power dissipation in operating 2 V-supply voltage is 5.22 mW.
Feng BAO Yoshihide IGARASHI Sabine R. OHRING
In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2n/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.
Jufang HE Yohsuke KINOUCHI Hisao YAMAGUCHI Hiroshi MIYAMOTO
A continuous-wave ultrasonic Doppler system using wide field ultrasound transducers was applied to telemeter blood velocity from the carotid artery of exercising subjects. Velocity spectrogram was obtained by Hanning windowed fast Fourier transformation of the telemetered data. Distortion caused by a high-pass filter and transducers in the telemetry system was discussed in the paper. As the maximum Reynolds number in our experiment was 1478 which is smaller than the critical level of 2000, the blood flow should be laminar. Spatial velocity profiles were then reconstructed from the velocity spectrogram. In this paper, we defined a converging index Q of the velocity spectrum to measure the bluntness of the spatial velocity distribution across the blood vessel. Greater Q, the blunter the velocity profile will be. Simulation results for spatial velocity distributions of theoretical parabolic flow and Gaussian-distribution spectra with varied Q value showed that the cut-off effect by a high-pass filter of cut-off frequency fc=200Hz in our system could be ignored when the axial velocity is larger than 0.30 m/s and Q is greater than 2.0. Our experimental results, in contrast to those obtained from phantom systems by us and by Hein and O'Brien, indicate that the distribution of blood velocity is much blunter than previously thought. The Q index exceeded 10 during systole, whereas it was 0.5 in parabolic flow. The peak of Q index lagged behind that of axial blood velocity by approximately 0.02s. The phase delay of the Q index curve might be due to the time needed for the red blood cells to form the non-homogeneous distribution.
Takao YAMAZAKI Yoshihito KONDO Sayuri IGOTA Seiichiro IWASE
We have developed a method to automatically generate a multi-input-adder circuit for an irregular array of partial products. "FASTOOL," an FIR Filter Automatic Synthesis TOOL for an HDL design environment, is proposed for use with this method and with conventional filter coefficient design programs. Filter design from specifications to the structure of Verilog-HDL has been automated. It is possible for a system designer to quickly perform filter LSI optimization by balancing cost and performance.