Eiji FUJIWARA Masakatsu YOSHIKAWA
Unidirectional/Asymmetric error control codes have extensively been studied, not only from theoretical interest but from application to computer systems or communication systems. Recently, attention has been focused on detecting only d, not all, unidirectional errors, that is, d bits unidirectional error ditecting (d-UED) codes. Borden proposed an optimal nonsystematic d-UED code. This paper shows a new design method for cost-effective self-testing checker for the optimal d-UED code. The checking policy is to check whether condition of the Borden code satisfies or not. The proposed checker includes the parallel weight counter, the comparator and th e modulo adder in which new residue operation is defined and hence this makes the circuit self-testing. These circuits are designed to have all possible input patterns in order to satisfy self-testing property. Finally, the proposed checker has greatly reduced hardware amount compared to the existing one.
This paper relates to a novel algorithm for fast estimation of the coefficients of the adaptive FIR filter. The novel algorithm is derived from a first order IIR filter experssion clarifying the estimation process of the NLMS (normalized least mean square) algorithm. The expression shows that the estimation process is equivalent to a procedure extracting the cross-correlation coefficient between the input and the output of an unknown system to be estimated. The interpretation allows to move a subtraction of the echo replica beyond the IIR filter, and the movement gives a construction with the IIR filter coefficient of unity which forms the arithmetic mean. The construction in comparison with the conventional NLMS algorithm, improves the covergence rate extreamly. Moreover, when we use the construction with a simple technique which limits the term of calculating the correlation coefficient in the beginning of a convergence process, the convergence delay becomes negligible. This is a very desirable performance for acoustic echo canceller. In this paper, double-talk and echo path fluctuation are also studied as the first stage for application to acoustic echo canceller. The two subjects can be resolved by introducing two switches and delays into the evaluation process of the correlation coefficient.
Hirofumi MATSUO Hideki HAYASHI Fujio KUROKAWA Mutsuyoshi ASANO
The characteristics of voltage-resonant dc-dc converters have already been analyzed and described. However, in the conventional analysis, the inductance of the reactor is assumed to be infinity and the loss resistance of the power circuit is not taken into account. Also, in some cases, the averaging method is applied to analyze the resonant dc-dc converters as well as the pwm dc-dc converters. Consequently, the results from conventional analysis are not entirely in agreement with the experimental ones. This paper presents a general design-oriented analysis of the buck-boost type voltage-resonant dc-dc converter in the continuous and discontinuous modes of the reactor current. In this analysis, the loss resistance in each part of the power circuit, the inductance of the reactor, the effective value (not mean value) of the power loss, and the energy-balance among the input, output and internal-loss powers are taken into account. As a result, the behavior and characteristics of the buck-boost type voltage-resonant dc-dc converter are fully explained. It is also revealed that there is a useful mode in the discontinuous reactor current region, in which the output voltage can be regulated sufficiently for the load change from no load to full load and for the relatively large change of the input voltage, and then the change in the switching frequency can be kept relatively small.
Hiroshi INAI Yuji KAMICHIKA Masayuki MURATA Hideo MIYAHARA
Rate-based congestion/flow control is a promising way to achieve high throughput in high speed packet-switching networks. We consider a rate-based congestion control to aim at obtaining high throughput and fair sharing of the communication resources. In the scheme, each intermediate node informs its congestion status to the source node. Two kinds of control packets are used for this mechanism. One (a choke packet) is to throttle the rate and another (a loosen packet) is to allow increase of the rate. The source node initiates transmission with a low rate and increases the rate slowly to avoid a rapid increase of the packet queueing at an intermediate node. When the source node receives a choke packet, it decreases the rate rapidly to relieve congestion as soon as possible. The source node upon receipt a loosen packet increases the rate slowly again. We develop a queueing model to investigate the parameter settings to provide a good performance via simulation. The increasing and decreasing parameters of the rate control function are first investigated in various load conditions. We next examine the effect of the queue-length threshold value for the indication of congestion at the intermediate node. The numerical results indicate that the threshold value should be small to obtain a good performance. We finally introduce a technique which accurately recognizes congestion and inhibits an acceptable queueing of the packets at intermediate nodes.
This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.
Shin'ichi HATAKENAKA Takashi NANYA
Strongly Fault-Secure (SFS) circuits are known to achieve the TSC goal of producing a non-codeword as the first erroneous output due to a fault. Strongly Code-Disjoint (SCD) circuits always map non-codeword inputs to non-codeword outputs even in the presence of faults so long as the faults are undetectable. This paper presents a new generalized design method for the SFS and SCD realization of combinational circuits. The proposed design is simple, and always gives an SFS and SCD combinational circuit which implements any given logic function. The resulting SFS/SCD circuits can be connected in cascade with each other to construct a larger SFS/SCD circuit if each interface is fully exercised.
Bernd FREISLEBEN Hans-Henning KOCH Oliver THEEL
In this paper we present and analyze multi-level quorum schemes for maintaining the consistency of replicated data in the presence of concurrency and failures in a large distributed environment. The multi-level quorum method operates on a logical hierarchy of the nodes in the network and applies well known flat voting algorithms for replicated data concurrency control in a layered fashion. We show how the number of hierarchy levels, the number of logical entities per level and the voting algorithms used on each level affect the costs and the degree of availability associated with a wide range of multi-level quorum schemes. The results of the analysis are used to provide guidelines for designing the most suitable multi-level quorum strategy for a given application scenario. Comparative performance measurements in a simulated network are presented to illustrate the properties of multi-level approaches when some of the assumptions of the analytical investigation do not hold.
Tsuyoshi USAGAWA Hideki MATSUO Yuji MORITA Masanao EBATA
This paper proposes a new adaptive algorithm of the FIR type digital filter for an acoustic echo canceller and similar application fields. Unlike an echo canceller for line, an acoustic echo canceller requires a large number of taps, and it must work appropriately while it is driven by colored input signal. By controlling the filter tap length and updating filter coefficients multiple times during a single sampling interval, the proposed algorithm improves the convergence characteristics of adaptation even if colored input signal is introduced. This algorithm is maned VT-LMS after variable tap length LMS. The results of simulation show the effectiveness of the proposed algorithm not only for white noise but also for colored input signal such as speech. The VT-LMS algorithm has better convergence characteristice with very little extra computational load compared to the conventional algorithm.
Kiyohito FUJII Masato ABE Toshio SONE
This paper proposes a method to estimate the waveform of a specified sound source in a noisy and reverberant environment using a sensor array. Previously, we proposed an iterative method to estimate the waveform. However, in this method the effect of reflection sound reduces to 1/M, where M is the number of microphones. Therefore, to solve the reverberation problem, we propose a new method using inverse filters of the transfer functions from the sound sources to each microphone. First, the transfer function from each sound source to each microphone is measured by the cross-spectrum technique and each inverse filter is calculated by the QR method. Then the initially estimated waveform of a sound source is the averaged signal of the inverse filter outputs. Since this waveform still contains the effects of the other sound sources, the iterative technique is adopted to estimate the waveform more precisely, reducing the effects of the other sound and the reflection sound. Some computer simulations and experiments were carried out. The results show the effectiveness of our method.
Mitsuo OHTA Noboru NAKASAKO Kazutatsu HATAKEYAMA
This paper describes a new trial of dynamical parameter estimation for the actual room acoustic system, in a practical case when the input excitation is polluted by a background noise in contrast with the usual case when the output observation is polluted. The room acoustic system is first formulated as a discrete time model, by taking into consideration the original standpoint defining the system parameter and the existence of the background noise polluting the input excitation. Then, the recurrence estimation algorithm on a reverberation time of room is dynamically derived from Bayesian viewpoint (based on the statistical information of background noise and instantaneously observed data), which is applicable to the actual situation with the non-Gaussian type sound fluctuation, the non-linear observation, and the input background noise. Finally, the theoretical result is experimentally confirmed by applying it to the actual estimation problem of a reverberation time.
Kazuhiko IWASAKI Shou-Ping FENG Toru FUJIWARA Tadao KASAMI
MISRs are widely used as signature circuits for VLSI built-in self tests. To improve the aliasing probability of MISRs, multiple MISRs and M-stage MISRs with m inputs are available, where M is grater than m. The aliasing probability as a function of the test length is analyzed for the compaction circuits for a binary symmetric channel. It is observed that the peak aliasing probability of the double MISRs is less than that of M-stage MISRs with m inputs. It is also shown that the final aliasing probability for a multiple MISR with d MISRs is 2dm and that for an M-stage MISR with m imputs is 2M if it is characterized by a primitive polynomial.
A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.
This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.
Masashi HASHIMOTO Yukio FUKUDA Shigeki ISHIBASHI Ken-ichi KITAYAMA
The newly developed GaAs-pin/SLM, that is structured with a GaAs-pin diode photodetector and a ferroelectric liquid crystal as the light phase modulator, shows the accumulative thresholding characteristic against the optical energy of the write-in pulse train. We experimentally investigate this characteristic and discuss its applications to optical parallel processings.
Masao IZUMI Takeshi ASANO Kunio FUKUNAGA Hideto MURATA
In this pater, we propose a method for matching of two images (stereo, motion stereo, etc.) using relaxation. We have already proposed an algebraic expression of line images using unit vectors, and matching method based on similarity measure between two image graphs. This similarity measure of images is insensitive to scaling, rotation, gray level modification and small motion between the two images in the case when we examine image registration or image matching. The approach based on the line structural similarity results in high rate of correspondence between nodes of the two images. In order to obtain higher rate of correspondence, we introduce a relaxation method when examine the degree of similarity between the two images. Our relaxation method improves a relational similarity of correspondence between two image graphs in an iterative manner. The relational similarity is defined as a correct likelihood of correspondence between nodes in consideration of connective relationship of the image graphs. Finally, we show several experimental results which confirm effectiveness of our approach.
Norihiko TANAKA Takakazu KUROKAWA Takashi MATSUBARA Yoshiaki KOGA
This paper proposes a new fault tolerant intercommunication scheme for real-time operations and three new interconnection networks to construct a fault tolerant multi-processor system for pipeline processings. The proposed intercommunication scheme using bank memory switching technique has an advantage to make a fault tolerant pipeline system so that it can detect any failure caused in a processing element of the system. In addition, it can overcome conventional problems caused in interconnection circuits to flow data with one way direction such as a pipeline processing.
Haruyuki HARADA Takashi TAKENAKA Mitsuru TANAKA
An efficient reconstruction algorithm for diffraction tomography based on the modified Newton-Kantorovich method is presented and numerically studies. With the Fréchet derivative obtained for the Helmholtz equation, one can derive an iterative formula for getting an object function, which is a function of refractive index of a scatterer. Setting an initial guess of the object function to zero, the pth estimate of the function is obtained by performing the inverse Fourier transform of its spectrum. Since the spectrum is bandlimited within a low-frequency band, the algorithm does not require usual regularization techniques to circumvent ill-posedness of the problem. For numerical calculation of the direct scattering problem, the moment method and the FFT-CG method are utilized. Computer simulations are made for lossless and homogeneous dielectric circular cylinders of various radii and refractive indices. In the iteration process of image reconstruction, the imaginary part of the object function is set to zero with a priori knowledge of the lossless scatterer. Then the convergence behavior of the algorithm remarkably gets improved. From the simulated results, it is seen that the algorithm provides high-quality reconstructed images even for cases where the first-order Born approximation breaks down. Furthermore, the results demonstrate fast convergence properties of the iterative procedure. In particular, we can successfully reconstruct the cylinder of radius 1 wavelength and refractive index that differs by 10% from the surrounding medium. The proposed algorithm is also effective for an object of larger radius.
Toshiro SATO Michio HASEGAWA Tetsuhiko MIZOGUCHI Masashi SAHASHI
A newly developed planar inductor and its application to dc-dc converters are described. The planar inductor consists of a planar spiral coil and soft magnetic sheets, it has a small size (11110.8mm), 33µH inductance and a maximum quality factor of 14. The step down chopper dc-dc converter has been developed by using planar inductor, which has small size (20154mm), 5V-2W typical output and output power/volume ratio of 1.7W/cc. The switching converter can be miniaturized by using the planar inductor.
Seiichi YAMADA Etsuo OTSUKI Tsutomu OTSUKA
Ac resistivity and power loss values for Mn-Zn ferrite material have been investigated by electrical and magnetic measurements. The ac resistivity shows an inductive dependency on frequency for the low dc resistive samples or for highly dc resistive ones at high temperature, while a capacitive dependency on frequency was observed for the highly resistive materials at the room temperature. These phenomena were interpreted by the dependence of ac resistivity on the dc resistivity, complex permeability and complex permittivity. The dependency of the power losses on the dc resistivity, temperature and frequence were also examined with analysis of power loss term. Dividing the power loss into hysteresis loss and eddy current loss, the frequency dependence of the eddy current loss was found to vary with the magnitude of the dc resistivity as follows: The eddy current loss of low dc resistive materials depends on the dc resistivity. On the other hand, the eddy current loss for high resistive materials is determined by the ac resistivity, contributed from dielectric loss.
Yumi TAKIZAWA Shinichi SATO Keisuke ODA Atsushi FUKASAWA
This paper describes a nonstationary spectral analysis method and its application to prognosis and diagnosis of automobiles. An instantaneous frequency spectrum is considered first at a single point of time based on the instantaneous representation of autocorrelation. The spectral distortion is then considered on two-dimensional spectrum, and the filtering is introduced into the instantaneous autocorrelations. By the above procedure, the Instantaneous Covariance method (ICOV), the Instantaneous Maximum Entropy Method (IMEM), and the Wigner method are shown and they are unified. The IMEM is used for the time-dependent spectral estimation of vibration and acoustic sound signals of automobiles. A multi-dimensional (M-D) space is composed based on the variables which are obtained by the IMEM. The M-D space is transformed into a simple two-dimensional (2-D) plane by a projection matrix chosen by the experiments. The proposed method is confirmed useful to analyze nonstationary signals, and it is expected to implement automatic supervising, prognosis and diagnosis for a traffic system.