The individually normalized least mean square (INLMS) algorithm is proposed as an adaptive algorithm suitable for the fixed point processing. The convergence property of the INLMS algorithm, however, is not yet analyzed enough. This paper first derives an equation describing the convergence property by exploiting the technique of expressing the INLMS algorithm as a first order infinite impulse response (IIR) filter. According to the equation derived thus, the decreasing process of the estimation error is represented as the response of another IIR filter expression. By using the representation, this paper second derives the convergence condition of the INLMS algorithm as the range of the step size making a low path filter of the latter IIR filter. This paper also derives the step size maximizing the convergence speed as the maximum coefficient of the latter IIR filter and finally clarifies the range of the step size recommended in the practical system design.

Efficient radio resource utilization and fairness are important goals that must be achieved since wireless ATM systems support various services with different traffic characteristics such as CBR and UBR. This paper proposes a novel delay-and-queuing data size-based MAC protocol for broadband wireless ATM. The proposed MAC protocol relies on a new resource scheduling algorithm that decides the priority of channel assignment based on both the queuing delay and the queuing data size in the transmission buffer. Simulation results confirm that the proposed MAC protocol is able to provide throughput fairness and to achieve excellent throughput performance for ATM services that experience dynamic traffic fluctuations.

This paper presents an accelerated image halftoning technique using an improved genetic algorithm with tiny populations. The algorithm is based on a new cooperative model for genetic operators in GA. Two kinds of operators are used in parallel to produce offspring: (i) SRM (Self-Reproduction with Mutation) to introduce diversity by means of Adaptive Dynamic-Block (ADB) mutation inducing the appearance of beneficial mutations. (ii) CM (Crossover and Mutation) to promote the increase of beneficial mutations in the population. SRM applies qualitative mutation only to the bits inside a mutation block and controls the required exploration-exploitation balance through its adaptive mechanism. An extinctive selection mechanism subjects SRM's and CM's offspring to compete for survival. The simulation results show that our scheme impressively reduces computer memory and processing time required to obtain high quality halftone images. For example, compared to the conventional image halftoning technique with GA, the proposed algorithm using only a 2% population size required about 15% evaluations to generate high quality images. The results make our scheme appealing for practical implementations of the image halftoning technique using GA.

To evaluate or compare the convergence speed of adaptive digital filters (ADF) with least mean squared (LMS) algorithm, the condition numbers of correlation matrices of tap-input vectors are often used. In this paper, however, the comparison of the conventional fullband ADF and the subband ADF based on their condition numbers is shown to be invalid. In some cases, the over-sampled subband ADF converges faster than the fullband ADF, although the former has larger condition numbers. To explain the above phenomenon, an expression for the convergence behavior of the subband ADF and simulation results are provided.

In this paper, a new set of difference equations is derived for transient analysis of the convergence of adaptive FIR filters using the Sign-Sign Algorithm with Gaussian reference input and additive Gaussian noise. The analysis is based on the assumption that the tap weights are jointly Gaussian distributed. Residual mean squared error after convergence and simpler approximate difference equations are further developed. Results of experiment exhibit good agreement between theoretically calculated convergence and that of simulation for a wide range of parameter values of adaptive filters.

An approach for analysis of the small signal response of the carriers in semiconductors is presented. The integro-differential equation, describing the phenomenon in the time domain is transformed into a Fredholm integral equation of the second kind. The response of the carrier system to a small signal of a general time dependence can be calculated by the knowledge of the response to an impulse signal, defined by a delta function in time. For an impulse signal, the obtained integral equation resembles the basic structure of the integral form of the time dependent (evolution) Boltzmann equation. Due to this similarity a physical model of the impulse response process is developed. The model explains the response to an impulse signal in terms of a relaxation process of two carrier ensembles, governed by a Boltzmann equation. A Monte-Carlo method is developed which consists of algorithms for modeling the initial distribution of the two ensembles. The numerical Monte-Carlo theory for evaluation of integrals is applied. The subsequent relaxation process can be simulated by the standard algorithms for solving the Boltzmann equation. The presented simulation results for Si and GaAs electrons serve as a test of the Monte-Carlo method and demonstrate that the physical model can be used for explanation of the small signal response process.

In high-speed TDMA mobile communications, frequency-selective fading is a serious problem because a delay time difference between multipath signals is large in comparison with symbol duration. We have proposed a spatial-domain RAKE receiver using a multibeam adaptive antenna to reduce frequency-selective fading and to realize path-diversity. The multibeam adaptive antenna resolves multipath signals in the spatial domain, and combines array outputs. In this paper, we propose the application of MUSIC algorithm to estimation of the time delays of multipath signals to make the incident signals coincide with a common reference signal. Because the MUSIC algorithm can estimate the time delays accurately, the BER performance of the proposed scheme is improved. Furthermore, we propose weighting factors which easily realize the maximal-ratio combining.

A highly reliable and available network which automatically can restore itself from failures is an important concept for the future high capacity broadband networks. Self-healing algorithm, restoring the failed VPs (Virtual Paths) in the backbone ATM networks, is an indispensable technique to meet these requirements. In this paper we propose a coordination-based restoring self-healing algorithm called C-TRUS, which meets different requirements of service classes of survivability by using a simple rerouting and capacity reserving protocols. The simulation results show that the proposed algorithm can restore VPs quickly and improve the restoration time in case of multi-failures by using network resources very efficiently. Furthermore, C-TRUS outperforms the combination method in both restoration ratio and restoration time. In addition, the significant improvement of restoration ratio in the multi-failure scenario has been achieved.

In conventional methods for detecting vanishing points and vanishing lines, the observed feature points are clustered into collections that represent different lines. The multiple lines are then detected and the vanishing points are detected as points of intersection of the lines. The vanishing line is then detected based on the points of intersection. However, for the purpose of optimization, these processes should be integrated and be achieved simultaneously. In the present paper, we assume that the observed noise model for the feature points is a two-dimensional Gaussian mixture and define the likelihood function, including obvious vanishing points and a vanishing line parameters. As a result, the above described simultaneous detection can be formulated as a maximum likelihood estimation problem. In addition, an iterative computation method for achieving this estimation is proposed based on the EM (Expectation Maximization) algorithm. The proposed method involves new techniques by which stable convergence is achieved and computational cost is reduced. The effectiveness of the proposed method that includes these techniques can be confirmed by computer simulations and real images.

This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.

For many military and civilian large-scale, real-world systems of interest, data are first acquired asynchronously, i. e. at irregular intervals of time, at geographically-dispersed sites, processed utilizing decision-making algorithms, and the processed data then disseminated to other appropriate sites. The term real-world refers to systems under computer control that relate to everyday life and are beneficial to the society in the large. The traditional approach to such problems consists of designing a central entity which collects all data, executes a decision making algorithm sequentially to yield the decisions, and propagates the decisions to the respective sites. Centralized decision making algorithms are slow and highly vulnerable to natural and artificial catastrophes. Recent literature includes successful asynchronous, distributed, decision making algorithm designs wherein the local decision making at every site replaces the centralized decision making to achieve faster response, higher reliability, and greater accuracy of the decisions. Two key issues include the lack of an approach to synthesize asynchronous, distributed, decision making algorithms, for any given problem, and the absence of a comparative analysis of the quality of their decisions. This paper proposes MFAD, a Mathematical Framework for Asynchronous, Distributed Systems, that permits the description of centralized decision-making algorithms and facilities the synthesis of distributed decision-making algorithms. MFAD is based on the Kohn-Nerode distributed hybrid control paradigm. It has been a belief that since the centralized control gathers every necessary data from all entities in the system and utilizes them to compute the decisions, the decisions may be "globally" optimal. In truth, however, as the frequency of the sensor data increases and the environment gets larger, dynamic, and more complex, the decisions are called into question. In the distributed decision-making system, the centralized decision-making is replaced by those of the constituent entities that aim at minimizing a Lagrangian, i. e. a local, non-negative cost criterion, subject to the constraints imposed by the global goal. Thus, computations are carried out locally, utilizing locally obtained dataand appropriate information that is propagated from other sites. It is hypothesized that with each entity engaged in optimizing its individual behavior, asynchronously, concurrently, and independent of other entities, the distributed system will approach "global" optimal behavior. While it does not claim that such algorithms may be synthesized for all centralized real-world systems, this paper implements both the centralized and distributed paradigms for a representative military battlefield command, control, and communication (C3) problem. It also simulates them on a testbed of a network of workstations for a comparative performance evaluation of the centralized and decentralized paradigms in the MFAD framework. While the performance results indicate that the decentralized approach consistently outperforms the centralized scheme, this paper aims at developing a quantitative evaluation of the quality of decisions under the decentralized paradigm. To achieve this goal, it introduces a fundamental concept, embodied through a hypothetical entity termed "Perfect Global Optimization Device (PGOD)," that generates perfect or ideal decisions. PGOD possesses perfect knowledge, i. e. the exact state information of every entity of the entire system, at all times, unaffected by delay. PGOD utilizes the same decision-making algorithm as the centralized paradigm and generates perfect globally-optimal decisions which, though unattainable, provide a fundamental and absolute basis for comparing the quality of decisions. Simulation results reveal that the quality of decisions in the decentralized paradigm are superior to those of the centralized approach and that they approach PGOD's decisions.

We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance k1 of at least one resource copy, which is called the k-bounded placement problem. The structure of a distributed computing system is represented by a graph. The k-bounded placement problem is first transformed into the problem of finding smallest k-dominating sets in a graph. Searching for smallest k-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known A* algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

A number of parallel algorithms have been developed to solve large-scale real world problems. Although there has been much work on the design of parallel algorithms, there has been little on the design of languages for expressing these algorithms. This paper describes the BPL, a new parallel language designed for butterfly networks. The purpose of this language is to help designers in hiding the complexity of the algorithm and leaving details of mapping between data and processors for lower level. BPL provides a simpler virtual machine for the designer , in order to avoid thinking about control of processors and data. From another point of view, BPL helps designer to logically check the algorithm and correct any possible error in it. The paper gives some examples implemented by this language. In addition, we have also implemented a software tool which simulates the running of the algorithm on the network. The results lead us to believe that this language would be useful in representing all kinds of algorithms on this network including normal algorithms and others.

In a client-server system, when LRU or its variant buffer replacement strategy is used on both the client and the server, the cache performance on the server side is very poor mainly because of pages duplicated in both systems. This paper introduces a server buffer replacement strategy which uses a replaced page-id than a request page-id, for the primary information for its operations. The importance of the corresponding pages in the server cache is decided according to the replaced page-ids that are delivered from clients to the server, so that locations of the pages are altered. Consequently, if a client uses LRU as its buffer replacement strategy, then the server cache is seen by the client as a long virtual client LRU cache extended to the server. Since the replaced page-id is only sent to the server by piggybacking whenever a new page fetch request is sent, the operation to deliver the replaced page-id is simple and induces a minimal overhead. We show that the proposed strategy reveals good performance characteristics in diverse situations, such as single and multiple clients, as well as with various access patterns.

In this paper we propose a new lattice based second-order adaptive infinite impulse response (IIR) notch filter that uses a simplified adaptation algorithm. Steady-state analysis of the proposed structure is then studied based on the mean-squared error analysis of the steady-state variable coefficient fluctuations. The analysis is used to derive simple analytical expressions for steady-state variable coefficient variance and an upper bound for the step size adaptation constant. The results are shown to be useful in designing an FSK demodulator using the proposed structure. Computer simulation results are shown to confirm derived analytical expressions.

A software antenna, which will be a key device realizing flexible and highly reliable wireless communications systems, is inherently matched with software defined radios (SDR). In this paper, first, key technologies on the software antenna are introduced. The technologies contain i) how to recognize the radio environment, ii) how to determine the optimum adaptive signal processing algorithm, and iii) how to reconfigure the digital beamforming circuit. Then, an image of a software antenna with reconfigurable eigenvector-beamspace configuration is presented. Finally, by assuming various propagation conditions, performance of the software antenna in terms of algorithm diversity is demonstrated.

The multiple access causes an interference problem in the direct-sequence code-division multiple access systems. An efficient adaptive algorithm should be used to suppress this interference for the improvement of system performance. In this paper, the new blind adaptive method is suggested using the constant modulus algorithm for the purpose of interference suppression. Simulation results show that the converged value of signal to interference ratio for the proposed method is approximately 6 [dB] larger than that of a conventional Blind-MOE receiver in the additive white Gaussian noise channel and channel with inter-symbol interference while the signal to interference ratio improvement is almost 4 [dB] better in the Rayleigh fading channel. The suggested method is also robust to the new user interference resulting the nearly 3 [dB] improvement of the SIR value comparing with the conventional receiver. Based on these results, it is shown that the BER of the proposed receiver is lower than that of any other conventional receiver. Therefore, using the newly suggested method, the considerable performance improvement can be obtained for the DS-CDMA systems.

In this paper, we study efficient scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin (WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.

All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

We propose a novel adaptive multiple-symbol differential detection (MSDD) scheme that has excellent performance over frequency selective fading (FSF) channels. The adaptive MSDD scheme consists of an adaptive noncoherent least mean square channel estimator that can accomplish channel estimation without any decision delay and the MSDD. The M-algorithm is introduced into this detection scheme to reduce the complication of computation due to increasing observed sequence length in the MSDD. Because of the application of the adaptive channel estimator and the M-algorithm, this adaptive MSDD make it possible that channel estimation is accomplished for every symbol along M surviving paths without any decision delay. And the SER performance of this adaptive MSDD is not affected by phase fluctuation introduced by a channel because the MSDD and the noncoherent channel estimator are applied. The adaptive MSDD scheme is applied to typical constellation of 16APSK, the (4,12) QAM and the star QAM. The excellent tracking performance of this adaptive MSDD scheme over FSF channels is confirmed by computer simulations.