The Kalman Filtering Blind Adaptive Multi-user Detector Based on Tracking Algorithm of Signal Subspace

Abstract

Multi-user detection is an effective method to reduce multiple access interference in code division multiple access (CDMA) systems. This paper discusses a signal subspace based blind adaptive multiuser detector and a Kalman filtering blind adaptive multiuser detector. Combining them together, a new Kalman filtering blind adaptive multiuser detector based on a tracking algorithm of the signal subspace is proposed. Analysis and simulation show that the proposed blind multiuser detector achieves better suppression of multiple access interference and has a higher convergence rate.

1. Introduction

Spread spectrum codes are not completely orthogonal in a code division multiple access (CDMA) mobile communication system, and non-zero cross correlation coefficients exists in spread spectrum sequences. As a result, users suffer interference with each other [1,2]. This is called multiple access interference. Multiple access interference is one of the key problems that affect system performance and capacity. Multi-user detection technology [3,4] is one of the most widely used approaches to mitigate multiple access interference.

It uses joint detection at the receiver side. It is based on single-user detection, which comprehensively makes use of known information including the disruptor’s. However, it has the following limitations [5]: (1) It needs to know all the disruptors’ amplitude, pseudo noise (PN) code and priori knowledge of timing information; (2) It is not effective to resist inter-cell interference; (3) It cannot be used on downlinks directly.

Adaptive multi-user detection technology can realize adaptive detection only on PN code and timing information of an anticipant user with the help of a training sample sequence. However, the training sequence occupies the bits transmission. Blind adaptive multi-user detection technology can realize adaptive detection only by utilizing user’s PN code which comes from the sample sequence of the received signal. It is suitable to be applied in the downlinks [6].

The Kalman filtering algorithm is a filtering that can estimate the observed variables related to the extracted signal to get required information. It can be applied in multi-user detection. In 2002, Zhang and Wei [7] proposed the blind multi-user Kalman filtering algorithm of adaptive from developing Kalman filtering algorithm, but it had a high computational complexity in practice. Wang and Poor proposed a blind multi-user detector [8] based on subspace method; the idea is to use parameters of the signal subspace as the detector’s weight vectors and then to apply a subspace tracking algorithm to get the information sequence of an anticipant user from the obtained detector’s weight vectors. This method has the following advantages [9,10,11]: (1) low computational complexity; (2) robustness to background noise; (3) the multi-user detector’s weight vectors can adapt to a dynamic environment. This paper combines Kalman filtering algorithm and the signal subspace method in a blind multi-user detector, and proposes a new Kalman filtering blind adaptive multi-user detector based on a tracking algorithm of the signal subspace. Analyses and simulation results show that it has better multiple access interference suppression ability and a higher convergence rate.

2. Signal and Channel Model

The received signal through an additive white Gaussian noise (AWGN) channel of CDMA mobile communication [12,13] is given by:

$$r(t)={\displaystyle \sum _{k=1}^K{A}_k{\displaystyle \sum _{i=0}^{M-1}{b}_k[i]s_k(t-iT)+n(t)}}$$

(1)

Here, $M$ is the number of symbols per user in the data frame, $K$ is the number of users, $T$ is the time interval, $A_k$ is the amplitude of the received signal, ${\left\{b_k[i]\right\}}_{i=0}^{M-1}$ is the transmission symbol stream, $s_k(t)$ is the normalized transmission signal waveform of the k-th user, and $n(t)$ is the baseband complex Gaussian noise with a power spectral density of ${\sigma }^2$. The real and imaginary parts of $n(t)$ are statistically independent.

In the receiver, the received signal $r(t)$ passes through a chip filter first, gets sampled according to the chip rate. The sample value of the j-th code element of the i-th symbol is:

$$r_j[i]\triangleq {\displaystyle {\int }_{iT+j{T}_c}^{iT+(j+1)Tc}r(t)\psi (t-iT-j{T}_c)}dt,j=0,\dots ,N-1;i=0,\dots ,M-1$$

(2)

where $\psi (t)$ is the normalized chip shape function, $T_c=T/K$ is chip period, ${{\displaystyle {\int }_0^{T_c}\Vert \psi (t)\Vert }}^{2}dt=1$. The corresponding discrete-time signal [14] of the i-th symbol is:

$$r[i]={\displaystyle \sum _{k=1}^K{A}_k{b}_k[i]s_k+n[i]}=SAb[i]+n[i]$$

(3)

where $r[i]\text{=}{\left[r_0[i]r_1[i]\cdots r_{N-1}[i]\right]}^T$, $s_k\text{=}\frac{1}{\sqrt{N}}{\left[c_{0,k}{c}_{1,k}\cdots c_{N-1,k}\right]}^T$, $n[i]\text{=}{\left[n_0[i]n_1[i]\cdots n_{N-1}[i]\right]}^T$, $n_j[i]\text{=}{\displaystyle {\int }_{iT+j{T}_c}^{iT+(j+1)T_c}n(t)\psi (t-iT-j{T}_c)}dt$, $n_j[i]$ is a random variable of complex Gaussian with statistically independent real and imaginary part, $n[i]\text{=}{N}_c(0,{\sigma }^2{I}_N)$( $N_c(,)$ is the complex Gaussian distribution, $I_N$ is the N × N identity matrix), $S\text{=}[s_1\cdots s_K]$, $A\text{=}diag(A_1,\dots ,A_K)$, $b[i]\text{=}{[b_1[i]\cdots b_K[i]]}^T$.

It is assumed User 1 is the anticipant user. The received signal vector [15] of User 1 from the receiver is, therefore, given by:

$$r=A_1{b}_1{\text{s}}_1+\underset{MAI}{\underbrace{{\displaystyle \sum _{k=2}^K{A}_k{b}_k{\text{s}}_k}}}+\underset{backgroindnoise}{\underbrace{n}}$$

(4)

3. Kalman Filtering Blind Adaptive Multi-user Detector Based on Tracking Algorithm of Signal Subspace

3.1. Kalman Filtering Blind Adaptive Multi-user Detector

The formula for Kalman filtering algorithm of blind multi-user detection is [16]:

$$c_1(n)=s_1-C_{1,null}{\omega }_1$$

(5)

The multi-user detector consists of a fixed part $s_1$ and sum of an adaptive part; these two parts are orthogonal, and column vectors of matrix $\left[s_1{C}_{1,null}\right]$ forms the signal subspace basis set, ${\omega }_1$ is a weight vector. Thus the ${s_1}^H\times C_{1,null}=0$. The $C_{1,null}$ can be obtained using an orthogonal method or singular value decomposition to the autocorrelation matrix $C_r$ of received signal $r$ if get the feature waveform vector $s_1$ of User 1. Furthermore, if the CDMA system is time invariant, the optimal detector or the tap weight vector $c_{opt1}[i]$ is also time invariant. Assuming ${\omega }_{opt1}$ is the adaptive part of $c_1$ in formula (5), corresponding to the optimum detector at time $i$, then we can obtain (6) below as the state transition equation.

$${\omega }_{opt1}[i+1]={\omega }_{opt1}[i]$$

(6)

Let

$$e[i]=\langle c_1,r\rangle =c_1^H[i]r[i]$$

(7)

the average of $e[i]$ is $\mu =E\left\{c_1^H[i]r[i]\right\}=c_1^H[i]E\left\{r[i]\right\}=0$, and the variance is:

$$\text{cov}\left\{e[i]\right\}=E\left\{e^2[i]\right\}=A_1^2+MSE(c_1[i])$$

(8)

So $e[i]$ is a white noise.

Substituting Equation (5) into Equation (7), we write:

$$e[i]=s_1^{H}r[i]-r^H[i]C_{1,null}{\omega }_1[i]$$

(9)

Let $\tilde{r}[i]=s_1^{H}r[i]$, $d^H[i]=r^H[i]C_{1,null}$. Then, the observation Equation (9) is:

$$\tilde{r}[i]=d^H[i]{\omega }_{opt1}[i]+e_{opt}[i]$$

(10)

The state transition Equation (6) and the observation Equation (10) make up the system dynamic formula of User 1, and this is the foundation of Kalman filtering algorithm. We now describe the Kalman filtering of blind multi-user detection: given the observation vector $d^H[i]$, we can use the observed data $\tilde{r}[i]$ to get all the coefficients’ minimum mean square error estimation of every state vector ${\omega }_{opt1}$.

According to Equation (8), we can get the variance of optimal detection error

$${\xi }_{\text{min}}=A_1^2+MSE(c_{opt1}[i])$$

(11)

Define ${\epsilon }_{\text{min}}=MSE(c_{opt1}[i])$, where ${\epsilon }_{\text{min}}$ is the minimum mean square error when the tap weight vector is optimal. Therefore ${\xi }_{\text{min}}=MOE(c_{opt1}[i])$ is the minimum mean output energy of User 1.

The above analyses are about User 1, and it can be extended to blind multi-user Kalman filtering adaptive algorithm for multi-user system. It was proposed by Zhang and Wei [7] in 2002. In the algorithm, Gaussian random vector should be selected as the initial state vector to get the best filtering performance. Assuming ${\tilde{\omega }}_{opt1}[0]=E\left\{{\omega }_{opt1}[0]\right\}$, the algorithm is as follows.

Algorithm 1. Kalman filtering blind adaptive multi-user detector algorithm with direct sequence code division multiple access (DS-CDMA).

Initial condition: $Q(1,0)=E\left\{\left[{\omega }_{opt1}[0]-E\left\{{\omega }_{opt1}[0]\right\}\right]{\left[{\omega }_{opt1}[0]-E\left\{{\omega }_{opt1}[0]\right\}\right]}^H\right\}=I$       ${\tilde{\omega }}_{opt1}(0)=E\{w_{opt1}(0)\}=0$

$fori=1,2,\dots ,do$

$g[i]=Q(i,i-1)d[i]{\left\{d^H[i]Q(i,i-1)d[i]+{\xi }_{\text{min}}\right\}}^{-1}$

$Q(i+1,i)=Q(i,i-1)-g[i]d^H[i]Q(i,i-1)$

${\tilde{\omega }}_{opt1}[i]={\tilde{\omega }}_{opt1}[i-1]+g[i]\left\{\tilde{r}[i]-d^H[i]{\tilde{\omega }}_{opt1}[i-1]\right\}$

$c_1[i]=s_1-C_{1,null}{\tilde{\omega }}_{opt1}[i]$

$end$

In the Algorithm 1, $g[i]$, $d[i]$ and ${\tilde{\omega }}_{opt1}[i]$ are both vectors of $(N-1)\times 1$, and $Q(i+1,i)$ is a matrix of $(N-1)\times (N-1)$.

3.2. The Blind Adaptive Multi-user Detector Based on Subspace Tracking Algorithm

According to the signal and channel model, the autocorrelation matrix of the received signal vector is

$$C_r=E\left\{r{r}^H\right\}={\displaystyle \sum _{k=1}^K{A}_k^2{s}_k}{s}_k^H+{\sigma }^2{I}_N=SA{S}^H+{\sigma }^2{I}_N$$

(12)

where $S=[s_1{s}_2\cdot \cdot \cdot s_K]$ represents the signature matrix, and $A=diag(A_1^2{A}_2^2\cdots A_K^2)$ denotes the diagonal matrix of the signal amplitudes.

Applying eigenvalue decomposition on the autocorrelation matrix $C_r$, we get:

$$C_r=SA{S}^H+{\sigma }^2{I}_N=U\Lambda U^H$$

(13)

Here $U=\left[u_1,\cdots ,u_K,u_{K+1},\cdots ,u_N\right]$ is comprised of the $N$ orthogonal eigenvectors of the autocorrelation matrix in decreasing order of the corresponding eigenvalues; and $\Lambda =diag\left({\lambda }_1,\cdots ,{\lambda }_K,{\lambda }_{K+1},\cdots ,{\lambda }_N\right)$ is composed of the $N$ eigenvalues of the autocorrelation matrix in decreasing order, that is ${\lambda }_1\ge \cdots {\lambda }_K\ge {\lambda }_{K+1}\cdots ={\lambda }_N={\sigma }^2$.

Continuing to decompose the Equation (13), we have:

$$C_r=U\Lambda U^H=\left[\begin{array}{cc}{U}_s& U_n\end{array}\right]\left[\begin{array}{cc}{\Lambda }_s& 0\\ 0& {\Lambda }_n\end{array}\right]\left[\begin{array}{c}{U}_s^H\\ U_n^H\end{array}\right]=U_s{\Lambda }_s{U}_s^H+U_n{\Lambda }_n{U}_n^H$$

(14)

In Equation (14), $U=\left[\begin{array}{cc}{U}_s& U_n\end{array}\right]$, $\Lambda =diag\left({\Lambda }_s,{\Lambda }_n\right)$, ${\Lambda }_s=diag\left({\lambda }_1,\cdots ,{\lambda }_K\right)$. K maximum eigenvalues are included in ${\Lambda }_s$ with descending order (i.e., ${\lambda }_1\ge \cdots {\lambda }_K$). $U_s=\left[u_1,\cdots ,u_K\right]$ is the eigenvector matrix corresponding to ${\Lambda }_s=diag\left({\lambda }_1,\cdots ,{\lambda }_K\right)$. ${\Lambda }_n={\sigma }^2{I}_{N-K}$ is the N-K eigenvalues of ${\sigma }^2$. $U_n=\left[u_{K+1},\cdots ,u_N\right]$ is the corresponding eigenvector matrix of ${\Lambda }_n={\sigma }^2{I}_{N-K}$.

The above analyses conclude that the column space of $U_s$ is equivalent to the column space of $S$. The column space of $U_s$ is, therefore, called the signal subspace. Since $U_n$ and $U_s$ are orthogonal, the column space of $U_n$ is called the noise subspace.

Figure 1 shows the blind adaptive multi-user detection based on subspace tracking algorithm.

Figure 1. Blind adaptive multi-user detector.

Figure 1. Blind adaptive multi-user detector.

In a dynamic environment, when users enter and leave randomly, the signal subspace rank and basis will change. For keeping the effectiveness of the proposed detector in the new subspace we need a way to determine or detect the changes when they happen and then resize the $C_{1,null}$ and weight vector ${\omega }_1$ , then the Kalman adaptive filtering and the signal detection will be operated in the new signal subspace. The rank estimation algorithm can use either Akaike criterion [17] of in information theory or the minimum description length (MDL) criterion to [18] of the subspace adaptively. Moreover, we can use the orthogonal projection approximation subspace tracking (OPAST) algorithm [19,20] as the subspace tracking algorithm. OPAST algorithm is improved from PAST algorithm and PASTd algorithm to overcome non-convergence coming from imperfect orthogonality under far-near influence of heavy multiple access interference, so have a good tracking performance because of a better orthogonality over PAST and PASTd, which is proposed by Yang [21].

3.3. Kalman Filtering Blind Adaptive Multi-user Detector Based on Tracking the Signal Subspace

According to the above analyses, we can combine the two detectors to get a Kalman filtering blind adaptive multiuser detector based on tracking signal subspace. The steps of the algorithm are as follows:

(1) Acquire the front I data vectors $C_r$ of the received signal $r$, and then perform eigenvalue decomposition for it.

$$C_r=\frac{1}{I}{\displaystyle \sum _{i=1}^I{r}_i}{r}_i^H=U\Lambda U^H=U_s{\Lambda }_s{U}_s^H+U_n{\Lambda }_n{U}_n^H$$

(15)

So ${\left\{u_k\right\}}_{k=1}^{R(0)}$ is the k-th column vector of $U_s$ and the initial value of the eigenvector. ${\left\{{\Lambda }_s=diag\left({\lambda }_k\right)\right\}}_{k=1}^{R(0)}$ is the initial value of the subspace eigenvalue.

(2) Use OPAST algorithm to update ${\left\{{\lambda }_k,u_k\right\}}_{k=1}^{R(n-1)}$:

Algorithm 2. Orthogonal projection approximation subspace tracking (OPAST) algorithm.

$\begin{array}{l}Initializtion:LetW(0)\text{=}{U}_{\text{s}},Z(0)={\Lambda }_s^{-1}\\ fort=1,2,\dots ,do\\ y(t)=W^H(t-1)r(t)\\ h(t)=Z(t-1)y(t)/\beta \\ g(t)={(1+y^H(t)h(t))}^{-1}\\ e(t)=g(t)\left(r(t)-W(t-1)y(t)\right)\\ \tau (t)=\frac{1}{{\Vert h(t)\Vert }^2}\left(\frac{1}{\sqrt{1+{\Vert e(t)\Vert }^2{\Vert h(t)\Vert }^2}}-1\right)\\ p(t)=\tau (t)W(t-1)h(t)+\left(\tau (t){\Vert h(t)\Vert }^2+1\right)e(t)\\ W(t)=W(t-1)+p(t)h^H(t)\\ Z(t)=Z(t-1)/\beta -g(t)h(t)h^H(t)\\ end\end{array}$

The $\beta$ is the forgetting factor, which is $0<\beta <1$.

(3) Use MDL criterion to estimate rank $R(n)$ of ${\Lambda }_s$.

Algorithm 3. Minimum description length (MDL) criterion.

$\begin{array}{l}fork=1,R(n-1)do\\ \alpha (k)=\frac{\left({\displaystyle \sum _{i=k+1}^N{\lambda }_i}\right)/\left(N-k\right)}{{\left({\displaystyle \prod _{i=k+1}^N{\lambda }_i}\right)}^{1/\left(N-k\right)}}\\ MDL(k)\triangleq (N-k){(1-\beta )}^{-1}\text{ln}\alpha (k)-k(2N-k)\text{ln}(1-\beta )/2\\ end\\ for\\ R(n)=\text{arg\hspace{0.17em}min}MDL(k)+1,0\le k\le N-1\\ if(R(n-1)\ne R(n))\\ \text{\hspace{1em}\hspace{1em}\hspace{1em}reconstruct\hspace{0.17em}}{c}_{1,null}\text{\hspace{0.17em}a}ccordingtotheupdated{C}_r\\ end\end{array}$   Adjust weight vector ${\omega }_1(0)$ to the size of $(R(n)-1)\times 1$ and initialize again.

Here N is the Spreading Gain and $\beta$ is the forgetting factor.

(4) Kalman adaptive filtering estimation.

Algorithm 4. Kalman adaptive filtering estimation.

$\begin{array}{l}forn=1,2,\dots \\ g(n)=Q(n,n-1)d(n){\left[d^H(n)Q(n,n-1)d(n)+{\xi }_{\text{min}}\right]}^{-1}\\ Q(n+1,n)=\left[I-g(n)d^H(n)\right]Q(n,n-1)\\ {\tilde{\omega }}_{opt1}(n)={\tilde{\omega }}_{opt1}(n-1)+g(n)\left[\tilde{r}(n)-d^H(n){\tilde{\omega }}_{opt1}(n-1)\right]\\ {\widehat{c}}_{opt1}(n)=s_1-C_{1,null}{\widehat{\omega }}_{opt1}(n)\\ \widehat{b}(n)=sign\left\{{\widehat{c}}_{opt1}^H(n)r(n)\right\}\\ end\end{array}$

In the Algorithm 4, $g[n]$, $d[n]$ and ${\tilde{\omega }}_{opt1}[n]$ are all vectors of $(R(n)-1)\times 1$, and $Q(n+1,n)$ is a matrix of $(R(n)-1)\times (R(n)-1)$.

4. Simulation Results and Analyses

This paper compares the proposed Kalman filtering blind adaptive multi-user detector based on the tracking subspace algorithm with none subspace one under the same conditions. Consider a synchronous DS-CDMA system under AWGN of variance 0.1. Here, we use Gold code of N = 31 as the spread spectrum sequence and BPSK as the modulation mode. The independent running times are 10,000, and the number of it is 3000. The bit energy of User 1 is set the unit energy $A_1^2=1$, and its SNR is 20 dB (i.e., ${\sigma }^2$ = 0.01). We consider nine interference users, such that four interference users’ SNR is 30 dB (i.e., $A_2^2=A_3^2=A_4^2=A_5^2=10$), three interference users’ SNR is 40 dB (i.e., $A_6^2=A_7^2=A_8^2=100$), and the other two interference users’ SNR is 50 dB (i.e., $A_9^2=A_{10}^2=1000$).

The mean Signal to Interference plus Noise Ratio (SINR) [22,23] in the n steps measured to compare the resistance of multiple access interference of different algorithms.

$$SINR(n)=10\text{log}\frac{{\displaystyle \sum _{j=1}^M(c_{1j}^H[n]s_1)}}{{\displaystyle \sum _{j=1}^M{c}_{1j}^H[n](r_j[n]-b_{1j}[n]s_1)}}$$

(16)

Here, M is the times of independent test, and j stands for j-th test.

Figure 2. Under AWGN Channel with ${\sigma }^2=0.01$, the SINR of subspace-based Kalman filter and full-rank Kalman filter against number of iterations.

Figure 2. Under AWGN Channel with ${\sigma }^2=0.01$, the SINR of subspace-based Kalman filter and full-rank Kalman filter against number of iterations.

Figure 3. Under AWGN Channel with ${\sigma }^2=0.01$. the time average remaining energy output of subspace-based Kalman filter and full-rank Kalman filter against number of iterations.

Figure 3. Under AWGN Channel with ${\sigma }^2=0.01$. the time average remaining energy output of subspace-based Kalman filter and full-rank Kalman filter against number of iterations.

Simulation results are shown in Figure 2 and Figure 3. We can see that the Kalman filtering blind adaptive multi-user detector combined with the signal subspace has a stronger multiple access interference suppression ability and a fast convergence rate.

Since the number of users is constantly changing in the communication system, the multi-user detector should take the adaptive tracking ability in a dynamic environment into consideration. We compare the Kalman filtering blind adaptive multi-user detector based on the signal subspace tracking algorithm, a Kalman filtering blind adaptive multi-user detector, a blind adaptive multi-user detector based on LMS algorithm [24] and blind adaptive multi-user detector based on RLS algorithm in a dynamic environment. The anticipant User 1 has unit energy, in the start of iteration, i.e., $n=0$. There are again 9 multiple access interferences, 4 is 30 dB, 3 is 40 dB, 2 is 50 dB; when $n=600$, 2 is 30 dB, 1 is 40 dB, 1 is 50 dB; When $n=1200$, 1 is 30 dB, 1 is 40 dB. Simulation results are shown in Figure 4.

Figure 4. The SINR of all algorithms.

Figure 4. The SINR of all algorithms.

5. Conclusions

The proposed Kalman filtering blind adaptive multi-user detector based on tracking algorithm of signal subspace applies the OPAST to perform subspace tracking, and MDL criterion as the rank estimation algorithm, then get multi-user detector from Kalman adaptive filtering. It decreases the algorithm complexity while its algorithm convergence is speedier compared to the full rank Kalman algorithm. It is a very effective method in AWGN channel. Moreover, it presents robust performance against multi-access interference. The results of simulations have proved all the conclusions. However, the detector will still suffer some kind of SINR performance loss. Further work will focus on improving the tracking algorithm of signal subspace.