Software with design flaws increases maintenance costs, decreases component reuse, and reduces software life. Even well-designed software tends to deteriorate with time as it undergoes maintenance. Work on restructuring object-oriented designs involves estimating the quality of the designs using metrics, and automating transformations that preserve the behavior of the designs. However, these factors have been treated almost independently of each other. A long-term goal is to define transformations preserving the behavior of object-oriented designs, and automate the transformations using metrics. In this paper, we describe a genetic algorithm based restructuring approach using metrics to automatically modify object-oriented designs. Cohesion and coupling metrics based on abstract models are defined to quantify designs and provide criteria for comparing alternative designs. The abstract models include a call-use graph and a class-association graph that represent methods, attributes, classes, and their relationships. The metrics include cohesion, inheritance coupling, and interaction coupling based on the behavioral similarity between methods extracted from the models. We define restructuring operations, and show that the operations preserve the behavior of object-oriented designs. We also devise a fitness function using cohesion and coupling metrics, and automatically restructure object-oriented designs by applying a genetic algorithm using the fitness function.

A study on improving the performance of the real-coded genetic algorithm for electromagnetic inverse scattering of two-dimensional perfectly conducting cylinders is presented. Three schemes, namely, the penalty function approach, the closed cubic B-splines local shape function approach and the adaptive hybrid algorithm approach are proposed to deal with the problem. These schemes can be used separately or be combined to improve the performance. Numerical examples validate the schemes.

Studies on artificial neural network have been conducted for a long time, and its contribution has been shown in many fields. However, the application of neural networks in the real world domain is still a challenge, since nature does not always provide the required satisfactory conditions. One example is the class size imbalanced condition in which one class is heavily under-represented compared to another class. This condition is often found in the real world domain and presents several difficulties for algorithms that assume the balanced condition of the classes. In this paper, we propose a method for solving problems posed by imbalanced training sets by applying the modified large-scale neural network "CombNET-II. " CombNET-II consists of two types of neural networks. The first type is a one-layer vector quantization neural network to turn the problem into a more balanced condition. The second type consists of several modules of three-layered multilayer perceptron trained by backpropagation for finer classification. CombNET-II combines the two types of neural networks to solve the problem effectively within a reasonable time. The performance is then evaluated by turning the model into a practical application for a fog forecasting problem. Fog forecasting is an imbalanced training sets problem, since the probability of fog appearance in the observation location is very low. Fog events should be predicted every 30 minutes based on the observation of meteorological conditions. Our experiments showed that CombNET-II could achieve a high prediction rate compared to the k-nearest neighbor classifier and the three-layered multilayer perceptron trained with BP. Part of this research was presented in the 1999 Fog Forecasting Contest sponsored by Neurocomputing Technical Group of IEICE, Japan, and CombNET-II achieved the highest accuracy among the participants.

This paper attempts to establish a theory for a general auto-associative memory model. We start by defining a new concept called supporting function to replace the concept of energy function. As known, the energy function relies on the assumption of symmetric interconnection weights, which is used in the conventional Hopfield auto-associative memory, but not evidenced in any biological memories. We then formulate the information retrieving process as a dynamic system by making use of the supporting function and derive the attraction or asymptotic stability condition and the condition for convergence of an arbitrary state to a desired state. The latter represents a key condition for associative memory to have a capability of learning from variant samples. Finally, we develop an algorithm to learn the asymptotic stability condition and an algorithm to train the system to recover desired states from their variant samples. The latter called sample learning algorithm is the first of its kind ever been discovered for associative memories. Both recalling and learning processes are of finite convergence, a must-have feature for associative memories by analogy to normal human memory. The effectiveness of the recalling and learning algorithms is experimentally demonstrated.

We examine a concatenated code which consists of a rate 1/2, 4-state turbo code (an inner code) and a single-parity-check product code (an outer code), and discuss the decoding structure called a double concatenated decoding scheme. From our Monte Carlo simulation trials, we show the advantage of the concatenated codes over turbo codes alone. Specifically, when we use an interleaver of 4096 bits, the Eb/No to obtain a BER of 10-6 is about 1.45 dB for the concatenated code. On the other hand, it is more than 2.5 dB for the turbo code alone. So, the Eb/No improvement can be achieved by about 1 dB. This improvement in Eb/No was also obtained for the interleavers of 8192 and 2048 bits. Therefore, the concatenated codes using a double concatenated decoding scheme can solve the problem of the BER flattening in decoding of turbo codes.

An LMS adaptive digital filter using distributed arithmetic (DA-ADF) has been proposed. Cowan and others proposed the DA adaptive algorithm with offset binary coding for the simple derivation of an algorithm and the use of an odd-symmetry property of adaptive function space (AFS). However, we indicated that a convergence speed of this DA adaptive algorithm degraded extremely by our computer simulations. To overcome these problems, we have proposed the DA adaptive algorithm generalized with two's complement representation and effective architectures. Our DA-ADF has performances of a high speed, small output latency, a good convergence speed, small-scale hardware and lower power dissipation for higher order, simultaneously. In this paper, we analyze a convergence condition of DA adaptive algorithm that has never been considered theoretically. From this analysis, we indicate that the convergence speed is depended on a distribution of eigenvalues of an auto-correlation matrix of an extended input signal vector . Furthermore, we obtain the eigenvalues theoretically. As a result, we clearly show that our DA-ADF has an advantage of the conventional DA-ADF in the convergence speed.

We propose a new effective method of managing flash memory space for flash memory-specific file systems based on a log-structured file system. Flash memory has attractive features such as non-volatility and fast I/O speed, but it also suffers from inability to update in situ and from limited usage (erase) cycles. These drawbacks necessitate a number of changes to conventional storage (file) management techniques. Our focus is on lowering cleaning cost and evenly utilizing flash memory cells while maintaining a balance between these two often-conflicting goals. The proposed cleaning method performs well especially when storage utilization and the degree of locality are high. The cleaning efficiency is enhanced by dynamically separating cold data and non-cold data, which is called 'collection operation.' The second goal, that of cycle-leveling, is achieved to the degree that the maximum difference between erase cycles is below the error range of the hardware. Experimental results show that the proposed technique provides sufficient performance for reliable flash storage systems.

In optical networks, wavelength converters are required to improve the efficiency of wavelength-division multiplexing. In this paper, we propose a genetic algorithm to determine the optimal locations of the nodes in the network where a given number of converters are placed. Optimality is achieved by the minimum wavelength blocking probability. Our algorithm is applied to two realistic networks constructed from the locations of major cities in Ibaraki Prefecture and from those in Kanto District in Japan and is shown to reach the nearly optimal solution in a limited number of generations. The accuracy is verified by simulation. The computational time is compared with that of an exhaustive search algorithm.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

In this paper, we present the division algorithm (DA) for the computation of b=c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.

M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in [14]. However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.

In this paper, we propose a new consolidation algorithm called the Selective Backward Resource Management (BRM) cell Feedback (SBF) algorithm. It achieves a fast response and low consolidation noise by selectively forwarding BRM cell from the most congested branch to the source instead of waiting from all branches. Mathematical models are derived to quantitatively characterize the performance, i.e. the response time and ACR of the source, of SBF and previously proposed algorithms. The interoperation of consolidation algorithms in point-to-multipoint available bit rate (ABR) is investigated. We address response time, consolidation noise and the effect of asymmetrical round trip delay (RTD) from branch point to destinations aspects. All combinations of four different consolidation algorithms are interoperated in both local/metropolitan area network (LAN/MAN) and wide area network (WAN) configuration. By a simulation method, we found that the consolidation algorithm used at the uppermost stream branch point, especially in WAN configuration, plays an important role in determining the performance of the network. However, consolidation algorithm used at the lower stream branch point affects the network performance insignificantly. Hence, in order to achieve a good and effective performance of the consolidation algorithms interoperated network, a fast response with low consolidation noise algorithm should be used at the uppermost stream branch point and a simple and easy to implement algorithm should be used at the lower stream branch point.

In this paper, we present a method to analyze the steady-state performance of a complex coefficient adaptive IIR notch filter which is useful for the rejection of multiple narrow-band interferences from broad-band signals in quadrature phase shift keying (QPSK) spread-spectrum communication systems. The adaptive notch filter based on the simplified gradient algorithm is considered. Analytical expressions have been developed for the conditional mean and variance of notch filter output. The signal-to-noise ratio improvement factor is also obtained from which the validity of the use of the notch filter can be concluded. Finally, the results of computer simulations are shown which confirm the theoretical predictions.

A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σi=1k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.

A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)2) time slots with no station being awake for more than O(log log n) time slots.

The paper presents a topology-oriented robust algorithm for the incremental construction of line arrangements. In order to achieve a robust implementation, the topological and geometrical computations are strictly separated. The topological part is proved to be reliable without any assumption on the accuracy of the geometrical part. A self-correcting property is introduced to minimize the effect of numerical errors. Computational experiments show how the self-correcting property works, and we also discuss some applications of the algorithm.