Search

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]

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]

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]

This paper proposes an application method of the cooperative distributed multiagent model in multipath allocation algorithm and confirms its valid calculation results by realizing this model in a distributed computer environment. The multiagent model in this paper is an environment where each agent has the same function of asynchronous and parallel calculation and no globally controlling agents exist. To realize this model, this paper proposes an appropriate dividing method of the multipath allocation problem for asynchronous and parallel calculation, a unifying method of each agent's answers end interagent communication protocols. It also compares the required calculation time and the number of allocated paths of a single agent with that of the multiagents end shows the practical calculation ability of the multiagent model. [ABSTRACT FROM AUTHOR]

The control of the cell contention is a technical problem in the input queueing ATM cross-connect switch. This paper considers this problem and proposes a scheduling control method which dynamically assigns the cell transmission time. A construction of the distributed scheduling circuit also is proposed based on Batcher's sorting network. The proposed method processes the cells in the order of their arrivals, as in the conventional three-phase algorithm but has an advantage in that the throughput can he increased by approximately 26 percent without increasing the number of control processes per cell. Mother merit is that multirate ports can directly be contained in the switch. In this paper, the approximate model for the proposed method is constructed, and the mean delay and the cell loss probability are calculated theoretically. The actual operating performance is evaluated by a computer simulation. By combining the proposed method with the conventional self-routing spatial switch, a distributed switching circuit can he constructed as a whole, which is useful in developing an economical large- capacity ATM cross-connect switch. [ABSTRACT FROM AUTHOR]

The existence problem for solution of a nonlinear resistive circuit and the problem of identifying the number of the solutions are classic and basic problems in circult theory. In their paper "On the application of degree theory to the analysis of resistive nonlinear networks" (int. J. Cir. Theor. Appl., 5, pp. 35-68 (1977)), Cbua and Wang presented a unified theory for the existence of solutions for nonlinear circuit equations. That is, on the basis of the degree theory the existence of solutions of many nonlinear resistive circuits can be guaranteed in a unified manner by showing that the circuit equations are homatopic to certain odd fields. Their arguments are, however, not constructive. In this paper, an algorithm based on the fixed-point algorithm theory is presented and it is proved that by this algorithm at least one solution can always be constructed for nonlinear circuit equations whose solutions are guaranteed to exist by Chua and Wang's theorems. Usefulness of the algorithm is also demonstrated by a few examples. [ABSTRACT FROM AUTHOR]

This paper presents a polynomial-time algorithm which can determine the multicommodity flows in a planar undirected graph G. It is assumed that G remains planar if an edge is added between each source-sink pair. Given positive and real demand to each source-sink pair, the algorithms determines whether or not there exists a multicommodity flow in G realizing the specified demand, i.e., feasibility, and if it exits, the multicommodity flow is determined. It is shown that by solving the maximum-weight matching problem once for a graph which is a modification of the graph dual to the given graph G, the feasibility is determined, and by solving the problem for 0(kn) times, the multicommodity flows are determined. Consequently, if G has a vertices and k source-sink pairs, the computation time required to determine the feasibility is 0(n² log n), and the time required to determine the k-commodity flow is O(kn³ log n). The memory storage required is 0(kn). It is known that the maximum-flow min-cut theorem exists for the case of planar graph considered in this paper. [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]

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]

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]

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]

The Berlekamp–Massey method is a method of algebraic error correction in which the key equation, expressing the congruence relation of the received syndrome polynomial, the error locator polynomial, and the error evaluation polynomial, is solved and the error locator polynomial is derived as the shortest LFSR tap polynomial that generates the received syndrome. However, this method is rarely used because of its complex computation process. Consequently, this paper presents a method of deriving the LFSR tap polynomial that generates the received syndrome by the matrix-reduction method. It is shown that all tap polynomials derived by the matrix-reduction method have the error locator polynomial as a factor polynomial, and that the factor polynomial is uniquely derived as the error locator polynomial. It is also shown that the matrix-reduction method is especially useful as a derivation procedure for the error locator polynomial in terms of processing time. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(1): 30–45, 2007; Published online in Wiley InterScience (www.interscience.wiley. com). DOI 10.1002/ecjc.20234 [ABSTRACT FROM AUTHOR]

Improved Enhanced Modulo Scheduling (Improved EMS) is proposed as an efficient software pipelining method for loops with conditional branches. In EMS and Improved EMS, multiple pipeline kernels are generated, depending on the truth value of the condition, and the appropriate one is selected on execution at each iteration. Since these kernels have variables that live for the number of stages with different conditions mixed together, register allocation becomes difficult. In this paper, the authors discuss register allocation methods using interference graphs for EMS and improved EMS. The first method is a register allocation method using conventional interference graph which is applied to the deployed kernels. Because the interference graph becomes very large, however, in proportion to the number of kernels deployed in the method, the proposed method reduces the size of the interference graph by overlapping the graphs and improves the results of register allocation. These two methods were evaluated with approximating coloring algorithms. It was clear that allocation could be performed rapidly, and in a manner in no way inferior to the conventional method for the number of registers by the method by overlapping and reducing the size of the graphs. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(12): 59– 69, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20290 [ABSTRACT FROM AUTHOR]

The increasing density of LSI chip circuits is causing the execution time of tests based on the full-scan design method to become problematical. In this paper, the authors propose a method of reducing the number of ATPG patterns for a full-scan designed LSI chip by inserting test points. To reduce the number of ATPG patterns, they proposed a test point insertion algorithm based on the improved fault detection probability and a test point insertion algorithm based on the improved value assignment probability. When the authors applied the proposed methods to several actual LSI chips, they were able to reduce the number of ATPG patterns by 48% to 78% compared with the conventional full-scan design by adding test points equivalent to 0.4% to 2.2% of the total number of flip-flops in the LSI chip. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(5): 54–68, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20267 [ABSTRACT FROM AUTHOR]

Although the bounded sliceline grid (BSG) is an effective data structure for treating rectangular placement, it needs to deal with more complicated rectilinear figures such as L- or T-shaped figures in its applications to VLSI layouts. A number of studies have been conducted regarding this problem, but the methods considered in these studies not only have not considered representation of the optimal placement of complicated rectilinear figures but also have not generated permissible neighboring solutions, and searching optimal solutions by search schemes based on these methods is difficult. In order to resolve this problem, this paper proposes multilayered parametric BSG and a placement algorithm using the multilayered parametric BSG. Multilayering allows descriptions representing conditions for nonoverlapping of rectilinear figures simultaneously with constraints of each layer. Parameterization allows multiple solutions represented by the BSG. The proposed method represents complicated rectilinear figures as combinations of a number of element rectangles. When a figure (core cell) with the element rectangles having common parts is the input, it gives the conditions of the multilayered parametric BSG guaranteeing the possibility of generating an optimal solution in terms of the surface area. The practicability of the idea of the proposed method has been verified by testing with several tens of figure inputs by implementing an optimal solution search algorithm based on simulated annealing based on the proposed data structure. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(7): 66–78, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10079 [ABSTRACT FROM AUTHOR]

The authors describe a technique for selectively sharpening only edges that were blurred due to various causes without making interference factors such as random noise more conspicuous. The selective sharpening technique described in this paper is implemented as an iterative updating nonlinear algorithm obtained by discretizing a type of nonlinear reaction-diffusion time-evolution equations. The update terms of this algorithm consist of a quadratic nonlinear smoothing term, reaction term, and overshooting term. By performing quantitative evaluation experiments, the authors showed that the proposed technique has significantly better selective sharpness enhancement capabilities than existing sharpness enhancement techniques such as the peaking method. In addition, the authors introduced a processing parameter adaptive control method in the proposed technique and applied it to the suppression of breathing distortions in video sequences. Breathing distortions, which are video sequence distortions that often appear in old films, are time-varying blurring distortions that occur due to temporal variations of the focus. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(5): 33–47, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10086 [ABSTRACT FROM AUTHOR]

The backpropagation (BP) algorithm is a learning algorithm for the multilayer perception. However, when this algorithm is applied to the pattern classification problem the generalization ability may not be maximized, even if the learning converges. This paper proposes an algorithm to improve the generalization ability by shifting the hyperplane constructed by the BP algorithm on the basis of internal information. The basic properties of the algorithm are analyzed. Then, the algorithm is extended to the multilayer perception and its generalization ability is examined by computer simulation. The proposed method is shown to be useful when the training data are sparse. [ABSTRACT FROM AUTHOR]

This paper describes multitone curve-fitting algorithms for accurate determination of intermodulation distortion products in the multitone testing of ADCs used in communication applications and the like. Accuracy of our curve-fitting algorithms for coherent sampling (input frequencies known) and incoherent sampling (input frequencies unknown) was validated by numerical simulations. We found that—especially for incoherent sampling—these algorithms provide better accuracy than conventional (single-tone) curve-fitting algorithms. © 2003 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 86(8): 1–11, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.10148 [ABSTRACT FROM AUTHOR]

When a region with a certain area needs silencing, no sufficient effect can be obtained with a single-channel active noise control system. Therefore, multiple channel noise control systems using several microphones and speakers have been proposed. One of the algorithms used frequently is the Multiple Error Filtered-X (MEFX) method. The MEFX method requires prior estimation of the error path system. In the case of multiple channels, the estimation error poses more complex effects in comparison to the single channel. In addition, variations of the system during operation are problematic. In this paper, the simultaneous equation method recently proposed for the single channel in which no estimation is required for the error path system is applied to the multiple channel active noise control. In the present procedure, the coefficients of the noise control filter can be estimated without estimation of the error path system as in the case of the single channel. The method can handle the variation of the path during operation and can obtain excellent silencing effects. © 2002 Scripta Technica, Electron Comm Jpn Pt 3, 85(5): 46–55, 2002 [ABSTRACT FROM AUTHOR]

Rectangle packing is a critical problem in applications such as placement in VLSI layouts. Recently, the sequence-pair method was proposed as a representation method for rectangle packing where the general configuration is not restricted to the slice configuration. This method has led to a variety of research on applications because of its feature of packing all sequence-pairs in addition to the ability to represent any kind of packing. In this paper, we propose a method that uses the sequence-pair to represent packing L-shaped modules and not only rectangular modules. Then we propose an algorithm to obtain the total number of modules, n, in O(n3) time in the densest packing in “packing that restored all of the L-shaped modules while obeying the horizontal and vertical constraints imposed by the given sequence-pair.” Furthermore, the necessary and sufficient conditions for packing the given sequence-pair and the proofs are given. These necessary and sufficient conditions are not related to the module size and depend only on the sequence-pair. Finally, the effectiveness of the proposed algorithm is demonstrated from test results. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(2): 52–64, 2002 [ABSTRACT FROM AUTHOR]

Estimating the amplitude and phase of a signal accurately even when the frequencies contained in the signal are already known is very important in many areas. The estimation accuracy and the estimation time are important issues in such areas and a method of improving both of these issues by combining the notch characteristics and the band passing characteristics of serially connected notch filters and an adaptive algorithm is presented in this paper. Computer simulations reveal that the performance of the proposed method is superior to previously proposed methods. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(2): 65–73, 2002 [ABSTRACT FROM AUTHOR]

An efficient algorithm is proposed for finding all solutions of piecewise-linear (PWL) resistive circuits using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of PWL equations of the form Pg(x) + Qx – s = 0 in a given region. In the LP test, the system of PWL equations is transformed into an LP problem, to which the simplex method is applied. Such an LP problem is obtained by surrounding the PWL functions by rectangles. In this paper, it is shown that the LP test can be performed very efficiently mostly by Phase II of the simplex method. Using the proposed techniques, the number of pivotings in the LP test becomes much smaller, which makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm could find all solutions of relatively large scale circuits (including those where the number of variables is 200 and the number of linear regions is 10200) in practical computation time. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(7): 1–11, 2001 [ABSTRACT FROM AUTHOR]

It is important to get a steady-state operation of a power electronic circuit for its design. The shooting method, which is one of the steady-state analysis methods, solves a boundary value condition which equates initial values to final values after one-period transient. This paper proposes how to process the analysis in parallel by using a Parallel Virtual Machine (PVM3) system. In particular, the multiple shooting method (MSM) which divides the shooting time into subsections is suitable because it can parallel numerical processes for the divided shooting times by using multiple CPU units independently. This parallel method is applied to converter examples which are processes by PVM3. The computed results are investigated for their convergence and CPU times to check their parallel effects. According to the MSM algorithm, CPU times are reduced almost to one-fifth by using five computer units from a PVM3 system example. © 2001 Scripta Technica, Electr Eng Jpn, 135(2): 69–76, 2001 [ABSTRACT FROM AUTHOR]

This paper makes a comparison study by using both the pseudospectral time-domain (PSTD) and finite-difference time-domain (FDTD) methods for a two-dimensional (2-D) scattering analysis. The time-domain incident plane-wave pulse used in the PSTD technique is herewith simulated with an initial-condition excitation technique to eliminate the unwanted Gibbs phenomenon. The pure scattered-field formulation is utilized to surmount the difficulty of generation of the incident field, and a PSTD near-to-far-zone field transform is developed for the analysis of the scattering width (SW) of targets. It is found that the PSTD computed results agree well with those derived from the FDTD method, while the PSTD requires much less computational space and CPU time. © 2000 John Wiley & Sons, Inc. Microwave Opt Technol Lett 25: 220–226, 2000. [ABSTRACT FROM AUTHOR]

The M3JPDA (multiple maneuver model joint probabilistic data association) system is a multiple target tracking algorithm that can cope with maneuvering targets. The system includes a straight-line constant-velocity movement model as well as multiple accelerated movement models, to be used in parallel, where the models are utilized according to their reliability. It sometimes happens in M3JPDA, however, that when the targets move in straight lines with constant velocities, the multiple tracking performance is worse than in the conventional JPDA using the straight-line constant-velocity movement model. This paper proposes adaptive M3JPDA to remedy this point. In this method, the target acceleration is estimated and is smoothed. If the resulting value is large, the conventional M3JPDA is used. If the value is small, the reliability of each motion model is calculated and the choice of models is based on the difference between the reliabilities of the conventional M3JPDA accelerated motion models and the straight-line constant-velocity motion model. Using the proposed algorithm, the reliability of the straight-line constant-velocity motion model is improved when the target executes straight-line constant-velocity motion. As a result of evaluation by simulation, it is seen that the proposed algorithm is capable of tracking two crossing targets in straight-line constant-velocity motions, as well as two targets rapidly maneuvering with 7 g accelerations, in contrast to JPDA based on the straight-line constant-velocity motion model and M3JPDA. © 1999 Scripta Technica, Electron Comm Jpn Pt 1, 83(2): 61–73, 2000 [ABSTRACT FROM AUTHOR]

Adaptive digital filters (ADF) estimating the transfer function of the unknown system can be classified as linear ADFs and nonlinear ADFs. In the linear ADF, the output is the inner product of the tap vector and the tap input vector unrelated to the tap vector. The transversal type ADF is a typical example. Other ADFs are nonlinear ones, among which the recursive ADF and logarithmic ADF are known. Previously, most discussions of nonlinear ADFs have been concerned with the recursive ADF. However, the transfer function H(z) of the nonlinear ADF is in general H (z) = Φ (G(z)) in which G(z) is the transfer function of a linear ADF. In the recursive ADF, Φ (G(z)) = 1/(1 - G(z)), which is a special case of Φ (G(z)). In this paper, the adaptive algorithm and its convergence condition are considered for a nonlinear ADF with a general transfer function H(z) = Φ (G(z)). The adaptive algorithm is based on the orthogonality principle and has a correlation between the tap input signal vector and the estimated error used as the updating vector. For this adaptive algorithm, the constraint condition on the transfer function of the unknown system needed for the tap vector to converge to that of the unknown system is derived. This condition can in general be derived from the condition under which the Hesse matrix becomes positive definite at the convergence value of the tap vector. Further, this condition is evaluated in detail for a specific example of Φ (G(z)). © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(11): 9–17, 1999 [ABSTRACT FROM AUTHOR]

Considering logic synthesis of FPGAs as a typical example, the basis of circuit partitioning problems under evaluations such as minimizing the number of blocks is the integer bin-packing problem. This is an NP-hard problem if the capacity of bin c is included in the input. An approximate method, FFD, that excels with respect to high speed and high precision has been widely used. Conventional research has studied the feature of asymptotic precision but, in application to designing logic circuits and so on, the range of the value c in which FFD outputs an optimal solution is important if c is regarded as a parameter. In this paper, we show that FFD outputs the optimal solution if c ≤ 6. The proof is easy to understand because it considers the performance of FFD when the output is not optimal. The consideration leads to the proposal of an extended FFD that outputs an optimal solution when c ≤ 8. Using the extended FFD, we evaluated the percentage of optimal solutions by the simple and high-speed conventional FFD when c = 7 or 8. © 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(12): 37–44, 1998 [ABSTRACT FROM AUTHOR]

The authors have previously proposed a fuzzy stack filter that is defined by a fuzzy Boolean function. We have also presented a specific design method (called the fuzzy Boolean function determination method) for the most fundamental fuzzy stack filter, the FCWM (fuzzy center weighted median). By varying the fuzzy Boolean function, we can achieve both an arbitrary CWM filter and a weighted average value filter in which only the weights at arbitrary processing points are varied. Hence, in comparison with the CWM filter, our filter is better at eliminating Gaussian noise. In this paper, to improve the reconstruction accuracy of nonsteady state signals, such as the image signals, a data-dependent FCWM (DD-FCWM) is proposed anew. The data-dependent filter is an adaptive filter in which the filter parameters are varied in response to the nature of the data near the processing point (local information). In a DD-FCWM filter, the fuzzy Boolean function is varied by using local information. We demonstrate that the proposed DD-FCWM filter uses the local signal information to appropriately vary, not only the weights of the processing points, but also the filter mode (average value type or median type). Furthermore, by use of image processing examples, we demonstrate that highly accurate signal reconstruction can be attained. © 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(8): 27–40, 1998 [ABSTRACT FROM AUTHOR]

It is known that the transient response of a ferroelectric material exhibits singular behavior due to hysteresis and dynamic capacitance characteristics. The authors have proposed a simulation model for the transient response of a ferroelectric material by using the dynamic capacitance derived from the hysteresis model as a dynamic time constant [1]. In this paper, the response characteristics of a ferroelectric memory at readout are examined by using the proposed transient response model. It is found that the read-out speed varies significantly with the load conditions and that an optimum point exists related to the detection sensitivity. The existence of an algorithm is demonstrated for a ferroelectric memory with a power consumption reduction while the readout is at a high speed. © 1999 Scripta Technica, Electron Comm Jpn Pt 2, 82(2): 39–47, 1999 [ABSTRACT FROM AUTHOR]

The application of the FDTD algorithm on generalized non-orthogonal meshes, following the basic ideas of Holland (1983), has been investigated by many authors for several years now, and detailed dispersion analysis as well as convergence studies have been published. Already in 1992 also a general stability criterion was given for the time integration using the standard leap-frog scheme (Lee et al.). Many authors, however, still propose some damped time stepping algorithms to work around unexpected instabilities in the discretization method. In this paper the origin of this type of instability is revealed, and a technique to obtain a stable discretization of Maxwell’s equations on non-orthogonal grids is proposed. To obtain more insight into the stability properties of the method, it is reformulated according to the matrix–vector notation of the Finite Integration Technique. © 1998 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Although various methods exist in soft decision decoding methods for block codes, of those that can be applied to linear and nonlinear coding, there are not many with low levels of computation that provide high levels of performance. In this paper, a method is proposed that reduces computation requirements while maintaining performance close to that of maximum likelihood decoding by a decision-making procedure in which a candidate codeword table is referenced by performing Euclidean distance comparisons on the received signal's hard decision binary sequence. The computation requirements and the block error rate performance are investigated through computer simulation to demonstrate the effectiveness of the proposed method in nonlinear β codes in additive Gaussian noise channels and fading channels. These results show that the block error rate performance of the proposed method in the additive Gaussian noise channel is about the same as the performance of the Chase 11 algorithm and is only slightly inferior to that of maximum likelihood decoding. Concerning the amount of computations, it is possible to reduce the complexity down to about 1% of that required by maximum likelihood decoding, and also the complexity can be reduced below that of the Chase II algorithm. On the other hand, in the fading channel, the block error rate performance of the proposed method, when compared to maximum likelihood decoding performance, reveals a decrease in Eb/N0 of about 1 dB, and it is seen to have good performance compared to the Chase II algorithm. Also, application toward quasi-cyclic coding/4-ary ASK coding using a candidate word table with respect to a 4-ary sequence applied with BCH coding is investigated, and superior results are obtained. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 1, 80(9): 56–67, 1997 [ABSTRACT FROM AUTHOR]

The prediction accuracy and the computation time of the tracking filter depend on the coordinate system in which the tracking algorithm is constructed. For instance, when the tracking filter is processed in a static orthogonal coordinate system, accurate prediction performance can be demonstrated from the accuracy of the target dynamic model. However, the amount of computation needed for algorithm realization becomes enormous. On the other hand, in the case of the radar reference coordinate system, the coordinate transformation can be omitted and the process becomes simpler, but the prediction performance becomes degraded due to the effect of rotation of the coordinate axis. To resolve the problems of prediction accuracy and computational load, this paper makes use of a radar reference coordinate system in which the computational load is light and proposes a tracking method that yields high prediction tracking accuracy. This method compensates the rotation of the coordinate axis, which is a problem in the radar reference coordinate system, by adjusting the prediction process in the range and angular filters. To evaluate the effectiveness of the present algorithm, computer simulations are carried out. It is found that the prediction accuracy is twice that of the conventional method if the effect of rotation of the coordinate axis is not taken into account and that the computation time is half that for the conventional method in the static orthogonal coordinate system. © 1997 Scripta Technica, Inc. Electron Comm Japn Pt 1, 80(7): 90–98, 1997 [ABSTRACT FROM AUTHOR]

This paper discusses the channel estimation algorithm in the adaptive maximum likelihood sequence estimation (MLSE) and proposes the variable-gain least square (VLMS) algorithm that can realize a fast acquisition by a simple configuration. When the sent code is a random sequence, VLMS is represented by a deterministic canonical equation based on the fact that a deterministic canonical equation based on the fact that a deterministic autocorrelation matrix for VLMS can be diagonalized. It is shown that VLMS can be realized with nearly the same computational complexity as least-mean square (LMS) algorithm. It is shown theoretically by analysis that VLMS can realize the same fast acquisition and tracking characteristics as those of the recursive least square (RLS) algorithm. An algorithm also is derived which is extension of the basic idea of VLMS and can be used for the fractional MLSE equalizer. It is shown experimentally that the fractional MLSE equalizer with VLSE algorithm can compensate the performance deterioration due to the sampling phase error. In the two-wave Rayleigh fading environment with faT = 4.0 x 10-4, the floor error can be suppressed below 10-4. It is shown also experimentally that the proposed equalizer has an excellent synchronization performance in which the initial acquisition can be completed in approximately six symbols. [ABSTRACT FROM AUTHOR]

This paper addresses a multiple-symbol differential detection scheme for 16 DAPSK. At the outset, conventional differential detection of 16 DAPSK is scrutinized analytically. As a result, it is seen that the energy penalty of differential amplitude detection compared with ideal coherent detection is larger than that of phase detection. Then, to improve the overall performance of 16 DAPSK, an MLSE algorithm is proposed for a large C/N as well as a suboptimum algorithm. Both allow multiple-symbol differential amplitude and phase detection. Their performance also are evaluated through computer simulation. [ABSTRACT FROM AUTHOR]

A multimedia communication network is expected to treat various kinds of information, e.g., voice, image, and data which have different demands of grade of service. Furthermore, in new high-speed networks, end- to-end delay distributions or packet-loss probabilities rather than average delays become more important performance measures. This paper presents a new heuristic design algorithm for packet switching communication networks in which the end-to-end delay distribution and packet-loss probabilities are adopted as design constraints. It is shown that, while the total cost is increased slightly when compared with the former approach, end-to-end delays and packet-loss probabilities between every two end- nodes can satisfy predefined constraint as expected. [ABSTRACT FROM AUTHOR]

One of the highly efficient coding methods for motion pictures is to combine the motion-compensation interframe prediction and the vector quantization. Among such methods, the normalized vector quantization is to represent the motion-compensated interframe difference signal, to separate the average value and to normalize the amplitude. It has a merit in that the general codebook can be utilized. This paper shows that the approximation error does not always decrease in those conventional methods, even if the vector quantization procedure is iterated. As a solution to this problem, it is shown to be sufficient to employ the vector quantizer with a gain/shape structure. An elaboration is made to the codebook size to handle the input vector amplitude. Then the motion picture coding algorithm is constructed using the proposed adaptive gain/shape vector quantizer. By optimizing the coding parameters aiming at the low bit-rate coded transmission, practical temporal and spatial resolutions are obtained for TV conferences and TV phones. [ABSTRACT FROM AUTHOR]

In conventional rule-based speech recognition, the rules have been constructed in a heuristic way. In that method, the rules with high accuracy have been difficult to construct when the recognition algorithm is complex, as in the case of consonant recognition. To cope with this problem, this paper presents a method for automatically constructing the recognition algorithm in the form of a set of rules. The method is a compromise between the transparency of the algorithmic representation by rule-based representation and the high accuracy by the optimization of the automatic construction. The unit of the rule is represented by if (condition), then (branch 1), and else (branch 2). The condition is a threshold logic using the discrimination parameter with clear meaning. The set of rules is constructed by the iterative procedure of selecting the optimum discrimination parameter and the threshold, for partitioning the consonant training samples into two sets. By connecting the constructed rules, a binary decision tree is formed. The consonant is recognized by iterating binary decisions on the tree and examining upon each which terminating node is arrived at. By constructing the rules depending upon each succeeding vowel, a set of rules with a higher accuracy can be obtained. By the evaluation experiment, it was seen that transparent rules with higher accuracies can be constructed. The obtained rules are in agreement with the empirical rules of phonology. Furthermore, using the rules, the consonant recognition rate in 1O0 city succeeding vowel-dependent names uttered by 50 subjects was improved from 72.4 to 80.0 percent. [ABSTRACT FROM AUTHOR]

In the three-stage rearrangeable switching network, an internal blocking can occur. However, such a blocking can be eliminated by rearranging the already set-up paths, and thus the network can satisfy any connection requirement. To eliminate this internal blocking, a successive rearrangement of more than one already set-up is required. The sequence of the paths to be rearranged can clearly be represented by extending the notion of the connection chain introduced by Gotoh. This paper presents a sufficient condition for the internal blocking to be eliminated by the rearrangement in the extended connection chain, which is a basis for the rearrangement algorithm. It is also verified that the rearrangement algorithm proposed by Gotoh satisfied the sufficient condition. Based on these results, a connection chain is shown in which the internal blocking can be eliminated by the rearrangement. The algorithm to search for the connection chain and to perform the rearrangement is presented. Compared with the past methods, in the proposed methods, a fewer number of paths is distorted. The usefulness of the method is examined by a simulation. [ABSTRACT FROM AUTHOR]

This paper describes an improvement of the solution by Krwczyk, Moore and Jones (KMJ algorithm) for nonlinear equations based on the interval analysis. When the KMJ algorithm is applied to practical problems such as the determination of the operatingpoint of a multistable electronic circuit, a large computation time is required. The reasom for large computation is as follows: (i) The existence of the solutions is determined using the direct-replacement type interval extension of functions, which enlargest the search regions for the solutions; (ii) the region partitioning is repeated until a region X is obtained such that k((x) sx, where k(x) is Krawczyk's interval function and X is the interval region. The situation is demonstrated by an example. As a solution for these problems, the following method is proposed. [ABSTRACT FROM AUTHOR]

Recent developments in computer technology have enabled the real-time treatment of signal processing with a large amount of computation which had been considered to be impossible. Moreover, with the development of LSI technology, it has become possible to speed up the execution of the algorithms by parallel computing hardware. This paper discusses a parallel architecture for the recursive least square method of system identification fitted for VLSI. If n is the order of system to be identified, the complexity T(n) required for updating the estimate at each measurement is TS(n) = 0(n²), using a single serial processor. However, it can be reduced to Tp(n) = 0(n) by using the architecture consisting of (2n + 6) elementary processors and a set of delay units. Moreover, we discuss a method to speed up p-time updates from TS(n,p) = 0(n²p) to TM(n, p) = 0(n + p) using 0(np) elementary processors by vectorizing the measurements. [ABSTRACT FROM AUTHOR]

This paper analyzes the tap weight variance for the FIA-ZF algorithm and the ADA-MSE algorithm. The covariance matrix of the FIA algorithms are clarified. Covariance matrices are also solved statistically for both the FIA Zero Forching (ZF) algorithm and the FIA Mean Squared Error (MSE) algorithm. Comparison are made with the simulation result. Finally, tap weight variance is studied for various noise levels and for the case of distorted input signals. [ABSTRACT FROM AUTHOR]

In the steady-state response in the nonlinear circuit, a number of frequency components is greatly affected by the amplitude and the frequency components contained in the forced input. In general, when there is only one frequency component as the input, only its harmonic components are produced. However, when it contains more than one frequency, the circuit will produce many frequency components by sum and difference as well as harmonics of the input frequencies. Especially, in the case of an FM input signal, in which the frequency is time-varying, it is know that the input contains a large number of frequency components, depending on the modulation index. In the analysis of such a nonlinear system containing a large number of frequency components as the input, the solution method in the frequency domain such as harmonic balance, is not effective. This paper discusses the method of solution in the time domain for the nonlinear circuit with time-varying frequency input. The waveform in the steady-stage response is expanded into Fourier series with periodically time-varying coefficients, and the initial value is determined which produces the steady-state response. The method is suited to the analysis of a nonlinear system with two frequency components as the input. In particular, it is seen that the method is especially effective in the analysis of steady-state response in the nonlinear system with time-varying frequency input. [ABSTRACT FROM AUTHOR]

The problems of testing the planarity of a graph and of embedding a planar graph in a plane arise in many applications. This paper presents a simple linear algorithm for the latter problem. The algorithm is based on the 'vertex-addition algorithm' of Lempel, Even and Cederbaum for planarity testing and is a slight modification of Booth and Leuker's implementation of the testing algorithm using a PQ-tree. Compared with the embedding algorithm known as the 'path-addition; algorithm of Hopcroft and Tarjan, our algorithm is conceptually simple and easy to understand or implement. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of resizing figures in a digitized XY coordinate plane. The figures are regions closed by line segment parallel to the X or Y axis or line segments at 45° angles to the axes. By resizing we mean that, given the closed regions and a change width, we expand or contract the input regions by the change width. After first proving some theorems on resizing, we response an algorithm solving the problem in running time 0 (n log n), where n is the number of vertices in the regions. For particular applications we consider examples using the algorithms for verifying compliance with design rules for the smallest feature size and spacing in a mask pattern, and also the compensation for characteristic machine error in pattern generators, apertures, etc. [ABSTRACT FROM AUTHOR]

With the progress of microelectronics technology, the amount of design for a variety of LSI's is increasing rapidly. To make the design and production of such LSI' easier and less costly, a gate array LSI is used extensively. This paper describes a global router for gate array LSI's which is incorporated into our layout system. This router is used to generate for each net an interconnection pattern consisting of channel segments in such a unified way that all interrelated interconnection requirements are taken into account at once. A main objective of the router is not only to minimize the maximum of the local wiring densities, but also to distribute all the interconnection requirements over channels evenly to attain 100% interconnection within a limited area. [ABSTRACT FROM AUTHOR]

Problems occur in the automatic routing for a gate array LSI. These include the logically equivalent terminals to be used for a net to be connected to any one of such terminals, and the vertical track of feed-through cell to be used for a net assigned to the feed-through cell. Since the routing area in such as LSI chip is predetermined, these problems are important in attaining 100% interconnection in each horizontal channel. This paper describes a heuristic algorithm for these problems, and experimental results of the algorithm are also shown to reveal its performance. [ABSTRACT FROM AUTHOR]

This paper proposes an effective scheduling algorithm called BOTTOM-UP for loop-folding scheduling. The loop-folding is a scheduling algorithm for higher-layer VLSI synthesis to shorten the latency of operations which have such processing sequence dependency as DSP algorithm, and repeat the same process (process unit) many times in a restricted hardware resource. The proposed algorithm, BOTTOM-UP, makes a scheduling to minimize the latency and execution time by using loop-folding effectively. BOTTOM-UP uses the result of the ALAP scheduling as an initial scheduling, and makes it possible to operate in high speed by reassigning operations from the latest control step while fulfilling the resource constraints and maintaining data sequence dependency. Furthermore, latency and execution time are minimized by giving high priority to the longest path operation. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(6): 39–51, 1998 [ABSTRACT FROM AUTHOR]

In this paper, an adaptive array is proposed in which the CMA (Constant Modulus Algorithm) and LMS algorithms are combined so that a pass diversity effect is obtained without using training signals. The basic operations of the proposed algorithm are as follows. CMA captures the direct wave with maximum power. Based on the output of the CMA adaptive filter, a reference signal is generated. The LMS algorithm, using this reference signal, captures the delayed wave. By combining the direct wave and the delayed wave at maximum rate, the receiving quality is improved. By means of a computer simulation, we confirmed that the convergence property is improved and that the effect of the reference signal error on the system convergence characteristics is small. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(7): 37–44, 1998 [ABSTRACT FROM AUTHOR]