Search

This paper presents the new upper bounds of channel width required in multi- layer channel routing under a wiring rule in which horizontal wires must be wired in the odd-numbered layers and vertical wires in the even-numbered layers. In (M ≧ 4)-layer channel routing, it is proved the upper bound is equal to [(dc +k)/[M/2]], where dc is the channel density, and k is 9 when M = 5, 7 when M is even, and 13 when M is odd and greater than 5. These upper bounds are obtained by presenting the multiple-layer channel routing algorithms, which wire the channels in a column-by-column manner. [ABSTRACT FROM AUTHOR]

This paper proposes a real-valued orthogonal periodic sequence of a period N=2ν derived from a real-valued shift-orthogonal finite-length sequence of length M=2ν+1. This paper also explains the principle of a fast correlation algorithm that efficiently executes periodic correlation processing for this real-valued orthogonal periodic sequence. The sidelobe of an aperiodic autocorrelation function for a real-valued shift-orthogonal finite-length sequence (length of M) is 0 except for the right and left ends of the shift. If the subsequent sequence of first values repeatedly overlap the final values of this sequence, a real-valued orthogonal periodic sequence of a period N=M-1 can be obtained. A real-valued orthogonal periodic sequence of a period N=2ν generated from real-valued shift-orthogonal finite-length sequence of length M=2ν+1 is obtained by convoluting partial sequences and based on that controls the number of multiplications and the number of additions to increment on the order of Nlog2N without using fast Fourier transformation. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(10): 18–28, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20294 [ABSTRACT FROM AUTHOR]

In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non-negative weights for edges is divided into k subsets, the set of edges for which both endpoints are contained in different subsets is called a k-way cut or k-cut. The problem of obtaining the k-way cut that minimizes the sum of the weights is an important research topic that appears in many practical applications such as VLSI design. In this paper, the author introduces recent results including cases in which sets of terminals or sets of terminal pairs that are to be separated are further specified in this problem and cases in which the objects to be partitioned are extended from graphs to hypergraphs or submodular set functions. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(10): 63– 78, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20341 [ABSTRACT FROM AUTHOR]

This paper discusses codes, and a decoding method, that can correct compound errors containing a mix of random and burst errors. Specifically, the paper provides a minimum compound distance that represents a compound error correcting capacity for iterated codes, proposes a compound error correcting decoding algorithm for the code, and demonstrates that the decoding algorithm is capable of correcting compound errors up to half the minimum compound distance of the code. The proposed decoding algorithm is a generalized decoding method in which the decoding method for iterated codes indicated by Reddy and Robinson is a particular case. By this generalization, the proposed decoding algorithm can correct compound errors that cannot be corrected by conventional decoding methods. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(1): 60–72, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20035 [ABSTRACT FROM AUTHOR]

This paper considers an Internet agent system in which a tremendous number of agents operate, frequently appearing and disappearing, and discusses the fault-tolerant algorithm. Application of the snapshot algorithm to the agent system is considered. The snapshot algorithm is used to view the whole situation (snapshot) of the distributed system. The snapshot algorithm of Chandy and Lamport [2] is considered as a representative snapshot algorithm, in terms of the high efficiency and the simplicity of the procedure. It is not practical, however, to apply their snapshot algorithm to the distributed agent system in which a tremendous number of agents operate. From such a viewpoint, this paper extends the idea of Chandy and Lamport's algorithm and proposes a subsnapshot algorithm, in which the snapshot is taken among the agents who are in the causal relation, through message exchange and agent creation. Then, an efficient rollback algorithm is proposed, which is based on the snapshots taken by the subsnapshot algorithm. In the general rollback algorithm utilizing the snapshot, all agents must roll back. In contrast, in the rollback algorithm proposed in this paper, it suffices that only some agents should roll back. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(12): 43–57, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20208 [ABSTRACT FROM AUTHOR]

This paper proposes a new algorithm for the unconstrained optimization problem, which is derived as an application of the control theory called Direct Gradient Descent Control. The static optimization problem is solved by using a dynamic controller in which the convergence speed can be greatly accelerated. The major idea is to consider the objective function F(x) and its time derivative dF(x(t))/dt as the evaluation criteria, and to apply the gradient descent method. It is verified by simulation that the proposed dynamic mathematical programming has a very great capability to converge to the optimal solution. It is also interesting to note that the method has to a certain extent the ability to find not only local optimal solutions, but also global optimal solutions. This paper improves the basic algorithm of dynamic mathematical programming so that it is suited to global optimization. The new algorithm generates movement toward the global optimal solution by utilizing two different trajectories with interaction (the chaotic trajectory and convergence trajectory). It is verified by simulation that the new algorithm functions as a global optimization procedure with a high success probability. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(6): 20–27, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20094 [ABSTRACT FROM AUTHOR]

This paper considers an extension of the hidden Markov model, called the hierarchical hidden Markov model, and proposes an EM algorithm and an approximate algorithm. The EM algorithm proposed in this paper differs from the existing training algorithm, which is called the Baum–Welch algorithm, and guarantees that the likelihood is always increased by updating the parameters. The approximate algorithm has the advantage that it can be applied to problems in which observation of the training sentence and training of the parameters proceed in parallel. These algorithms and their derivations are simplified, compared to the existing training algorithm, by using stochastic context-free grammar. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(5): 59–69, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10172 [ABSTRACT FROM AUTHOR]

The problem of finding the point in time at which a known audio or video source (reference signal) appears in a long audio or video source (input signal) is referred to as a time series search, in contrast to a text string search. In a time series search, a search can be performed quickly by combining the audio and video, and then identifying several search conditions using logical equations. Thus, in this paper the authors describe the application of the time series active search method, a method to search audio signals proposed in the authors' previous paper, to video searches. Next, the authors propose an efficient algorithm for AND searches and OR searches of reference signals. In addition, the authors propose a multimodal AND search which combines audio and video. The proposed algorithms are faster than combining the results of searches performed individually. For instance, in an OR search of a reference signal, when the mutual similarity in the reference signals is above 0.8, five reference signals can be searched in a search time that is 1.2 times faster than searching one reference signal. © 2003 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 86(12): 54–64, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10142 [ABSTRACT FROM AUTHOR]

In this paper, a formulation of the convergence property of the NLMS method, an updating algorithm for an adaptive Volterra filter, is discussed. To date, much research has been carried out on the convergence property of the updating algorithm in a linear adaptive filter. However, there has been insufficient study of the updating algorithm for the second-order adaptive Volterra filter. In this paper, the convergence property of the E-NLMS method, an updating algorithm in the second-order adaptive Volterra filter, is formulated and the convergence property of the second-order adaptive Volterra filter is theoretically determined. In the formulation of the convergence property we use the first-order recursive filter expression, which is effective for studying various characteristics of the NLMS method in linear adaptive filters. In addition, it is recognized that the nature of the input signal to the diagonal (D) elements of the second-order Volterra system is different from that of the input to the other (ED) components. By means of computer simulation, it is confirmed that the convergence property given by the derived theoretical equation can sufficiently express the actual convergence property. © 2002 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 85(10): 40–50, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.1124 [ABSTRACT FROM AUTHOR]

In this paper, we propose an active noise control (ANC) system without secondary path model (Ĉ filter). The proposed system is based on the simultaneous perturbation optimization method with block process. Consequently, the coefficients of the adaptive filter in the proposed system are updated by error signals only. The conventional ANC system using the Filtered-x algorithm becomes unstable due to the error between the secondary path from a secondary source to an error sensor and its model. On the other hand, the proposed ANC system has the advantage of becoming stable because of not using the model. In this paper, we show the principle of the proposed ANC system and also the effectiveness of this system by computer simulations. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(10): 47–55, 2000 [ABSTRACT FROM AUTHOR]

This paper discusses a new figure fracturing algorithm to be used in input data generation for the variable-shaped EB (electron beam) exposure system. In the input data generation of this kind of system, processing is required in which the individual polygons composing the mask pattern are represented as a set of trapezoids (figure fracturing). The figure fracturing considered in this paper differs from those in the conventional methods, in that the generation of a narrow trapezoid as well as the partitioning of the critical part is suppressed, in order to improve the accuracy of LSI mask fabrication. In this paper, the problem is solved as the fracturing of the composite rectangle into a set of rectangles by removing slant edges from the polygon. The relation graph is introduced to represent the relation among the partitioning line candidates. A graph-based algorithm is presented that efficiently selects the adequate partition lines from all possible candidates. The proposed method is applied to the mask fabrication for 64 M and 256 M DRAM, and a satisfactory fractured result is obtained in a practical execution time. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 87–102, 2000 [ABSTRACT FROM AUTHOR]

It is known in the normalized least mean square (NLMS) algorithm that the convergence time can be reduced by applying a control in which the step gain is gradually reduced, as the estimation precision is improved. A problem in realizing this idea is that the instantaneous value of the estimation precision which is needed in the control of the step gain cannot be observed directly from the residual signal which contains external disturbances. This paper considers a block length control, which can be used in the “summational” NLMS method. The method is able to improve the convergence of the estimation precision, as in step gain control, and a method of reducing the convergence time is proposed, utilizing the fact that saturation of the convergence behavior can be observed iteratively by extending the block. In addition, it is highly likely in an actual adaptive system that the reference signal, the power of the external disturbance, and the impulse response of the unknown system to be estimated as the coefficients of the finite impulse response (FIR) filter will change. It is not realistic to ignore the possibility of these changes in discussing the control of convergence. In the last part of this paper, it is shown that the proposed control method can handle these changes. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(12): 54–64, 1999 [ABSTRACT FROM AUTHOR]

The stack filter is the most systematic among the nonlinear filters, including the weighted median filter and the morphology filter. The authors undertook to expand the class of stack filters and to increase the number of degrees of freedom in the design. They employed a fuzzy Boolean function in which the output Boolean function takes a continuous value between “0” and “1,” and proposed a fuzzy stack filter defined by that function. Up to the present, the fuzzy median filter and the fuzzy center weighted median filter have been presented as the most fundamental and simplest fuzzy stack filters. This paper proposes a fuzzy weighted median filter in which the weighted median filter, which is a more general nonlinear filter, is given a fuzzy property through the stack filter. The fuzzy weighted median filter changes continuously from the weighted median filter to the weighted average filter by varying the setting of the fuzzy Boolean function. This implies that the fuzzy weighted median filter has a high noise elimination ability for both impulsive and Gaussian noise. The fuzzy weighted median filter can be designed independently for the weight function and the fuzzy Boolean function. This paper aims at a simple design for the weight function and the fuzzy Boolean function, without losing its general character. The weight is approximated by an S-shaped function with only the distance from the processed point as the parameter, and the fuzzy Boolean function is approximated by a sigmoid function. The design is reduced to the determination of four parameters, which is performed by the LMS algorithm. Through application examples, the properties and the effectiveness of the fuzzy weighted median filter are revealed. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(10): 40–49, 1999 [ABSTRACT FROM AUTHOR]

In this paper, the geometric learning algorithm (GLA) is proposed for an elementary perceptron which includes a single output neuron. The GLA is a modified version of the affine projection algorithm (APA) for adaptive filters. The weight update vector is determined geometrically with respect to the orthogonal complement of the k patterns to be classified, where k is the order of the GLA. In the case of the APA, the target of the coefficient update is a single point which corresponds to the best identification of the unknown system. On the other hand, in the case of the GLA, the target of the weight update is the area in which all of the given patterns are classified correctly. Thus, their convergence conditions are different. In this paper, the convergence condition of the first-order GLA for 2 patterns is derived theoretically. The condition is represented by the relation between the angle θ of 2 patterns and the learning rate λ. Next, the new concept of the angle ψmin of the solution area is introduced for the case of many patterns. Computer simulation results indicate that the relation between ψmin and λ for convergence can be approximated by the relation between θ and λ for 2 patterns. Furthermore, it is proved that the first-order GLA always converges regardless of the number of patterns when λ = 2. By our analysis and proof, the convergence of the first-order GLA is guaranteed and its usefulness as the learning algorithm is confirmed. The distributions of ψmin and λ for the convergence of the first-order GLA are approximately determined. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(9): 29–38, 1999 [ABSTRACT FROM AUTHOR]

The solution of a system of linear equations is very important in various fields of engineering, and various methods have been presented for the numerical solution. Especially, in the adaptive signal processing and adaptive control, the system of equations is often considered where the coefficient matrix is (pseudo-) positive-definite and symmetrical. The conjugate graduate method is known as a means to solve such a system of equations. Letting the rank of the coefficient matrix be R, it is a method where the solution for the system of equations is determined by iterating a certain procedure R times. In this method, even if the iterative process is terminated on the way due to the constraint for the computation time, for example, an approximate solution which is somewhat accurate is obtained. This method, however, still has room for improvement with respect to the accuracy of the approximate solution. From such a viewpoint, this paper examines geo- metrically the iterative computation process in the con- jugate gradient method and, based on that result, propos- es a new method of iterative solution for the system of linear equations with symmetrical coefficient matrix. Then the original method is slightly modified and an adaptive algorithm is derived by applying the result to the parameter estimation of the adaptive filter. Those methods are based on the orthogonal projection operation from the solution to be determined to the linear space. Consequently, it is expected that, even if the iterative computation is terminated on the way, a more accurate approximate solution is obtained, compared to the case of the conjugate gradient method or the adaptive algorithm based on the conjugate gradient method. By the property of the method proposed in this paper, the method is useful when the coefficient matrix is ill-conditioned. It is expected that the method will effectively be utilized in the signal processing and control. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of a multirate complex recursive weighted least squares (MC-RLS) algorithm based on an analytic signal. Conventional adaptive filters for multiple sinusoid extraction have been based on lattice filter structures or gradient methods because of their low computational cost and/or low sensitivity to quantization errors. On the other hand, the RLS algorithm is easy to introduce assuming time-variant quantities in the algorithm when sinusoid frequencies have the time-varying property. However, the relationship between the tracking capability and the quantization error of the least-squares (LS) algorithm in the transversal structure has not been reported. In addition, an improvement algorithm for these errors have not been reported. In this paper, we shall describe a new RLS algorithm in a transversal filter structure with a superior transient property, reduced sensitivity to quantization errors, and low computational cost. First, an analytic signal-based autoregressive model is introduced and the MC-RLS algorithm is shown. Then, using an excess mean-square error of the MC-RLS algorithm, the tracking capability shown to be unaffected by the analytic transform and the decimation. In addition, the floating-point error and the computational cost of the MC-RLS algorithm are analyzed. It is shown that both floating-point error and computational cost are smaller than those of conventional RLS algorithms that use real signals. [ABSTRACT FROM AUTHOR]

In the convolutional code. the minimum free distance is the important parameter to evaluate the performance of the code. Recently, it has been considered necessary, however, for a more strict evaluation of the performance to examine the number of code words with weights around the minimum free distance, i.e., the more general distance spectrum. In general, it is difficult to derive the distance spectrum of a code, including the derivation of the minimum free distance when the code size is enlarged, and it will be significant if it is derived easily. This paper proposes an algorithm that can be derive the distance spectrum with a high speed, compared to the method already proposed. The algorithm presented in this paper is an improvement of the fast algorithm for searching trees (FAST) proposed by M. Cedervall and R. Johannesson. The distance spectrum can be derived with approximately one-half the computational complexity compared to FAST. [ABSTRACT FROM AUTHOR]

This paper presents a design method of data-dependent filters that uses simplified fuzzy interference. Since the antecedents of fuzzy inference can comprise several local characteristics (i.e., observation values), it is possible for the fuzzy filter to adjust its weights to adapt to local image data. The tuning of membership functions and fuzzy rules of the proposed filter results in a least mean square (LMS)-like algorithm. Thus, local characteristics can be increased for the proposed fuzzy filter optimally. This paper, introduces a new observation value (calculated from local statistics) into the proposed filter. The proposed filter changes filter behavior according to the local properties of signals and provides good noise attenuation in all regions of image, including detail regions while still preserving the details. [ABSTRACT FROM AUTHOR]

This paper proposes a new method for designing the optimal infinite impulse response (IIR) Hilbert transformer. Until now, finite impulse response (FIR) filters have mostly been used in the design of the digital filter for the circuit such as the Hilbert transformer, where the linear-phase response is required. Several methods have been proposed for designing the IIR filter, which, however, had problems in the complexity of the algorithm or the accuracy of the designed Hilbert transformer. This paper considers first the FIR Hilbert transformer as a model. The design of the tap coefficients for the IIR filter which gives the same output as that of the model, when the same input is given, is reduced to the parameter estimation problem when the Kalman filter is used for control. Then the IIR Hilbert transformer is designed in the time domain. To obtain a better response, an evaluation function is defined that represents the error from the ideal frequency response. The tap coefficients are fine-adjusted by the Fletcher-Powell method so that the evaluation function is minimized. By this approach, it is possible to design the IIR Hilbert transformer while maintaining the stability and the phase linearity, which are the features of the FIR filter. The 16th-order IIR Hilbert transformer actually is designed by the proposed method, and it is shown that a performance better than the 30th- and the 31st-order reference FIR Hilbert transformers can be realized. [ABSTRACT FROM AUTHOR]

This paper discusses the hierarchical properties of digraphs and proposes flowchart decomposition algorithms using these properties. The hierarchical structure discussed here is based on only the topological relation- skips between vertices and the inclusive relationship among sets of vertices. When the given flowchart represents the control flow of a computer program, this hierarchical structure also shows strong correspondence between these inclusive relationships and program modules. The proposed flowchart decomposition algorithm consists of one algorithm for detecting modules and another algorithm for further decomposing the detected modules. This paper focuses on the former algorithm. Because the hierarchical structure discussed in this paper corresponds to the traditional program modules (e.g., function or procedure) of most of the computer programming languages, the module-detection algorithm can be used not only for decomposing flowchart but for more general purposes, including module design. Two types of module-detection algorithm are discussed in this paper. One detects all modules, and the other detects a restricted subset of modules from the standpoint of flow-chart decomposition. We then demonstrate with a practical example that the latter algorithm is ten times faster than the former. [ABSTRACT FROM AUTHOR]

The information storage algorithm of a Hopfield-type network is a kind of self-correlation learning. This algorithm needs the condition in which vectors of learning patterns cross at right angles to each other. This paper proposes n method to make this condition easier. To this purpose, threshold is used. An investigation of how to decide quantity is included. This paper discusses a network with units whose state is 1 or 0. Fixing method of threshold has not been proposed before to this type of network. It is, therefore, proposed in this research; the goal is to facilitate learning patterns. [ABSTRACT FROM AUTHOR]

This paper notes the fact that the recording code often takes the form of a multitrack code, as well as the fact that the k-constraint in the (d, k)-constraint is considerably relaxed, which increases the capacity. Then the paper proposes a systematic construction algorithm for the fixed block-length multitrack (d, k) code and discusses the coding characteristics. A simple idea is applied in the code construction to apply the (d, ∞) code to all tracks except for one in order to reflect the relaxation of the k-constraint on the improvement of the coding rate. The (d, ∞) code is applied to the left track if the vector obtained by the elementwise logical sum of the code words satisfies the k-constraint and, if not, the (d, k) code is applied. The author has already proposed a systematic construction algorithm for the efficient fixed block-length (d, k) code. This paper discusses mainly the systematic construction algorithm and the coding characteristics for the fixed block-length (d, ∞) code, based on the unique ordering technique of the binary sequence by the Schalkwijk algorithm, as the systematic construction algorithm for the fixed block-length multitrack (d, k) code based on the forementioned idea. The coding rate and the coding efficiency are examined, and the result indicates that the characteristics are very close to those of the (d, ∞) code. [ABSTRACT FROM AUTHOR]

This paper proposes a fast learning algorithm of neural networks and evaluates the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel. The backpropagation (BP) algorithm which is used widely to train neural networks has a slow convergence rate because it is based on the gradient descent method. This paper presents a fast learning algorithm using the recursive least squares (RLS) algorithm which has a fast convergence rate as an adaptive algorithm for adaptive linear filters. In the proposed algorithm, the sum of the squared error between the actual total input and the desired total input is used as the cost function to apply the RLS algorithm. A simulation result on the exclusive-OR problem indicates that the proposed algorithm is about 8.8 times faster than the BP for the number of iterations required to converge. Recently, there has been interest in adaptive equalizers as an application field of neural networks. However, the performance of an adaptive equalizer using a neural network in a frequency-selective fading channel which is observed in land mobile communications has never been evaluated. Therefore, in this paper, the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel are evaluated. Especially, an adaptive equalizer using the selectively unsupervised learning neural network proposed by the authors is considered. The adaptive equalizer can reject the false learning by carrying out learning selectively. It is shown that the adaptive equalizer is superior to the conventional one and the one using the conventional neural network. [ABSTRACT FROM AUTHOR]

This paper proposes a design method for the FIR two-channel perfect quadrature mirror filter (QMF) with the linear phase. The two-channel perfect QMF can be designed by Vetterli's method, where a system of equations representing the condition for the perfect reconstruction of the signal is solved. The filter designed by this method, however, does not, in general, have good frequency characteristics. This paper presents the design for the two-channel QMF with a perfect reconstruction and a good amplitude characteristic. The method is based on Vetterli's method, and a constraint to approximate the amplitude charac- teristic in the frequency domain is added to the condition of perfect reconstruction in time domain. Then Remez' algorithm is applied to the derived system of equations. The construction of the two-channel perfect QMF, when the coefficient is quantized, also is discussed. Furthermore, a method is shown in which the two-dimensional (2-D) perfect QMF is designed by applying the McClellan transformation to the obtained 1-D QMF. The condition for the McClellan transformation for the perfect reconstruction is derived. [ABSTRACT FROM AUTHOR]

With the recent development of semiconductor integration technology, the amount of data that must be handled in the layout design of VLSI is increasing rapidly. Even if the improvement of the processing speed of the computer in the future is considered, it is desired to develop a high-speed layout algorithm compared to the conventional method. This paper discusses the k (> 2)-way graph partitioning problem, which is one of the most basic problems concerning the layout design. A parallel algorithm is proposed. The general method to solve this problem has been to apply hierarchically the two-way graph partitioning algorithm. In this method, the algorithm can easily be executed in parallel by operating a number of processors at each hierarchy. A problem then is the efficiency of the processor and the computation time. This paper considers the k-way graph partitioning and proposes a new method called nonhierarchical k-way graph partitioning, aiming at the education of the computation time by parallel processing. In general, it is considered difficult to improve the speed sufficiently by the parallel processing, while maintaining the same accuracy of the solution as that of the sequential algorithm. In this paper, the effectiveness of the proposed algorithm is shown by a simulation experiment on the sequential computer. [ABSTRACT FROM AUTHOR]

Numerous studies have been made to analyze the input/output relation of the weakly nonlinear system by applying the theory of Volterra series. When this theory is applied directly to the analysis, a complex multiple integration must be calculated. On the other hand, it is shown in this paper that the solution can be derived by a systematic calculation using multiplications and additions if the input is restricted to the sum of sinusoidal waves and only the steady-state output is considered for the system represented by a nonlinear equation or a circuit equation. A detailed algorithm is presented, which is called the &;dquo;nonlinear steady-state method.” The purpose of this paper is to demonstrate the usefulness as well as the problems of the nonlinear steady-state method through examples. The first step is to derive the algorithm for the analysis, which can product a result equivalent to that of the theory of Volterra series. The Duffing equation is used as an example of the system represented by a nonlinear differential equation. Then, as an example of the system represented by a circuit equation, the method is applied to the analysis of the linear antenna with a nonlinear load. The application of the method is inevitably limited due to the condition that the system is weakly nonlinear and the input is the sum of a finite number of sinusoids. However, the result seems to indicate that the method is very useful when those conditions are satisfied. [ABSTRACT FROM AUTHOR]

This paper considers an unknown nonlinear static system with an adjustable parameter (input parameter). The problem is to find the least-square approximation input parameter. A recursive algorithm is proposed that estimates this least-square approximation parameter without an identification of the system. An output of the system is observed under a noisy environment. Suppose that the dimension of the output is equal to that of the input. In this case, the system characteristic can be regarded as a regression function, hence a recursive algorithm that can be constructed that minimizes tile difference between the expectation of the output and a desired value of the output by using the stochastic approximation method or the adaptive Robbins-Monro procedure. On the other hand, if the dimension of the output is greater than that of the input, the regression equation has no solution. Therefore, the usual stochastic approximation method or the adaptive Robbins-Monro procedure cannot be used. The algorithm proposed in this paper estimates the least-square approximation input parameter that minimizes the squared error of the output. Especially, this algorithm agrees with the usual adaptive Rohbins-Monro procedure if the dimension of the output is equal to that of the input. Some numerical simulations ale shown and the availability of the algorithm presented herein is confirmed. [ABSTRACT FROM AUTHOR]

Suppose that a biconnected planar graph G = (V, E) is given such that each vertex and edge are weighted. This paper proposes an algorithm for finding a planar embedding such that the total sum of weights of vertices and edges on the exterior window is maximized (among all possible planar embeddings of G). Among algorithms for determining planarity of a graph there is one that uses a data structure called a PQ tree. The algorithm presented in this paper is the one which extends it and uses the PQ tree as its data structure as well. However, it can find a required planar embedding in O(¦V¦) time by assigning special weights to each node of each PQ tree generated in the algorithm. [ABSTRACT FROM AUTHOR]

This paper shows that the learning identification (the normalized LMS) algorithm can be expressed by a first-order IIR lowpass filter having rapidly varying coefficients as a function of output signal to be sent to an unknown system to be estimated. Based on the expression, this paper studies the estimation error of adaptive filters obtained by the learning identification algorithm. It is pointed out that the mean of estimation error given by the conventional analysis corresponds to the output fluctuation which can be computed by replacing varying coefficients of the lowpass filter with its arithmetic mean. However, the output fluctuation is affected by the time constant specified by the coefficients of the lowpass filter and it has a characteristic that it increases rapidly when time constant is short and decreases slowly when it is long. This means that the actual estimation error becomes larger than the result given by the conventional analysis. According to the analysis shown in this paper, it can be seen that the estimation error consists of elements for which the portion increased by the effect of time constant become fewer anti-proportionally to the number of the tap, and those elements which increase at a constant rate independently of the number of the tap. It was shown also by simulation using white noise that the difference between the estimation error obtained in actual estimation operation which occurs when the number of the tap is small and the result given by the conventional analysis can be explained well by the analysis by simulation using white noise. [ABSTRACT FROM AUTHOR]

A priori estimation is presented for a computational complexity of the homotopy method applied to a certain class of hybrid equations for nonlinear strongly monotonic resistive circuits. First, an explanation is given as to why a computational complexity of the homotopy method cannot be a priori estimated for calculating solutions of hybrid equations in general. In this paper, the homotopy algorithm is considered in which a numerical path-following algorithm is executed based on the simplified Newton method. Then by introducing Urabe's theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, it is shown that a computational complexity of the algorithm can be a priori estimated when applied to a certain class of hybrid equations for nonlinear strongly monotonic resistive circuits whose domains are bounded. This paper considers two types of path-following algorithms: one with a numerical error estimation in the domain of a nonlinear operator; and one with a numerical error estimation in the range of the operator. [ABSTRACT FROM AUTHOR]

This paper discusses the system for automatic design of the parallel/pipelined VLSI architecture based on the signal processing algorithm. A new design language is introduced into the proposed system. The language is defined so that the time variable used in the signal processing algorithm can easily be described. The system has a high modularity, and the modules can be combined into a hierarchical structure. By this scheme, the algorithm with a high complexity can easily be described. The algorithm inputted to the system may contain a backward time-flow of the delayed data as well as a complex hierarchical. structure, which makes it difficult to execute the data-flow graph obtained directly from the algorithm by the parallel/pipelined structure. From such a viewpoint, this paper adopts the following procedure. The data-flow graph is derived from the given algorithm. A sufficient parallelism and a highly efficient pipelined mechanism are extracted from the obtained graph. Then the parallel processing architecture is designed. As an example, a parallel/pipelined architecture is designed for a simple adaptive signal processing algorithm. The result is compared with the traditional design examples, and it is shown that the efficient data-flow architecture is derived. [ABSTRACT FROM AUTHOR]

In a VLSI layout design using the building block approach, design is divide into two phases, placement and routing. On the other hand, a new hierarchical floorplanning method was proposed by Dai et al., in which a global routing for the evaluation of the placement. However, the precise estimation of routability is difficult since the global routes in this method do not correspond to the routing region such as channels and switchboxes. In this paper, a new method is proposed, which simultaneously and hierarchically obtains floorplan, shapes and positions of modules, and global routes which directly correspond to switchboxes and channels. In this method, the routing-based partitioning, the hierarchical detailed global routing, and the hierarchical positioning are repeatedly executed, and a chip which small area and short wire length is obtained. This paper presents these three algorithms, and discusses the experimental results of each algorithm and the whole proposed method in a comparison to the conventional method that separately executes placement and routing. [ABSTRACT FROM AUTHOR]

In nonlinear programming problems, an objective f(x) is optimized (maximized or minimized) subject to some constraints. Such problems are also called constrained optimization problems. Most of the algorithms in nonlinear programming are classified into two categories: 1) transformation methods; 2) projection methods. The homotopy methods, which are the subject of this paper, belong to the category of projection methods. The main feature of the homotopy methods compared with other projection methods is that they are good at global convergence (which is lacking in most of the projection methods) but are not good at convergence speed (which is the strong point of most of the projection methods). This paper discusses the homotopy methods in nonlinear programming and show that the piecewise-linear homotopy method using the Newton homotopy and polyhedral subdivision is very effective for solving nonlinear optimization problems. A new algorithm is proposed that exploits the partial separability and linearity of the Kuhn-Tucker equations (which appear in the nonlinear programming problems). By this exploitation, the computation efficiency is improved markedly compared with the conventional homotopy methods using simplicial subdivision. Moreover, the proposed algorithm converges quadratically, thus accurate solutions can be obtained rapidly. It is proved also that the proposed algorithm is globally convergent for the constrained convex optimization problems. Except for the shortcoming that the programming is complicated, the proposed algorithm has well-balanced effectiveness. [ABSTRACT FROM AUTHOR]

This paper derives a design method for an ARMA 4-line lattice filter using a sliding rectangular window. The adaptive ARNA 4-line lattice filter already proposed uses a forgetting factor, which is one of the weighting functions to estimate coefficients of a time-varying system in which system coefficients vary with sufficient smoothness. Therefore, the effect of past observed signal over the estimated coefficients decreases exponent tally. The filter presented here is realized using a rectangular window because the concern is over the effects of past observation signal rather than window length. Using this filter, an input signal is estimated when designing; furthermore, a system can be identified in which an arbitrary section in the frequency domain is weighted. Thus, by not only analyzing voice signal which is considered a model whose input signal is unknown and EEC data but also by weighting the frequency domain, for example, the holmant in the low-frequency domain can be estimated in low degree with very high precision and a specific wave (such as α activities) in EEC data can also be detected. Moreover, in this paper the algorithm is verified by model experiments. [ABSTRACT FROM AUTHOR]

Pattern recognition methods in which multiple templates are prepared for each category and which recognize input patterns using those templates usually partition training patterns into clusters and generate templates as centroids of each cluster. However, most clustering algorithms proposed in the literature aim at minimizing the square error distortion measure when each cluster is represented by Its centroid. Therefore the result obtained is not necessarily optimal iron the viewpoint of discrimination. This paper describes a new clustering algorithm which is a method of obtaining an optimum solution to a template generation problem. The simulated annealing is used for searching for a cluster partition that minimizes the "degree" of recognition error when all training patterns are recognized by using centroids as templates. This paper also describes a vowel template generation problem in speech recognition as an example of pattern discrimination problems. The new algorithm yielded better experimental results than the LBC algorithm and the LVQ algorithm. [ABSTRACT FROM AUTHOR]

In information theory, the channel capacity is defined as the maximum of the transmission rate at which information can be conveyed reliably over a noisy channel. This paper presents a new algorithm for computing the capacity of discrete memoryless channels. The problem of determining the capacity is a concave programming. Thus it can be computed by solving a system of nonlinear equations termed the Kuhn-Tucker equations. Newton's method often is used to solve nonlinear equations. However, it does not have global convergence and may not converge when the starting point is not close to the solution. A globally convergent algorithm using simplicial subdivision has been proposed for the capacity evaluation, but it is very slow and cannot be applied to large-scale problems. In this paper, the Kuhn-Tucker equations are transformed into a system of equations with separable mappings by introducing auxiliary variables. This system of equations can be solved by a homotopy method using rectangular subdivision, which Is much more efficient than the simplicial-type algorithm. Moreover, the proposed algorithm has quadratic convergence, so it converges rapidly similarly to Newton's method, The global convergence of the proposed algorithm is also proved herein. By numerical examples, it is shown that the proposed algorithm is more efficient than the welt-known Arimoto algorithm.

In information theory, the channel capacity is defined as the maximum of the transmission rate at which information can be conveyed reliably over a noisy channel. This paper presents a new algorithm for computing the capacity of discrete memoryless channels. The problem of determining the capacity is a concave programming. Thus it can be computed by solving a system of nonlinear equations termed the Kuhn-Tucker equations. Newton's method often is used to solve nonlinear equations. However, it does not have global convergence and may not converge when the starting point is not close to the solution. A globally convergent algorithm using simplicial subdivision has been proposed for the capacity evaluation, but it is very slow and cannot be applied to large-scale problems. In this paper, the Kuhn-Tucker equations are transformed into a system of equations with separable mappings by introducing auxiliary variables. This system of equations can be solved by a homotopy method using rectangular subdivision, which is much more efficient than the simplicial-type algorithm. Moreover, the proposed algorithm has quadratic convergence, so it converges rapidly similarly to Newton's method. The global convergence of the proposed algorithm is also proved herein. By numerical examples, it is shown that the proposed algorithm is more efficient than the well-known Arimoto algorithm. [ABSTRACT FROM AUTHOR]

Recently, for signal processing such as echo cancellation and equalization it is required to develop IIR-adaptive digital filters. This paper proposes a new-type IIR- adaptive algorithm based on the orthogonalization method, considers the convergence of the algorithm, and verifies its effectiveness by simulation. White's algorithm is one of IIR-adaptive algorithms reported thus far and Feintuch's algorithm is known as its approximation algorithm. This paper also derives an IIR-adaptive algorithm using both Feintuch's algorithm and the orthogonalization method, First, it can be shown that a generalized algorithm (IIR-LI) of IIR-learning identification method based on previous heuristic methods can be derived using the idea of Feintuch's algorithm and the conjugate gradient method. Next, a new IIR-adaptive algorithm (IIR-AACG) based on the orthogonalization principle of the conjugate gradient method is presented. Further, by applying the orthogonalization method to a past input vector sequence we derive an IIR-Affine projection algorithm (1IR-AP). Finally, these algorithms are compared by computer simulation to verify the effectiveness of the orthogonalization method. [ABSTRACT FROM AUTHOR]

gggggAssume that an n × n dot matrix is stored in consecutive n words of a computer with one word being n bit. This paper discusses eight operations to rotate or transpose the dot matrix in horizontal/vertical! slant direction. As is well known, such operations form a group. This paper presents a unified description of the algorithms, and it is shown that all eight algorithms can be derived by suit- ably setting the constants in the unified algorithm. Then it is shown that the algorithms can be transformed to each other by simple transformation rules for the constants, and those transformation rules are shown to form a group. The foregoing algorithms for the dot matrix are not unique, and there can be different descriptions for the algorithm producing the same result. Consequently, there can be various versions of the eight algorithms as well as versions of transformation rules. This paper shows that one of the two groups formed by the transformation rules is isomorphic to the group of algorithms, but the other is not isomorphic. [ABSTRACT FROM AUTHOR]

The paper treats the problem of automatic placement of building blocks of different sizes. This problem arises frequently in automating the layout design of LSIs. In this paper, a method is described for finding a global placement taking into account the connectivity between blocks as well as dimensions of blocks and placing regions. A method is proposed to establish a force model such that attractive forces caused by the connectivity between blocks and repulsive forces caused by the block overlaps are exerted on the blocks. and to derive a placement result as a system equilibrium state. The placement procedure is as follows. We start with the initial placement obtained only by applying attractive forces caused by connectivity, and then add gradually repulsive forces which are calculated based on the actual overlapping area between blocks. As a result, block overlap is removed and thus we can obtain a global placement considering local shape fitness while taking connectivity between blocks in a global way. In this paper, we explain first an outline of the proposed algorithm and then describe details of the methods for realizing it, e.g., functional forms of repulsive force against overlapping area, increasing ratio of repulsive force, and calculation method I or the block equilibrium position and block orientation. Finally, the experimental results using examples with 17 and 33 blocks to demonstrate the effectiveness of the proposed algorithm are explained. [ABSTRACT FROM AUTHOR]

This paper presents a realization of an arbitrary conductance matrix using operational amplifiers, together with same applications. It is shown first that any conductance matrix can be realized using operational amplifiers, and the design algorithm which is convenient in the realization is given in the form of a flowchart. Then as an application, a construction of a practical matched bilateral amplifier is presented, together with its application. The realization of a gyrator is also shown. The method presented in this paper is a new and simple way to realize an arbitrary conductance matrix. The matched bilateral amplifier obtained by the proposed method is simple and better than the traditional circuit in terms of the number of circuit elements, element sensitivity, adjustment of the matching impedance, dynamic range and stability. As a practical example of application, the circuit is applied to the four-line carrier telephone link. [ABSTRACT FROM AUTHOR]

This paper proposes a first-order algorithm for unconstrained nonlinear optimal control problems based on the fixed point theorem. The method has the following features: (a) the algorithm is simple; (b) unlike second-order algorithms, the choice of the first approximation is less critical; and (c) unlike gradient methods, experimental selections of parameters during iterative calculations are not required. This paper also describes the conditions of convergence of the algorithm in the space of continuous functions, and the optimality of a solution derived. [ABSTRACT FROM AUTHOR]

ggThis paper discusses a design of two-dimensional IIR digital filter in the frequency domain, where the magnitude and the phase responses are assigned separately to the denominator and the numerator, respectively, and are designed independently, The design procedure is as follows. Considering only the phase, the all-pole filter (denominator polynomial) is designed. Then the numerator is designed from the 2-D mirror-image polynomial as a correction for the magnitude. In earlier methods of this kind, a nonlinear problem is encountered in the design of the all-pole filter in approximating the phase. By contrast, in this paper, the 2-D group-delay (phase) approximation is reduced to the 2-D spectral approximation by using the cepstrum, and the derivation of the parameters is reduced to the solution of the 2-D normal equation. From the viewpoint of ensuring the stability, an approximation by three-term separable all-pole filter is also shown, which makes the stability test easy. An algorithm is shown which solves the approximation problem for this case by iteratively solving the linear problem. The proposed design method features smaller computational complexity, since the denominator and the numerator polynomials are derived independently. In addition, the design is made easy since the linear problems arc handled throughout the filter design. [ABSTRACT FROM AUTHOR]

This paper proposes an iterative approximation technique of log-magnitude response for IIR filters. Minimization of the mean-square error between a desired log-frequency response and that of an IIR filter leads to a nonlinear problem. In this paper, the least squares problem on the logarithmic scale is approximated by the iteration of a weighted least squares problem on the linear scale. The weighting function is updated using the result of the previous iteration so that the weighted error on the linear scale approximates the squared error on the logarithmic scale. The filter coefficients at each iteration step can efficiently be obtained using a fast recursive algorithm for a set of linear equations. Several design examples are presented, which show that the iterative algorithm converges after one or two iterations in practice and the weighted error at convergence gives a good, estimate of the mean-square error on the logarithmic scale. An example is also presented, where both log-magnitude and phase responses are approximated simultaneously. [ABSTRACT FROM AUTHOR]

This paper describes a new fast computation algorithm for the discrete Fourier transform (DFT) of a real-valued sequence. The algorithm derived in this paper can compute by in-place processing using real arithmetic computation alone, in the same way as the method which uses the discrete Hartley transform (DHT). Structurally, the algorithm requires fewer computation operations than in the case with the DHT. An N-point DFT of a real-valued sequence can be computed by breaking it up into a single length-(N/2) DFT over the even-indexed part of the input sequence and two length-(N/4) DCTs over the odd-indexed part of the input sequence. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(9): 11–20, 1997 [ABSTRACT FROM AUTHOR]

This paper proposes an efficient algorithm for finding all solutions of nonlinear resistive circuits. As a computational method of finding all solutions of nonlinear equations, interval analysis is well known, and the Krawczyk algorithm is one of the most typical algorithms of interval analysis. However, the Krawcyzk algorithm is extremely inefficient for circuit equations whose nonlinearity is very great. In this paper, several techniques are proposed for improving the computational efficiency of the Krawczyk algorithm for circuit equations. These techniques exploit the special structure of the circuit equations such as separability or partial linearity. It is shown that the computation time of the Krawczyk algorithm is substantially decreased by using the proposed techniques. © 1997 Scripta Technica, Inc Electron Comm Jpn Pt 3, 80(7): 28–36, 1997 [ABSTRACT FROM AUTHOR]

This paper proposes algorithms for computing three kinds of distance between two rooted and unordered trees (R-trees) and those between two unrooted and unordered trees (trees). Those are the distance based on the strongly structure preserving mapping (SSPD), that based on the maximal closest common ancestor mapping (MCD). The time and space complexities to compute each distance between two R-trees Ta and Tb are OT(maNaNb) and OS(NaNb), respectively, and those to compute each distance between two trees Ta and Tb are OT(max(ma,mb)²NaNb) and OS(NaNb), respectively , where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The proposed algorithms for SSPD and CD are more efficient than the algorithms previously proposed, MCD is newly proposed in this paper. Those distances can be applied to structure-activity studies in chemistry and various structure comparison problems. [ABSTRACT FROM AUTHOR]

This paper introduces the parallel processing into the separable-denominator 3-D adaptive state-space filter, and discusses a realization method which is suited to the high-speed processing. The LMS (least-mean-square) algorithm is used as the adaptive algorithm, and the parallel processing-oriented structure of the separable-denominator 3-D filter is used as the filter model. The parallel processing-oriented structure of the 3-D adaptive state-space filter is obtained by extending the adaptive algorithm of the 2-D state-space adaptive filter to the above 3-D structure. The proposed algorithm is evaluated in this paper in terms of the time required for the filtering and the coefficient update, as well as the number of multipliers (adders). Finally, the proposed adaptive filter is applied to the design of the 3-D state-space digital filter, and the effectiveness of the algorithm is demonstrated. [ABSTRACT FROM AUTHOR]

In the acoustic echo canceller, the speaker input signal is sued as a reference signal to update adaptive filter coefficients, and is sometimes composed of only the far-end background noise. This paper proposes a configuration in which the estimation error is kept constant also for a voiceless noise period, while continuously updating the coefficients. The summational normalization LMS is used as the adaptive algorithm, where the products of the residual echo and the transmitted signal (i.e., the numerators of the coefficient update resulting from the normalized least mean square (NLMS) algorithm), as well as the norm of the transmitted signal (i.e., the denominator of the forementioned), are accumulated, respectively, for a certain number, and the ratio of the two sums is used as the coefficient update. The summation number is controlled by the power of the transmitted signal. When, for example, the configuration is such that the coefficients are updated only when the sum of the norms reaches a certain value (i.e., the threshold), the echo cancellation is maintained at the desired value, independently of the power of the transmitted signal. The cancellation is enhanced in the period where the power of the transmitted signal is increased. In addition to the control method, which can calculate the power of the environmental noise needed in determining the threshold, this paper analyzes the structure of the filter. [ABSTRACT FROM AUTHOR]

This paper shows that two complex coefficient transfer functions can be realized by a single hypercomplex coefficient network, utilizing all four outputs of the hypercomplex network. The realization is considered for the case where the two arbitrary complex coefficient transfer functions do and do not have a common denominator. It is shown that the transfer functions can he realized by the hypercomplex coefficient network of the same order in the former case and by the hypercomplex coefficient network with the half-order in the latter case. The realization of the transfer functions with the common denominator is interesting, but the general method to derive the transfer functions is not known. From such a viewpoint, this paper proposes the discrete-type Kautz approximation with the positive frequency as the domain of approximation, including the optimal pole determination algorithm. By this approach, two complex coefficient transfer functions with an n-th-order common denominator are derived from the two 2n-th-order real or complex coefficient transfer functions. The method can be considered as one that simultaneously approximates the amplitude and the phase. The proposed approximation method is an approximation only for the positive frequency domain, and the property of the analytic signal that the negative frequency component is zero can be utilized. As a result, the method proposed in this paper has the advantages that the degree of freedom in the filter design is enhanced and the sampling frequency can be halved. In addition, the network structure can be simplified. [ABSTRACT FROM AUTHOR]