Implementing matrix inversions in fixed-point hardware

Matrix inversion is an important operation in many state-of-the-art DSP algorithms and implementations, including radar, sonar, and multiple antenna systems for communications. A common component of these algorithms is a beamformer or spatial filter, whose function is to steer (in some optimal fashion) the response of an array of sensors for the reception of signal sources.

When using the least-squares (LS) criterion, the computation of optimum weights is based on the solution of a system of linear equations known as the deterministic normal equation. This is shown in the equation:

R_x w = p

Here, w is a vector of beamformer weights, which can be obtained with inversion of the correlation matrix R_x as shown in the equation

w = R_x^-1 p

From a numerical point of view, the best approach to matrix inversion is to not do it explicitly, whenever possible. Instead, it is better to solve the system of equations using an adequate solution technique.

Traditionally, implementations like this have been done with general-purpose DSP devices using floating-point arithmetic to minimize round-off error. A disadvantage of these implementations, however, is the limited processing power because of the small number of floating-point processing units commonly available per device. An appealing alternative for implementation is to use the Xilinx Virtex-4 FPGA family, which offers large amounts of parallelism. One complication with these silicon fabrics is that they are tailored for fixed-point arithmetic, and implementation in these is inherently challenging because of sensitivity to round-off error.

In this article, we'lI present an efficient methodology that enables the implementation of algorithms involving matrix-inversion operations in hardware with fixed-point arithmetic. This methodology includes three essential steps to follow in the development process:

• Capturing the DSP algorithm description in the MATLAB language
• Definition of the fixed-point parameters directly coupled to the MATLAB algorithm description
• Automated generation of a hardware implementation that is bit-accurate to the fixed-point arithmetic model and that meets area/speed requirements for a particular application

Using this methodology, you can fully exploit the benefits of the processing power offered by implementations in FPGA or ASIC fixed-point hardware.

Beamforming and Matrix Inversion
Figure 1 shows a basic narrowband beamformer with K sensor elements arranged in a uniform linear array (ULA); this also shows a signal source s_q(t) impinging on the array at an angle of incidence q. The K beamformer weights (w₁, w₂, …, w_K) are used to linearly combine the array data observation samples (x₁(n), x₂(n), ..., x_K(n)). These are set to "steer" the response of the array for optimum reception. The output of the beamformer is the scalar y(n).

1.Narrowband beamformer

A generalized sidelobe canceller (GSC) is a special beamformer structure that allows the use of unconstrained optimization methods in the design of the optimum beamformer weights. The structure of the GSC is shown in Figure 2. To find the optimum weights w_a using the LS criterion, the following deterministic normal equation must be solved:

R_x w_a = b

Here, R_x is the correlation matrix of the input to the unconstrained section of the GSC and the vector b is the cross-correlation of the input X_a and the ideal response.

2. Generalized sidelobe canceller (GSC)

One effective technique for the solution of this equation is the recursive least-squares (RLS) approximation with QR decomposition of the input data matrix. This technique finds the solution without explicit inversion of a matrix and avoids constructing the correlation matrix, explicitly reducing the dynamic range requirements of signals involved in the computations.

Figure 3 shows the diagram of an adaptive GSC beamformer that uses a QRD-RLS algorithm for a recursive solution of the normal equation.

3. Adaptive GSC beamformer