Regularized fast recursive least squares algorithms for adaptivefiltering

Fast recursive least squares (FRLS) algorithms are developed by using factorization techniques which represent an alternative way to the geometrical projections approach or the matrix-partitioning-based derivations. The estimation problem is formulated within a regularization approach, and priors are used to achieve a regularized solution which presents better numerical stability properties than the conventional least squares one. The numerical complexity of the presented algorithms is explicitly related to the displacement rank of the a priori covariance matrix of the solution. It then varies between O(5m) and that of the slow RLS algorithms to update the Kalman gain vector, m being the order of the solution. An important advantage of the algorithms is that they admit a unified formulation such that the same equations may equally treat the prewindowed and the covariance cases independently from the used priors. The difference lies only in the involved numerical complexity, which is modified through a change of the dimensions of the intervening variables. Simulation results are given to illustrate the performances of these algorithms     

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     

A generalization of consecutive-k-out-of-n:Fsystems

A linear (m, n)-lattice system consists of m ·n elements arranged like the elements of a (m ,n)-matrix, i.e. each of the m rows includes m elements, and each of the n columns includes m elements. A circular (m,n)-lattice system consists of m circles (centered at the same point) and n rays. The intersections of the circle and the rays represent the elements, i.e. each of the circles includes n elements and each of the rays has m elements. A (linear or circular) (m, n)-lattice system is a (linear or circular) connected-X-out-of-(m,n):F lattice system if it fails whenever at least one subset of connected failed components occurs which includes failed components connected in the meaning of connected-X. The paper presents some practical examples and the reliability formulas of simple systems using results of consecutive-k-out-of-n:F systems     

Systolic array designs for Kalman filtering

Systolic Kalman filter (SKF) designs based on a triangular array (triarray) configuration are presented. A least squares formulation, which is an expanded matrix representation of the state space iteration, is adopted to develop an efficient iterative QR triangularization and consecutive data prewhitening formulations. This formulation has advantages in both numerical accuracy and processor utilization efficiency. Moreover, it leads naturally to pipelined architectures such as systolic or wavefront arrays. For an n state and m measurement dynamic system, the SKF triarray design uses n(n+3)/2 processors and requires only 4n+m timesteps to complete one iteration of prewhitened Kalman filtering system. This means a speedup factor of approximately n²/4 when compared with a sequential processor. Also proposed for the colored noise case are data prewhitening triarrays which offer compatible speedup performance for the preprocessing stage. Based on a comparison of several competing alternatives, the proposed array processor may be considered a most efficient systolic or wavefront design for Kalman filtering     

The role of integer matrices in multidimensional multirate systems

Various theoretical issues in multidimensional (m-D) multirate signal processing are formulated and solved. In the problems considered, the decimation matrix and the expansion matrix are nondiagonal, so that extensions of 1-D results are nontrivial. The m -D polyphase implementation technique for rational sampling rate alterations, the perfect reconstruction properties for the m-D delay-chain systems, and the periodicity matrices of decimated m-D signals (both deterministic and statistical) are treated. The discussions are based on several key properties of integer matrices, including greatest common divisors and least common multiples. These properties are reviewed     

1/f noise in MODFETs at low drain bias

The 1/f noise in normally-on MODFETs biased at low drain voltages is investigated. The experimentally observed relative noise in the drain current S_I/I² versus the effective gate voltage V_G=V_GS-V_off shows three regions which are explained. The observed dependencies are S_I/I²∝V_G ^m with the exponents m=-1, -3, 0 with increasing values of V_G. The model explains m =-1 as the region where the resistance and the 1/f noise stem from the 2-D electron gas under the gate electrode; the region with m=0 at large V_G or V_GS≅0 is due to the dominant contribution of the series resistance. In the region at intermediate V_G , m=-3, the 1/f noise stems from the channel under the gate electrode, and the drain-source resistance is already dominated by the series resistance     

On the number of memories that can be perfectly stored in a neuralnet with Hebb weights

Let {w_ij} be the weights of the connections of a neural network with n nodes, calculated from m data vectors v¹, ···, v^m in {1,-1}ⁿ, according to the Hebb rule. The author proves that if m is not too large relative to n and the v^k are random, then the w_ij constitute, with high probability, a perfect representation of the v^k in the sense that the v ^k are completely determined by the w_ij up to their sign. The conditions under which this is established turn out to be less restrictive than those under which it has been shown that the v^k can actually be recovered by letting the network evolve until equilibrium is attained. In the specific case where the entries of the v^k are independent and equal to 1 or -1 with probability 1/2, the condition on m is that m should not exceed n/0.7 log n     

Fast decoding of codes from algebraic plane curves

Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d*/2-m² /8+m/4-9/8 errors, where d* is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O(n^7/3 ), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O(n²), and the same complexity can be obtained in the general case if only d*/2-m²/2 errors are corrected     

Multistage sigma-delta modulation

A theoretical basis is provided for multistage sigma-delta modulation (MSM), which is a cascade realization of several single-loop sigma-delta modulators with a linear combinatorial network. Equations are derived describing the output and the quantization noise of MSM for an arbitrary input signal, and the noise-shaping characteristic of MSM is investigated. The spectral characteristics of an m-stage sigma-delta modulator with both DC and sinusoidal inputs are developed. For both types of inputs the binary quantizer noise of the mth (m⩾3) quantizer, which appears at the output as an m th order difference, is asymptotically white, uniformly distributed, and uncorrelated with the input level. It is also found that for an m-stage sigma-delta quantizer with either an ideal low-pass filter or a sinc^m+1 filter decoder, the average quantization noise of the system is inversely proportional to the (2m+1)th power of the oversampling ratio. This implies that the high-order systems are favourable in terms of the trade-off between the quantization noise and oversampling ratio. Simulation results are presented to support the theoretical analysis     

A fast topology maintenance algorithm for high-bandwidth networks

A fast time-driven algorithm for topology maintenance in high-speed networks is presented. The algorithm uses only four time units for each broadcast by each computer. The best previous algorithm required O(log m) time units for each broadcast by each computer, where m is the number of currently operational computers in the network. In addition to its speed, the presented algorithm makes several significant contributions. I. Cidon et al. (1988) have shown that Ω(log m) time units are necessary for time-driven topology maintenance algorithms of high-speed networks that do not allow a packet to traverse the same edge in both directions. The proposed algorithm shows that this lower bound does not hold for networks that do allow a packet to traverse the same edge in both directions. The O(log m) algorithm assumed that it takes each computer at most one time unit to simultaneously broadcast messages to all neighbors of the computer. In contrast, a node in the proposed algorithm can send at most, one message per time unit. As in the O(log m) algorithm, the algorithm requires O (D) broadcasts per node before all nodes know the correct topology of the network, where D is the diameter of the currently operational portion of the network     

A linear bound for sliding-block decoder window size

The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n -ary data into any constrained system Σ with capacity at least log(n) presented by a graph G with memory m and anticipation a. Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t:t and with window length m+a+2t, where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Σ with finite memory must grow at least linearly with the number of states of the graph G presenting Σ     

Some results on the covering radii of Reed-Muller codes

Let R(r,m) be the rth-order Reed-Muller code of length 2^m and let ρ(r,m ) be its covering radius. R(2,7), R(2,8), R (3,7), and R(4,8) are among those smallest Reed-Muller codes whose covering radii are not known. New bounds for the covering radii of these four codes are obtained. The results are ρ(2,7)⩾40, ρ(2,8)⩾84, 20⩽ρ(3,7)⩽23, and ρ(4,8)⩾22. Noncomputer proofs for the known results that ρ(2,6)=18 and that R(1,5) is normal are given     

Reliability polynomial for a ring network

A mathematical model is developed for the reliability of a system made up of m unreliable nodes arranged in a ring. The model can be used to calculate the reliability of single-ring networks in which the network recovery mechanism depends on bypassing failed stations, but link signal power margins are inadequate to overcome losses due to more than n bypass switches in series. Computational complexity is 0(n²m+nm²/2) in time, and 0(m²/2) in memory requirements     

Orthogonality of binary codes derived from Reed-Solomon codes

The author provides a simple method for determining the orthogonality of binary codes derived from Reed-Solomon codes and other cyclic codes of length 2^m-1 over GF(2^m) for m bits. Depending on the spectra of the codes, it is sufficient to test a small number of single-frequency pairs for orthogonality, and a pair of bases may be tested in each case simply by summing the appropriate powers of elements of the dual bases. This simple test can be used to find self-orthogonal codes. For even values of m, the author presents a technique that can be used to choose a basis that produces a self-orthogonal, doubly-even code in certain cases, particularly when m is highly composite. If m is a power of 2, this technique can be used to find self-dual bases for GF(2 ^m). Although the primary emphasis is on testing for self orthogonality, the fundamental theorems presented apply also to the orthogonality of two different codes     

A geometric approach to root finding in GT(qm)

The problem of finding roots in F of polynomials in F [x] for F=GF(q^m), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available     

On the duality between fast QR methods and lattice methods in leastsquares adaptive filtering

The authors show that fast QR methods and lattice methods in least squares adaptive filtering are duals and follow from identical geometric principles. Whereas the lattice methods compute the residuals of a projection operation via the forward and backward prediction errors, the QR methods compute instead the weights used in the projections. Within this framework, the parameter identification problem is solved using fast QR methods by showing that the reflection coefficients and tap parameters of a least squares lattice filter operating in the joint process mode are immediately available as internal variables in the fast QR algorithms. This parameter set can be readily exploited in system identification, signal analysis, and linear predictive coding, for example. The relations derived also lead to a fast least squares algorithm of minimal complexity that is a hybrid between a QR and a lattice algorithm. The algorithm combines the order recursive properties of the lattice approach with the robust numerical behavior of the QR approach     

Bounds for reliability of consecutivek-within-m-out-of-n:F systems

Upper and lower bounds for the reliability of a (linear or circular) consecutive k-within-m-out-of-n:F system with unequal component-failure probabilities are provided. Numerical calculations indicate that, for systems with components of good enough reliability, these bounds quite adequately estimate system reliability. The estimate is easy to calculate, having computational complexity O(m²×n). For identically distributed components, a Weibull limit theorem for system time-to-failure is proved     

Evaluation of the quantization error in denominator-separable 2-Drecursive filters

The evaluation of the quantization error in two-dimensional (2-D) digital filters involves the computation of the infinite square sum J=Σ^∞_m=φΣ ^∞_n=φy² (m, n). A simple method is presented for evaluating J based on partial fraction expansion and using the residue method provided the Z-transform Y(Z₁, Z₂) of the sequence y(m, n) having quadrant support is a causal bounded input, bounded output (BIBO) stable denominator-separable rational function. The value of J is expressed as a sum of simple integrals which can easily be evaluated. The simple integrals are tabulated for ready reference. The proposed method is suitable for analytical as well as numerical computation and can easily be programmed     

Analytical methods to calculate the performance of a cellularmobile radio communication system with hybrid channel assignment

Two approximate techniques are presented to evaluate the performance of large-scale mobile radio systems using a hybrid channel assignment scheme and a cellular structure, The two approximate analyses give the steady-state probability distributions of the system which are used to obtain expressions for the blocking probabilities. In the first method, the blocking probability is obtained by finding the interarrival time probability distribution function of one composite interrupted Poisson process (IPP) stream consisting of several IPP streams overflowing from the cell of interest and its cochannel interference cells. The second method is proposed to solve the blocking probability of the system by regarding each call as a GI/M/m (m) model. Analytical results are compared with simulation results, and good agreement is observed for both channel assignments (hybrid and fixed). The methods presented are applicable to the design of hybrid channel assignment schemes and dynamic channel assignment schemes     

Short codes with a given covering radius

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m⩽12 and r⩽12