Search

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]

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]

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

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.

The impressive generalization capacity of AdaBoost has been explained using the concept of a margin introduced in the context of support vector machines. However, this ability to generalize is limited to cases where the data does not include misclassification errors or significant amounts of noise. In addition, the research of Schapire and colleagues has served to provide theoretical support for these results from the perspective of improving margins. In this paper we propose a set of new algorithms, AdaBoostReg,ν-Arc, and ν-Boost, that attempt to avoid the overfitting that can occur with AdaBoost by introducing a normalization term into the objective function minimized by AdaBoost. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(9): 69– 78, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20344 [ABSTRACT FROM AUTHOR]

An algorithm for arbitrarily minimizing the width of the interval which does not contain the solutions from the interval which contains the solutions of equations using nonlinear functions in which the dimension of the definition domain is greater than the dimension of the value range is proposed in this paper. In addition, the effectiveness of the proposed algorithm is shown using specific numerical examples. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(4): 39–44, 2002 [ABSTRACT FROM AUTHOR]

The RSA cryptosystem is extended to the algebraic field by using ideal theory. In this paper, we describe the generation algorithm of prime ideals, how to select a representative class using an ideal as modulus, and the algorithm to compute a representative element, for cyclotomic fields and quadratic fields. From here, an RSA cryptosystem can be constructed on cyclotomic fields and quadratic fields. To break completely the proposed cryptosystem, when the public key is a product of inert prime numbers, is the same as for the conventional RSA cryptosystem and its security is better against the Håstad attacks. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 19–29, 2000 [ABSTRACT FROM AUTHOR]

This paper proposes an efficient maximum-likelihood decoding algorithm (hard decision) for cyclic codes such as BCH code. As the first step, the frequency spectrum of the polynomial over the finite field is analyzed by the Fourier transform over the finite field. The normalizing polynomial that masks the particular spectrum is introduced based on the viewpoint of the spectrum. Then, the normalizing parity check polynomial is used to extract the information concerned with errors on the received word. Based on the extracted information concerned with errors, and the fact that the occurrence probability is higher for the error with a smaller weight, maximum-likelihood decoding is shown to be executed efficiently in hard-decision decoding using the code word obtained from the successively generated error candidates. Furthermore, an efficient generation method for the error candidates is also proposed. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(1): 78–89, 2000 [ABSTRACT FROM AUTHOR]

This paper presents a new method for designing orthonormal wavelet filter banks using the Remez exchange algorithm. It is well known that orthonormal wavelet bases can be generated by paraunitary filter banks. Thus, synthesis of orthonormal wavelet bases can be reduced to the design of paraunitary filter banks. From the orthonormality and regularity of wavelets, we derive some conditions that must be satisfied for FIR paraunitary filter banks, and investigate the relationship between the filter coefficients and their zeros. According to the relationship, we apply the Remez exchange algorithm in the z-domain directly and formulate the design problem in the form of a linear problem. Therefore, we can easily get a set of filter coefficients by solving the linear equations. Optimal solutions with an arbitrary regularity can be obtained after using an iteration procedure. In the proposed method, the main advantage is that less computational complexity is required as compared with the conventional methods. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(6): 1–8, 1998 [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 past studies, the digital straight-line segment is defined as a figure approximating the straight-line segment in the continuous space, by grid points in the discrete space. Because of this definition, the properties of the segment vary depending on the approximation process, which prevented the development of a general discussion. For this problem, the authors introduced a topology into the discrete space, and defined the digital straight-line segment using only the topology. As a result, the digital straight-line segment can be defined generally for various spaces and topologies, and the properties of the segment can be analyzed. In this paper, the properties of the digital straight-line segment are analyzed based on the 5-neighborhood concept. As the first step, the assertion that characterizes the digital straight-line segment, as well as five equivalent assertions are presented. Then, it is shown that by using those assertions, the corresponding segment generation algorithm can easily be obtained, and the figure generated by the segment generation algorithm which is known in the CG technology is the same as the proposed digital straight-line segment. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(6): 16–26, 1998 [ABSTRACT FROM AUTHOR]

The k-element graph partition is as follows: given an input consisting of (1) a non-directed graph G = (V, E), (2) S ⊆ V ∪ E. (3) k different points or edges ai (a1, a2 ..., ak ε S) (all of the ai are called bases), and (4) k natural numbers n1, n2, ..., nk such that $\sum_{i=1}^{k} n_i= \mid S \mid$, to find a solution such that each Ri in the partition R1, R2 ..., Rk of S contains ai and contains ni elements, and the connected partial graphs Gi (G1, G2, ...., Gk) that contain the Ri are mutually edge-independent. The same problem with condition (3) removed is called the basis-unspecified k-element problem. In this paper we demonstrate that a necessary and sufficient condition for the existence of a k-element partition is that the input graph be k-edged-connected; we then show that it is efficiently solvable for the cases k = 2, 3. For the basis-unspecified k-element problem we demonstrate that (1) if G is 2-edge-connected, then the base-unspecified 3-element problem is solvable in time O(|V|2); (2) if G is 4-edge-connected, then the k-element partition for k ≥ 3 is effectively solvable in time $O({\mid V\mid}\sqrt{{\mid V\mid} \log {\mid V\mid}}+{\mid E\mid})$. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(7): 74–84, 1997 [ABSTRACT FROM AUTHOR]

This paper discusses the problems of finding one of the largest similar substructures in tree Tb to tree Ta, where both Ta and Tb are rooted and ordered trees (RO-trees) or unrooted and cyclically ordered trees (CO-trees). A maximal closest common ancestor mapping and a largest similar substructure in Tb to Ta based on this mapping are defined and two algorithms are proposed for finding one of the largest similar substructures for RO-trees and that for CO-trees. The time and space complexities of the algorithm for RO-trees are OT(NaNb) and OS(NaNb), respectively; and those of the algorithm for CO-trees are OT(mambNaNb) and OS((ma + mb)NaNb), respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(2): 92–104, 1997 [ABSTRACT FROM AUTHOR]

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

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

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

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

The dc driving-point and transfer characteristics of nonlinear circuits are the multivalued curves that arise from the nature of the circuit. These curves cannot be analyzed by general-purpose circuit simulators. One known method for analyzing these kinds of characteristic curves is the backward differentiation formula (BDF) curve-tracing algorithm proposed by Ushida and Chua. In this method, the circuit equations f(x) = 0, f (·): Rn + 1 → Rn, where the input voltage is assumed to be a variable, are analyzed by the predictor-corrector algorithm where the arc-length of the solution curve in n + 1-dimensional space is the parameter. However, it is not clear that this method is practical for large-scale circuits. In this paper, we extend the Ushida-Chua method from a practical method standpoint and demonstrate that the multivalued characteristic curves of large-scale circuits can easily be analyzed using general-purpose circuit simulators. In the proposed method, first, the solution curve in n + l-dimensional space is projected into m + l-dimensional space, where m ≤ n and the arc-length of this new curve is used as the parameter. Second, the relationship between the arc-length and the components of the curve is expressed by a function generator circuit, the solution-tracing circuit. Finally, transient analysis is performed using a general-purpose circuit simulator and the solution curve is traced. The effectiveness of this method is verified through several examples, including a bipolar analog IC with 296 nodes. [ABSTRACT FROM AUTHOR]

The construction of robust communication networks is discussed from a viewpoint of graph augmentation problems. Suppose that faults in a communication network occur at terminals or links; each terminal fault disables that terminal and the incident links, and each link fault prevents communication through that link. A network with a specified set of terminals is robust with respect to k-1 link faults (k-1 terminal faults, respectively) if communication between any pair of nonfaulty specified ones continues even if k-1 link faults (k-1 terminal faults) occur. A robust network is constructed from an existing one, possibly without links, by adding a set of links. Here, a cost is assigned to each link and it represents the total cost necessary for a physical linkage between corresponding terminals. In this paper links are bidirectional and it is considered how to construct a robust network with respect to 1 link fault (1 terminal fault) by adding a set of links that minimizes the total sum of costs assigned to those links. The problem is formulated as the 2-edge connectivity (2-vertex-connectivity) augmentation problem for a specified set of vertices, and an O(|V|²) (an O(|V|³)) approximation algorithm BRA-SV (BIA-SV) is proposed. It is shown that the worst approximation of BRA-SV (BIA-SV) is no more than twice (strictly less than four times) the optimal.

This paper describes a method to avoid the singular problem at the "S-control" algorithm. The "S-control" is proposed to determine the correct operating state in any bia polar transistor network (BTN). Each diode of the Ebers-Moll model is replaced with a directional switch called an S-branch which has "on" and "off" states. The switch status is changed by the S-control algorithm. How- ever, the matrix singular problem occurs in the process of the S-control. The singular matrix is formed by a cutset of only current sources or a loop of only voltage sources. The singular problem is solved by the sign- discrimination method by which the sign of each node voltage is judged by the introduction of small immittances in cutset (loop) of only current (voltage) sources formed in process of the S-control. The S-control algorithm will be continued to obtain the next switch state unless the limit cycle is not generated. [ABSTRACT FROM AUTHOR]

River routing in VLSI and the one-layer wire routing problem for printed circuit boards can be formulated as a problem of finding a forest in a planar (grid) graph. Given a planar graph G representing a wiring region and sets of terminals to be equipotential (that is, nets), we want to find vertex-disjoint trees (i.e., a forest), each of which interconnects terminals of each net. This paper presents an algorithm for solving the forementioned problem in 0 (MIN {kn, n log n}) time when terminals of nets are placed on the two faces of a planar graph C, where n is the number of vertices of G, and k, that of nets. [ABSTRACT FROM AUTHOR]

As a method to estimate the frequency spectrum, the discrete Fourier transform is employed widely, since a high-speed algorithm is available. However, the discrete Fourier transform has the following problems. The presence of noise is not considered, and the resolution of the frequency spectrum is determined uniquely by the sample duration. Other problems are that the sampling inter- val must be kept constant and the decay of the signal is not considered. This paper proposes a high-resolution frequency spectrum estimation where the complex Kalman filter is applied to the observed signal represented by the complex stochastic system, effectively utilizing the a priori knowledge of the signal source. The method is applied to the measured data and to the simulation, and it is demonstrated that a high-resolution frequency spectrum is obtained by suppressing the effect of the discrete approximation of the frequency component, and, when the frequency spectrum is concentrated, the resolution can be improved approximately by a factor of two, without iterating the measurement. It is shown also that the sampling interval can be set arbitrarily in the proposed method, and the noise and the decay can be considered. A theoretical discussion is made on the relation between the special case of the proposed method and the discrete Fourier transform. [ABSTRACT FROM AUTHOR]