Multi-user detection CDMA receivers in mobile telecommunications systems

0001The present invention relates to Code Division Multiple Access (CDMA) receivers in mobile telecommunications systems, particularly though not exclusively multi-user detection receivers.

0002The issues involved in satisfactory reception at a Base Transceiver Station (BTS) of multiple transmissions from mobile stations (MS), modulated with spread spectrum "spreading codes" are well documented, see the following references: <ul id="ul0001" list-style="none" compact="compact"><li>[1] S. Verdu, "Multiuser Detection", Cambridge University Press, 1998, ISBN 0 521 59373 5.</li><li>[2] S. Moshavi, "Multi-User Detection for DS-CDMA Communications", IEEE Communications Magazine, pp. 124-136, October 1996.</li><li>[3]A. Duel-Hallen, J. Holtzman, Z.Zvonar, "Multiuser Detection for CDMA Systems", IEEE Personal Communications Magazine, pp. 46-58, April 1995.</li></ul>

0003As appears from these references, the spreading codes are in principle orthogonal, and should not interfere with one another to enable detection by "matched filter" correlation . In practice however for a variety of reasons, e.g. time delay between the various received signals, there exists cross correlation between the received signals - multiple access interference (MAI). This greatly complicates satisfactory reception, the mathematical complexities making an optimal detector impractical. Various approximation techniques have therefore been devised such as decorrelating detectors which applies the inverse of the correlation matrix to the output of the matched filters. Other detectors are the class of linear detectors including the minimum mean-squared error (MMSE) detector, which minimises the mean squared error between the actual data and the soft output of the detector, and the polynomial expansion (PE) detector which applies a polynomial expansion in the correlation matrix to the matched filter bank output. There is also a class of detectors employing subtractive interference cancellation which creates at the receiver separate estimates of the MAI contributed by each user in order to subtract out some or all of the MAI seen by each user. In order to simplify computation, it has been proposed in [1], that knowledge of or processing of cross correlations may be avoided in certain circumstances, and Reference [2] points out with short spreading the partial correlations for each bit can be assumed the same.

0004Despite the large number of detectors which have been proposed and implemented, there remains a need for improved detectors for multi-user detection CDMA receivers in mobile telecommunications systems.

SUMMARY OF THE INVENTION

0005The concept of the present invention is to provide a receiver which enables a significant part of the computation of the correlation matrix to be carried out prior to the establishment of a communications link. This therefore enables a reduced complexity of computation during the reception process, (or alternatively enables use of a more complex algorithm without increasing overall complexity of real-time computation). Thus computational complexity associated with the computation of the correlation matrix in multi-user parameter estimation in a CDMA system, specifically multi-user detection (MUD) CDMA receiver, is reduced.

0006A time-sampled signal segment received at a base-transceiver station (BTS)can be written as a vector <u>r</u> = A<u>x</u>+<u>n</u> where <u>r</u> is the vector of unknown symbols transmitted by all K mobile users in the cell, <u>n</u> is the noise vector. Matrix A is a sparse multi-user "system matrix" whose columns represent the channel-filtered user spreading codes. The objective of multiuser detection is to estimate the vector <u>x</u> of all user symbols, given the received vector <u>r</u> and the matrix A. The implementation of a MUD scheme according to the invention (including joint-detection and symbol-level interference cancellation algorithms) involves the computation of a correlation matrix R=A^HA whose elements represent the cross-correlations between various scaled and delayed replicas of the users' spreading codes. The computation of R, which significantly contributes to the overall computational complexity, is reduced by noting in accordance with the invention that the user spreading codes are known a priori at the base station. As a result, the code cross-correlations are computed off-line and stored prior to the establishment of the communication link. The stored values are retrieved in real time to implement the multi-user detection process.

0007Thus in a first aspect, the invention provides a Code Division Multiple Access (CDMA) receiver for a mobile telecommunications system, including means for forming a channel estimate for each of a plurality of users, means for forming a system matrix wherein rows and columns represent users and spreading codes as modified by channel estimates , means for forming a correlation matrix, and means employing said correlation matrix and system matrix to recover user symbols, characterised in that said means for forming a correlation matrix includes means for computing prior to signal reception at least some cross-correlations between user spreading codes , and storage means for storing such cross-code correlations for use in calculation of the correlation matrix.

0008The invention is applicable in principle to any type of CDMA receiver having a multi-user detector employing a correlation matrix, specifically joint detectors and symbol-level subtractive interference cancellation detectors.

0009More generally, the invention relates to reduction of computational complexity of multi-user parameter estimation in CDMA systems, and accordingly the invention provides in a more general aspect, a Code Division Multiple Access receiver for a mobile telecommunications system, including means for multi-user parameter estimation for a plurality of users, including means for forming a correlation matrix, characterised in that said means for forming a correlation matrix includes means for computing prior to signal reception at least some cross- correlations between user spreading codes, and storage means for storing such cross-code correlations for use in calculation of the correlation matrix.

0010In a further aspect, the invention provides in a multi-user detection Code Division Multiple Access (CDMA) mobile telecommunications system, a method of receiving individual user signals, comprising: <ul id="ul0002" list-style="none" compact="compact"><li>forming a multi-user parameter estimation for a plurality of users (1...K), including forming a correlation matrix (R), and employing said correlation matrix to recover user symbols, characterised in that the method comprises detecting a new call, recovering the spreading code for the respective kth mobile station at the base transceiver station (BTS) during the call set-up process;</li><li>computing during the call set-up process cross-correlations between the codes of mobile station k and those of the k-1 mobile stations which have already established calls with the BTS; and</li><li>employing the cross-correlations during the call for reception of the symbols transmitted by all k mobile stations.</li></ul>

BRIEF DESCRIPTION OF THE DRAWINGS

0011A preferred embodiment of the present invention will now be described with reference to the accompanying drawings, wherein:- <ul id="ul0003" list-style="none" compact="compact"><li>Figure 1 is a diagram of a system matrix employed in the present invention;</li><li>Figure 2 is a block schematic diagram of a known multi-user detection receiver for multi-user CDMA signals;</li><li>Figure 3 is a block schematic diagram of the preferred embodiment of the multi-user detection receiver according to the invention;</li><li>Figure 4 is a diagram of a correlation matrix employed in the present invention;</li><li>Figures 5 and 6 are explanatory diagrams showing the computation of sub-matrices of the correlation matrix; and</li><li>Figure 7 is a flow chart showing a method of call establishment in accordance with the invention.</li></ul>

DESCRIPTION OF THE PREFERRED EMBODIMENT

0012A time-sampled segment of the signal received at a CDMA base-station can be written as a complex vector <u>r</u> = A<u>x</u> + <u>n</u> where <u>x</u> is the vector of unknown complex symbols transmitted by all K mobile users in the cell and <u>n</u> is the complex noise vector. The complex matrix A is a multi-user "system matrix" whose columns represent the user spreading codes which are modified by the filtering action of the radio channel.

0013Without loss of generality (users may have different spreading factors, i.e. different data rates), consider a scenario as shown in the matrix representation of Figure 1 involving K cochannel asynchronous mobile transmissions each using a spreading factor of Q. The first K columns represent K transmissions of the first symbol, and the nth K columns represent the nth symbol for each of K users. In each column, there is contained the user spreading code as modified by the respective user channel. Thus the system matrix may be represented by an array of sub-matrices B, one sub-matrix for each user symbol, generally arranged along the diagonal of A. Figure 1 shows the system matrix for a chip-sampled time slot duration corresponding to N bits per user. Each sub matrix B may be written as<maths id="math0001" num=""><img file="EP1128564A1_D0001.tif" /></maths> where the non-zero elements of the k^th column, <u>b</u>^(k), of sub-matrix B represent the convolution between the k^th user's complex spreading code <u>c</u>^(k) (of length Q) and the k^th user's propagation channel <u>h</u>^(k) or channel estimate (of length W). As is well known in the art, the array of sub-matrices B, one sub-matrix for each user symbol, generally arranged along the diagonal of A. Figure 1 shows the system matrix for a chip-sampled time slot duration corresponding to N bits per user. Each sub matrix B may be written as where the non-zero elements of the k^th column, <u>b</u>^(k), of sub-matrix B represent the convolution between the k^th user's complex spreading code <u>c</u>^(k) (of length Q) and the k^th user's propagation channel <u>h</u>^(k) or channel estimate (of length W). As is well known in the art, the channel <u>h</u>^(k) is typically represented by a filter having L taps (or fingers) of complex amplitudes <i>h</i><maths id="math0002" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">(k)</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0002.tif" /></maths> 1=1...L and delays τ<maths id="math0003" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">(k)</mtext></mrow><mrow><mtext>1</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0003.tif" /></maths> &lt; τ<maths id="math0004" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">(k)</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0004.tif" /></maths> &lt; ... &lt; τ<maths id="math0005" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">(k)</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0005.tif" /></maths>. The channel is assumed fixed over a time slot period, and the notation <u>c</u>^(k) (τ₁^(k)) represents the code <u>c</u>^(k) delayed by τ₁^(k) Many multi-user detection schemes involve the computation of the correlation matrix R=A^HA. A^H is the complex transposed skew symmetric representation of the matrix A, and the correlation matrix R is Hermitian. It will be appreciated that other representations of the correlation matrix are possible, and that the present invention does not depend on the precise formulation of the correlation matrix.

0014The block diagram for a known multi-user-detection receiver, embodying the above considerations, is depicted in Figure 2. In figure 2, an incoming signal <u>r</u> is applied to a channel estimation unit 10. Typically this forms for each user from an initial training sequence the coefficients h₁^(k), τ₁^(k). These coefficients are applied to a system matrix computation unit 12, which, together with the user spreading codes <u>c</u>^(k) computes the matrix A. The complex transposed skew symmetric form of the matrix, AH is applied to a rake filter 14 , having L taps or fingers. The incoming signal is modified in rake filter 14 according to A^H. The modified signal <u>y</u> is applied to multi-user detection unit 16. The correlation matrix A^HA is computed in unit 18 and applied to MUD unit 16, for recovering the user symbols. Thus the signal <u>y</u> applied to MUD unit 16 from rake filter 14 includes cross correlation interference (MAI). It is the task of unit 16 to remove such cross correlations, and derive estimates of the symbols x transmitted by the users.

0015In a <b>joint detection receiver</b>, MUD unit 16 derives joint estimates of symbols x by simultaneously solving the equations for the signal <u>y</u>, in known manner. It will be noted the present invention is also applicable to the known class of symbol-level <b>subtractive interference cancellation detectors</b>. These create at the receiver separate estimates of the MAI contributed by each user in order to subtract out some or all of the MAI seen by each user. Both in the case of the joint detector and the subtractive interference cancellation detector, computation of the correlation matrix R is necessary.

0016Referring now to Figure 3, the preferred multi-user detection receiver of the present invention is shown in block schematic form. Similar parts to those of Figure 2 are represented by the same reference numerals. In figure 3, unit 20 is provided for computing spreading code cross correlations p prior to initiation of a user call, as will be described more specifically below. Only spreading codes of active users are applied to unit 20, and to system matrix unit 12. These spreading code cross correlations p are stored in a look up table 22. The look up table 22 is accessed by the channel delay values τ₁^(k), computed by channel estimate unit 10, to provide the appropriate values of cross correlations p to the correlation matrix unit 18. Thus unit 18 is relieved of the burden of computing the cross correlation values p during a user call. It will be observed that cross correlation unit 18 requires in addition the values h₁^(k) computed by estimate unit 10. It does not require the system matrix computed in unit 12, in contrast to the arrangement of Figure 2.

0017In more detail, the correlation matrix of the present invention R=A^HA computed in unit 18 may be represented as shown in Figure 4, wherein sub matrices B in A result in sub matrices in R, comprising matrices R_1,1 and cross matrices R_2,1 and R_2,1^H. The effort required for the computation of R isas follows.

COMPUTATION OF R

1,1

0018The sub-matrix <b><i>R</i></b>_1,1 = <b><i>B</i></b>^<i>H</i><b><i>B</i></b> is Hermitian (see above) . The computation of R_1,1 is shown diagrammatically in Figure 5, as multiplication of B with its transposed skew symmetric form. The resulting coefficients are as shown in the lower diagonal of the matrix, with ½ K(K+1) unique elements given by<maths id="math0006" num=""><img file="EP1128564A1_D0006.tif" /></maths> where the computation of each inner product ρ<maths id="math0007" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">p,q</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0007.tif" /></maths> requires an average of ½Q multiply-and-accumulates of the form (±1±j1)(±1±j1) + ... = (±1±1) + j(±1±1) + ... implying a total of ½Q×4 negations (NEGS) and ½Q×4 real additions (RADDS). The computation of each product-and-add <i>h</i><maths id="math0008" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0008.tif" /></maths> × <i>h</i><maths id="math0009" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">q</mtext><mtext>)*</mtext></mrow><mrow><mtext>λ </mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0009.tif" /></maths> × ρ<maths id="math0010" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext mathvariant="italic">p,q</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0010.tif" /></maths> + ... requires 16 real multiplications RMULTS and 8 real additions RADDS. It will be appreciated that NEGS, RADDS and RMULTS are software instructions each of a single machine cycle in a DSP. The total complexity for computing R_1,1 is given by <tables id="tabl0001" num="0001"><img file="EP1128564A1_D0011.tif" /></tables>

0019For implementation on a typical programmable DSP where a negation, real addition and real multiplication are each single-cycle instructions, the MIPS count would be as follows: <tables id="tabl0002" num="0002"><img file="EP1128564A1_D0012.tif" /></tables>

COMPUTATION OF R

2,1

0020The sub-matrix R_2,1 equals the inner product of one segment, B_1, of B with a different segment, B_2, of B. Or more specifically<maths id="math0011" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>2,1</mtext></mrow></msub><mtext> =</mtext><msubsup><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>2</mtext></mrow><mrow><mtext mathvariant="italic">H</mtext></mrow></msubsup><mtext></mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = [</mtext><mtext mathvariant="italic">B</mtext><msubsup><mrow><mtext>]</mtext></mrow><mrow><mtext>1:</mtext><mtext mathvariant="italic">Q</mtext><mtext>+</mtext><mtext mathvariant="italic">W</mtext><mtext>-2,1:</mtext><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">H</mtext></mrow></msubsup><mtext> [</mtext><mtext mathvariant="italic">B</mtext><msub><mrow><mtext>]</mtext></mrow><mrow><mtext mathvariant="italic">Q</mtext><mtext>+1:2</mtext><mtext mathvariant="italic">Q</mtext><mtext>+</mtext><mtext mathvariant="italic">W</mtext><mtext>-2,1:</mtext><mtext mathvariant="italic">K</mtext></mrow></msub></mrow></math><img file="EP1128564A1_D0013.tif" /></maths> as depicted in Figure 6. It will be seen the multiplication of B₁ with the skew symmetric transposed matrix B₂^H results in a truncation of the spreading codes of both sub-matrices with a resulting square matrix R_2,1 having K² elements. Thus we are now dealing with inner products between delayed and "truncated replicas" of user spreading codes. The extent of truncation for each spreading code is a function of the its corresponding channel delays and needs to be accounted for when computing the inner products. The matrix R_2,1 is not symmetric and has K² unique elements given by<maths id="math0012" num=""><img file="EP1128564A1_D0014.tif" /></maths> where <img file="EP1128564A1_D0015.tif" />represents a truncated version of <u>v</u>. The computation of each inner product <img file="EP1128564A1_D0016.tif" /> requires an average of approximately ½×½Q multiply-and-accumulates of the form (±1± j1)(±1±j1)+ ... = (±1±1) + j(±1±1) + ... implying a total of ½×½Q×4 NEGS and ½×½Q×4 RADDS. The computation of each product-and-add <i>h</i><maths id="math0013" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0017.tif" /></maths> × <i>h</i><maths id="math0014" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">q</mtext><mtext>)*</mtext></mrow><mrow><mtext>λ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0018.tif" /></maths> × <img file="EP1128564A1_D0019.tif" /> + ... requires 16 RMULTS and 8 RADDS. The total complexity for computing R_2,1 is given by <tables id="tabl0003" num="0003"><img file="EP1128564A1_D0020.tif" /></tables> For implementation on a typical programmable DSP where a negation, real addition and real multiplication are each single-cycle instructions, the MIPS count would be as follows: <tables id="tabl0004" num="0004"><img file="EP1128564A1_D0021.tif" /></tables>

0021Thus, the computation of the R_1,1 and R_2,1 correlation sub-matrices requires the computation of the inner-products between delayed replicas of the user's spreading codes. This is a chip-level operation and, as is evident from Tables (2) and (4), contributes significantly to the overall computational burden. Since the base-station receiver is, by definition, aware of the spreading codes used by the active mobiles in its cell, it is possible, as shown in Figure 3 to compute the inner products off-line prior to the establishment of the communication session. Since the code delays are a function of radio channels which vary significantly during the course of a communication session, it is necessary to pre-compute the inner products for all possible combinations of multipath delays.

0022Specifically, regarding R_1,1 , the inner products ρ<maths id="math0015" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext mathvariant="italic">p,q</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0022.tif" /></maths> p,q=1...K 1-λ=-(Q-1)...(Q-1) need to be pre-computed and stored in memory look-up table 22. For K users, there are a total of K² possible combinations of p and q. However, only ½K(K+1) of these are required since R_1,1 is symmetric. For each combination of p and q there are 2Q-1 possible relative code delays. The extreme values of the real and imaginary components of ρ<maths id="math0016" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext mathvariant="italic">p,q</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0023.tif" /></maths> are +2Q and -2Q respectively. Then assuming Q_max=128, two 10-bit words are sufficient for storing each value of p resulting in a total memory storage requirement of ½K(K+1) x (2Q-1) x 20 bits. For K=54 and Q=128, this implies ∼ 1Mbytes of memory for the look-up table. This amount of memory provides a saving by a factor of about ×22 in a DSP-based computation of R_1,1. Regarding R_2,1, the inner products <img file="EP1128564A1_D0024.tif" /> p,q=1...K 1-λ=-(Q-1)...(Q-1) need to be pre-computed and stored in another region of memory look-up table 22. For K users, there are a total of K² possible combinations of p and q. For each combination of p and q there are 2Q-1 possible relative code delays (many of whom result in zero inner products due to the truncation, however this will be ignored). The extreme values of the real and imaginary components of <img file="EP1128564A1_D0024.tif" /> are +2Q and -2Q respectively. Then assuming Q_max=128, two 10-bit words are sufficient for storing each value of p resulting in a total memory storage requirement of K² × (2Q-1) × 20 bits. For K=54 and Q=128, this implies ∼ 2Mbytes of memory. This amount of memory provides a saving by a factor of about × 12 in a DSP-based computation of R_2,1.

0023Note that the look-up table 22 need only contain the code cross-correlations of the mobiles that have already established dedicated communication channels on the uplink.

0024A sequence of events for the use of the embodiment of Figure 3 in computation and storage of code cross-correlations is shown in the flow chart of Figure 7, as follows.

0025In an initial step 70, k-1 mobiles stations (MS) have already established dedicated communication channels with a BTS (Base Transceiver Station) to provide a signal <u>r</u>.

0026A repetitive check is made at 72 for a new call originating from a k^th mobile via a random-access channel <u>or</u> the BTS initiating a network-originated call via a paging channel targetted at the k^th mobile.

0027In either case, the mobile specifies the nature of its spreading code, <u>c</u>^(k), to the BTS during the call set-up process, as at 74. The BTS then computes the cross-correlations ρ<maths id="math0017" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext mathvariant="italic">k,q</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1128564A1_D0025.tif" /></maths> and <img file="EP1128564A1_D0026.tif" /> q=1...k-1 between the codes of mobile k and those of the k-1 mobiles which have already established dedicated channels with the BTS. The cross-correlations are stored in look up table 22.

0028In step 76, during the call, relevant values are accessed from the look up table by addressing the look up table with the delay values τ₁^(k) computed in unit 10, and the retrieved values from the look up table are applied to the correlation matrix unit18. Values of the channel estimate h₁^(k) are applied from estimator unit 10, and the sub matrices R_1,1, R_2,1 of the correlation matrix are computed, as explained above. The matrix R is then applied to MUD unit 16 to perform multi-user detection of the symbols transmitted by all k mobiles.

0029A repetitive check is made at 78 to determine whether the call for user k is terminated. Once the call between the base and user k is determined as terminated as at 80, the cross-correlation values for user k are erased from the look-up table since they are no longer needed.