Search

A connected-(r, s)-out-of-(m, n): F system, which is defined as a two-dimensional version of a consecutive-k-out-of-n: F system, is used as a reliability evaluation model for a sensor system, an X-ray diagnostic system, a pattern search system, etc. This system consists of m × n components arranged like an (m, n) matrix and fails if the system has an (r, s) submatrix that contains all failed components. This paper presents a method of obtaining reliability of a connected-(r, s)-out-of-n: F system recursively. Some numerical examples are presented to show the relationship between component reliability and system reliability. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(1): 27–35, 1997 [ABSTRACT FROM AUTHOR]

With recent developments in integrated circuit (IC) technology and digital communication networks, the demand for efficient and high-quality conversion, transmission, and coding of high-definition images has greatly increased. For this purpose, construction of higher parallel two-dimensional (2-D) digital filtering systems based on efficient parallel processing algorithms of 2-D digital filters is necessary. This paper proposes a systolic array implementation for separable denominator 2-D state-space digital filters by applying block processing based on the reduced-dimensional decomposition. First, the 2-D state-space digital filter using reduced-dimensional decomposition is described. Next, the 2-D state equations are derived by applying block processing and its properties are shown. As a result, the reduced-dimensional decomposition suitable for systolic array implementation is shown. Then the systolic array implementation corresponding to derived state equations is proposed and its effectiveness is evaluated. As a result, it is shown that this implementation can have not only extremely high throughput but it also greatly reduces the number of processing elements compared to other realizations. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(1): 69–79, 1997 [ABSTRACT FROM AUTHOR]

Using the operation by fixed-point processing, cheap and fast processors can be realized, which helps to reduce the production cost. This paper uses a newly defined cost function. It discusses also the convergence of the "polarized-x" method. This method updates the coefficient of the nonrecursive filter based on the product with the reference signal polarity, which is an operation suited to fixed-point processing. A normalized recursive adaptation algorithm is derived from the new cost function, which is useful in the application to the system with the reference signal condition is given as 0 , K < 4/π, and the estimation error increases only by approximately 2 dB compared to the conventional normalized least mean square (NLMS) algorithm. The obtained structure is modified to construct an adaptive algorithm so that the normalization is applied individually to the coefficients and the convergence is deteriorated little for the operation by the fixed-point processing. [ABSTRACT FROM AUTHOR]

In spectrum estimation of nonstationary signals, the modeling of time-varying characteristics and the parameter estimation of the model are important. Several adaptive estimation methods such as the recursive least-squares (RLS) method are often used for parameter estimation of time-varying models. However, the RLS method becomes less efficient for rapidly time-varying models because this method assumes short-time stationarity. This paper proposes an adaptive estimation method of time-varying parameters modeled as linear combinations of a set of basis functions. In this method, linear exponential time functions are employed as basis functions. This algorithm is realized by the RLS algorithm with a rectangular window and a procedure that shifts basis functions. In some experiments, the performance of the proposed method is compared with that of the conventional method with short-time stationary assume. [ABSTRACT FROM AUTHOR]

This paper introduces a method for suppression of multiple access interference in the direct sequence/spread spectrum multiple access system (DS/SSMA). It is especially effective for the near-far problem. When an integration period of cross correlation is divided into subintervals in the DS/SSMA system, the partial cross correlation values in the presence of noise and interference vary considerably from subinterval to subinterval. In the proposed system, allocating small weight coefficients to subintervals with large cross-correlation values and large weight coefficients to subintervals with small cross-correlation values results in considerable, improvement in signal-to-noise ratio. Using this method, multiple access interference can be suppressed without knowing the PN sequences of other users. The principle of this system, a novel algorithm using partial correlation weight coefficient control techniques, will be illustrated with the help of computer simulations. [ABSTRACT FROM AUTHOR]

Recently, in acoustic and audio engineering where wideband signals are handled, it has become required to realize a large-scale adaptive filter by small computational complexity. This paper proposes an efficient adaptive filter, based on the time-frequency characteristics of the impulse response on the unknown system. First, the filter structure is shown which can extract the time-frequency characteristics of the impulse response of the unknown system. Then a nonuniform resolution filter is proposed which can represent the impulse response in the time-frequency domain with a nonuniform resolution by allocating a small numner of tap coefficients. an adaptive algorithm based on the proposed filter structure is derived. Finally, it is shown by a simulation that the computational complexity can be reduced by the proposed method when the unknown system has a nonuniform structure in the time-frequency domain. [ABSTRACT FROM AUTHOR]

A local connected recurrent neural network with the ability to memorize and regenerate some nonlinear complex dynamics is proposed in this paper and a new learning algorithm for this network is also developed. The network, constructed of adaptive oscillating modules, is easily applied to the realization of nonlinear dynamics. The module consists of two simple neuron nodes with recurrent connections. The new learning algorithm can independently train each module with suitable speed for given input data. The network size is also adaptively determined during the learning process. This network also has a suitable structure of a parallel VLSI system. Finally, some simulation results are given to verify the effectiveness on the proposed network structure and the learning algorithm. [ABSTRACT FROM AUTHOR]

There are some cases where feedforward control can be utilized effectively, e.g., the active noise control and the vibration control of a building. When there exists an indeterministic factor or a fluctuation, the adaptive filter must be introduced. The algorithm that adjusts the coefficient of the adaptive filter has mostly been based on the filtered-x algorithm. A problem in this approach, however, is that the stability is not guaranteed and the stepwidth of least-mean square (LMS) algorithm must carefully be determined. From such a viewpoint, this paper proposes the adaptive algorithm both in the time and the frequency domains, where an arbitrary stepwidth can be used, and the robust stability is guaranteed even if an additive noise is mixed. As the first step, the infinite impulse response (IIR) adaptive filter is considered, aiming at implementation of the controller in the time domain, and the properties of the adaptive algorithm are analyzed. Then, the adaptive algorithm in the frequency domain is proposed where the controller is implemented using the frequency-sampling filter and the stability is guaranteed In contrast to the case of the design in the time domain, the implementation in the frequency domain has the advantage that the realization is ensured independently of the order or the structure. Finally, the usefulness of the proposed adaptive algorithm is demonstrated by numerical example and experiment in the active noise canceler. [ABSTRACT FROM AUTHOR]

This paper proposes a method for realizing two-dimensional (2-D) adaptive filters by applying a one-dimensional (1-D) recursive least squares (RLS) algorithm. First, by applying a 1-D RLS algorithm along horizontal and vertical directions, a novel 2-D adaptive algorithm is developed. It is shown that the amount of calculations in the proposed algorithm is less than that in the existing 2-D RLS algorithm. Moreover, the convergence properties of the proposed algorithm and its relation to the conventional 2-D RLS algorithm are investigated. A method for accelerating the rate of convergence of the algorithm using a priori estimation error also is described. The proposed niter has good performance in nonstationary processes and the accuracy of convergence is better than that in the existing 2-D adaptive filters based on the least mean square (LMS) algorithm. Therefore, the proposed filter is suitable for processing an image with strongly nonstationary characteristics. Finally, the utility of the proposed filter is illustrated by applying it to 2-D system identification under a nonstationary environment as well as noise reduction of an image. [ABSTRACT FROM AUTHOR]

Learning identification is one of the most widely utilized adaptive algorithms due to its small computational complexity. A problem with this algorithm is that a division by the square norm of the state vector is includ- ed in the coefficient update process which easily produces an instability when the nonstationary such as speech is given as the input. A method known to cope with such a problem and to realize the stable convergence involves not updating the coefficient when small input signals continue. This paper discusses this approach. As a first step, the situation is assumed where the square norm of the state vector is less than the specified threeshold and the effect of interrupting the coefficient update is analyzed. The convergence and the time-constant are formulated and the guarantee of the estimation accuracy for the convergence value is discussed. Then, the step gain is derived for the specified guarantee value so that the convergence speed is the fastest in the stochastic sense while ensuring stability. Lastly, the effectiveness of the proposed method is verified by computer simulation. It is shown that, even if the input signal is annotation, the fastest convergence speed is realized, together with the satisfactory estimation accuracy, which is always obtained according to the specified guarantee value after the convergence. [ABSTRACT FROM AUTHOR]

A novel adaptive filter is proposed that adapts to the sample spacing as well as to the tap weights. Although in adaptive digital processing, the tapped-delay line usually has uniformly spaced taps, with the spacing equal to symbol period or a fraction of symbol period, an adaptive filter with a few taps should be adaptively arranged for nonuniform spacing for better convergence as the sampling timing varies. The conventional non-uniformly spaced filters are not adaptively changed or not arranged under the constraint of the acceptable mean-square error. In this paper, a least-mean square (LMS)- type algorithm is derived in which an adaptive filter adaptively changes the amount of delay, as well as the filter coefficients. The performance of the proposed algorithm is investigated by computer simulation. [ABSTRACT FROM AUTHOR]

A set Ϝ of rectangles is considered which are placed on the surface of a right cylinder such that two of their sides are parallel to the axis of the cylinder. A graph G = (V, E) is called a rectangle-on-a-cylinder-intersection graph with a model Ϝ, if the vertices of G can be put into a one-to-one correspondence with the rectangles in Ϝ, such that two rectangles in Ϝ have nonempty intersection if and only if two vertices corresponding to them are connected by an edge in G. In this paper, it is shown that given an Ϝ, a maximum clique of the corresponding rectangle-on-a-cylinder-intersection graph can be obtained in polynomial time, by repeatedly using an algorithm for finding a maximum clique of a circular-arc graph. Furthermore, an algorithm is structed which, given a dynamic set C (initially empty) of circular arcs which changes as arcs are added to or deleted from C, finds a maximum clique of the circular-arc graph corresponding to C in O (m(d + 1)) time every time C is changed (here m is the number of arcs and d is the number of arcs intersecting the added or deleted arc). It is also shown that, using this algorithm, an algorithm can be constructed for finding a maximum clique of a rectangle-on-a-cylinder-intersection graph in O (n(n + e)) time (n is the number of vertices and e is the number of edges). [ABSTRACT FROM AUTHOR]

In the echo canceller, where the normalized least mean square (NLMS) algorithm is used as the adaptive algorithm, the double-talk disturbs the coefficients of the adaptive filter and increases the probability of howling generation. To cope with this phenomenon, the echo canceller usually is provided with a detector to detect the generation of the double-talk. The echo canceller is designed to minimize the disturbance by stopping the update of the adaptive filter coefficients when the double- talk is detected. In the detection of the double-talk, it is effective to monitor the increase of the residual echo since the double-talk component masked by the echo can be detected. In this method, however, the residual echo also is increased by the fluctuation of the echo path and the fluctuation of the echo path should also be detected. This paper proposes a method to differentiate between the double-talk and the echo path fluctuation, based on the magnitude of the correlation between the input-containing echo and the echo replica. In other words, the property is utilized that the correlation between the echo replica and the echo is large for the double-talk and is small for the echo path fluctuation. A double-talk detection method also is proposed where the power ratio of the residual echo and the echo replica is used as the parameter. It is shown that the double-talk detection without deteriorating at all the echo elimination can be realized by a structure with a delay preceding the coefficient update operation. [ABSTRACT FROM AUTHOR]

Cyclic codes are often used for the purpose of correcting burst errors in digital transmission and recording systems. Since the implementations of the encoding and syndrome calculations of these codes are simple, these codes have superior properties from a practical perspective. In this paper, an effective decoding method is given for certain burst errors (multiple solid-burst errors) that are contained within the detected errors resulting from a binary cyclic ‘predecoding’ process, where the preceding process for burst error correction is terminated at the detection stage. Such burst errors can be expressed as random errors by superimposing a copy of itself that has been cyclically shifted by one bit. So, by performing random error decoding on a version of the received sequence that has been superimposed with a one-bit cyclically shifted copy of itself, burst errors can be accurately corrected. This decoding method completely preserves the correction capacity of the precede and is applicable to any binary cyclic code with a minimum distance of at least 5. The correctable multiple solid-burst errors depend on the minimum distance of the code. Furthermore, by applying this technique to interleaved random error-correction codes for the purpose of correcting burst errors, it is shown that it is possible to extend the length of correctable burst errors. [ABSTRACT FROM AUTHOR]

By the fixed-point processing, a cheap and fast processor can be obtained which is an effective approach in reducing the production cost. In the adaptive filter, where the coefficient correction which is calculated in each sampling period to be added to the filter coefficient, the adjustment of the filter coefficient is made impossible if the coefficient correction is less than the minimum value that can be represented by the fixed-point representation. In the normalized least mean square (NLMS) algorithm, the normalization using the norm is applied, which increases the probability that the coefficient correction is less than the minimum value. This problem is solved by extracting the coefficient correction as the ‘difference between the impulse response of the unknown signal transmission system as the object of identification and its estimation.’ In the ‘individually normalized’ least mean square (LMS) algorithm, this difference is derived by calculating the ratio between the product-sum of the residual response with the adaptive filter output and the square-sum of the tap output. Then, the result is normalized individually for each coefficient. This paper then presents the stability condition which serves as the design principle of the proposed method. The parallel-shifting integrating configuration is presented, which has the computational complexity less than that of the NLMS algorithm. The method is applied to the filtered-x algorithm, and the usefulness is verified. [ABSTRACT FROM AUTHOR]

This paper proposes a new method to quantize coefficients of filters where frequency-characteristic deterioration is suppressed. When a digital filter is realized, quantization errors cannot be avoided because operation circuits and registers have finite word lengths. Generally, filter coefficients are quantized by popular methods, such as rounding and omitting, etc. The pro- posed method obtains the quantized coefficients by search. The Genetic Algorithm is used for the search because it needs only objective function information. Further, by using the proposed method, the filter coefficients can be quantized with the frequency weight. Therefore, deterioration of the coefficients quantized by the proposed method is suppressed in the specified frequency region. The effectiveness of this method is shown by some simulations that quantize the four-line lattice and the direct form filter coefficients. [ABSTRACT FROM AUTHOR]

This paper presents a new encoding algorithm based on the face hypercube embedding for satisfying given input constraints. The algorithm works for a constraint relation matrix derived from the sets of the input symbols grouped for each output symbol independently and finds the encoding through row-by-row (group-by-group) cover assignment. A cover is found by the extension of a core cover generated from the magnitude estimations and adjacent relations of the currently known covers. Each cover is formed to be a single cube; and, if it is unsuccessful for specified code length, then the encoding length is extended. The experimental results indicate that this encoding technique has advantages over well-known existing methods in the quality of encoding. [ABSTRACT FROM AUTHOR]

The bifurcation diagram is constructed in the analysis of the bifurcation phenomenon. A problem in the conventional method of bifurcation diagram construction is that the computation is interrupted at the cusp point on the tangent bifurcation curve. Consequently, it has been necessary to determine the bifurcation set independently, excluding the cusp point, and then connect the curves afterward. This increases the time for constructing the bifurcation diagram when there exists a cusp point. Especially, when there exist multiple cusp points in the range where the parameter takes a small value, it has been almost impossible to trace the bifurcation curve. From such a viewpoint, this paper proposes an algorithm based on the concept of the vector field, where the tangent bifurcation curve can be determined as a continuous curve, even if cusp points are included. The proposed algorithm is applied to the Duffing equation, and the result of computation is shown when the tangent bifurcation set including multiple cusp points is traced. [ABSTRACT FROM AUTHOR]

Quicksort is a well-known sorting algorithm based on the divided control. The array to be sorted is divided into two sets as follows. An element in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value are constructed. Each of those two sets are sorted independently. The procedure is iterated for the divided sets. In other words, the algorithm has a recursive structure. The average time-complexity of the quicksort (the aver- age number of comparisons) is O(n log n). Depending on the data to be sorted, however, the performance may be deteriorated drastically. In the worst case, the time complexity is O(n2). In this paper, the generating function based on the time complexity of the quicksort is introduced and the mean and the variance of the time complexity is deter- mined analytically using the generating function. Based on the derived mean and the variance, the chi-square test is applied as to whether or not the distribution of the time complexity can be approximated by the normal distribution. Then, a method is proposed in which the probability R(x) that the time complexity exceeds a certain value x is determined accurately by approximating the distribution of the time complexity of the quicksort by a three-parameter Weibull distribution. Finally, the selection of the sorting algorithm is discussed. [ABSTRACT FROM AUTHOR]

In this paper, a new Chebyshev approximation (amplitude and phase simultaneous approximation) method for IIR digital filters is proposed. The proposed algorithm is based on the Remez algorithm. By solving the eigenvalue problem at each iteration, the frequency characteristic of the filter is interpolated so that the error function in the complex domain is made with equal ripples. Since the previously proposed amplitude and phase simultaneous approximation methods for the IIR digital filters are based on the nonlinear equation, they all require substantial computation. On the other hand, the present method is extremely simple and the amount of computation can be reduced significantly. Nevertheless, the performance equal to or more than the conventional one can be obtained. Further, the present method can be applied not only for the real coefficient filters but also for the characteristic approximations limited to the positive frequency range. Hence, a further reduction of the filter order needed for signal processing can be attempted. [ABSTRACT FROM AUTHOR]

As location problems in flow networks, there are p-center and p-median problems; and they are known to be solvable in polynomial time. In this paper, wer propse a new location problem. It is the problem of locating p-sinks so that the maximum flow is maximized given a flow network N with a source (this problem is called a p-collection problem). First, a linear time algorithm to solve the 1-collection problem for trees in given. Then a pseudo-polynomial time algorithm to solve the p-collection problem for trees based on dynamic programming is presented. Since the decision problem corresponding to the p-collection problem for trees is known to be NP-complete, its decision problem turns out to be strongly NP-complete. [ABSTRACT FROM AUTHOR]

This paper proposes the parallel construction of the second-order infinite impulse response (IIR) adaptive digital filter (ADF) as an adaptive digital filter for eliminating multiple narrowband signals mixed in the broadband signal. Then the pole-control method for the filter is proposed. In the proposed pole-control, the pole radius and the pole argument are controlled separately by different algorithms. In this study, the pole argument is corrected by estimating the deviation of the central frequency of the signal to be eliminated from the convergent value of the multiplier coefficient that determines the zero. The pole radius is controlled by the method that determines the direction of correction, using the parallel-connected three ADFs with the same pole argument and a slightly different pole radius. It is verified by a simulation that those pole-control methods work effectively. It is demonstrated that the pole radius and the pole argument can be controlled simultaneously. [ABSTRACT FROM AUTHOR]

When a formant is modified based on the pole of the AR model, a problem arises due to the interaction between the pole to be modified and other poles such as the apparent elimination of the formant, if the frequency of the considered pole simply is modified. To solve this problem, the method proposed in this paper uses the spectral intensity at the pole frequency as a new future parameter and the spectral intensity at the pole after the frequency modification is corrected to the desired value by iterative processings. To examine the effectiveness of the proposed method, an experiment was conducted in which a phoneme in a word is replaced into the same phoneme in a different environment, and then the format frequency is modified by the proposed method in order to restore the original speech. The speeches before and after the modification are compared in terms of the cepstral distance (CD) from the original speech, and it is verified that the proposed method is effective in the modification of the formant. An attempt is made to solve the formant discontinuity problem at the concatenation point in waveform based speech synthesis-by-rule and to modify the formant frequency accompanying the modification of the fundamental frequency using the proposed method. It was verified as a result of experiment that the speech after formant modification is better than the speech before modification, indicating that the proposed method is useful in improving the quality of the synthesized speech. [ABSTRACT FROM AUTHOR]

In the detailed routing for VLSI standard cell layout design, the over-the-cell channel routing, which utilizes the over-the-cell region as the routing region, has been proposed. In this design method, after determining the net assignment to each channel in the global routing step, the track assignment both in channel and on over-the-cell regions is performed by an over-the-cell channel router. However, conventional global routing algorithms do not assume over-the-cell routing but conventional channel routing. Therefore, the minimization of channel density does not always successfully lead to the minimization of the final channel height. This paper presents a new global routing method for standard cell layouts to determine global routes for each net in both channel and over-the-cell regions simultaneously. The standard cell layout design system GLORIA based on the proposed algorithm is developed, and the experimental results compared with the conventional global routing method that performs the over-the-cell channel routing after global-routing with TimberWolf-SC4.2c are reported. Experimental results showed that the proposed routing algorithm can route about 18.4 percent fewer number of tracks than the conventional routing method, and the effectiveness of the proposed method is shown. The experimental results of applying the proposed method to the three-layer routing layout model also are presented. [ABSTRACT FROM AUTHOR]

The problem of finding routing and layer assignment, which minimize the number of vias ignoring the line width and the separation of lines, is NP-hard even if the nets are restricted to two-terminal nets. Numerous heuristic algorithms have been developed in an attempt to improve efficiency. However, as for properties of solutions, it has only been proven that the number of vias for t-terminal nets in an optimum solution (min vias) is at most t - 1, if the number of layers is restricted to 2. It is also known that properties of vias and terminals can be defined in a number of different ways for the multiplayer topological via minimization (TVM) problem using unlimited number of layers. The problem becomes complex. In this paper, the forementioned theorem is generalized and it is proven that a t-terminal net uses at most t - 1 adjacent-layer connecting vias in any optimum solution for the general case without any restriction on the number of layers. Further, a class of problems is shown to exist which require that many vias. Similar results are also shown for all-layer connecting vias. [ABSTRACT FROM AUTHOR]

The following figure realization problem has already been posed. "For arbitrarily given figure (two-dimensional array), find the (mathematical) model that realizes (describes) the figure. If there exist two or more models, show that they are isomorphic. "As a solution to the problem, the figure realization theorem is obtained as follows. "For any given figure, there always exists a canonical cumulative linear representation system that realizes the figure, which is unique except for the isomorphism." There also are studies to analyze the finite-dimensional canonical commutative linear representation system. Based on those results, this paper discusses the partial realization (faithful description) problem for the finite-size two-dimensional array. An algorithm is given which derives the minimum-dimensional commutative linear representation system that partially realizes (faithfully describes) the given finite-size two-dimensional array. As an application example, the dyeing and weaving pattern are considered and the usefulness of the proposed algorithm is shown. The proposed method is a processing to compress the information of the finite-size two-dimensional array by maximally utilizing the regularity of the finite-size two-dimensional array considering the vertical and horizontal positions. [ABSTRACT FROM AUTHOR]

This paper proposes a stochastic approximation adaptive algorithm aiming at a fast convergence speed, where the step size is normalized by the instantaneous power ...x(k)...² of the input signal and a constant time-shift β is included at the weight update, as α/(k + β)...x(k)...². It is shown first that the proposed algorithm gives a convergence to the Wiener solution. Then the transient response of the mean error is analyzed. It is as a result β ≥ α/2 is the conditions for the time-shift parameter to guarantee the uniform convergence of the algorithm. It is shown also that the speed of convergence is improved greatly compared to the conventional algorithm when α is set large enough so that the product of α and the minimum eigenvalue of the autocorrelation matrix exceeds 100 and the time-shift parameter is set as β ∼ α/ 2. The performance is evaluated by a computer simulation. The above result of analysis is verified, and it is shown that the proposed algorithm can realize the same convergence speed as that of the recursive least-squares (RLS) algorithm. [ABSTRACT FROM AUTHOR]

This paper describes a new design algorithm for finite impulse response (FIR) digital filters, which approximates constant passband amplitude and linear phase characteristics. The algorithm converts a filter's specification characteristic into a continuous impulse response by using the frequency response of a window function. The continuous impulse response is translated into discrete values to calculate tap-gain coefficients of an FIR filter. In this design algorithm, window functions belonging to the Hanning window series (such as the Harris' window whose characteristics are already known) are used. This design algorithm is an analytical design technique, featuring a filter length that can be decided when the specification is decided and does not require iterative numerical calculations to calculate tap-gain coefficients. [ABSTRACT FROM AUTHOR]

In this paper, a new method is introduced for designing IIT digital allpass functions with specified phase tolerances, Since the phase error characteristics subject to the desired phase response have been specified in the interest bands, the phase design of digital allpass functions in the form of a linear programming problem can be formulated by using the Remez exchange algorithm. Then the linear equations are solved to obtain a set of filter coefficients and the optimal coefficients in the Chebyshev sense can easily b obtained through a few iterations. By approximately selecting the initial external frequencies, the proposed design algorithm always converges, and the phase error characteristics can be arbitrarily specified. Finally, some design examples are presented to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm with a guaranteed accuracy for the finite-dimensional nonlinear equation. First, an algorithm is shown which can determine the interval containing the true solution, based on the given approximate solution. This method is based on the interval analysis and considers the representation error of the equation. Then the interval iteration method is shown which can arbitrarily reduce the interval. The rational number arithmetic is used and the rounding of the rational number us utilized effectively. Finally, an experimental implementation of the algorithm on a computer is presented, together with some numerical examples. [ABSTRACT FROM AUTHOR]

This paper considers the large-scale multi-objective nonlinear programming problem with block angular structure. A new method is proposed for deriving the compromising solution of the decisionmaker based on the fuzzy decision, considering the fuzzy goal of the decisionmaker for each objective function. The large-scale nonlinear programming problem (original problem) for deriving the solution based on the fuzzy decision is formulated. Then, based on the dual decomposition technique introduced by Lasdon, the dual problem for the original problem is formulated. A two-level optimization algorithm is proposed where the formulated dual problem is decomposed and the solution for the original problem is obtained by iteratively solving the subproblems. The validity of the algorithm is examined through a simple numerical example with the block angular structure. [ABSTRACT FROM AUTHOR]

Assume that G is an undirected planar graph and the edge length of G is nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the "noncrossing paths" with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. The computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not to be a constant. [ABSTRACT FROM AUTHOR]

The free-choice net is a subclass of the Petri net. It is a class which can explicitly represent both the essential concurrency and the nondeterministic aspects of the concurrent system. The class can be considered as an extension of the state machine where concurrency is included. It can also be considered as an extension of the marked graph where the nondeterministic aspect is included. There have been a number of studies on the free choice net with the dynamic constraint that it should be live and safe (LSFC). This LSFC net has a structural feature; it can be decomposed into a set of strongly connected state machines (called S components). If the minimal set of S components (S decomposition set) covering the given LSFC net can be efficiently determined, it will be possible to derive powerful methods in the analysis and performance evaluation of the parallel system. This paper discusses the polynomial-order algorithm that determines the S-decomposition set for the LSFC net. [ABSTRACT FROM AUTHOR]

This paper proposes a highly parallel algorithm of separable denominator two-dimensional (2-D) state-space digital filters, called a block parallel algorithm. To derive the block parallel algorithm, the processing image is divided into several blocks and all dependency constraints in a divided block are eliminated. In the block parallel algorithm, the number of multiply-and-accumulate operations required to process one image is proportional to 1/L for the block length L. We also study the architec- ture of the block processor which implements our proposed algorithm. As a result, one 250-K gales VLSI chip to implement one block processor with the block length L = 8 must be designed. The multiprocessor system comprising 66 proposed VLSI chips can propose 2048 × 2048 pixels image at the rate of 60 frames/s. [ABSTRACT FROM AUTHOR]

When a random noise is superposed on a signal with an abrupt change (i.e., edge), as in the case of the image signal, there is a large overlap of the frequency component between the abrupt changes (edge) of the signal and the noise. Then it is impossible to realize both the noise elimination and the edge preservation sufficiently by the conventional linear filter, such as the mean filter. Thus, a nonlinear technique is required in order to eliminate the noise and preserve details of the original signal where the coefficient of the smoothing filter is determined according to the properties of the data in the window. There can be more than one observed value in the filter window that can be used to specify the properties of the data. It is difficult, however, to represent precisely the properties of the image signal using a single observed value. In addition, the observed values contain ambiguities since they are calculated from the local image data with superposed noise. In other words, it is required to determine the filter coefficients based on multiple observed values containing ambiguities. For such a problem, the fuzzy control rule, which is utilized effectively in control problems, can be applied to calculate the control variable (i.e., filter coefficient) adequately by the nonlinear technique from the multiple observed values containing ambiguities. In this paper, the nonlinear filtering technique based on the fuzzy control rule is presented and the usefulness of the filter in the noise elimination from the image signal is demonstrated. [ABSTRACT FROM AUTHOR]

In general, it is difficult to derive a finite sequence which minimizes the sidelobe of the autocorrelation function. However, it is shown that there exist the even-shift orthogonal sequences, i.e., the finite sequences for which the even-shift autocorrelation function takes the zero value. The generation method also is shown. On the other hand, there has not been known the general method for generating the odd-shift orthogonal sequences, for which the odd-shift auto-correlation takes the zero value. Neither have the properties of such sequences been analyzed. This paper presents the general method for deriving the odd-shift orthogonal sequences, using the complex function as the generating function and constructing the numerical sequence from the Fourier expansion coefficients. First, the one- and two-dimensional odd-shift orthogonal complex sequences and odd-shift orthogonal real sequences are defined from their autocorrelation functions. Then, it is shown that those numerical sequences are odd-shift orthogonal sequences if they are skew-symmetrical sequences. Finally, the properties of the generating functions that derive those odd-shift orthogonal sequences are shown, together with the generation algorithm. [ABSTRACT FROM AUTHOR]

The Berlekamp-Massey algorithm and the Euclidean algorithm are well known as decoding methods for Reed-Solomon codes. Sakata's algorithm, which finds the minimal set of polynomials that generate a given two-dimensional (2-D) array, is used as a decoding method for algebraic-geometric codes; Reed-Solomon codes are a subclass of the algebraic-geometric codes. The Sakata algorithm is an extension of the Berlekamp-Massey algorithm to two dimensions, hut there is no corresponding extension of the Euclidean algorithm to give it the edge in implementation. Theorems are presented here to demonstrate in general the equivalence between the Berlekamp-Massey algorithm and the Euclidean algorithm and from these theorems a 2-D Euclidean algorithm that corresponds to the 2-D Berlekamp-Massey algorithm (Sakata algorithm) is developed. Moreover, the algorithms described here correspond to the multidimensional Berlekamp-Massey algorithm and to the Kamiya-Miura algorithm, a modification of the Sakata algorithm. The algorithms proposed in this paper may be implemented at high speeds with parallel processing, a difficult task for the Berlekamp-Massey algorithm. [ABSTRACT FROM AUTHOR]

In the nonlinear dynamical system, the singular point analysis (Painleve test) is known to be an analytic method for identifying integrable systems or characterizing chaos. In this paper, nonlinear dynamical networks, which are simplified models for mutually connected analog neurons, are studied mainly in terms of the singular point analysis by introducing the complex time. The following results were obtained: 1) some conditions for integrability and first integrals are identified; 2) as an application of Yoshida's theorem, it is proven that many cases in our system are (algebraically) noninegrable; 3) a self-validated numerical algorithm is proposed to overcome some difficulties known to appear in applying the singular point analysis (Yoshida's theorem) to higher-order systems. [ABSTRACT FROM AUTHOR]

This paper proposes a new HVHD four-channel routing technique using the channel-graph. The diagonal routing model, which differs from the conventional fourlayer channel routing, is introduced in the proposed method; and the nets for the diagonal routing are selected by the algorithm based on the weighted channel-graph. The rest net, left after the diagonal routing, is routed in HVH three-layers. The proposed method is applied experimentally to several benchmark data, including Deutsch's difficult example. It is shown that tracks are reduced by approximately 20 percent compared to the conventional fourchannel routing method, and the result by the proposed method is closer to the result of the conventional fivelayer routing. Thus, the effectiveness of the proposed method based on the channel-graph is demonstrated. [ABSTRACT FROM AUTHOR]

This paper presents some conditions to determine decimation ratio in subband adaptive identification ofa time-varying system. It has been reported in some experiments that a large decimation ratio is not suitable for subband identification of a time-varying system. However, theoretical conditions for a maximally decimated ratio in a time-varying system have not to date been reported. A short-time invariant mode! is the starting point for this research. The relation between a forgetting factor used in the recursive weighted least-squares (RWLS) algorithm and a time variation of the time-varying system are derived. Then, new forgetting factors are derived for the multirate processing case. Using a convergence property provided by these forgetting factors, theoretical conditions are obtained having parameters estimated from decimated signals that are as accurate as those from all observed signals. The propriety of these conditions is demonstrated using simulations. [ABSTRACT FROM AUTHOR]

This paper proposes a speech recognition algorithm for large vocabulary continuous speech. The proposed algorithm is based on the hidden Markov model (HMM)- LR algorithm using a generalized predictive LR parser and phoneme HMMs. The following three techniques are applied to improve recognition performance and reduce processing time. (1) The forward and the backward likelihood are used to accurately determine the likelihood in the beam search. (2) To reduce the trellis computation in HMM speech recognition and for efficient search, only the speech frames in which the predicted phoneme seems to exist are used by the window for phoneme matching. (3) For efficient search, adjusting identical phoneme sequences are merged by checking the stack and the state of the LR parser. The algorithm was applied to a telephone directory assistance task involving more than 70,000 subscribers. A recognition experiment for continuous word utterance was done. The sentence recognition rate was 85 percent speech recognition. The sentence understanding rate was 59 percent for speaker-dependent speech recognition with spontaneous utterances. [ABSTRACT FROM AUTHOR]

SPICE-type general-purpose circuit simulators are used widely as a support tool for circuit design. It often happens, however, that the dc operating-point analysis does not converge. To cope with such a situation, various approaches have been proposed based on continuation methods with the global convergence property, but these have yet to come to the stage of practical application to large-scale circuits. This paper proposes a practical algorithm which can be implemented on the general-purpose circuit simulators with modified nodal formulation, for determining the dc operating-point of large-scale circuits. As the first step, the concept of "modified cut-set analysis" is introduced and some properties of the modified nodal equation are presented. Then it is shown, in practical circuits, that the convergence of the algorithm is theoretically guaranteed. The proposed algorithm is then implemented on an existing general-purpose circuit simulator and applied to a bipolar analog LSI to demonstrate its effectiveness. For the LSI circuit formulated in 18,553 modified nodal equations, the dc operating point was determined in 270 minutes using an IBM RS6000-550. [ABSTRACT FROM AUTHOR]

The block orthogonal projection algorithm exhibits an excellent convergence property in a noise-free environment. However, a compromise must be sought between the speed and the precision of the convergence when there exists a noise. This paper considers the block orthogonal projection algorithm using the conjugate-gradient method, which is one of the realizations of the block orthogonal projection algorithm. The convergent value is evaluated, and it is shown that one of the major factors that determine the convergent value is the number of iterations in the algorithm. Based on the result of the error analysis, the optimal number of iterations for the block orthogonal projection algorithm is derived so that the effect of the noise can be reduced without sacrificing the high-speed property. For this purpose, the block adaptive algorithm is proposed, based on the block orthogonal projection algorithm using the conjugate-gradient method. computational complexity can be reduced drastically compared to the block orthogonal projection algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the topological via minimization problem in the permutation layout, under the constraint that no wire passes between pins which are adjacent on the same horizontal line. Under a constraint that the upper side of the upper horizontal line not be used as the wiring area, an algorithm is proposed with time complexity (n² log n) for k = 1 and O(n3k-1) for the general value of k, for the problem of determining the set of maximum k-layer wiring (n is the number of nets). Then an algorithm is proposed with time complexity O(8kn3k-1) for the case where the wiring can be the whole plane. [ABSTRACT FROM AUTHOR]

This paper considers the learning of discrete dynamical systems using recurrent neural networks. The discussion is based on the theory of the probabilistic descent method, and the learning algorithms are compared by numerical experiment. In the discussion based on the theory of the probabilistic descent method, it is shown that, from the viewpoint of the learning speed in the early stage of the learning, is equivalent to the backpropagation method with a large learning constant. For the case where the variable is not constrained to the value of the teacher signal and a chaotic time series with a large Lyapunov exponent is to be learned, it is found that the effect of the recurrent connections is not manifest at the early stage of the learning but the learning is accelerated with the progress of the learning by the fluctuation caused by the chaos. [ABSTRACT FROM AUTHOR]

This paper considers the realization of high-speed phase synchronization when there exists a frequency error and discusses the application of the recursive least square (RLS) algorithm to the burst signal demodulator. Especially, as a phase control algorithm for the coherent detection where there is an error in the carrier frequency, a method is proposed to represent the phase variation by the frequency error as the state transition function and a detailed algorithm is derived. It is shown that the theoretical convergence and the tracking performance of the algorithm agree with those of the ordinary RLS algorithm. The algorithm is applied to the frequency control circuit of the π/4-QPSK differential detector and the phase control circuit of the 16-QAM quasi-coherent detector. It is demonstrated experimentally that the system has an excellent performance and that the initial convergence is complete in approximately ten symbols when there exists a frequency error. [ABSTRACT FROM AUTHOR]

Understanding electromagnetic scattering phenomena at high frequencies is important in specifying the location of the local scattered wave (scattering center). This procedure also is available for the practical radar target recognition. Detection of the scattering center also is possible by means of the Fourier transform in the frequency data measured by a network analyzer. However, since its resolution is limited by the measured frequency bandwidth, practical applications may often be difficult. In this paper, the use of the MUSIC algorithm which has a higher resolution than the Fourier transform is proposed for the time-domain estimation method of the electromagnetic scattering. As an example, the detection of the scattering center in the backscattering measurement of a conductive sphere is discussed. It is pointed out that the algorithm can be applied without significant modifications. Most of the super-resolution methods require many snapshots. It is found by computer simulation that the noise suppression preprocessing by time domain gating is effective for reduction of the snapshots. The setting of the number of incident signals (scattering center) of the MUSIC algorithm in the time-gated data is discussed. Further, by experiments, these investigations were verified and the high-resolution nature of the present method is proven. [ABSTRACT FROM AUTHOR]

This paper describes an automatic text- and speaker- independent language identification method based on bidden Markov models (HMMs) for acoustic features. The bidden Markov modeling is used to represent the phonotactics for each language. Each language has its proper phonotactics. The HMM topology here is a fully structured (ergodic) model wherein any state could transit to all states. Two kinds of HMMs are used: the discrete HMM (DHMM) with the code book and the continuous density HMM (CHMM). The HMM was trained using both the Bam-Welch (forward-backward) algorithm and the Viterbi algorithm. The latter was used for emphasizing the state transition probability. For comparison, experiments also were conducted on the identification using a mixtured Gaussian distribution model with one state. This single-state Gaussian distribution model gave the same performance as the HMM trained with the Baum-Welch algorithm. This is because the transition between states which reflects the characteristics of each language does not affect the likelihood scores very much. This problem was addressed by emphasizing the transition probabilities and using the Viterbi algorithm, which resulted in an improvement in the recognition rates. The trigram for optimal state sequence is introduced. Combining it with the HMM produced the best results. [ABSTRACT FROM AUTHOR]

As the efficient methods to determine the weight distribution of the convolutional code, there have been proposed the high-speed algorithm based on the tree search on the trellis [1] and the variational method based on the variation of the weight of the code word [2]. This paper proposes a method to determine the weight distribution of the convolutional code with the coding ratio 1:2 where an algorithm (called modified variational method), which is efficient and can easily be realized on the computer, is derived by modifying the variational method. It is shown that the modified algorithm has a better perforce than the conventional method. Then an efficient method is proposed which searches the best nonsystematic convolutional code with the coding ratio 1:2, assuming the maximum likelihood decoding. The best codes are sought for the constraint length from 6 to 19 using the proposed method, and a large number of the best codes is shown which heretofore have not been known. [ABSTRACT FROM AUTHOR]

This paper describes a new numerical calculation algorithm for the nonlinear quadratic optimal problem with nonlinear terminal constraint. Synthetic Riccati transformation proposed earlier by the authors is utilized to solve the fore mentioned problem. The state differential equation is changed into two differential equations with respect to the two substates vector selected from the state vector. Then, based on the maximum principle and Kronecker's product, two differential equations with respect to the adjoint variables can be derived. To solve the fore mentioned differential equations, synthetic Riccati transformation is introduced to obtain a Riccati differential equation and an accessory differential equation. Thus, we can calculate the initial values of the adjoint variables by solving Riccati equations backward in time. The convergence condition about this algorithm also is provided. [ABSTRACT FROM AUTHOR]