| Fractionally Sampled Linear Detectors for DS-CDMA
D.R. Brown, D.L. Anair, and C.R. Johnson, Jr.*
Cornell University
The 32nd Asilomar Conference on Signals, Systems, and
Computers, November 2–5, 1998
Abstract
In this paper we analyze the performance of fractionally chip sampled
linear multi-user detectors for Direct-Sequence CDMA communication systems.
We consider a general DS-CDMA system model accounting for user asynchronism
and frequency-selective propagation channels. Analysis shows that FIR
linear detectors with chip rate sampling cannot perfectly recover N or
more users for a system with spreading gain N in the presence of frequency
selective channel dynamics or user asynchronism. Drawing inspiration from
fractionally-spaced equalization, we propose the fractionally chip sampled
receiver and show that a FIR linear detector may be able to perfectly
recover 
N users.
Back to top of page
Introduction
This paper considers the problem of demodulating digitally modulated
signals in the presence of multi-access and multipath interference with
a linear multi-user detector. Linear multi-user detectors for DS-CDMA
systems have received increased attention due to their advantages of relatively
low complexity over the optimal MLSE detector and significantly improved
performance over the conventional matched filter detector.
In this paper we investigate the advantages of fractional chip sampling
for linear multi-user detectors proposed in [6]
where the sampling period of the receiver is some fraction of the chip
duration  .
Fractionally sampled equalizers (FSEs) for single user linear detection
have been studied since the late 1960’s and their desirable properties
have led to several commercial applications [8].
The documented advantages of FSEs include robustness to timing phase errors
[7],
the ability to effectively compensate for more severe delay distortion
than a baud spaced equalizer [1],
and the existence of FIR zero-forcing (ZF) solutions for data distorted
by a FIR channel [3].
The necessary and sufficient conditions for the existence of FIR ZF solutions
for a (single user) FSE can be summarized as
- sufficient equalizer length,
- subchannel disparity, and
- no additive channel noise.
This paper examines similar conditions for multi-user DS-CDMA communication
systems. In particular, we focus on deriving a length condition necessary
for the existence of ZF solutions which, in the absence of noise, allows
for perfect recovery of the transmitted symbols by completely canceling
all multi-access and multipath interference. The derived length condition
indicates that FIR linear detectors with chip rate sampling are unable
to perfectly recover K
N users in the presence of multipath channel dynamics or user asynchronism.
Our necessary length condition also implies that FIR fractionally chip
sampled multi-user detectors may be able to perfectly recover transmitted
symbols from K
N users.
Simulation results verify the analysis and additionally demonstrate that
the fractional chip sampled multi-user detectors may also provide significant
performance advantages in the presence of additive channel noise.
Back to top of page
Discrete Time System Model
Consider the baseband asynchronous DS-CDMA system model shown in Figure
1. Let N represent the spreading gain common to all users
and assume the spreading codes are periodic with period N. Let
represent the combined system impulse response of the pulse shaping filter,
the  user’s
(fixed or slowly time varying) channel, and the receiver input filter.
The baseband signal r(t) at the input of the sampler may be written
as
.gif)
Figure 1. DS-CDMA system model.
where 
represents the spread (and oversampled) discrete information bearing sequence
of the user,
is
the chip duration,  is
an arbitrary delay with respect to some reference, w(t) is the
aggregate additive channel noise, and 
is the impulse response of the receiver input filter. Note that 
where  denotes
the set of all integers. The output of the sampler may then be expressed
as
.gif)
where 
represents the sampled receiver filtered aggregate channel noise.
Denoting the user’s
symbol delay as  where
and  represent
the integer and fractional number of samples in the delay, respectively,
we can rewrite (2) as
.gif)
Assuming that is
FIR with support 
for 
we can rewrite (3) as
.gif)
where 
Note that there are exactly L terms in the inner
summation and approximately  of
these terms are zero since  .
Given a linear detector f with 
taps, (4) enables us to directly express the output of the linear detector
in terms of finite dimensional linear operators on a vector of source
symbols. The linear detector output may be expressed as 
where  .
In light of the linear convolution in (4), let  denote
the  dimensional
convolution matrix such that
.gif)
where 
is the user’s
-sample
delayed vector of (oversampled) chip rate information constructed from
(4). In general, has
the Toeplitz from
 .
Recognizing that may
be formed from a linear combination source symbols, we can rewrite (5)
as .gif)
where 
is the map from the user’s
symbol sequence
 .
In general
has the form
 .
where  is
a column vector of length NP representing the user’s
(oversampled) spreading code. The expressions 
and 
denote spreading codes which may be upper or lower-truncated, respectively,
due to user asynchronism and the finite observation interval. Finally,
constructing a user-ordered stacked source vector  ,
we can rewrite (6) as .gif)
where  .
Back to top of page
Common Linear Multi-user Detectors
Given the discrete time linear model in (7) it is straightforward
to write expressions for zero-forcing (ZF) and minimum mean square error
(MMSE) detectors under arbitrary asynchronism and multipath channels.
We have intentionally avoided deriving the “decorrelating” detector
since it is conventionally defined without consideration for multipath
interference. The ZF detector may be viewed as a generalized decorrelating
detector that completely cancels the effects of both multiuser and multipath
interference [2].
Given a desired user k and symbol delay  ,
a ZF detector is defined as any element of the set  .
Let 
represent the total number of symbols in the observation interval or,
equivalently, the number of columns in H. The ZF detector exists
for all k and
if and only if the span of the columns of  is
all of  .
Since  then
this condition is equivalent to requiring that rank (H) = Q
or H must have full column rank. Under this assumption, the unique
minimum norm ZF detector may be written as
where  is
a column vector with all elements equal to zero except a value of one
in the position corresponding to the  position
is s(n) and  denotes
the Moore-Penrose pseudoinverse.
Given a desired user k and symbol delay ,
the MMSE detector is defined as
 .
Assuming that the source symbols are BPSK and i.i.d.,
(7) leads to a straightforward closed form expression for the MMSE detector:
where  is
the autocorrelation matrix of the receiver filtered noise.
Back to top of page
System Matrix Dimensional Analysis
This section applies the previous development of the discrete time model
to analyze the effects of linear detector length 
on the existence of ZF solutions for f. To be specific, we will
require that ZF solutions exist for all  and
all  .
Since the ZF detector exists if and only if  is
invertible then this is equivalent to requiring H to have full
column rank. We recognize that a necessary condition for H to have
full column rank is that H must be “tall” in the sense
that it must have at least as many rows than columns. We note that the
tall condition is not sufficient for full column rank in the same sense
that length conditions are not sufficient for the existence of zero-forcing
FSEs for single user equalization.
Inspection of the individual users’ sub-system matrices  allows
us to express the number of columns per user as
.gif)
where  is
a term representing the effects of user asynchronism on H. To be
precise,  is
equivalent to the condition that the user
contributes an additional column to the system matrix by having an additional
symbol in the observation interval when compared to a synchronized user.
As an example, Figure 2 shows a two user asynchronous
scenario where  .
Note that the overlap in the bits is due to the multipath channel effects
when L>1.
Figure 2. Example of asynchronous users.
In the synchronous case  and
in the asynchronous case 
is a function of  .
The exact expression for is
not required to develop the necessary length condition.
It follows directly from (8) and the “tall” condition necessary
for full column rank may be stated as
.gif)
We consider the implications of this result in the following examples.
Back to top of page
Examples
- Consider the conventional case with no multipath (L=1),
chip-rate sampling (P=1), and synchronous users
 .
If the number of users equals the spreading gain (K = N)
then (9) reduces to
which is satisfied when  (or
any positive integer multiple of N). This agrees with the well
known result for decorrelating detectors [4]
where the decorrelating detector is realized as a bank of code matched
filters X followed by the inverse of the K x
K matrix R of cross-correlations between spreading codes,
i.e.,  .
Since  has
dimensions K x
N, it follows that the decorrelating detector is equivalent
to an N-tap, chip-spaced, linear filter for each user. If the
spreading codes are linearly independent then the decorrelating detector
achieves perfect symbol recovery.
- Consider the previous case with the addition of multipath channels
(L>1). When the number of users equals the spreading gain
(9) reduces to
which implies that no finite value for  can
cause H to be tall. The failure to satisfy this necessary condition
implies that FIR ZF detectors do not exist for K = N
synchronous users in the presence of multipath interference with chip
rate sampling.
- Consider the first case with the addition of user asynchronism such
that
 for
at least one user. When the number of users equals the spreading gain
(9) reduces to
which implies that no finite value for can
cause H to be tall. Again, the failure to satisfy this necessary
condition implies that FIR ZF detectors do not exist for K
= N asynchronous users with chip rate sampling.
- Consider the case of an oversampling receiver with P = 2
and K = 2N – 1. Note that the number of users
is greater than the spreading gain. Assume further that the users are
asynchronous. In this case, we can manipulate (9) to write
where  .
Observe that even for worst case asynchronism, is
finite for  .
The next section verifies these results with simulations and demonstrates
that, in addition to the aforementioned desirable properties in a noiseless
scenario, the fractionally sampled receiver may provide improved performance
in the presence of additive channel noise as well.
Back to top of page
Simulations
Figure 3 shows a comparison between MMSE solutions
for and
 spaced
linear detectors in a noiseless, synchronous communication scenario with
multipath interference. To provide a fair comparison, the channel delay
spread is fixed at  which
implies that L = 14 and L = 28 in the and
spaced simulations, respectively. The transmit filter is assumed to have
square root raised cosine spectrum with excess bandwidth ß = 0.2
and the propagation channel coefficients are random. The receiver input
filter is an ideal low pass filter with cutoff  .
The length N = 8 spreading codes are also random (with elements
in {–1, +1}). The linear detector length in both cases is  which
satisfies the length in (9) for the spaced
receiver.
Figure 3. MMSE by user and delay for
and
spaced linear detectors. Simulation parameters: channel support ,
spreading gain N = 8, K = 8 equal power users, .
Observe that the spaced
linear detector is able to perfectly recover the symbols of all users
at all delays implying that complete cancellation of both multiple access
interference and multipath interference is achieved since the system matrix
is full column rank and ZF solutions exist for all users at all possible
delays. The spaced
detector exhibits considerably worse performance since the system matrix
is not full column rank for any finite choice of when
K = N and L>1.
Note that the MMSE solutions may be indexed by user and
delay, i.e.,  where
y(n) is the output of the appropriate MMSE linear detector.
We will use this notation in the next simulation.
Figure 4 is a Monte Carlo comparison between
and
spaced linear detectors in the presence of AWGN with synchronous and asynchronous
equal power users. The asynchronous users each have uniformly distributed
delay over  .
As in the first simulation, MMSE is calculated for all users at all possible
delays but in this case the delay-optimal MMSE, given by  ,
is selected for each user and then averaged over all users and 500 experiments.
The noise variance  .
The linear detector length is
varied from 2 to 100. All other parameters are as in the first simulation.
Figure 4. Averaged delay-optimal MMSE for (solid
lines) and spaced
(dashed lines) linear detectors with synchronous and asynchronous equal
power users. Simulation parameters: channel support ,
spreading gain N = 8.
This simulation provides evidence indicating that
spaced receivers may achieve better MMSE performance than
spaced receivers in the presence of additive channel noise, but only for
larger values of .
The relatively poor performance of the fractionally spaced receiver for
small values of
is due to the fact that, for a fixed value of ,
the observation interval of the
spaced receiver is half that of the
spaced receiver. In this simulation, values of  cause
the
spaced receiver’s observation interval to not contain even one full
bit (including multipath) from a synchronous user. Also note that this
simulation suggests that the effects of asynchronism on averaged delay-optimal
MMSE performance are almost negligible for both
and
spaced receivers.
Back to top of page
Conclusions
In this paper we have explored the concept of fractional
sampling to improve the performance of linear multiuser detectors for
DS-CDMA communication systems. The analysis has shown that fractionally
sampled receivers of sufficient length satisfy a necessary condition for
the existence of zero-forcing solutions under conditions where no FIR
solution exists for chip rate sampled receivers. Furthermore, simulations
in the presence of additive channel noise indicate that fractionally sampled
receivers may also offer improved MMSE performance over chip rate receivers.
The “robustness to timing phase errors property”
of single user FSEs was not explored for fractionally sampled multi-user
detectors and remains an open research topic. Necessary and sufficient
conditions for the existence of FIR zero-forcing solutions in DS-CDMA
communication systems with arbitrary asynchronism and multipath channels
are also a topic of current research.
Back to top of page
References
- R.D. Gitlin and S.B. Weinstein, “Fractionally-spaced
equalisation: An improved digital transversal equaliser,” Bell System
Technical Journal, vol. 60, pp. 275–96, Feb. 1981.
- S. Gollamudi, et al, “On the
dimensional limitations of linear multiuser detection,” in Proc. Thirty-Fifth
Annual Allerton Conference on Communication, Control, and Computing (Monticello,
IL), pp. tbd, Sep. 25–29, 1998.
- C.R. Johnson Jr., et al, “Blind
equalization using the constant modulus criterion: A review,” Proceedings
of the IEEE, vol. 86, no. 10, pp. 1927–50, Oct. 1998.
- R. Lupas and S. Verdu, “Linear
multi-user detectors for synchronous code-division multiple-access channels,”
IEEE Trans. on Information Theory, vol. 35, pp. 123–36, Jan. 1989.
- U. Madhow and M.L. Honig, “MMSE interference suppression for direct-sequence spread-spectrum CDMA,” IEEE Trans. on Communications, vol. 42, no. 12, pp. 3178–88, Dec. 1994.
- U. Madhow, “Signal processing for interference suppression in direct-sequence CDMA systems,” in Proc. International Conference on Acoustics, Speech and Signal Processing (Atlanta, GA), pp. 1065–68, May 1996.
- M. Shafi and D.J. Moore, “Further results on adaptive equalizer improvements for 16 QAM and 64 QAM digital radio,” IEEE Trans. on Communications, vol. 34, no. 1, pp. 59–66, Jan. 1986.
- J.R. Treichler, I. Fijalkow, and C.R. Johnson, Jr., “Fractionally spaced equalizers: How long should they really be?,” Signal Processing Magazine, vol. 13, pp. 65–81, May 1996.
Footnotes
- Supported in part by NSF grants MIP-9509011,
ECS-9528363, and ECS-9811297 and Applied Signal Technology.
|
