[attachment=3708]
QRD “ RLS ADAPTIVE EQUALIZER AND CORDIC
ALGORITHM FOR CDMA SYSTEMS

---

Presented By:
K.L.Pragathi (IV ECE) Grace Shilpa (IV ECE)
SKTM College of Engineering Kodair, Mahaboob Nagar - Dist

---

ABSTRACT:
To combat the performance deterioration brought by the time-varying propagation conditions and multiuser / intersymbol interference in the CDMA system, this paper proposes a novel means of adaptive equalizer based on QR Decomposition-based Recursive LeastSquare (QRD-RLS) algorithm to replace the conventional RAKE receiver. The RLS algorithm has been exploited due to its relatively superior convergence property in comparison with other adaptive filtering algorithms. However, the high quality brings about high computational complexity as well. With regards to such a side-e_ect , the CORDIC algorithm has been exploited and it plays essential role in the hardware implementation of the new approach. The proposed RLS structure is simulated extensively under different channel parameters and performance is compared against additional RAKE structure.
Keywords : Code Division Multiple Access (CDMA) ; adaptive equalizer, recursive least-squares ; QR-decomposition ; Coordinate Rotations Digital Computer (CORDIC) algorithms.

INTRODUCTION
The modern wireless communication systems based on the Code Division Multiple Access(CDMA) technology are limited in capacity and performance by three major factors: multipath fading, Multiple Access Interference (MAI) and Interference (ISI). The commonly proposed schemes to overcome these impairments are the use of the transmitter power control, the error control coding and the diversity technique which is typically represented by the conventional RAKE receiver. However, the performance of the RAKE receiver has been substantially degraded in the presence of a rapid time-varying channel, which is the usual case for a practical mobile radio system. There are two kinds of interference associated with a RAKE receiver for a CDMA downlink: one is the Inter-Finger Interference (IFI); the other is the Multiple Access Interference (MAI), both of which are due to the frequency selectivity of the wireless channel. IFI and limit the CDMA system capacity when RAKE receivers are applied.
In order to improve the performance of CDMA downlink transmission, receivers that provide for the suppression of IFI and MAI are needed. When the delay spread is large, the frequency selective fading channel may be transformed into a frequency non-selective fading channel trough channel equalization. Therefore, the equalizat5ion receiver based on adaptive algorithms seems to be an effective M. Zhong, A. S. Madhukumar &F. Chin CDMA receiver for the recovering of the transmitted data through the restoration of the orthogonality of the spreading codes, thus suppressing both IFI and MAI. Adaptive algorithms based on Least-Mean-Square (LMS) and Recursive Least-Squares (RLS) calculate the time-varying channel, iteratively and they have the advantage of shorter processing delay with relatively short bu_er size for data storage. The RLS algorithm takes into account all the information that extend back to the initialization stage and updates the estimation of the tap-weight vector upon the arrival of new data. Thus it is preferred over the LMS algorithm due to its superior convergence properties [Eweda, 1994]. Moreover, if the adaptive algorithm diverges, or
An efficient parallel triangular systolic processor array realization of the QR Decompositionbased RLS (QRD-RLS) algorithm using Givens rotations was introduced in [Gentleman & Kung, 1981]. The systolic array is controlled by a uniform cyclic clock and it executes plane rotations to annihilate certain elements of the input signal matrix. Commonly the computation of rotation angles requires either square roots and divisions or trigonometric functions, which is time-consuming and thus not applicable for hardware implementation. To solve the problem, the famous CORDIC (Coordinate Rotation Digital Computer) algorithm [Volder, 1959] has been introduced to perform the two-dimension vector rotation instead of the conventional Givens rotations. The main idea underelying this algorithm is to do phase shifting through a series of microrotations using a fixed set of elementary rotation angles. Through a proper choice of the lementary angles all computations can be implemented efficiently in VLSI using a sequence of shift and
Add/subtract operations. Generally, a look-up-table holding the elementary rotation angles is set up in advance to perform the phase shifting replacing the trigonometric functions exploited in the Givens rotations.
This paper discusses the design and development of a CORDIC-based QRD-RLS channel equalizer in a CDMA system and compares its performance with the conventional RAKE structure. A simplified diagram of the CDMA system is diagram of the CDMA system is illustrated in Fig. 1. The traditional RAKE structure is highlighted by a dash line rectangle. Stress has been cast on the receiveing part which consisted of the base band filter, the multipath dispreading, the channel estimation and the RAKE receiver. Figure 2 provides the structure of the new QRDRLS- based adaptive equalizer, which is proposed to replace the highlighted part in the previous figure. More details of the proposed system will be discussed in the following sections.
This paper is organized as follows: Section 2 introduces the mathematical principles of the QRD-RLS algorithm and discusses its limitation due to the high computational complexity. QRD-RLS Adaptive Equalizer and Its CORDIC-Based Implementation for CDMA Systems 27 Section 3 introduces the CORDIC algorithm.

2. QRD-RLS algorithm
The computational complexity has to be reduced considerably in order to increase the practical applicability of the RLS algorithms in a high-speed CDMA receiver. For fast and numerically robust RLS filtering, the method of choice is based upon orthogonal triangularization of the input data matrix using QR decomposition [Haykin, 1996]. The following subsections briey reviews the basics of the QR Decomposition-based Recursive Least Squares (QRD-RLS) method for channel equalization.

2.1 Least Mean Square algorithm
Since the RLS algorithm is merely an extension of the fundamental LMS (Least Mean Square) algorithm, this elementary scheme is discussed beforehand. The basic idea underlying the LMS can be described in two processes :
(1) Calculate the output of a transversal_lter produced by a set of tap inputs and then try to obtain the error estimation by comparing the output with the desired response.
(2) Find a method to minimize this error by adjusting the tap weights of the transversal filter so that it can approach the desired response at the output.
The notations are listed below before the complicated mathematical deducations are presented.
d(i) : the desired response, here in the system, d(i) stands for the pilot bits have been transmitted.
w(n): the tap-weight vector at time n, defined by
w(n) = [w0(n), w1(n), . . . , wM-1(n)]T.
u(i) : the pilot signal vector received at time I, defined by
u(i) = [u(i), u(i-1), . . . , u(I-M+1)]T.
1n-1 : the forgetting factor which is used to ensure that the effect brought by past pilot signals is reduced or forgotten.
Assuming the weight vector w(n) is constant during the observation interval 1 = i n, the cost function can be expressed as :
n
E = Xn-1 d(i)-wH(n)u(i)2. (1) i=1
The goal is to find the optimum value of the tapweight vector, w(n) for which the cost function of Eq. (1) attains its minimum value.
First, a toeplitz matrix is constructed by the received pilot signals as given in Eq. (2).
u(1) u(2) u(u)
0 u(1) u(n-1)
AH(n)=

0 0 0 u(n-M+1) (2)
Additionally, the desired data vector or the pilot bits vector can be expressed as follows:
DH(n) = [d(1), d(2)d(n)]. (3)
Given the exponential weighting matrix which consist of the forgetting factor 1.
Xn-1
Xn-2
A =
(4)
1
the cost function can be rewritten in a matrix format as follows
= ¦A(n)d(n) “ A(n)A(n)w(n)¦2 (5)
where the symbol ¦ .¦2 represents the squared Euclidean norm.
In order to obtain the optimum w(n) from Eq. (5), the QR-decomposition method has been applied and it will be discussed in the following subsection.

2.2. QR-decomposition
Since multiplying by a unitary matrix does not change the norm of a matrix, we introduce a n x n sized unitary matrix Q(n) and apply it to Eq. (5) as follows.
= ¦Q(n)A(n)d(n) “ Q(n)A(n)A(n)w(n)¦2 (6)
(1) (2)
Investigating the two parts of Eq. (6) respectively leads to:
Part (1): By separating the Qn x n(n) into two fragments:
FM x n(n)
S(n “ M) x n(n)
Where the subscript denotes the size of the matrix, this part is expressed as :

F(n)A(n)d(n)
S(n)A(n)d(n)
PM x1(n)
V(n-M x 1(n) (7)
Part (2) : Through a proper choice of the unitary matrix Q(n), the weighted pilot signal matrix can be transformed into an upper-triangular matrix as given below:
RM x M(n)
O(n-M) x M (8)
Where is a null matrix and R(n) is an upper-triangular matrix. According to Eq. (8), the matrix A(n)A(n) can be be expressed as a product of the unitary matrix QH(n) and the upper-triangular matrix [R(n), O]T. Such a factorization is referred to as the QR-decomposition [Haykin, 1996].

From Eq. (8), the second part of Eq. (6) can be re-expressed as follows :
R(n)
O
R(n)wM x 1(n)
O(n-M) x 1 (9)
Applying Eqs. (7) and (9) into (6) :
P(n) R(n)w(n) 2
V(n) O
P(n) “ R(n)w(n)
V(n) (10)
It is easy to observe from Eq. (10) that the cost function eapproaches its minimum value ¦v)n)¦2 when the equation
R(n)w(n) = P(n) (11)
is satisfied.
This the desired weight vector can be obtained from Eq. (11) simply by multiplying the inversion of R(n) on both sides.
W(n) = R(n)-1P(n). (12)
The QR-decomposition can be realized using Givens. Householder or Gram-Schmidt transformations [Golub & Van Loan, 1989], For the current system on a sample-by-sample basis. The Givens rotations is preferred and is discussed in next subsection.

2.1 Givens rotations
Please rotation of vectors has been carried out comprehensively for many algorithms with respect to matrix transformational. Consider a 2-by-2 orthogonal matrix:
Cos sin
-sin cos (13)
The multiplication of a 2-by-1 data vector by J amounts to a plane rotation by of the vector. Such transformation is referred to as the Givens rotations [Haykin, 1996].
Consider a complex matrix YnxM (where n>M) that has a format as follows:
R
Y = O
A (14)
where R is an upper-triangular matrix, O is a null matrix and ** is a non-zero vector.
The function and destination of the Given rotations is to annihilate the last row of the above matrix by left-multiplying it with a series of unitary matrices. These kinds of matrices have the following format :
1 l
1

cos 0 0 sin* k
0 1 0 0
O
0 0 1 0
-sin 0 0 cos n
l k n (15)

With successive matrices Jk(n) the last row of matrix Y(n) will be nullified :
R
J(M(n)J2(n)J1(n)Y(n) = O (16)
OT
The value of the angle in Eq. (15) is determined by the element in matrix Y(n). The determination of this angle is referred to as the vectoring mode for the CORDIC algorithm. Which will be further discussed is Sec.3

2.1 Recursive Least Squares algorithm
As mentioned previously, the so-called Recursive Least-Squares (RLS) algorithm is an extended version of the LMS approach. Upon the entrance of the newly received pilot bits, the equalizer would then perform adaptively to adjust its tap weights. Form the algorithmic point of view, it allows the real-time calculation of the updated weight during every iteration. This iterating process contributes to the phrase recursive in the name of the new method.
The illustration would be continued on the basis of Eq. (6) which consists of two parts. With regards to the second part, assuming that at time n “ 1, the following equation is already satisfied:
R(n-1)
O (17)
At time n, supposing a new signal vector enters the system as denoted by u(n), the updated version of the signal matrix can be redefined as A¬l(n):
A(n-1)
uH(n) (18)
We now define a new unitary matrix
Q(n-1) O
O 1 (19)
Having this it is easy to obtain the updated forgetting factor matrix at time n:
A(n-1) O
O 1 (20)
By applying Eq. (18) through Eq. (20) into Eq. (17), we get:
R(n “ 1)
Ql(n “ 1) A(n)A(n) = O
UH(n) (21)
Combining Eq. (16) with Eq. (21) will lead to :
R(n)
JM(n)J2(n)J1(n)Ql(n-1)A(n)A(n) = O
oT (22)
By comparing Eqs. (22) and (9), it is obvious that we get:
Q(n) = JM(n) = JM(n) J2(n) J1(n)Ql(n-1). (23)
By observing Eqs. (22) and (23), evidently, the updated version of R(n) at time n can be obtained given the knowledge of Q(n-1) and the series of Givens rotations matrices
JM(n) J2(n)J1(n).
Similarly, consider the _rst part of Eq. (6) with reference to Eq. (7), a similar conclusion can be reached:
P(n “1)
= JM(n)J2(n)J1(n) V(n-1)
d*(n) (24)
where d*(n) is one desired pilot bit that enters the equalizer at time.n, and the updated version of P(n) can be attained given the knowledge of Givens rotations matrices. With these two updated versions of matrices P(n) and R(n), the weight vector can be obtained through Eq. (12).
Equation (12) is mathematically simple but practically intricate because a totally di_erent hardware structure called the \back substitutions is required to compute the weight

3. CORDIC Algorithm :
CORDIC is the abbreviation for Coordinate Rotations Digital Computer [Volder, 1959] and the main idea underlying this algorithm is to perform phase shifting through a series of micro-rotations using a fixed set of elementary rotation angles. Through a proper choice of elementary angles all computations can be implemented efficiently in VLSI using a sequence of shift and add/subtract operations. Such algorithm is used here to replace the complex Givens rotations that contain trigonometric functions, which are not applicable in hardware implementation. Instead, a look-up-table holding the elementary rotation angles has been set up in advance to be ready for call up during phase shifting.
There are two modes of CORDIC algorithm : the vectoring mode, which is used to determine the phase and magnitude of one vector and the rotation mode, which actually performs the rotation of the input vector. In order to execute the Givens rotations, the vectoring mode is first applied to determine the angle to be rotated. This is followed by the rotation mode which rotates the vector through a set of sub-rotation for certain loops.
Consider a two-dimensional vector v represented by v = x+jy in the complex plane as shown in Fig.3. If the vector is rotated by an angle, the new vector is represented as v “ vej0. The angle can be expanded into a set of elementary angles i with pseudodigits qi¬ {-1, +1} and angle expansion error, Zn-1, such that
n-1
= qi- ¬i +zn-1, (31)
i = -1
where the sub-rotation angles_I take on the following values:
/2 (I = 1)
aretan(2-1) (I = 0, 1 n “1) (32)
so that the maximum possible phase shift is p. The detailed value of ¬_I is given in Table1.

The detailed process of the two modes of CORDIC algorithm are illustrated respectively in the following two subsections.

3.1. Vectoring mode
The initializing process consists of two parts :

n-1
v-1 = v Cos(aretan(2-1)).
i=0 (33a)
z “1 = 0, (33b)
where v is the input vector. The purpose of the vectoring mode is to rotate the input vector to the abscissa and then record the angle that has been rotated through the recursive process
(thus obtaining the magnitude and the phase of the vector. With the above initial conditions, the recursion process proceeds with i = -1, 0, , n “ 1 as follows :
qi = -sign(real(vi)). Sign(imag(vi)), (34a)
vi - jqi ( i = - 1)
vi(1 + jqi “ 2-1) ( i 0) (34b)

zi+1= zi - qi i. (35c)
It can be deduced from Eq. (34a) that the direction of the rotation is decided by the position of the current vector. Once the vector resides in the first quadrant, both the real and imaginary part of the vector are positive so that qi is negative; therefore the rotation will be executed clockwise towards the abscissa. On the contrary, if the vector resides in the fourth quadrant, qi will be positive so that the rotation is executed anti-clockwise towards the abscissa. In the vectoring mode, vi approaches the abscissa while the output of z turns out to be the phase of the input vector. The process is illustrated in Fig. 3(a). Only the first three steps have been presented in the figure. The subsequent iterations can be deduced by analogy.

3.2 Rotation mode
This mode is merely a clone of the vectoring mode except for the determination of the direction sign qi. The initializing process includes two parts :
n-1
v-1 = v cos(aretan(2-1). (35a)
i=0
z “1 = , (35b)
Where v is the vector to be rotated, is the rotating angle, v and z are the two temporary variables use4d during the iteration process, and the production on the right side of Eq. (35a) serves as a scaling factor to guarantee that the length of the input vector remains unchanged.
With the initial conditions, the recursion process proceeds with i = -1, 0,, n-1 as follows:
-1 (zi < 0)
+1 (zi = 0) (36a)
vi “ jp¬I (i = -1
vi(1 + jqi “ 2-I) (i = 0) (36b)
zi+1 = zi - qi¬ i. (36c)
The pseudo-digits qi is used to determine the direction of rotation according to the present value of zi which is being updated by the elementary angles to approach zero. At the same time, the vector v I is being updated according to the direction sign qi. Towards the end of the recursion process, zi approaches zero and the final output of vi turns out to be the rotated vector desired. It can be illustrated clearly in Fig. 3(b).

4. CONCLUSION
This paper has focused on one novel approach of signal reception in a CDMA system : replacing the RAKE with an adaptive equalizer for better performance in a multipath environment. The QRDRLS algorithm has been employed due to its superior convergence property that is essential in achieving the suppression of IFI and MAI. Considering the computational complexity that hinders it from practical realization, the CORDIC algorithm has been introduced to make it feasible for hardware implementation. The adaptive equalizer out performs the RAKE receiver in a multi path channel without considerable increase in the system complexity.

5. REFERENCES
1. Biglieri, B., Proakis, J. and Shamai, S., [1998]
- Fading channels: Information-theoretic and
communications aspects,
2. Eweda, E. [1994]
- Comparison of RLS, LMS, and sign algorithms for tracking
randomly time “ varying channels,
3. Haykin, S.[1996]
- Adaptive Filter Theory,
4. Haykin, S., Sayed, A.
- Adaptive tracking of linear time-variant systems by extended RLS algorithms,
5. John G.Proakis
- Digital Communications.