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.

Recently a selection of sequential matrix diagonalisation (SMD) algorithms have been introduced which approximate polynomial eigenvalue decomposition of parahermitian matrices. These variants differ only in the search methods that are used to bring energy onto the zero-lag. Here we analyse the search methods in terms of their computational complexities for different sizes of parahermitian matrices which are verified through simulated execution times. Another important factor for these search methods is their ability to transfer energy. Simulations show that the more computationally complex search methods transfer a greater proportion of the off-diagonal energy onto the zero-lag over a selected range of parahermitian matrix sizes. Despite their higher cost per iteration experiments indicate that the more complex search algorithms still converge faster in real time.

This paper introduces a causality constrained sequential matrix diagonalisation (SMD) algorithm, which generates a causal paraunitary transformation that aprroximately diagonalises and spectrally majorises a parahermitian matrix, and can be used to determine a polynomial eigenvalue decomposition. This algorithm builds on a multiple shift technique which speeds up diagonalisation by diagonalisation per iteration step based on a particular search space, which is contrained to permit a maximum number of causal time shifts. The results presented in this paper show the performance in comparison to existing algorithms, in particular an unconstrained multiple shift SMD algorithm, from which our proposed method derives.

A recent class of sequential matrix diagonalisation (SMD) algorithms have been demonstrated to provide a fast converging solution to iteratively approximating the polynomial eigenvalue decomposition of a parahermitian matrix. However, the calculation of an EVD, and the application of a full unitary matrix to every time lag of the parahermitian matrix in the SMD algorithm results in a high numerical cost. In this paper, we replace the EVD with a limited number of Givens rotations forming a cyclic-by-row Jacobi sweep. Simulations indicate that a considerable reduction in computational complexity compared to SMD can be achieved with a negligible sacrifice in diagonalisation performance, such that the benefits in applying the SMD are maintained.