An efficient cell-scheduling algorithm for multicast ATM switchingsystems

We propose an efficient multicast cell-scheduling algorithm, called multiple-slot cell-scheduling algorithm, for multicast ATM switching systems with input queues. Cells in an input-queueing system are usually served based on the first-in-first-out (FIFO) discipline, which may have a serious head-of-line (HOL) blocking problem. Our algorithm differs from previous algorithms in that we consider the output contention resolution for multiple time slots instead of the current time slot only. Like a window-based scheduling algorithm, our algorithm allows cells behind an HOL cell to be transmitted prior to the HOL cell in the same input port. Thus, HOL blocking can be alleviated. We have illustrated that the delay-throughput performance of our algorithm outperforms most of those algorithms that consider only the output contention resolution for the current time slot. We also present a simple and efficient architecture for realizing our algorithm, which can dramatically reduce the time complexity. We believe that the proposed architecture is very suitable for multicast asynchronous transfer mode (ATM) switching systems with input queues     

Asynchronous Congestion Control in Multi-Hop Wireless Networks With Maximal Matching-Based Scheduling

We consider a multi-hop wireless network shared by many users. For an interference model that constrains a node to either transmit to or receive from only one other node at a time, and not to do both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms.      

An optimal vector-network-analyzer calibration algorithm

We present an iterative algorithm for calibrating vector network analyzers based on orthogonal distance regression. The algorithm features a robust, yet efficient, search algorithm, an error analysis that includes both random and systematic errors, a full covariance matrix relating calibration and measurement errors, 95% coverage factors, and an easy-to-use user interface that supports a wide variety of calibration standards. We also discuss evidence that the algorithm outperforms the MultiCal software package in the presence of measurement errors and accurately estimates the uncertainty of its results.     

Time-delay estimation for filtered Poisson processes using anEM-type algorithm

We develop a modified EM algorithm to estimate a nonrandom time shift parameter of an intensity associated with an inhomogeneous Poisson process N_t, whose points are only partially observed as a noise-contaminated output X of a linear time-invariant filter excited by a train of delta functions, a filtered Poisson process. The exact EM algorithm for computing the maximum likelihood time shift estimate generates a sequence of estimates each of which attempt to maximize a measure of similarity between the assumed shifted intensity and the conditional mean estimate of the Poisson increment dN_t. We modify the EM algorithm by using a linear approximation to this conditional mean estimate. The asymptotic performance of the modified EM algorithm is investigated by an asymptotic estimator consistency analysis. We present simulation results that show that the linearized EM algorithm converges rapidly and achieves an improvement over conventional time-delay estimation methods, such as linear matched filtering and leading edge thresholding. In these simulations our algorithm gives estimates of time delay whose mean square error virtually achieves the CR lower bound for high count rates     

Genetic algorithms for a robust 3-D MR-CT registration

Presents an original usage of genetic algorithms as a robust search space sampler in an application to 3D medical image elastic registration. An overview of the standard steps of a registration algorithm is given. We focus on the genetic algorithm use, and particularly on the problem of extracting the optimal solution among the final genetic population. We provide an original encoding scheme relying on a structural approach of point matching and then point out the need for a local optimization process. We then illustrate the algorithm with a concrete registration example and assert the results with a direct multi-volume rendering tool. Finally, the algorithm is applied to the Vanderbilt medical image database to assert its robustness and in order to compare it with other techniques     

A fast parallel implementation of a Berlekamp-Massey algorithm foralgebraic-geometric codes

We obtain a parallel Berlekamp-Massey-type algorithm for determining error locating functions for the class of one point algebraic-geometric codes. The proposed algorithm has a regular and simple structure and is suitable for VLSI implementation. We give an outline for an implementation, which uses as main blocks γ copies of a modified one-dimensional Berlekamp-Massey algorithm, where γ is the order of the first nongap in the function space associated with the code. Such a parallel implementation determines the error locator for an algebraic-geometric code using the same time requirements as the underlying one-dimensional Berlekamp-Massey algorithm applied to the decoding of Reed-Solomon codes     

Application of an anisotropic perfectly matched layer absorber for open boundary truncation in the multiresolution time domain scheme

We apply an anisotropic perfectly matched layer (APML) absorber for open boundary truncation in implementation of the multiresolution time domain (MRTD) scheme. We develop an APML update algorithm to handle a general APML region in the MRTD formulations with the content of the leapfrog algorithm applied in the conventional finite-difference time-domain method. We also discuss the boundary truncations for both perfectly electric conductor (PEC) and perfectly magnetic conductor (PMC) walls using the image techniques. We validate the algorithm by analyzing various guided wave and antenna structures. It is found that the APML performs well for absorbing electromagnetic waves in the MRTD algorithm.     

A path decomposition approach for computing blocking probabilitiesin wavelength-routing networks

We study a class of circuit-switched wavelength-routing networks with fixed or alternate routing and with random wavelength allocation. We present an iterative path decomposition algorithm to evaluate accurately and efficiently the blocking performance of such networks with and without wavelength converters. Our iterative algorithm analyzes the original network by decomposing it into single-path subsystems. These subsystems are analyzed in isolation, and the individual results are appropriately combined to obtain a solution for the overall network. To analyze individual subsystems, we first construct an exact Markov process that captures the behavior of a path in terms of wavelength use. We also obtain an approximate Markov process which has a closed-form solution that can be computed efficiently for short paths. We then develop an iterative algorithm to analyze approximately arbitrarily long paths. The path decomposition approach naturally captures the correlation of both link loads and link blocking events. Our algorithm represents a simple and computationally efficient solution to the difficult problem of computing call-blocking probabilities in wavelength-routing networks. We also demonstrate how our analytical techniques can be applied to gain insight into the problem of converter placement in wavelength-routing networks     

Incremental augmented complex adaptive IIR algorithm for training widely linear ARMA model

In this paper, we propose a distributed adaptive learning algorithm to train the coefficients of a widely linear autoregressive moving average model by measurements collected by the nodes of a network. We assume that each node uses the augmented complex adaptive infinite impulse response (ACA-IIR) filter as the learning rule, and nodes interact with each other under an incremental mode of cooperation. To derive the proposed algorithm, called the incremental ACAIIR (IACA-IIR), we firstly formulate the distributed adaptive learning problem as an unconstrained minimization problem. Then, we apply stochastic gradient optimization argument to solve it and derive the proposed algorithm. We further find the step size range where the stability of the proposed algorithm is guaranteed. We also introduce a reduced-complexity version of the IACA-IIR algorithm. Since the proposed algorithm relies on the augmented complex statistics, it can be used to model both types of complex-valued signals (proper and improper signals). To evaluate the performance of the proposed algorithm, we use both synthetic and real-world complex signals in our simulations. The results exhibit superior performance of the proposed algorithm over the non-cooperative ACA-IIR algorithm.     

Sequential diagnosis of processor array systems

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.     

A quasi-Newton adaptive algorithm for generalized symmetriceigenvalue problem

We first recast the generalized symmetric eigenvalue problem, where the underlying matrix pencil consists of symmetric positive definite matrices, into an unconstrained minimization problem by constructing an appropriate cost function. We then extend it to the case of multiple eigen-vectors using an inflation technique. Based on this asymptotic formulation, we derive a quasi-Newton-based adaptive algorithm for estimating the required generalized eigen-vectors in the data case. The resulting algorithm is modular and parallel, and it is globally convergent with probability one. We also analyze the effect of inexact inflation on the convergence of this algorithm and that of inexact knowledge of one of the matrices (in the pencil) on the resulting eigenstructure. Simulation results demonstrate that the performance of this algorithm is almost identical to that of the rank-one updating algorithm of Karasalo (1986). Further, the performance of the proposed algorithm has been found to remain stable even over 1 million updates without suffering from any error accumulation problems     

Exact Bayesian curve fitting and signal segmentation

We consider regression models where the underlying functional relationship between the response and the explanatory variable is modeled as independent linear regressions on disjoint segments. We present an algorithm for perfect simulation from the posterior distribution of such a model, even allowing for an unknown number of segments and an unknown model order for the linear regressions within each segment. The algorithm is simple, can scale well to large data sets, and avoids the problem of diagnosing convergence that is present with Monte Carlo Markov Chain (MCMC) approaches to this problem. We demonstrate our algorithm on standard denoising problems, on a piecewise constant AR model, and on a speech segmentation problem.     

Optimal Multicast Routing and Wavelength Assignment on WDM Ring Networks Without Wavelength Conversion

We consider the multicast routing and wavelength assignment (MC-RWA) problem on WDM bidirectional ring networks without wavelength conversion. We give an integer programming formulation of the problem and propose an algorithm to solve it optimally. The algorithm is based on column generation and branch-and-price. We test the proposed algorithm on randomly generated data and the test results show that the algorithm gives optimal solutions to all of the test problems.     

An Optimized Supply Chain Network Model Based on Modified Genetic Algorithm

For complex multi-source, multi-product, multi-stage Supply chain network (SCN) design problem, we propose an optimization supply chain network model. We consider cash conversion cycle as an objective to this model and utilize a modified genetic algorithm to solve the problem. To describe the structure of supply chain network, we propose a new encoding method and a ge-netic algorithm with modified genetic operators. We use the Pareto approach to obtain the set of Pareto-optimal solutions. In order to evaluate the performance of the mod-ified genetic algorithm and validate the model, we conduct comparisons with standard genetic algorithm and the sim-ulated annealing genetic algorithm. Experimental results show that the modified genetic algorithm achieved better CPU time and the accuracy of the Pareto-optimal solu-tions than the alternative algorithms and the model was effective.     

Jitter control in QoS networks

We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: we propose on-line algorithms that control jitter and compare their performance to the best possible (by an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of different packets, we show that a simple on-line algorithm using a buffer of B slots guarantees the same delay jitter as the best off-line algorithm using buffer space B/2. We prove that the guarantees made by our on-line algorithm hold, even for simple distributed implementations, where the total buffer space is distributed along the path of the connection, provided that the input stream satisfies a certain simple property. For rate jitter, where the goal is to minimize the difference between inter-arrival times, we develop an on-line algorithm using a buffer of size 2B+h for any h⩾1, and compare its jitter to the jitter of an optimal off-line algorithm using buffer size B. We prove that our algorithm guarantees that the difference is bounded by a term proportional to B/h     

DOA estimation in multipath: an approach using fourth-ordercumulants

We consider the problem of direction of arrival (DOA) estimation in the presence of multipath propagation. The sensor elements are assumed to be linear and uniformly spaced. To perform DOA estimation, we combine two existing algorithms which are often used for other purposes. The first algorithm exploits fourth-order cumulants to perform blind estimation of the steering vectors and the second algorithm estimates the directions of arrival using the estimated vectors. We refer to this two step approach as the SV-DOA estimation algorithm. We also present an algorithm independent performance analysis for the DOA estimation problem based on fourth-order cumulants. We summarize the algorithms and present Monte-Carlo simulations demonstrating the effectiveness of the SV-DOA algorithm as well as verifying the performance analysis using an optimal (but computationally expensive) DOA estimation algorithm     

An LMS-based decision feedback equalizer for IS-136 receivers

In digital mobile communication systems, intersymbol interference is one of the main causes of degrading system performance. Decision feedback equalization (DFE) is the commonly used remedy for this problem. Since the channel is fast-varying, an adaptive algorithm possessing a fast convergence property is then required. The least mean square (LMS) algorithm is well known for its simplicity and robustness; however, its convergence is slow. As a consequence, the LMS algorithm is rarely considered in this application. In this paper, we consider an LMS-based DFE for the North American IS-136 system. We propose an extended multiple-training LMS algorithm accelerating the convergence process. The convergence properties of the multiple-training LMS algorithm are also analyzed. We prove that the multiple-training LMS algorithm can converge regardless of its initial value and derive closed-form expressions for the weight error vector power. We further take advantage of the IS-136 downlink slot format and divide a slot into two subslots. Bidirectional processing is then applied to each individual subslot. The proposed LMS-based DFE has a low computational complexity and is suitable for real-world implementation. Simulations with a 900-MHz carrier show that our algorithm can meet the 3% bit error rate requirement for mobile speeds up to 100 km/hr     

An efficient multi-exponentiation scheme based on modified Booth's method

We propose an efficient multi-exponentiation algorithm based on the modified Booth' algorithm and Montgomery's modular multiplication algorithm. The multi-exponentiation algorithm can be used to implement fast modern cryptosystems. Owing to the reduced number of multiplications, this algorithm is about 10% faster than Pekmestzi's algorithms. The proposed algorithm can be implemented in hardware as a small component. The component can then be used to form an efficient modular multi-exponentiation module by combining it with an efficient Montgomery modular multiplication module.     

New decoding algorithm for Reed - Muller codes (Corresp.)

We interpret Reed-Muller codes in terms of superimposition and present a new decoding algorithm for Reed-Muller codes. Before presenting this algorithm, we propose a decoding algorithm for a class of simple iterated codes (SI codes) that will play an important role in our new decoding algorithm. Finally, we compare our algorithm with the conventional algorithm for the cyclic Reed-Muller codes from the standpoint of decoding delay.     

The design and implementation of COSEM, an iterative algorithm for fully 3-D listmode data

In this paper,we present coincidence-list-ordered sets expectation-maximization (COSEM), an algorithm for iterative image reconstruction directly from list-mode coincidence acquisition data. The COSEM algorithm is based on the ordered sets EM algorithm for binned data but has several extensions that makes it suitable for rotating two planar detector tomographs. We develop the COSEM algorithm and extend it to include analytic calculation of detection probability, noise reducing iterative filtering schemes, and on-the-fly attenuation correction methods. We present an adaptation of COSEM to the Varicam\VG camera and show results from clinical and phantom studies.