Search

In this memorandum we show how the method of QR decomposition (QRD) may be applied to the adaptive filtering and beamforming problems. QR decomposition is a form of orthogonal triangularisation which is particularly useful in least squares computations and forms the basis of some very stable numerical algorithms. When applied to the problem of narrowband adaptive beamforming where the data matrix, in general, has no special structure, this technique leads to an architecture which can carry out the required computations in parallel using a triangular array of relatively simple processing elements. The problem of an adaptive time series filter is also considered. Here the data vectors exhibit a simple time-shift invariance and the corresponding data matrix is of Toeplitz structure. In this case, the triangular processor array is known to be very inefficient. Instead, it is shown how the Toeplitz structure may be used to reduce the computational complexity of the QR decomposition technique. The resulting orthogonal least squares lattice and 'fast Kalman' algorithms may be implemented using far fewer processing elements. These 'fast' QRD algorithms are very similar to the more conventional ones but, in general, are found to have superior numerical properties. A narrow-band beamformer is essentially a spatial filter and the corresponding adaptive beam-forming problem may be formulated in terms of least squares minimisation. A fundamental structure in least squares minimisation problems is an adaptive linear combiner. This may be applied directly to the problem of narrowband adaptive beamforming, resulting in the so-called generalised sidelobe canceller.

We derive, from first principles, the least squares lattice algorithm for adaptive filtering based on the QR decomposition (QRD). In common with other lattice algorithms for adaptive filtering, this algorithm only requires O(p) operations for the solution of a p-th order problem. The algorithm has as its root the QRD-based recursive least squares minimisation algorithm and hence is expected to have superior numerical properties when compared with other fast algorithms. This algorithm contains within the QRD-based algorithm for solving the least squares linear prediction problem. These algorithms are presented in two forms: one that involves taking square-roots and one that does not. Some computer simulations of a channel equaliser, using finite-precision arithmetic, are presented in which the lattice algorithms are compared to the more established triangular systolic array ones. The relationship between the QRD- based lattice algorithms and other least square lattice algorithms is briefly discussed. Various extensions to this work are discussed including the multi- channel QRD-based adaptive filtering algorithm that can be used for a wide-band beamforming. Keywords: Great Britain, Digital signal processing.

It is shown that a non-separate arithmetic code that preserves both addition and multiplication must be an AN code where the generator A is an idempotent element of the ring being used. An idempotent element is one that satisfies the equation x squared = x. Given this type of code, its ability to detect errors in arithmetic expressions is explored and shown to be poor, due to error masking in multipliers. The constraints placed on a non-separate multiplication-preserving arithmetic code that avoids such problems are discussed. The simplest code satisfying these conditions turns out to be an AN+B code where both A and B are idempotent elements. Conditions for the existence of this type of code are given along with a list of examples. The fault tolerance provided by these codes is then considered for a specific example. This paper considers an approach and addresses the problem of classification of error- detecting codes than can protect large arithmetic expressions involving addition and multiplication, or more correctly circuits that implement such expression.

A reduction in the minimum attainable feature size in integrated circuits has lead to the possibility of more and more complex circuits being built on a single chip (VLSI). This technological advance brings with it the need to make these circuits fault tolerant: to increase yield and reliability and to reduce testing times. This Memorandum briefly reviews current techniques for designing fault tolerant circuits before concentrating on a new, high-level fault tolerance technique: algorithmic fault tolerance. The concept of algorithmic fault tolerance is explained and various techniques are reviewed with regard to their suitability for providing fault tolerance for signal processing algorithms. Suggestions are made for the direction for further research.