Fast cosine transform of Toeplitz matrices, algorithm andapplications

A fast algorithm for the discrete cosine transform (DCT) of a Toeplitz matrix of order N is derived. Only O(N log N)+O(M) time is needed for the computation of M elements. The storage requirement is O(N). The method carries over to other transforms (DFT, DST) and to Hankel or circulant matrices. Some applications of the algorithm are discussed     

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³)     

Zero-crossings of a wavelet transform

The completeness, stability, and application to pattern recognition of a multiscale representation based on zero-crossings is discussed. An alternative projection algorithm is described that reconstructs a signal from a zero-crossing representation, which is stabilized by keeping the value of the wavelet transform integral between each pair of consecutive zero-crossings. The reconstruction algorithm has a fast convergence and each iteration requires O( N log² (N)) computation for a signal of N samples. The zero-crossings of a wavelet transform define a representation which is particularly well adapted for solving pattern recognition problems. As an example, the implementation and results of a coarse-to-fine stereo-matching algorithm are described     

Electromagnetic scattering of finite strip array on a dielectricslab

A feast recursive algorithm is used to compute the scattering properties of a finite array of strip gratings on a dielectric slab. this algorithm has a computational complexity of O(N log² N) for one incident angle and O(N ² log N) for N incident angles. It uses plane wave basis for expanding the incident wave and the scattered wave. The scattered wave is expanded in terms of a Sommerfeld-type integral with spectral distribution along a vertical branch cut, rendering its expansion very efficient. To validate the scattering solution obtained using the recursive algorithm, comparisons with the method of moments are illustrated. The current distributions on the strips and scattering patterns are both presented. Since this algorithm has reduced computational complexity and is fast compared to other conventional methods, it can be used to analyze very large strip arrays. Scattering solution of a 50-wavelength wide strip is illustrated     

Fast computation of transform coefficients for a subadjacent blockfor a transform family

The authors examine several different kinds of subadjacent blocks, and consider fast computation for a transform family including the Walsh-Hadamard transform and the Rh transform as special cases. The approach proposed here provides a direct frequency-frequency procedure. Results indicate that, for this transform family, a reduction of the number of multiplications and additions is achieved by a factor of two-thirds. An example for the Rh transform shows that further reduction of arithmetic operations is also possible. The results of this method are even better for the Walsh-Hadamard transform. The new algorithms can reduce the number of additions from the level O(N log ₂ N) to the level O(N), as compared to the traditional method     

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 new time domain, multistage permutation algorithm [switchingsystems]

It is shown that a frame of N time slots can be arbitrarily permuted with 2log₂N-1 controlled exchange switches with associated delay elements. This is an improvement over previously known interconnection networks that require O( N) exchange elements. The proof utilizes the recursive algorithm of V.E. Benes (1965) and the time interchange properties of a particular configuration of a single exchange element. The architecture is especially applicable in optical systems, since optical exchange switches are among the simplest optical logic devices to build, are inherently very fast, and are the best developed, although expensive     

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     

Maximum likelihood estimation of the parameters of discretefractionally differenced Gaussian noise process

A maximum-likelihood estimation procedure is constructed for estimating the parameters of discrete fractionally differenced Gaussian noise from an observation set of finite size N. The procedure does not involve the computation of any matrix inverse or determinant. It requires N²/2+O(N) operations. The expected value of the loglikelihood function for estimating the parameter d of fractionally differenced Gaussian noise (which corresponds to a parameter of the equivalent continuous-time fractional Brownian motion related to its fractal dimension) is shown to have a unique maximum that occurs at the true value of d. A Cramer-Rao bound on the variance of any unbiased estimate of d obtained from a finite-sized observation set is derived. It is shown experimentally that the maximum-likelihood estimate of d is unbiased and efficient when finite-size data sets are used in the estimation procedure. The proposed procedure is extended to deal with noisy observations of discrete fractionally differenced Gaussian noise     

A fast recursive least squares adaptive second order Volterrafilter and its performance analysis

A fast, recursive least squares (RLS) adaptive nonlinear filter modeled using a second-order Volterra series expansion is presented. The structure uses the ideas of fast RLS multichannel filters, and has a computational complexity of O(N³) multiplications, where N-1 represents the memory span in number of samples of the nonlinear system model. A theoretical performance analysis of its steady-state behaviour in both stationary and nonstationary environments is presented. The analysis shows that, when the input is zero mean and Gaussian distributed, and the adaptive filter is operating in a stationary environment, the steady-state excess mean-squared error due to the coefficient noise vector is independent of the statistics of the input signal. The results of several simulation experiments show that the filter performs well in a variety of situations. The steady-state behaviour predicted by the analysis is in very good agreement with the experimental results     

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     

Modular VLSI architectures for computing the arithmetic Fouriertransform

Modular, area-efficient VLSI architectures for computing the arithmetic Fourier transform (AFT) are proposed. By suitable design of PEs and I/O sequencing, nonuniform data dependencies in the AFT computation which require nonequidistant inputs and assignment of Mobius function values are resolved. The proposed design employs 2N+1 PEs to compute 2N+1 Fourier coefficients. Each PE has an adder and a fixed amount of local storage, and one PE has a multiplier. I/O with the host is performed using a fixed number of channels. This results in simple PE organization, compared with those needed in known DFT/FFT architectures. The design achieves O(N) speedup. It uses significantly fewer PEs than designs in the literature and supports real-time applications by allowing continuous sequential input. It can be extended to achieve linear speedup in a fixed size array with 2p+1 PEs, 1⩽p⩽N     

Roundoff error analysis of the discrete Wigner distribution usingfixed-point arithmetic

The issue of roundoff noise effects in the implementation of the discrete Wigner distribution using fixed-point arithmetic is addressed. The sign-magnitude number representation is assumed throughout the analysis. The measure of roundoff noise effects in an algorithm is the output noise-to-signal ratio. Using a statistical model, an analytical expression of the noise-to-signal ratio is derived as a function of the wordlength b and the transform length N. The noise-to-signal ratio is obtained by evaluating the signal and noise powers at different points in the algorithm, then reflecting to the output both signal and noise powers. Based on the derived noise-to-signal ratio is is noted that if the transform length is doubled, then) one additional bit is required in the wordlength to maintain a constant noise-to-signal ratio. It is demonstrated through the software simulations that the predicted noise-to-signal ratio is a good closed-form estimate of the `true' roundoff error. It is also found from the simulation that the wordlength b and the transform length N=2^v must satisfy the condition b- v⩾4     

Recursive updating the eigenvalue decomposition of a covariancematrix

The author addresses the problem of computing the eigensystem of the modified Hermitian matrix, given the prior knowledge of the eigensystem of the original Hermitian matrix. Specifically, an additive rank-k modification corresponding to adding and deleting blocks of data to and from the covariance matrix is considered. An efficient and parallel algorithm which makes use of a generalized spectrum-slicing theorem is derived for computing the eigenvalues. The eigenvector can be computed explicitly in terms of the solution of a much-reduced (k ×k) homogeneous Hermitian system. The overall computational complexity is shown to be improved by an order of magnitude from O(N³) to O(N ²k), where N×N is the size of the covariance matrix. It is pointed out that these ideas can be applied to adaptive signal processing applications, such as eigen-based techniques for frequency or angle-of-arrival estimation and tracking. Specifically, adaptive versions of the principal eigenvector method and the total least squares method are derived     

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     

Modulatable orthogonal sequences and their application to SSMAsystems

A set of N-1 orthogonal sequences of period N ² is proposed, where N is a natural number. Each orthogonal sequence proposed can be modulated by N complex numbers of absolute value 1, so the modulated sequence is also orthogonal. When N is an odd prime number, the absolute value of the cross-correlation function between any two of the N-1 orthogonal sequences is constant and satisfies the mathematical lower bound. This property of the cross-correlation function is not changed when each of the two orthogonal sequences is modulated by N complex numbers of absolute value 1. Two spread-spectrum multiple-access (SSMA) systems using these sequences are proposed. One system is an asynchronous SSMA system, using the proposed sequences unmodulated. The cochannel interference peak between any two channels in this system realizes the mathematical lower bound for an asynchronous SSMA system using a set of orthogonal sequences. The other system is a synchronous SSMA system without cochannel interference which uses the modulated form of the proposed sequences     

A replacement policy maximizing MTTF of a system with several spareunits

A replacement policy is considered that maximizes mean time-to-failure (MTTF) of a system with N spare units. The optimum replacement time of a system with k spares (k=1, 2, ..., N) is derived successively from MTTF with k-1 spares by induction. The maximum MTTF is approximately given by a reciprocal of the hazard rate     

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     

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     

Reliable and fast reconfigurable hierarchical interconnectionnetworks for linear WSI arrays

A self-pruning binary tree (SPBT) interconnection network architecture that tolerate faults in a wafer scale integration (WSI) environment is proposed. The goal of the SPBT network is to provide a reliable and a quickly reconfigured interconnection network architecture for linear WSI arrays. The proposed architecture uses a bottom-up approach to reconfigure a linear pipelined array on a potentially defective WSI array using a binary tree interconnection scheme. The binary tree is generated by successive formation of hierarchical modules. For N processing elements (PEs) on the wafer, reconfiguration time is O(log N). The propagation delay is bounded by Θ(log N) and is independent of the number of faulty PEs. Faults in the switching network as well as faulty processing elements are tolerated