Digital Beam Forming Using RLS-QRD Algorithm

Digital Beam Forming Using RLS-QRD Algorithm

Sumit Verma,

Research Scholar, Lingayas University, Faridabad, Haryana (INDIA).

Arvind Pathak,

Assistant Professor, Lingayas University, Faridabad, Haryana (INDIA).

Digital beam formers are a means for separating a desired signal from interfering signals. This paper describes the GSC technique using the QRD Algorithm and RLS QRD Algorithm for digital Beamforming.

1. INTRODUCTION

   Today the demand of high data rate services is increasing very highly in wireless communication. At the same time the need to support more users per base station is also increasing. The result is that the higher data rates and higher capacities become the pressing need. To increase the capacity the attempts are made to increase the traffic within the fixed bandwidth. But increasing the traffic within the fixed bandwidth creates more interference in the system and the result is degradation of signal quality. The interference can be reduced by using the sectored antenna in place of omnidirectional antenna.

   Figure-1.

   Smart antenna technology can also be used to reduce the interference level. With this technology each users signal is transmitted or received by the base station only in the direction of that particular user. This results in the reduction of interference. A

   smart antenna system consists of an array of antennas that together direct different transmission/reception beams toward each user in the system. This method of transmission and reception is called Beamforming.

   Figure-2: Smart Antenna

   The magnitude and phase of the signal to and from each antenna is adjusted by multiplying each user signal by complex weights. This results in a transmit/receive beam in the desired direction and minimizes the output in other directions.

   If the complex weights are selected from a table of weights, the beam is formed in specific, predetermined direction; this type of Beamforming is called switched Beamforming. In this case the base station basically switches between the different beams based on the received signal strength measurements. On the other hand, if the weights are computed and adaptively updated in real time, the process is called adaptive Beamforming. Through adaptive Beamforming, the base station can form narrower beams towards the desired user and nulls towards interfering users, considerably improving the signal-to-interference- plus-noise ratio.

2. Beamforming is one type of processing used to form beams to simultaneously receive a signal radiating from a specific location and attenuate signals from other locations. Systems designed to receive spatially propagating signals often encounter the presence of interference signals. If the desired signal and interference occupy the same frequency band, unless the signals are uncorrelated, e. g., CDMA signals, the temporal filtering often cannot be used to separate signal from interference. However, the desired and interfering signals usually originate from different spatial locations. This spatial Separation can be exploited to separate signal from interference using a spatial filter at the receiver. Implementing a temporal filter requires processing of data collected over a temporal aperture. Similarly, implementing a spatial filter requires processing of data collected over a spatial aperture. A beamformer is a processor used in conjunction with an array of antennas to provide a versatile form of spatial filtering. The antenna array collects spatial samples of propagating wave fields, which are processed by the Beamformer. Typically a beamformer linearly combines the spatially sampled time series from each antenna to obtain a scalar output time series in the same manner that an FIR filter linearly combines temporally sampled data. There are two types of beamformer, narrowband beamformer, and wideband beamformer. A narrowband beamformer is as shown in Figure 3, the output at time M, y (M), is given by a linear combination of the data at the K.

   K

   1. An adaptive beamformer can separate signals collocated in the frequency band but separated in the spatial domain. To optimize the array the elemental control weights are adjusted until a prescribed objective function is satisfied. For calculating the adaptive weights the choice of adaptive algorithm is very important as the adaptive algorithm determines the speed of convergence and hardware complexity required. To calculate the adaptive weights the various algorithms used are LMS (Least Mean Squares) algorithm, the SMI (Sample Matrix Inversion) technique and RLS (Recursive Least Squares) algorithm.

      W x

      y(M )

      * (M )

      i i

      i 1

      — Eq(1)

      Where * denotes complex conjugate. Since we are now using the complex envelope representation of

      the received signal, both Wi

      complex.

      and

      xi (M ) are

      Figure 4: Adaptive Beamforming system

3. There are various ways for SMI like QRD decomposition, SVD, LU decomposition, RLS QRD Decomposition.

   1. QR matrix decomposition (QRD), sometimes referred to as orthogonal matrix triangularization, is the decomposition of a matrix (A) into an orthogonal matrix (Q) and an upper triangular matrix (R). QRD is useful for solving least squares problems and simultaneous equations.

      Consider the following equation:

      AX= b ——-eq(2)

      Where:

      A, X and b are matrices

      A is of order N × N

      X and b are column vectors of order N × 1

      A and b are known; X is unknown. The objective is to determine the N different unknowns in the X matrix.

      Performing QRD (substituting QR for A) results in: (QR)X = b ——- eq(3)

      Moving Q to the right hand side of the equation gives:

      RX = Q-1 b ——- eq(4)

      Q is an orthogonal (unitary) matrix, thus Q-1 is equal to the complex Conjugate transpose of Q. This operation requires minimal resources to Perform in hardware.

      So:

      RY = b' ——- eq (5)

      Where:

      b' = Q-1 b. ——- eq (6)

      To find the Q and R the method used is given Rotation method.

   2. Given Rotation

      Given rotation are orthogonal plane rotation used to eliminate the elements within a matrix for [aij] =o when i>j.This method is known as QR decomposition method, by using this the matrix A can be reduced to upper triangular matrix R(n) and Orthogonal matrix Q(n).

      A (n) =R (n) Q (n) ——- eq (7)

      The A (n) matrix is pre-multiplied by rotation matrices one element at a time. The rotation parameters are calculated so that the sub-diagonal elements of the first column are zeroed. Then the next columns sub-diagonal elements are zeroed and so forth, until an equivalent upper triangular matrix is formed. The following example illustrate the given rotation method, by the following matrix.

      This matrix is transformed into pseudo-triangular matrix by eliminating the element; a21.This is achieved by multiplying the matrix by the rotation of matrix.

      Thus:

      * =

      To eliminate a21

      -a11sin + a21cos =0

      Therefore from trigonometry Sin = a21/(a112+a212 )1/2

      Cos = a11/ (a112+a212 )1/2

      The same procedure is repeated till matrix get converted into upper triangular matrix .The orthogonal matrix is got by multiplying transpose of all rotation matrices used to convert the given matrix into the upper triangular matrix. Hence any matrix can be expressed as the product of upper triangular matrix and the orthogonal matrix by using the given rotation method.

4. RLS Solved by QRD

   decomposition is an extension o this QR factorization, which enables the matrix to be triangularized again when new data enter the data matrix, without having to compute the triangularization from the original square matrix format. In other words, it updates the old triangular matrix when new data are entered. The data matrix X(n) and the measurement vector y(n) at time n can be represented in a recursive manner by the previous resulting matrix and vector and the new data, such that:

   The P*N dimensional data matrix, X(n) is decomposed into an N*N dimensional upper triangular matrix R(n) ,through the application of

   X (n)

   (n)X(n-1)

   T

   X (n)

   and

   X (n)

   (n)y(n-1)

   y(n)

   unitary matrix ,Q(n),such that:

   Where XT(n) and y(n) form the append Row at time

   Q(n) * X (n)

   R(n) 0

   n. A square root of the Algorithm is achieved as follows.

   —- eq(8)

   Where 0 is the zero matrix resulting if N<p. Since Q

   (n) is a unitary matrix, then:

   .5R(n-1)

   QT

   X T (n)

   WLS

   (n)

   QT (n)

   .5U(n-1)

   y(n)

   QT (n)e(n)

   –eq(12)

   (n)=

   T

   X (n) X (n)

   X T (n)QT (n)Q(n) X (n)

   RT (n)R(n)

   Where = .5

   This is computed to give

   — eq(9)

   R(n)

   0

   WLS

   (n)

   U (n)

   (n)

   The triangular matrix, R (n) is the cholesky factor of

   the data correlation matrix. Since Q(n) is unitary then the original system equation may be expressed as:

   —- eq(10)

   Where QT(n) X(n) =R(n) and QT(n)y(n)=u(n)

   The least square vector square weight vector

   WLS (n) must satisfy the equation

   R (n) WLS (n) + u (n) = 0 —-eq (11)

   As R(n) is a upper triangular matrix, the weights can be solved by using Back substitution . QR

   Where e(n)= (n) (n)

   Where (n) is the product of cosines generated in course of eliminating X T (n)

   Figure 5. High-level dependence graph for the QR- RLS solution

5. A uniform linear array (ULA) with M sensors has been considered between each element /2 spacing is given, where is the smallest signal wavelength of the signal with specified gain/null arrangements. If the spacing between the elements is increased beyond /2 than it will result in large side lobes in radiation pattern .Assume that K narrowband and far field signals are impinging on the array from direction angles i =1, 2, 3..K

   .At the mth array sensor the signal received can be expressed as :

   K

   To find the optimum weights Wa using LS criteria the following deterministic equation must be solved.

   RX Wa=b.Where RX is the correlation matrix of the input x(t) to the unconstrained section of GSC and

   si (t )am ( i )

   i 1

   m 1, 2, 3……M

   nm (t )

   —eq(13)

   the vector b is the cross-correlation of input x(t) and

   the ideal response.

   To find the optimum weights Wa using LS criteria the following deterministic equation must be solved.

   Where

   am (

   i ) =exp ( j2

   dm sin(

   i ) /

   ) and dm is

   the distance between the first and mth array sensor. Si (t) is the ith signal complex waveform and nm(t) is the spatially white noise .The data received by the array is given as x(t)=As(t)+n(t).

   RX Wa=b.Where RX is the correlation matrix of the

   input x(t) to the unconstrained section of GSC and the vector b is the cross-correlation of input x(t) and the ideal response.

   Where A=[a(

   1 )a(

   2 )……..a(

   K )] .The signal source

   T

   vector is given as S(t)= [s1 (t)s2 (t)……….sK (t)] and

   the noise vector n(t)= [n (t)n (t)……….n (t)]T .

   1 2 M

   q

   In GSC structure the Blocking Matrix (B) function is to remove the desired signal from the received array data. d(n) is given as w Hx(t).

   The quiescent weight vector wq is utilized to realize the constrained weight subspace and is chosen such

   that the output signal power

   E[d (t)2 ] is minimized

   Figure 7. Adaptive GSC Beamformer

   subject to a set of L linear constraints.

   The above equation can be solved without any need of matrix inversion by using the RLS QRD ALGORITHM.

The GSC beamformer model has been designed for performing the simulations .The feature of the design includes.

• A uniform linear array of four sensors.

• An input signal impinging at an angle of 0 degree.

• A narrow band interfering signal at an angle of 10 degree.

• Uncorrelated white noise at a level of – 20 db.

Figure 8: Input Signal

Figure 9: Broad-side array output & its FFT using QRD

Figure 10: Beamformer output & its FFT using QRD

Figure 11: Broadside array output & its FFT using RLS QRD

Figure 12: Beamformer output & its FFT using RLS QRD

Figure 13: Beamformer output & its FFT after passing output of RLS QRD from Low pass filter.

An efficient beamforming technique has been proposed and the system level simulation is performed. The overall system was simulated for four sensors. The results are calculated by using QRD, RLS-QRD and than after applying the low pass

filter on RLS – QRD .The result shows that the error has been reduced in the beamformer output when we used the RLS QRD ALGORITHM and it has been further reduced by applying the low pass filter to the results of the RLS-QRD.

REFERENCES

1. Reeta Gaokar, Dr. Alice Cheeran, Performance analysis of beamforming algorithms, IJECT, Vol. 2 Issue1, March 2011, pp. 43-48.

2. Irturk, Benson Automatic generation of decomposition based matrix inversion architectures ICECE 2008, pp. 373-376.

3. Yi Zhao, Raviraj Adve, and Teng Joon Lim Beamforming with limited feedback in Amplify

   and- cooperative networks IEEE transactions on wireless communication, Vol. 7, NO. 12, December 2008, pp. 5145-5149.

4. M.Shoaib, S.Werner, J.A.Apolinario Jr. , .I.Laakso Equivalent Output-Filtering Using Fast QRD-RLS Algorithm for Burst-Type Training Applications ICAS 2006 ,pp. 133-136.

5. Geert Rombouts and Marc Moonen., Fast QRD- Lattice Based Uncontrained optimal filtering for acoustic noise reduction, IEEE Transaction on speech and audio processing, vol.13, NO. 6, Nov.2005, pp. 1130-1143.

6. Marjan Karkooti, Joseph R.Cavallaro FPGA Implementation of Matrix inversion using QRD- RLS Algorithm IEEE,2005,pp. 1625-1629.

7. Ju-Hong-Lee , Ching-Lun Cho , GSC-based adaptive beamforming with multiple-beam Constraints under random array position errors, Elsevier signal processing 84 2004, pp 341-350.

8. George-Othon Glentis Implementation of adaptive generalized side lobe cancellers using efficient complex valued arithmetic Int. J. Appl. Math. Comput. Sci., 2003, Vol. 13, No. 4, pp.549- 566.

9. B.R.Breed , Member, IEEE, and Jeff Strauss, Member,IEEE A Short proof of the equivalence of LCMV and GSC beamforming IEEE Signal processing letters , Vol. 9, NO. 6 , June 2002, pp. 168-169.

10. Jun Ma ,Keshab K.parhi and Ed F.Deprettere Annihilation- Recording Look-Ahead Pipelined CORDIC-Based RLS Adaptive Filters and Their Application to Adaptive Beamforming IEEE transaction on signal processing, vol. 48, NO. 8, August 2000, pp. 2414-2431.

11. Z.Liu, J.V Mccanny Implementation of adaptive beamforming based on QR decomposition for CDMA IEEE International conference on signals, systems, and computers, 1999.

12. G.Lightbody, R.L.Walke, R.Woods, J.Mccanny, Novel mapping of a linear QR architecture Proc ICASSP , Vol 4 ,pp. 1933-6, 1999.

13. Harteneck, M.; Stewart,R.W.; Adaptive IIR filtering using QR matrix decomposition Proceeding on signal processing IEEE Transactions, Vol. 46, sept 1998, pp. 2562-2565.

14. Jablon Adaptive beamforming with generalized side lobe canceller in the presence of array imperfections, IEEE transaction, Vol.34, Issue 8, Aug 1986, pp.1996-1012./p>