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.

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.

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 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.

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 multi-valued addressing scheme is proposed for a high speed, high packing density memory system. This scheme is a level-multiplex addressing scheme instead of standard time-multiplex addressing scheme, and provides all address signals to the DRAM at the same time without increasing the address pin counts. This scheme makes memory matrix strechable and achieves the low power dissipation using the enhanced partial array activation. The 16 Mb stretchable memory matrix DRAM (16MbSTDRAM) is examined using this addressing design. A power dissipation of 121.5 mW, access time of 30 ns, and 20 pin have been estimated for 3.3 v 16MbSTDRAM with X/Y=15/9 adress configuration. The low power battery-drive memory system for such as the note-book or the handheld-type personal computers can be realized by the STDRAMs with the multi-valued addressing scheme.

It has been reported that the efficiency of a low voltage power supply is improved by replacing diodes in an output-stage with synchronous rectifiers (SR). A SR consists of a bipolar junction transistor with a low-saturation voltage and a current transformer. Although the SR has low offset-voltage, its reverse recovery characteristic is usually poor. In this paper, an RCD circuit which improves the reverse recovery characteristic of the SR is proposed. This circuit is simple, and it is composed of a diode, a capacitor and a resistor. The analysis and the experimental results of the SR with the proposed RCD circuit are presented. The optimum design of the RCD to improve the reverse recovery characteristic of SR is discussed.

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.

Fahlman and Lebiere's (FL) learning algorithm begins with a two-layer network and in course of training, can construct various network architectures. We applied FL algorithm to the same three-layer network architecture as a back propagation (BP) network and compared their generalization properties. Simulation results show that FL algorithm yields excellent saturation of hidden units which can not be achieved by BP algorithm and furthermore, has more desirable generalization ability than that of BP algorithm.

This paper presents a new type of zero-voltage-switched (ZVS) push-pull dc-dc converter with two synchronous rectifiers in the secondary circuit. ZVS is realized using the magnetizing current of the transformer as a constant current source during the commutation. The output voltage is controlled by PWM with a constant switching frequency. The circuit operation is described using equivalent circuits. The steady-state and dynamic characteristics are analyzed and confirmed experimentally.

This article discusses a synthesis procedure of a discrete-time asynchronous neural network whose information is a limit cycle. The synthesis procedure uses a novel connection matrix and can be reduced into a linear epuation. If all elements of desired limit cycles are independent at each transition step, the equation can be solved and all desired limit cycles can be stored. In some experiments, our procedure exhibits much better storing performance than previous ones.

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.

Synchronous clocks are an essential requirement for a variety of distributed system applications. Many of these applications are safety-critical and require fault tolerance. In this paper, a general probabilistic clock synchronization model is presented. This model is uniformly probabilistic, incorporating random message delays, random clock drifts, and random fault occurrences. The model allows faults in any system component and of any type. Also, a new Sliding Window Clock Synchronization Algorithm (SWA) providing increased fault tolerance is proposed. The probabilistic model is used for an evaluation of SWA which shows that SWA is capable of tolerating significantly more faults than other algorithms and that the synchronization tightness is as good or better than that of other algorithms.

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.

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.

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.

An acoustic echo canceller that also cancels room noise is proposed. This system has an additive (noise reference) input port, and a noise canceller (NC) precedes the echo canceller (EC) in a cascade configuration. The adaptation control problem for the cascaded echo and noise canceller is solved by controlling the adaptation process to match the occurrence of intermittent speech/echo; the room noise is a stationary signal. A simulation shows that adaptation using the NLMS algorithm is very effective for the echo and noise cancellation. Sub-band cancelling techniques are utilized. Noise cancellation is realized with a lower band EC. Hardware is implemented and its performance evaluated through experiments under a real acoustic field. The combination of the EC with NC maintains excellent performance at all echo to room noise power ratios. It is shown that the proposed canceller overcomes the disadvantages traditionally associated with ECs and NSc.

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.

The realization of acoustic inverse filter is often difficult because of the non-minimum phase property and the long time duration of the impulse response of the acoustic enclosure. However, if the signals are divided into a large number of sub-bands, many of the sub-bands are found to be invertible. The invertibility of a sub-band signal depends on the zero distribution of the transfer function in the z-plane. In a multi-microphone system, the transfer functions between the sound source and the mirophones have different zero distributions. The method proposed here, taking advantage of the differences of zero distributions, selects the best invertible microphone in each sub-band, and reconstructs the full band signal by summing up the inverse filtered sub-band signals of the best microphones. The quality of the dereverberated signal using the proposed inverse filtering approach is improved with increasing number of microphones and sub-bands. When seven microphones are used and the number of sub-bands is 513, the quality of the dereverberated speech signals are almost the same with the original ones even when the revergeration time is about one second. The introduction of multi-microphones in addition to sub-band processing provides a new way of dealing with the non-minimum phase problem in deconvolution.

There have been few studies on formal approaches to the specification and realization of asynchronous sequential circuits. For synchronous sequential circuits, an algebraic method is proposed as one of such approaches, but it cannot be applied to asynchronous ones directly. This paper describes an algebraic method of specifying the abstract behavior of asynchronous sequential circuits. We select an daisy chain arbiter as an example of them. In the arbiter, state transitions are caused by input changes, and all the modules do not always make state transitions simultaneously. These are main obstacles to specify it in the same way as sychronous sequential circuits. In order to remove them, we modify the meaning of input in specifications and introduce pseudo state transitions so that we can regard all the modules as if they make state transitions simultaneously. This method can be applied to most of the other asynchronous sequential circuits.