Recursive T-matrix algorithms for the solution ofelectromagnetic scattering from strip and patch geometries

Two recursive T-matrix algorithms are presented and their reduced computational complexities and reduced memory requirements are demonstrated. These algorithms are applied to the problem of electromagnetic scattering from conducting strips and patches with canonical geometries. The geometries are reminiscent of finite-sized frequency selective surfaces. Computational complexities of O( N²) and O(N^7/3) and memory requirements of O(N) and O(N ^4/3) are shown to be feasible for two-dimensional and three-dimensional geometries, respectively. The formulation uses only two components of the electric field. Therefore, the vector electromagnetic problem of scattering from three-dimensional patch geometries can be solved using scalar addition theorems for spherical harmonic wave functions. For a two-dimensional strip problem, both TM and TE polarizations can be solved simultaneously using this formulation. Numerical scattering results in the form of radar cross sections (RCS) are validated by comparison with the method of moments     

Design and characterization of optimal FIR filters with arbitraryphase

An algorithm for designing a Chebyshev optimal FIR filter that approximates an arbitrary complex-valued frequency response is presented. This algorithm computes the optimal filter by solving the dual to the filter design problem. It is guaranteed to converge theoretically and requires O(N²) computations per iteration for a filter of length N. For the first time, properties of the optimal filter are derived, and the case where the desired filter has arbitrary constant group delay is studied in detail     

Efficient algorithm for reliability of a circular consecutive-k-out-of-n:F system

The time complexities of previously published algorithms for circular consecutive-k-out-of-n:F systems are O (nk²) and O(nk). The authors propose a method to improve the original O(nk² ) algorithm, and hence derive an O(nk) algorithm     

A fast quasi-Newton adaptive filtering algorithm

The convergence rate of an adaptive system is closely related to its ability to track a time-varying optimum. Basic adaptive filtering algorithms give poor convergence performance when the input to the adaptive system is colored. More sophisticated algorithms which converge very rapidly regardless of the input spectrum algorithms typically require O(N²) computation, where N is the order of the adaptive filter, a significant disadvantage for real-time applications. Also, many of these algorithms behave poorly in finite-precision implementation. An adaptive filtering algorithm is introduced which employs a quasi-Newton approach to give rapid convergence even with colored inputs. The algorithm achieves an overall computational requirement of O(N) and appears to be quite robust in finite-precision implementations     

Fast algorithm and architecture for constrained adaptive side-lobecancellation

An efficient implementation of auxiliary constraints for a concurrent-block least-squares adaptive side-lobe canceler is described. A QR decomposition of the auxiliary data matrix is computed, and this information is sent to one or more main beam processors, where the constraints are applied using blocking matrices and the individual residuals are computed. Structured blocking matrices are used to derive a fast algorithm and architecture for constrained main beam processing. This approach reduces the operation count of this phase of the processing from O(n³) to O(n ²), where n is the number of auxiliary sensors     

Reliability of linear and circular consecutively-connected systems

J.G. Shanthikumar (IEEE Trans. Reliability, vol.R-36, p.546-50, Dec. 1987) proposed a new system structure called the consecutively connected system, which is a generalization of the well-studied consecutive-k-out-of-n:F system. An O(n ²) algorithm was developed for its reliability evaluation. This work studies the structure of the consecutively connected system and provides more efficient algorithms for its reliability evaluation. The complexities of the algorithms are of order O(kn) for linear systems and O(k³n) for circular systems (k <n). The concepts of transmitting capability and receiving capability are introduced     

Adaptive set-membership identification in O(m)time for linear-in-parameters models

Some fundamental contributions to the theory and applicability of optimal bounding ellipsoid (OBE) algorithms for signal processing are described. All reported OBE algorithms are placed in a general framework that demonstrates the relationship between the set-membership principles and least square error identification. Within this framework, flexible measures for adding explicit adaptation capability are formulated and demonstrated through simulation. Computational complexity analysis of OBE algorithms reveals that they are of O(m²) complexity per data sample with m the number of parameters identified. Two very different approaches are described for rendering a specific OBE algorithm, the set-membership weighted recursive least squares algorithm, of O(m) complexity. The first approach involves an algorithmic solution in which a suboptimal test for innovation is employed. The performance is demonstrated through simulation. The second method is an architectural approach in which complexity is reduced through parallel competition     

Solution to the problem of instability in banded Toeplitz solvers

The author presents a numerically stable approach to solving banded Toeplitz systems of n linear equations. The algorithm is fast in that it requires only O(nq) operations, where q is the bandwidth of the matrix. An earlier version of the banded Toeplitz algorithm presented in the literature suffers from numerical instability. The author solves the instability problem by developing numerically stable alternatives to the back substitution process. These new algorithms have roughly the same number of calculations as simple back substitution, O(nq), and therefore can be used effectively in place of back substitution. The stabilization procedures described have been used to find accurate solutions to systems of order several thousand     

Restoration of color images by multichannel Kalman filtering

A Kalman filter for optimal restoration of multichannel images is presented. This filter is derived using a multichannel semicausal image model that includes between-channel degradation. Both stationary and nonstationary image models are developed. This filter is implemented in the Fourier domain and computation is reduced from O(Λ ³N³M⁴) to O(Λ³N³M² ) for an M×M N-channel image with degradation length Λ. Color (red, green, and blue (RGB)) images are used as examples of multichannel images, and restoration in the RGB and YIQ domains is investigated. Simulations are presented in which the effectiveness of this filter is tested for different types of degradation and different image model estimates     

The fast multipole method (FMM) for electromagnetic scatteringproblems

The fast multipole method (FMM) developed by V. Rokhlin (1990) to efficiently solve acoustic scattering problems is modified and adapted to the second-kind-integral-equation formulation of electromagnetic scattering problems in two dimensions. The present implementation treats the exterior Dirichlet problem for two-dimensional, closed, conducting objects of arbitrary geometry. The FMM reduces the operation count for solving the second-kind integral equation from O(n³) for Gaussian elimination to O(n^4/3) per conjugate-gradient iteration, where n is the number of sample points on the boundary of the scatterer. A sample technique for accelerating convergence of the iterative method, termed complexifying k, the wavenumber, is also presented. This has the effect of bounding the condition number of the discrete system; consequently, the operation count of the entire FMM (all iterations) becomes O(n^4/3). Computational results for moderate values of ka, where a is the characteristic size of the scatterer, are given     

An O(kn)-time algorithm for computing thereliability of a circular consecutive-k-out-of-n:Fsystem

I. Antonopoulou and S. Papastavridis (1987) published an algorithm for computing the reliability of a circular consecutive-k-out-of-n:F system which claimed O (kn) time. J.S. Wu and R.J. Chen (1993) correctly pointed out that the algorithm achieved only O(kn²) time. The present study shows that the algorithm can be implemented for O(kn) time     

Multidimensional multirate filters and filter banks derived fromone-dimensional filters

A method by which every multidimensional (M-D) filter with an arbitrary parallelepiped-shaped passband support can be designed and implemented efficiently is presented. It is shown that all such filters can be designed starting from an appropriate one-dimensional prototype filter and performing a simple transformation. With D denoting the number of dimensions, the complexity of design and implementation of the M-D filter are reduced from O(N^D) to O(N). Using the polyphase technique, an implementation with complexity of only 2N is obtained in the two-dimensional. Even though the filters designed are in general nonseparable, they have separable polyphase components. One special application of this method is in M-D multirate signal processing, where filters with parallelepiped-shaped passbands are used in decimation, interpolation, and filter banks. Some generalizations and other applications of this approach, including M-D uniform discrete Fourier transform (DFT) quadrature mirror filter banks that achieve perfect reconstruction, are studied. Several design example are given     

A system for systolic modules for the MUSIC algorithm

The authors believe that special-purpose architectures for digital signal processing (DSP) real-time applications will use closely coupled processing elements as array processor modules to implement the various portions of the new algorithms, and several such modules will cooperate in a pipelined manner to implement complete algorithms. Such an architecture, based upon systolic modules, for the MUSIC algorithm is presented. The architecture is suitable for VLSI implementation. The throughput of the pipelined approach is O(N), whereas the sequential approach is O(N³)     

Asymptotically optimal design of congestion control for high speeddata networks

The basic mechanism of sliding windows for the congestion control of virtual circuits is examined. A problem concerning the optimal design of windows is formulated and formulas for basic quantities of interest, such as throughput, delay and moments of packet queues, in the optimal operating regime as well as in other regimes, are obtained. All results are asymptotic, in which the main parameter is λ, the delay-bandwidth product. It is shown that K*~λ+O(√λ), where K* is the optimum window size. Also, in the optimal operating regime, the steady-state mean and standard deviation of the queued packets at individual nodes O(√/λ). The design consequences are examined in the contexts of adaptive dynamic windowing, buffer sizing, and shared versus separate buffers in the case of multiple virtual circuits     

Superlattice/superladder computational organization for linearprediction and optimal FIR filtering

A family of computational organizations for the solution of the Toeplitz systems appearing in the digital signal processing (DSP) techniques of linear prediction and optimal FIR filtering is presented. All these organizations are based on a structure called superlattice which governs the Toeplitz solving procedure and provides many possible implementations. Algorithmic schemes for the implementation of these organizations, suitable for single-processor and multiprocessor environments, are developed. Among them there are order recursive algorithms, parallel-algorithms of O(p) complexity which use O(p) processing elements, and partitioned-parallel algorithms. The last can make full use of any number of available, parallel-working processors, independently of the system order. Superlattice-type algorithms are described for many Toeplitz-based problems     

Fast conversion between binary and residue numbers

New, efficient hardware implementations are considered which perform code conversions between the three moduli (2ⁿ-1, 2 ⁿ, 2ⁿ+1) residue number systems and their binary representations. Significant hardware saving together with high-speed throughput is achieved by using only n and (n+1)-bit binary adders     

Delay analysis of continuous bit rate traffic over an ATM network

A packet multiplexer is modeled for continuous bit rate (CBR) traffic in an asynchronous transfer mode (ATM) network as an nD/D/1 queue. The efficiencies of various algorithms for finding the delay distribution are compared. In particular, a new algorithm is proposed whose time complexity is O(n²), where n is the number of voice sources being multiplexed. The use of the central limit theorem can reduce the time complexity to O(n) for large n . An asymptotic formula is found whose time complexity is independent of n and it works well (for practical purposes) over a wide range of parameter values. The authors examine and comment on the use of the M/D/1 results as an approximation. In addition to comparing the performances of these algorithms, they show that the buffer requirements for such a queue are significantly less than the theoretical maximum (even when the requirement on the call disruption probability is very low). This result has important implications in the design of buffer size. The buffer requirement is relatively insensitive to the design criterion (call disruption probability)     

On the reduction in multiplicative complexity achieved by thepolynomial residue number system

The polynomial residue number system is known to reduce the complexity of polynomial multiplication from O(N² ) to O(N). A new interpretation of this complexity reduction is given in the context of associative algebras over a finite field. The new point of view provides a clearer understanding of the Chinese remainder theorem     

An updating algorithm for subspace tracking

In certain signal processing applications it is required to compute the null space of a matrix whose rows are samples of a signal with p components. The usual tool for doing this is the singular value decomposition. However, the singular value decomposition has the drawback that it requires O(p³) operations to recompute when a new sample arrives. It is shown that a different decomposition, called the URV decomposition, is equally effective in exhibiting the null space and can be updated in O( p²) time. The updating technique can be run on a linear array of p processors in O(p) time     

Stable and efficient lattice algorithms for adaptive IIR filtering

Previous attempts at applying lattice structures to adaptive infinite-impulse-response (IIR) filtering have met with gradient computations of O(N²) complexity. To overcome this computational burden, two new lattice-based algorithms are proposed for adaptive IIR filtering and system identification, with both algorithms of O(N) complexity. The first algorithm is a reinterpretation of the Steiglitz-McBride method (1965), while the second is a variation on the output error method. State space models are employed to make the derivations transparent, and the methods can be extended to other parameterizations if desired. The set of possible stationary points of the algorithms is shown to be consistent with the convergent points obtained from the direct-form versions of the Steiglitz-McBride and output error methods, whose properties are well studied. The derived algorithms are as computationally efficient as existing direct-form based algorithms, while overcoming the stability problems associated with time-varying direct-form filters