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     

Performance analysis of nonblocking packet switch with input andoutput buffers

The performance of nonblocking packet switches such as the knockout switch and Batcher banyan switch for high-speed communication networks can be improved as the switching capacity L per output increases; the switching capacity per output refers to the maximum number of packets transferred to an output during a slot. The N×N switch with L=N was shown to attain the best possible performance by M.J. Karol et al. (1987). Here a N×N nonblocking packet switch with input and output buffers is analyzed for an arbitrary number of L such that 1⩽L⩽N. The maximum throughput and packet loss probability at input are obtained when N=∞     

Quadtree-structured recursive plane decomposition coding of images

The approximation of two-dimensional highly correlated grey value functions can be performed using a linear model of the type f( x, y)=a+bx+cy. The set of plane parameters (PPs) [a, b, c] can be determined in the least squares sense for a block of size N×N pixels, for example. Starting with a block size of 2×2 pixels, it is shown that the PPs obey a recursive law such that the PPs of a 2N×2N block can be computed recursively when only the PPs of the four adjacent subblocks of size N×N in the lower decomposition level are known. This concept of recursive plane decomposition (RPD) is embedded in a quadtree data structure to obtain a new variable block size image coding algorithm that offers a high performance at a low computational cost. Extensive comparisons to other state-of-the-art image coding algorithms are reported     

The inductance matrix of a multiconductor transmission line inmultiple magnetic media

A simple relationship between the inductance matrix and the auxiliary capacitance matrix is given. For a multiconductor transmission line consisting of N_c conducting cylinders in inhomogeneous media consisting of N_d homogeneous regions with permeabilities μ_i and permittivities ϵ _i, the inductance matrix [L] for the line is obtained by solving the magnetostatic problem of N_c conductors in N_d regions with permeabilities μ _i. The capacitance matrix [C] for the line is obtained by solving the electrostatic problem of N_c conductors in N_d regions with permittivities ϵ _i. It is shown that [L]=μ₀ϵ₀[C^'] ^-1, where [C^'] is the capacitance matrix of an auxiliary electrostatic problem of N_c conductors in N_d regions with relative permittivities set equal to the reciprocals of the relative permeabilities of the magnetostatic problem, i.e. ϵ^' _i/ϵ₀=μ₀/μ_i     

Error-correcting codes for list decoding

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p<1/2 of the bits in an n-bit linear block code cannot prevent reliable communication at a positive rate using list-of- L decoding for sufficiently large n and an L⩽n. The new bounds are stronger for small n , but weaker for fixed e/n in the limit of large n and L than known random coding bounds     

Line search algorithms for adaptive filtering

Line search algorithms for adaptive filtering that choose the convergence parameter so that the updated filter vector minimizes the sum of squared errors on a linear manifold are described. A shift invariant property of the sample covariance matrix is exploited to produce an adaptive filter stochastic line search algorithm for exponentially weighted adaptive equalization requiring 3N+5 multiplications and divisions per iteration. This algorithm is found to have better numerical stability than fast transversal filter algorithms for an application requiring steady-state tracking capability similar to that of least-mean square (LMS) algorithms. The algorithm is shown to have faster initial convergence than the LMS algorithm and a well-known variable step size algorithm having similar computational complexity in an adaptive equalization experiment     

Complete classification of roots to one-dimensional median andrank-order filters

The set of roots to the one-dimensional median filter is completely determined. Let 2N+1 be the filter window width. It has been shown that if a root contains a monotone segment of length N+1, then it must be locally monotone N+2. For roots with no monotone segment of length N+1, it is proved that the set of such roots is finite, and that each such root is periodic. The methods used are constructive, so given N, one can list all possible roots of this type. The results developed for the median filter also apply to rank-order filters     

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     

A stable and distortion-free IIR echo and howling canceler

The authors propose a configuration for an infinite impulse response (IIR) adaptive echo and howling canceller, which consists of a two-channel maximum entropy lattice filter and its inverse filter. The echo is canceled by the adaptive lattice filter, while the signal distortion is eliminated by the inverse lattice. With stability guaranteed without the necessity of testing, the structure costs O (N) multiplications per sampling period. The algorithm can also be greatly simplified for white input cases     

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     

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     

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     

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 low delay 16 kb/s speech coder

A code tree generated by a stochastically populated innovations tree with a backward adaptive gain and backward adaptive synthesis filters is considered. The synthesis configuration uses a cascade of two all-pole filters: a pitch (long time delay) filter followed by a formant (short time delay) filter. Both filters are updated using backward adaptation. The formant predictor is updated using an adaptive lattice algorithm. The multipath (M, L) search algorithm is used to encode the speech. A frequency-weighted error measure is used to reduce the perceptual loudness of the quantization noise. The addition of the pitch filter gives 2-10-dB increase in segSNR (segmental signal-to-noise ratio) in the voiced segments. Subjective testing has shown that the coder attains a subjective quality equivalent to 7 b/sample log-PCM (pulse code modulation) with an encoding delay of eight samples (1 ms with an 8-kHz sampling rate)     

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     

On the Hamming distance properties of group codes

Under certain mild conditions, the minimum Hamming distance D of an (N, K, D) group code C over a non-abelian group G is bounded by D⩽N -2K+2 if K⩽N/2, and is equal to 1 if K>N/2. Consequently, there exists no (N, K, N-K+1) group code C over an non-abelian group G if 1<K<N. Moreover, any normal code C with a non-abelian output space has minimum Hamming distance equal to D=1. These results follow from the fact that non-abelian groups have nontrivial commutator subgroups. Finally, if C is an (N, K, D) group code over an abelian group G that is not elementary abelian, then there exists an (N, K, D) group code over a smaller elementary abelian group G'. Thus, a group code over a general group G cannot have better parameters than a conventional linear code over a field of the same size as G     

Moment preserving quantization [signal processing]

The general solution to the moment-preserving (MP) quantizer problem is presented. It is shown that the moment preserving quantizer is related to the Gauss-Jacobi mechanical quadrature, the output levels of the N-level MP quantizer are the N zeros of an Nth degree orthogonal polynomial associated with the input probability distribution function, and the N-1 thresholds of the MP quantizer are related to the Christoffel numbers through the Chebyshev-Markov-Stieltjes separation theorem. The statistical convergence of the MP quantizer is investigated. MP quantizer tables are presented for the uniform, Gaussian, and Laplacian density functions. The moment-preserving quantizer is shown to be related to block truncation coding     

Recursive algorithms for calculating the scattering from Nstrips or patches

Using the definition of recursive relations for the reflection operator for N strips or patches, two easily programmable recursive algorithms are developed to calculate the electromagnetic scattering by N strips or patches. One algorithm is for arbitrary excitation, and the other is for a fixed excitation. The recursive algorithms require the inversion of small matrices at each stage and hence are suitable for programming on smaller computers. If the N strips or patches are identical and equally spaced, symmetry can be exploited to speed up the algorithms. A program was developed to calculate scattering by N strips, and the result is shown to converge to scattering by a large strip when the N strips are contiguous     

Light-to-input nonlinearities in an R-LED series network

The light-to-current (L-I) and light-to-voltage (L-V) differential nonlinearities in the simple network of a customary LED and an external resistor R in series are analyzed and calculated theoretically and compared with experimental data. Particular emphasis is placed on the influence of the log-arithmetic slope ν of the L-I characteristic and the bias current I upon the ratio of the corresponding nonlinearity parameters. It is thus deduced that, for a given optical power P, over superlinear portions of the L-I curve (ν>1) the L-I linearity is typically better than its corresponding L-V linearity. On the contrary, when the L-I dependence is sublinear (ν<1) the voltage driving scheme may ensure for the R-LED network, or the LED alone, a local L-V response much more linear than the L-I response, provided that appropriate (optimum) I and/or R values are chosen     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible