ITTS20000007A1 - MAXIMUM LIKELIHOOD MULTIUSER DETECTION TECHNIQUES WITH REDUCED LAYERS FOR DOWNLINK CONNECTIONS IN TD-CDMA SYSTEMS - Google Patents

Description

DESCRIPTION

In Time Division-Code Division Multiple Access (TD-CDMA) systems, users transmit and receive data in packets being separated, in the time domain, from the specific code sequences of each user. However, the dispersivity of the physical transmission channel and the imperfect orthogonality of the code sequences of the various receiving users, causes interference from intersymbol and from multiple access (ISI and MAI respectively).

JD's techniques are able to address both of these problems and have therefore aroused considerable interest in recent years by virtue of their wide applications. The "optimal" receiver in this case, that is the one that is created according to the Maximum Likelihood (ML) criterion, however, has a computational complexity that grows exponentially with the number of active users. Compared to single-user equalization methods (Single User), JD techniques present a considerable increase in computational complexity, especially in downlink type connections, that is, where economic and technical requirements require it to be reduced to a minimum.

In this work two algorithms are proposed whose formulation derives directly from the criterion of the Maximum Likelihood Sequence Detection (MLSD); to reduce the number of online operations, it was decided to extend the reduced state (RS) technique to the multi-user case and with particular reference to the downlink. In this way, while maintaining good performance, a computational complexity has been achieved which depends proportionally on the number of users.

State of the art

Single-user equalization techniques using Zero Forcing (ZF) and Minimum Mean Squared Errar (MMSE) criteria have already been studied. An important feature of these equalizers is simplicity, since they can be realized by linear filtering, exploiting only the knowledge of the useful user's spreading code. JD's techniques provide better performance than single-user ones, especially in very dispersive radio channels where the contribution of ISI and MAI is considerable; however they require knowledge of the spreading codes of active users. In the context of the JD, the equalizers proposed in the literature are based on the MMSE criterion, in the symbol and block versions.

The reduced-state method is instead proposed for applications on single-user systems, in which the mere presence of ISI must be combated. System model

Consider a transmission system of the CDMA type, in which K users use the same transmission channel at the same instant and in the same frequency band Each user transmits symbols belonging to a QPSK alphabet with period Ts and both the information contained in a data-block. Each user is associated with a spreading sequence, defined as a chip period Tc by means of the following equation:

where is the spreading sequence of the user k-th, p (t) is the modulation pulse with raised cosine root and

spreading factor. In the case of a down-link connection, the users in the system are synchronous and propagate through a dispersive channel of the Rayleigh fading type.

The multi-user information sequence is denoted by the vector while the equivalent multi-user channel is. The mathematical model of this transmission system is therefore constituted by a linear system with K inputs and 1 output (see Fig. 1).

The received signal r (t) can be suitably modeled as the superposition of a useful signal s (t) perturbed by a complex Gaussian additive noise with zero mean and having a spectral density N0, as expressed in the following equation:

(3.2)

Two formulations of the ML criterion

Suppose you have broadcast the sequence

useful signal is given by:

(4.1)

The Maximum Likelihood Sequence Detection (MLSD) criterion determines the maximum likelihood sequence with the received signal in a finite time interval I, assuming that the signal has been transmitted. In other words, the criterion ML chooses that sequence Μ which maximizes the functional L thus defined:

(4.2)

Now define the following quantities:

(4.3)

Note that the kth element of the vector yn represents the kth output of a bank of K filters, each tuned with the equivalent channel associated with the k-th user and whose output is sampled instantly.Note that the system thus obtained, represented in Fig. 2, it is a system with K inputs and K outputs. The matrix function of dimensions KxK represents the transfer function of the system. The two quantities defined in (4.3) are in fact linked together, in terms of the D-transform, by the following relationship:

(4.4)

where n (D) is the equivalent noise after the bank of despreaders (see Fig. 2).

Since R (Z)) is a correlation matrix, the spectral factorization criterion holds:

(4.5)

where in (4.5) F (D) is the minimum phase spectral factor.

The metric (4.2) can be developed in two different ways, thus giving rise to two different realizations of the MLSD criterion, which respectively represent the generalizations to the multiuser case of the Ungerboeck and Forney approaches.

where in (4.7) v indicates the number of past interferers and the vector z n is the signal at the output of the whitening filter, applied after the despreaders bank, having a frequency response equal to

It should also be borne in mind that, while (4.6) must be maximized, (4.7) must be minimized.

The reduced state technique

The solution obtained with the ML criterion, for both formulations (4.6) and (4.7) requires the use of dynamic programming, ie the Viterbi algorithm. The computational complexity, evaluated in number of states, is for both techniques equal to if a QPSK constellation is assumed. In this paper, for simplicity of explanation, suppose that the condition v = 1 is verified (The reduced state technique can easily be generalized to the case in which condition (5.1) is no longer verified), that is:

(5.1)

so that the state

The multi-user symbol can be interpreted as a vector belonging to a K-dimensional lattice of 4 <k> points.

Following this geometric approach, the original states can be grouped to form a subset of states or reduced state which constitutes a suitable subset of the original K-dimensional lattice. In practice it is partitioned into subsets (or reduced states), each containing original states (or lattice points).

The reduced state method first determines that multi-user symbol within the reduced state that minimizes the metric; to do this, the decision taken at the previous moment is used as feedback. Then the current symbol is added to the list of survivors, associating it with the current reduced state. In this way, only paths must be kept in the reduced trellis. It is essentially a generalization to the multi-dimensional case of the Reduced State Sequence Estimation (RSSE) solution already proposed in the literature for systems that only have to fight the ISI.

In this paper, methods of subdivision of the K-dimensional grid are considered suitable for downlink type connections, that is, aimed at single user detection. For the partitioning of the K-dimensional set, each state has in fact been chosen and consists of the QPSK symbol belonging to the user to be detected, while the other K-1 elements correspond to all the possible combinations of symbols of the other users.

Efficient reduced state algorithms

The multi-dimensional partitioning method reduces the number of states from. Reducing the number of states allows you to limit the amount of memory required, which becomes proportional to

instead of a The number of in-line operations is always high; the computational complexity in terms of the number of branch metric to be calculated passes from The reduced state method in fact first determines, for each arrival and departure state, the multi-user symbol within the reduced state to do this all must be calculated the metrics relating to the “parallel” transitions between the same states

While in single-user systems the symmetry of the constellation allows to solve parallel transitions by means of simple threshold elements, this does not happen in the multi-dimensional case. In the following subsections two techniques are illustrated to avoid the calculation of parallel transitions through suitable thresholds; these methods descend respectively to the two formulations (4.6) and (4.7).

SIC-RS

Consider the expression (4.6), detailed in the case where v = l, and set:

(6.1.1) With the previous one (6.1.1), the branch-metric (4.6) becomes:

(6.1.2)

To avoid the computation of parallel transitions it was decided to exploit the geometric meaning of (6.1.2); the element of the reduced state that maximizes (4.6) is that vector that has the maximum orthogonal projection in the direction of rendering

independent of the choice can be made with K threshold elements, one for each component of the vector

In order to make it independent from, it was decided to use a first stage with subsequent cancellations (Successive Interference Cancellation, SIC). In other words, the component is first considered and, by applying a threshold detector, the estimate of the symbol is obtained. Then it is reconstructed and eliminated from the interference due to the general formula:

(6.1.3)

and a threshold detector is applied to the value thus obtained.

Having said the multi-user symbol at the exit of the SIC stage, consider now:

(6.1.4) where Assuming the metric (6.1.2) it becomes:

(6.1.5)

are the terms of the diagonal of 0 and the factor 2 derives from the fact that the transmitted symbols are QPSK. Since the first term of (6.1.4) is independent of the minimization, it can be carried out easily, as illustrated at the beginning of the subsection. The computational complexity of this scheme is 0 (16K). WF-RS

Now consider expression (4.7), in which a whitening filter (WF) is applied at the output of the despreaders bench; carrying out the metric we obtain:

From (6.2.1) we can deduce the following properties of the metric It can be expressed as the sum of the branch-metric of each user, being expressed as the sum of Euclidean distances.

It is causal, as a consequence of the lower triangular structure of

To avoid the direct calculation of parallel transitions, you can use the properties listed above; assume, without loss of generality, that the user to be detected is the first. As a result of the partitioning introduced in the previous section, the first component of the state is fixed for each.

The only unknown of (6.2.2) is fixed and the calculation can then be performed using the symmetry of the QPSK constellation. This procedure is repeated until all the components of the vector are determined. Similarly to the SIC-RS algorithm, the number of in-line operations is O (16K).

Claims (1)

CLAIMS 1- Calculation method applied to TD-CDMA systems in downlink configuration with k users, characterized by the fact that the interference from intersymbol (ISI) and from multiple access (MAI) is reduced through a partitioning of the multi-user alphabet according to the Reduced State Maximum Likelihood Detection (RS). 2- Calculation methods according to claim 1, characterized by the fact that the aforementioned reduced-state technique allows to reduce the computational complexity in terms of the number of "branch metric" to be calculated through the division of the kdimensional lattice, containing according to the QPSK 4 constellation <k> originating states, in reduced state subsets J1, each containing 4 <k> / J1 originating states. 3- Calculation method according to claims 1-2, characterized by the fact that a second reduction of the computational calculation is obtained through the use of a successive cancellation processing stage (Successive Interference Cancellation SIC), which refers to the Maximum Likelihood Sequence Detection (MLSD) by Ungerboeck (4.6). 4- Calculation method according to claim 3, characterized by the fact that said processing stage with successive cancellations is carried out by means of techniques which allow to avoid, through suitable thresholds (in the same way as what is possible to do in single-user systems), the calculation direct parallel transitions. 5- Calculation method according to claims 1-2, characterized by the fact that a second reduction of the computational calculation alternative to that of claim 3, is obtained through the use of a whitening filter (WF) which takes its cue from Forney's MLSD approach (4.7). 6- Calculation method according to claim 5, characterized by the fact that said stage using a whitening filter allows, through the partitioning referred to in claim 2, to avoid the direct calculation of parallel transactions using the property of the matrix (6.2.1) .