A VLSI algorithm for division in GF(2m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.

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.

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.

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.

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.

We propose two novel blind LMS algorithms, called exponential step size LMS algorithms (ES-LMS), for adaptive array antennas with fast convergence speeds. Both of the proposed algorithms are much better at tracking signal sources than the conventional LMS algorithms. In addition, they require neither spatial knowledge nor reference signals since they use the finite symbol property of digital signal. Computer simulations verify performances of the two proposed algorithms.

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

The group organization used for group learning in a knowledge intensive domain like software development affects educational achievement. This paper proposes a group organization system for software engineering education done through group learning. The organizational problem itself is defined and why a Genetic Algorithm (GA) is an appropriate means of solving this problem is explained. This system is a Web application developed with open source software and runs on an open source software platform. Based on the group organization data collected from actual classes, we generated various group organizations by using different strategy parameter values. We then gave a questionnaire to actual students asking them which solution produced the fairest group organization. The replies received revealed that the candidate solution that set greater weight on leadership capability and system analysis capability was the fairest.

In computer-aided drafting and design, interactive graphics is used to design components, systems, layouts, and structures. There are several approaches for using automated graphical layout tools currently. Our approach employs a genetic algorithm to implement a tool for automated 3D graphical layout design and presentation. The effective use of a genetic algorithm in automated graphical layout design relies on defining a fitness function that reflects user preferences. In this paper, we describe a method to define fitness functions and chromosome structures of selected objects. A learning mechanism is employed to adjust the fitness values of the objects in the selected layout chosen by the user. In our approach, the fitness functions can be changed adaptively reflecting user preferences. Experimental results revealed good performance of the adaptive fitness functions in our proposed mechanism.

In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).

Recently, feature maps have been applied to various problem domains. The success of some of these applications critically depends on whether feature maps are topologically ordered. Several different approaches have been proposed to improve the conventional self-organizing feature map (SOM) algorithm. However, these approaches do not guarantee that a topologically-ordered feature map can be formed at the end of a simulation. Therefore, the trial-and-error procedure still dominates the procedure of forming feature maps. In this paper, we propose a healing mechanism to repair feature maps that are not well topologically ordered. The healed map is then further fine-tuned by the conventional SOM algorithm with a small learning rate and a small-sized neighborhood set so as to improve the accuracy of the map. Two data sets were tested to illustrate the performance of the proposed method.

The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.

The detection of timing constraint violation is crucial in reactive systems. A method of detecting deadline violation based on Floyd-Warshall shortest path algorithm has been proposed by Chodrow et al. We extend this method to detect the violation of minimum delay time in reactive systems where the repetition of event sequences frequently occurs.

The redundancy allocation problem for a series-parallel system is a well known as one of NP-hard combinatorial problems and it generally belongs to the class of nonlinear integer programming (nIP) problem. Many researchers have developed the various methods which can be roughly categorized into exact solution methods, approximate methods, and heuristic methods. Though each method has both advantages and disadvantage, the heuristic methods have been received much attention since other methods involve more computation effort and usually require larger computer memory. Genetic algorithm (GA) as one of heuristic optimization techniques is a robust evolutionary optimization search technique with very few restrictions concerning with the various design problems. However, GAs cannot guarantee the optimality and sometimes can suffer from the premature convergence situation of its solution, because it has some unknown parameters and it neither uses a priori knowledge nor exploits the local search information. To improve these problems in GA, this paper proposes an effective hybrid genetic algorithm based on, 1) fuzzy logic controller (FLC) to automatically regulate GA parameters and 2) incorporation of the iterative hill climbing method to perform local exploitation around the near optimum solution for solving redundancy allocation problem. The effectiveness of this proposed method is demonstrated by comparison results with other conventional methods on two different types of redundancy allocation problems.

The major concern at a branch point in asynchronous transfer mode (ATM) networks for point-to-multipoint available bit rate (ABR) services is how to consolidate backward resource management (BRM) cells from each branch for a multicast connection. In this paper, we propose an efficient feedback consolidation algorithm based on an adaptive dynamic threshold (ADT) to eliminate consolidation noise and to reduce consolidation delay. The main idea of the ADT algorithm is that each branch point estimates the ABR traffic condition of the network through virtual queue estimation. Simulation results show that the proposed ADT algorithm can achieve a faster response in congestion status and a higher link utilization compared with the previous works.

An advanced center biased search algorithm for block motion estimation is proposed in this letter. It adopts an innovative center biased search strategy to get correct motion vector. The computational complexity is reduced by strict application of the unimodal error surface assumption and half stop technique. Experimental results show that proposed algorithm has improved performance as compared to the conventional block matching algorithms.

This paper describes the outline of the active noise control system and the adaptive signal processing used in the practical systems. Focus is on the adaptive signal processing and algorithms which are widely used in many applications. Some variations in the algorithms for improving the control effect and for reducing the amount of calculation are also shown. Additionally, the limitations and some design guide are shown with the results of the numerical simulations.