Enhancing CDMA multiuser detection by constraining soft decisions

CROSS-REFERENCE TO RELATED APPLICATIONS

P-0001[0001] This application is related to U.S. patent application Ser. No. 09/917,837, filed Jul. 31, 2001, which is assigned to the assignee of the present patent application and whose disclosure is incorporated herein by reference.

FIELD OF THE INVENTION

P-0002[0002] The present invention relates generally to digital signal processing, and specifically to methods and systems for simultaneous reception and processing of signals from multiple transmitters sharing a common frequency band using code-division multiple access (CDMA).

BACKGROUND OF THE INVENTION

P-0003[0003] CDMA is widely used in cellular and other wireless systems for multiplexing communications among multiple users on a common frequency band. In direct-sequence (DS) CDMA, the transmitter multiplies each user's signal by a distinct code waveform. The code waveforms of the different users have the form of “pseudo-noise” (PN) sequences, also known as spreading codes, and are chosen so as to be as much as possible mutually orthogonal. The receiver receives a composite signal made up of the sum of all of the users' signals, which overlap in time and frequency. To recover the individual signal of a given user, the receiver correlates the composite signal with that user's distinct code.

P-0004[0004] Multiple access interference (MAI) limits the capacity and performance of DS-CDMA systems. MAT results from the lack of complete orthogonality between the spreading codes, due to random time offsets between the signals of different users, for example. MAI becomes increasingly problematic as the number of interfering users and their power increases, particularly when there are power imbalances among the users. These imbalances typically result from differences in distance between the users and the base station, as well as from fading and other factors that affect signal power. The problems caused by MAI have led a number of groups to develop multi-user detection techniques, in which information about multiple users and their respective code waveforms is used jointly to better detect each individual user. A survey of these techniques is presented by Moshavi in “Multi-User Detection for DS-CDMA Communications,” <i>IEEE Communications Magazine </i>(October, 1996), pages 124-136, which is incorporated herein by reference.

P-0005[0005] To formulate the multi-user detection problem, we consider a CDMA receiver that receives signals from K users. The received complex-envelope baseband signal x(t) is a superposition of the users' individual signal waveforms, including channel distortion and additive noise n(t): <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><msub><mi>h</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>*</mo><mrow><msub><mi>ξ</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>+</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00001.TIF" id="EMI-M00001" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20040101034A1-20040527-M00001.NB" /></attachments></maths>

P-0006[0006] Here “*” denotes convolution, and h_k(t) is the impulse response of the kth user channel (including delay, attenuation, multipath and filtering effects). In the derivation that follows, n(t) is assumed to be Gaussian with mean zero and without correlation between successive noise samples.

P-0007[0007] The kth user's signal waveform is given by: <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>ξ</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><msub><mi>b</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>p</mi><mi>Tb</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>mT</mi><mi>b</mi></msub></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00002.TIF" id="EMI-M00002" he="24.01245" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20040101034A1-20040527-M00002.NB" /></attachments></maths>

P-0008[0008] In this equation, b_k(m) is the mth symbol transmitted by the kth user, wherein b_kis selected from a predefined constellation (or alphabet) A. In phase-shift keyed (PSK) modulation, the alphabet set lies on the unit circle in the complex plane. For example, in quadrature phase shift keying (QPSK), A={−1, −j, 1, j}. For binary phase shift keying (BPSK), which is currently the most common modulation scheme in current cellular systems, b_kis a bit selected from A={−1,1}. T_bis the symbol duration, and p_T(t) is a rectangular pulse with unity value in tε[0,T), and zero elsewhere. c_k(t) is a complex-valued PN spreading waveform, with a chip period T_c=T_b/N, wherein N is the spreading response of the DS modulation: <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><mrow><mfrac><mn>1</mn><msqrt><mn>2</mn></msqrt></mfrac><mo></mo><mrow><mo>[</mo><mrow><mrow><msubsup><mi>γ</mi><mi>k</mi><mrow><mo>(</mo><mi>I</mi><mo>)</mo></mrow></msubsup><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>j</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><msubsup><mi>γ</mi><mi>k</mi><mrow><mo>(</mo><mi>Q</mi><mo>)</mo></mrow></msubsup><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>]</mo></mrow></mrow><mo></mo><mrow><msub><mi>p</mi><mi>Tc</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>iT</mi><mi>c</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00003.TIF" id="EMI-M00003" he="29.0304" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20040101034A1-20040527-M00003.NB" /></attachments></maths>

P-0009[0009] γ_k^(I)(i) and γ_k^(Q)(i) are independently drawn from {−1,1} with uniform distribution.

P-0010[0010] The multi-user detection problem can be stated as follows: Let the received signal x(t) be sampled, and assume that the impulse responses h_k(t) and the spreading waveforms c_k(t) are known. Now estimate the symbols b_k(m) from the samples x(t) for all k and m. For the sake of simplicity in framing the problem, it is assumed that the impulse responses of the channels can be expressed as complex scalars h_k, that the user signals are mutually synchronized, and that the samples are taken at mid-chip, at a sampling rate equal to the chip rate (i.e., N samples per symbol). It is possible to relax some of these assumptions and still achieve multi-user detection, as described hereinbelow.

P-0011[0011] The symbols transmitted by the K users at symbol interval m can be written as a K-1 real vector:

b(m):=(b₁(m), . . . , b_K(m))^T  (4)

P-0012[0012] The samples taken during the mth symbol interval can be arranged as a N-1 complex vector x(m). Rearranging equations (1) and (2) in similar vector form gives the following expression:

x(m)=S(m)b(m)+n(m)   (5)

P-0013[0013] Here n(m) is a N-1 complex vector of noise samples. S(m) is a complex N×K matrix, whose kth column is a signature vector s_k(m) representing the “symbol signature” of the kth user during the mth symbol interval. The elements of the signature vectors s_k(m) are samples of the following waveform:

<i>s</i>_k(<i>t; m</i>):=<i>h</i>_k<i>c</i>_k(<i>t</i>), <i>mT</i>_b<i>≦t</i>≦(<i>m+</i>1)<i>T</i>_b  (6)

P-0014[0014] Given the known elements of x(m) and S(m), in order to solve the multi-user detection problem it is necessary to find the elements of b(m) that best satisfy equation (5). An optimal, maximum-likelihood solution to this problem was framed by Verdu in “Minimum Probability of Error for Asynchronous Gaussian Multiple-Access Channels,” <i>IEEE Transactions on Information Theory </i>32:1 (January, 1986), pages 85-96, which is incorporated herein by reference. According to this solution, for each m, we find the elements of b within the applicable constellation A that minimize ∥x−Sb∥². (For brevity, here and below, we write simply b, S and x to represent b(m), S(m) and x(m).) Although optimal, this detector is usually impractical, since it requires an exhaustive search over all possible bεA^K.

P-0015[0015] As a less costly (though suboptimal) alternative, Lupas and Verdu proposed a decorrelating detector in “Linear Multi-User Detectors for Synchronous Code-Division Multiple Access Channels,” <i>IEEE Transactions on Information Theory </i>35:1 (January, 1989), pages 123-136, which is also incorporated herein by reference. The decorrelating detector finds a vector {tilde over (b)} that minimizes ∥x−Sb∥²over bεC^K, wherein C is the complex plane. The “soft decision” vector {tilde over (b)} is projected onto the constellation A^Kto arrive at the hard decision output {circumflex over (b)}. For BPSK modulation, the elements {circumflex over (b)}_kare given simply by the sign of the real part of the corresponding elements {tilde over (b)}_k. Assuming K≦N and full column-rank S, the soft decision solution is given by:

{tilde over (b)}=(S^HS)⁻¹S^Hx   (7)

P-0016[0016] wherein S^His the conjugate transpose of S.

P-0017[0017] The decorrelating detector has been found to provide substantial performance responses over conventional single-user detection, with significantly lower computational complexity than the maximum-likelihood detector proposed previously. It performs well even in the presence of substantial power imbalances among the users. It still entails a substantial computational burden, however, in inverting the matrix S^HS.

P-0018[0018] A number of different solutions have been proposed in order to improve multi-user detection performance. For example, Duel-Hallen suggests combining the decorrelating detector with decision feedback, in “Decorrelating Decision-Feedback Multiuser Detector for Synchronous Code-Division Multiple-Access Channel,” <i>IEEE Transactions on Communications </i>41:2 (February, 1993), pages 285-290, which is incorporated herein by reference. This detector generates decisions {circumflex over (b)}_kiteratively, working down from the stronger user signals to the weaker signals. The decisions made with respect to the stronger users are used in forming decisions for the weaker ones. The decision-feedback detector has been found to outperform the original decorrelating detector as long as the bit-error rate (BER) is not too high, and reliable estimates of the channel responses h_kare available.

P-0019[0019] Various other technique have been suggested in the patent literature for canceling interference among the signals received from multiple CDMA users. For example, U.S. Pat. No. 5,644,592, to Divsalar et al., whose disclosure is incorporated herein by reference, describes a method of parallel interference cancellation, which estimates and subtracts out all of the interference for each user in parallel. U.S. Pat. Nos. 5,363,403, 5,553,062, 5,719,852 and 6,014,373, all to Schilling et al., whose disclosures are also incorporated herein by reference, describe methods for solving the (S^HS)⁻¹matrix using a fast polynomial expansion.

P-0020[0020] Multi-user detection methods generally require that the channel responses h_kbe known. Typically, the channel responses are not known a priori, but must rather be determined by a suitable channel estimator in the receiver. When short-period, repetitive spreading codes C_k(t) are used, subspace-based signal array processing techniques can be used to solve the channel estimation problem. Such techniques are described, for example, by Madhow in “Blind Adaptive Interference Suppression for Direct-Sequence CDMA,” <i>Proceedings of the IEEE </i>86:10 (October, 1998), pages 2049-2069, which is incorporated herein by reference.

P-0021[0021] Commercial CDMA standards, such as IS-95, however, use PN spreading codes whose periods are so long that they can be considered purely random for reasonable observation times, rather than repetitive. To address this problem, Torlak et al. offer an iterative approach in “Blind Estimation of FIR Channels in CDMA Systems with Aperiodic Spreading Sequences,” <i>Proceedings of the </i>31<i>st Asilomar Conference on Signals, Systems </i>&amp; <i>Computers </i>(Pacific Grove, California, November, 1997), which is incorporated herein by reference. According to this approach, the receiver alternately estimates the channel responses and, based on these responses, estimates the transmitted signals, until the estimated signals converge. Weiss et al., in “Channel Estimation for DS-CDMA Downlink with Aperiodic Spreading Codes,” <i>IEEE Transactions on Communications </i>47:10 (October, 1999), pages 1561-1569, which is likewise incorporated herein by reference, describe a sub-space approach for finding an initial estimate of the channel responses, followed by an iterative calculation similar to that described by Torlak et al.

SUMMARY OF THE INVENTION

P-0022[0022] Preferred embodiments of the present invention provide simpler, more efficient methods and systems for estimating channel response and detecting CDMA multi-user symbols, particularly PSK symbols.

P-0023[0023] In some preferred embodiments of the present invention, a CDMA receiver performs multi-user detection using a model that inherently incorporates prior knowledge that the symbols have a fixed magnitude, i.e., that |b_k| is constant for all symbols in the constellation. As described above, decorrelating detectors known in the art calculate complex-valued soft decisions ({tilde over (b)}_k), and then project these values onto the actual constellation of the user signals to generate the corresponding hard decisions ({circumflex over (b)}_k). In the case of PSK modulation, however, the constellation consists exclusively of values that can be expressed as b_k=e^jφ^_k, so that {circumflex over (b)}_kmust lie on the unit circle.

P-0024[0024] Therefore, in preferred embodiments of the present invention, the soft decisions themselves are constrained a priori to a fixed magnitude in the complex plane, typically to the unit circle. This constraint reduces by half the number of unknown parameters that must be solved for, by eliminating the need to find the magnitude of {tilde over (b)}_k. Only the phase φ_kneed be determined. Application of the constraint thus simplifies the decorrelation calculation, improves detection performance and doubles the number of users that can be detected simultaneously. This constrained decorrelation approach is applicable to any type of PSK modulation, and may thus be applied to real-valued BPSK constellations, as well. It can also be used to extract signals from complex signatures that are introduced by factors other than PN spreading waveforms, such as the complex response of multiple receiving antennas used for spatial diversity in wireless communications.

P-0025[0025] In some of these preferred embodiments, the receiver implements an alternating phase search (ALPS) method to iteratively determine the phases φ_kof the individual user signals. This method preferably uses decisions made with respect to strong user signals to improve the detection of weaker user signals, and then returns to cycle through the user signals repeatedly until convergence is reached. ALPS provides a reliable, computationally-inexpensive method that generally achieves multi-user detection with greater accuracy than methods known in the art.

P-0026[0026] There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for multi-user detection, including:

P-0027[0027] receiving a complex input signal due to a superposition of waveforms encoding symbols in a constellation of fixed magnitude and variable phase, which symbols are transmitted respectively by a plurality of transmitters in a common frequency band;

P-0028[0028] sampling the complex input signal at sampling intervals over the duration of an observation period to provide a sequence of complex samples;

P-0029[0029] processing the sequence of complex samples to determine soft decision values corresponding to the symbols transmitted by the plurality of the transmitters in the observation period, while constraining the soft decision values to a circle in a complex plane; and

P-0030[0030] projecting the soft decision values onto the constellation to estimate the transmitted symbols.

P-0031[0031] Typically, the waveforms include code-division multiple access (CDMA) waveforms transmitted by the plurality of the transmitters, and the symbols transmitted by the transmitters are modulated by respective spreading codes to generate the waveforms, wherein the spreading codes may include complex-valued codes. The constellation of the symbols typically includes a phase-shift keyed (PSK) constellation. Preferably, constraining the soft decision values includes projecting the soft decision values onto a unit circle in the complex plane. In a preferred embodiment, the PSK constellation includes a binary PSK (BPSK) constellation, and projecting the soft decision values includes taking respective signs of the soft decision values in order to reach a hard decision with respect to the corresponding symbols.

P-0032[0032] Preferably, the observation period has a duration substantially equal to a single symbol period, during which each of the transmitters transmits a single one of the symbols. Alternatively, the observation period has a duration during which at least some of the transmitters transmit more than a single one of the symbols.

P-0033[0033] Preferably, processing the sequence of complex samples includes determining a phase angle of each of the soft decision values in the complex plane so as to minimize a cost function indicative of a difference between the soft decision values and the transmitted symbols. Typically, the samples are related to the transmitted symbols by an expression having a form x=Sb+n, wherein x is a vector of the samples, b is a vector having elements corresponding to the values of the symbols, S is a matrix including columns corresponding to respective complex signatures of the plurality of the transmitters, and n is a vector corresponding to noise components in the samples, and determining the phase angle includes inverting the expression to determine the phase angle φ_kof each of the elements of b. Preferably, inverting the expression includes finding the phase angle φ_kof each of the elements of b that minimizes a norm given by ∥x−Sb∥².

P-0034[0034] Additionally or alternatively, inverting the expression includes decomposing S to yield an upper-triangular matrix T that satisfies an equation z=Th+ν₁, wherein z and ν₁are vectors obtained by applying a unitary transformation to x and n, respectively, finding an initial phase angle for each the elements of b iteratively beginning from a final one of the elements so as to solve the equation, and using the initial phase angle for each of the elements to initialize an alternating phase search for the soft decision values that will minimize the norm.

P-0035[0035] In a preferred embodiment, determining the phase angle includes performing an alternating phase search over all the estimated transmitted symbols so as to determine the soft decision values that minimize the cost function. Preferably, performing the alternating phase search includes computing the phase angle for one of the symbols transmitted by a first one of the transmitters, substituting the computed phase angle into a vector of the soft decision values, using the vector with the substituted phase angle to compute the phase angle of another one of the symbols transmitted by a second one of the transmitters, and repeating the steps of substituting the computed phase angle and using the vector to compute the phase angle of another one of the symbols over all the transmitters until the soft decision values have converged.

P-0036[0036] There is also provided, in accordance with a preferred embodiment of the present invention, a multi-user receiver, including:

P-0037[0037] input circuitry, coupled to receive a complex input signal due to a superposition of waveforms encoding symbols in a constellation of fixed magnitude and variable phase, which symbols are transmitted respectively by a plurality of transmitters in a common frequency band, and to sample the complex input signal at sampling intervals over the duration of an observation period to provide a sequence of complex samples; and

P-0038[0038] multi-user detection circuitry, coupled to receive and process the sequence of complex samples so as to determine soft decision values corresponding to the symbols transmitted by the plurality of the transmitters in the observation period, while constraining the soft decision values to a circle in a complex plane, and to project the soft decision values onto the constellation in order to estimate the transmitted symbols.

P-0039[0039] The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which:

BRIEF DESCRIPTION OF THE DRAWINGS

P-0040[0040]FIG. 1 is a schematic, pictorial illustration of a multi-user communication system, in accordance with a preferred embodiment of the present invention;

P-0041[0041]FIG. 2 is a block diagram that schematically illustrates a transmitter operated by a user in the system of FIG. 1;

P-0042[0042]FIG. 3 is a block diagram that schematically illustrates a receiver with multi-user detection capability, in accordance with a preferred embodiment of the present invention;

P-0043[0043]FIG. 4 is a flow chart that schematically illustrates a method for multi-user detection based on alternating phase searching (ALPS), in accordance with a preferred embodiment of the present invention;

P-0044[0044]FIG. 5 is a block diagram that schematically illustrates a multi-user detection circuit based on alternating phase searching (ALPS), in accordance with a preferred embodiment of the present invention;

P-0045[0045]FIG. 6 is a flow chart that schematically illustrates a method for initializing a multi-user detection process, in accordance with a preferred embodiment of the present invention;

P-0046[0046]FIG. 7 is a block diagram that schematically illustrates aspects of signal generation and reception in a multi-user communication system;

P-0047[0047]FIG. 8 is a flow chart that schematically illustrates a method for channel estimation in a multi-user communication system, in accordance with a preferred embodiment of the present invention;

P-0048[0048]FIG. 9 is a block diagram that schematically illustrates circuitry for channel estimation and tracking, in accordance with a preferred embodiment of the present invention; and

P-0049[0049]FIG. 10 is a flow chart that schematically illustrates a method for channel estimation and multi-user detection based on alternate-searching likelihood maximization (ASLM), in accordance with a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS SYSTEM OVERVIEW

P-0050[0050]FIG. 1 is a schematic, pictorial illustration of a wireless communication system <b>20</b>, typically a cellular system, in accordance with a preferred embodiment of the present invention. A base station <b>22</b> transmits downlink signals to a plurality of users <b>24</b>, and receives uplink signals from the users in return. The signals are modulated using a DS-CDMA scheme, with PSK modulation, as described in the Background of the Invention. In order to separate and process the signals that it receives from multiple users <b>24</b>, base station <b>22</b> employs a novel detection scheme using a constrained statistical model, as described in detail hereinbelow.

P-0051[0051]FIG. 2 is a block diagram that schematically illustrates elements of a transmitter <b>26</b> operated by users <b>24</b> in system <b>20</b>. The operation of this transmitter is represented mathematically by equations (2) and (3) above. Each symbol b(t) to be transmitted is multiplied by a complex PN spreading waveform, with different real (I) and imaginary (Q) parts C_I(t) and C_Q(t), respectively. In the general case of PSK, b(t) has real and imaginary parts, as well, b_I(t) and b_Q(t). In the specific case of real-valued modulation, such as BPSK, b_I(t)=b_Q(t). The output of transmitter <b>26</b> is a complex-valued signal b(t)[C_I(t)+jC_Q(L)]e^jω^₀^t, wherein ω₀is the carrier frequency.

P-0052[0052]FIG. 3 is a block diagram that schematically illustrates a receiver <b>28</b> used in base station <b>22</b> for demodulating and decoding the signals from transmitters <b>26</b>, in accordance with a preferred embodiment of the present invention. The signals are received over the air and downconverted to baseband by a radio receiver front end <b>30</b>. The baseband signals are then digitized by an analog/digital converter (ADC) <b>32</b>. The design and operation of these elements are well known in the art, as are those of other elements typically used in base station receivers, which would normally be included in receiver <b>28</b> but are omitted here for the sake of brevity.

P-0053[0053] Front end <b>30</b> and ADC <b>32</b> provide an input to a channel estimator <b>36</b> and to a multi-user detection block <b>38</b> that is substantially of the form given by equation (1). The channel estimator estimates the respective impulse responses (or channel responses) h_k(t) of the user channels. Multi-user detection block <b>38</b> uses the channel response estimates to processes the superposed signal x(t) of all of users <b>24</b>, modulated by the respective PN complex signatures of the users, in order to estimate an individual symbol stream {circumflex over (b)}_k(m) for each user. The estimated user symbol streams generated by multi-user detection block <b>38</b> are input to an individual data processing block <b>40</b> for each user. This block performs further data decoding and control channel processing, as is known in the art. The operation of blocks <b>40</b> is outside the scope of the present invention.

P-0054[0054] The novel operations of both channel estimator <b>36</b> and multi-user detection block <b>38</b> are described in detail hereinbelow. Typically, estimator <b>36</b> and block <b>38</b> comprise one or more digital signal processor circuits, comprising a single dedicated chip or a group of chips that are configured to carry out the methods described below. Alternatively or additionally, some or all of the functions of estimator <b>36</b> and block <b>38</b> may be carried out in software on a suitable general-purpose microprocessor. Still further alternatively or additionally, certain digital processing functions of estimator <b>36</b> and block <b>38</b> that are described below may equivalently be accomplished in the analog domain using suitable matched filters, as are known in the art. All these various implementations will be apparent to those skilled in the art and are considered to be within the scope of the present invention.

P-0055[0055] It should be noted that channel estimators in accordance with the principles of the present invention may also be used in other receivers and in conjunction with multi-user detectors of other types, and not only with multi-user detection block <b>38</b>. Similarly, the multi-user detection block may receive its channel response estimates from sources other than channel estimator <b>36</b>, including other types of channel estimators, as are known in the art.

Multi-User Detection by Constraining Soft Decisions to the Unit Circle

P-0056[0056] Multi-user detection block <b>38</b> solves equation (5), above, by constraining the soft decision values {tilde over (b)}_kto the unit circle. This constraint is equivalent to substituting:

b_k=e^jφ^_k  (8)

P-0057[0057] The model of equation (8) permits equation (5) to be restated as follows in terms of a cost function f(φ) and a vector φ of the phases of the soft decision values:

f(φ)=∥x−<i>Se</i>^jφ∥²

e^jφ=(e^jφ^₁, . . . , e^jφ^_k)^T  (9)

P-0058[0058] The soft decision values {tilde over (b)}_kare then determined by minimizing f(φ) over φ.

P-0059[0059] Because {tilde over (b)} is constrained to the unit circle, the number of real parameters that must be solved for in equation (8) is only half the number used in methods known in the art, as exemplified by the more general equation (5). Detection block <b>38</b> must estimate only the phase angles of {tilde over (b)}_k, and not the amplitudes. In other words, it is evident from this analysis that, at least where PSK modulation is concerned, methods known in the art use an over-parameterized model for their solution. Over-parameterization tends to increase estimation error, and the inventors have indeed found that in most cases, the constrained detector implemented in block <b>38</b> achieves a lower bit-error rate (BER) than do decorrelating detectors known in the art. The reduction in the number of parameters also reduces the computational cost of the detector geometrically, so that the cost of implementing block <b>38</b> is considerably less than that of a conventional decorrelating detector for the same number of users. On the other hand, because the number of real unknowns in equation (8) is reduced by half, the usual constraint in decorrelating detectors that the number of users K cannot exceed N is now relaxed to K≦2N, permitting receiver <b>28</b> to handle twice the number of users as could be detected by a conventional decorrelating detector with the same spreading gain.

P-0060[0060]FIG. 4 is a flow chart that schematically illustrates a method for multi-user detection implemented by block <b>38</b>, in accordance with a preferred embodiment of the present invention. The method performs an alternating phase search (ALPS) to iteratively reduce the cost function f along each of the axes {φ_k}. Rearranging equation (9), it can be shown that at any step of the iteration, the value of φ_kthat will minimize f is given by:

φ_k=angle(s_k^Hx^(k))   (10)

P-0061[0061] wherein s_kis the k-th column of S, and x^(k)is defined by:

x^(k)=x−<i>Se</i>^jφ^_k  (11)

P-0062[0062] To begin the ALPS procedure, the entries of φ (i.e., the estimated symbol values of b) are set to some initial values, at an initialization step <b>50</b>. A useful method for initialization is described below with reference to FIG. 6. The estimated user signals are preferably ordered according to the approximate strengths of the signals, from weakest (x₁) to strongest (x_K). It is also useful to introduce and initialize a residual vector r, given by:

r=x−S{tilde over (b)}wherein {tilde over (b)}=e^jφ  (12)

P-0063[0063] Detection block <b>38</b> then iterates through the users, preferably beginning with the strongest user signal (user K), finding for each user k the angle φ_kthat will minimize f, as given by equation (10), at an angle determination step <b>52</b>. After each angle φ_kis calculated, the new value is substituted into {tilde over (b)}, at a substitution step <b>54</b>, for use in calculating φ_kfor the subsequent users in the iteration. The residual vector r is updated at the same time. Using the definitions of equations (10), (11) and (12), the computations of steps <b>52</b> and <b>54</b> can be expressed as follows:

{tilde over (b)}_k←ω(s_k^Hr+∥s_k∥²{tilde over (b)}_k)

r←r+s_k({tilde over (b)}_k^(old)−{tilde over (b)}_k)   (13)

P-0064[0064] Here the operator ω( ) projects its argument onto the unit circle. {tilde over (b)}_k^(old)represents the value of {tilde over (b)}_kprior to the current update.

P-0065[0065] After this procedure has been carried out for all the users, detection block <b>38</b> checks the results to determine whether the computation has converged, at a convergence checking step <b>56</b>. Convergence may be inferred, for example, when the differences between the previous and current soft decision values ({tilde over (b)}_k) drop below a predetermined threshold. Until convergence is reached, block <b>38</b> repeats the iteration of steps <b>52</b> and <b>54</b>.

P-0066[0066] Once the soft decision values have converged, block <b>38</b> converts them to the nearest elements of the constellation alphabet A, in a hard decision step <b>58</b>. At this step, the detection block iterates through the user soft decision values, from the strongest to the weakest, to determine the hard decision values:

{circumflex over (b)}_k←α(s_k^Hr+∥s_k∥²{tilde over (b)}_k)

r←r+s_k({tilde over (b)}_k−{circumflex over (b)}_k)   (14)

P-0067[0067] Here the operator α( ) projects the soft decisions onto the nearest alphabet members, taking into account the residual r (which is adjusted after each step in the iteration). The final residual gives an estimate of the noise vector {circumflex over (n)}.

P-0068[0068]FIG. 5 is a block diagram showing a part of detection block <b>38</b>, including a circuit suitable for carrying out the method of FIG. 4, in accordance with a preferred embodiment of the present invention. Current soft decision values {tilde over (b)}_kare held in respective registers <b>60</b>. At each iteration of the procedure, a spreader <b>62</b>, comprising a bank of multipliers <b>64</b>, multiplies each soft decision value by the respective entries of matrix S, except for the soft decision value for user k, which is currently being updated. The choice of k at each iteration is determined by a bank of switches <b>66</b>, as shown in the figure. An adder <b>68</b> sums the products of multipliers <b>64</b> to give the current value of s_ke^jφ^_k. A second adder <b>70</b> subtracts this current value from the received signal x(t) to give x^(k)(t), as defined above.

P-0069[0069] A matched filter <b>72</b> holding the current values of the elements of matrix S multiplies x^(k)(t) to give the result s_k^Hx^(k)derived above. A projector <b>74</b> projects this result onto the unit circle to give the new estimate of the soft decision value {tilde over (b)}_k=e^jφ^_k. A multiplexer <b>76</b> enters this value into the appropriate register <b>60</b>, and the circuit then iterates to user k+1, thus continuing until done.

P-0070[0070]FIG. 6 is a flow chart that schematically illustrates a method for initializing the estimated signal values at step <b>50</b> of the ALPS procedure, in accordance with a preferred embodiment of the present invention. Substantially any suitable method may be used to set the initial values of b, but the inventors have found the method of FIG. 6 to give generally superior results. The method begins by recasting equation (8) in terms of an upper triangular matrix T, using QR factorization of matrix S, as is known in the art, at a signal recasting step <b>80</b>. The factorization is preferably performed using successive Givens rotations or Householder transformations of the matrix, as described, for example, by Golub and Van Loan in <i>Matrix Computations </i>(Johns Hopkins Series in Mathematical Sciences, 1996), which is incorporated herein by reference. Prior to factorization, the columns of the matrix are preferably ordered according to the approximate strengths of the signals received from the respective users, so that the first column corresponds to the weakest user, and the last column to the strongest.

P-0071[0071] The QR decomposition at step <b>80</b> gives the expression:

S=QT₁  (15)

P-0072[0072] wherein Q is a N×N unitary matrix, and T₁is a N×K matrix having the structure <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mrow><mrow><msub><mi>T</mi><mn>1</mn></msub><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mi>T</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math><img file="US20040101034A1-20040527-M00004.TIF" id="EMI-M00004" he="21.12075" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00004" attachment-type="nb" file="US20040101034A1-20040527-M00004.NB" /></attachments></maths>

P-0073[0073] in which T is a K×K upper-triangular matrix. Q can be partitioned into Q=|Q₁Q₂|, wherein Q₁is a N×K matrix having a column span equal to the column span of S, and Q₂is its complement. In practice, explicit computation of Q is preferably avoided, by applying the Givens rotations to the signal vector x, as well as to S.

P-0074[0074] Substituting the representation of equation (15) into equation (5), we are left with the following model:

<i>z</i>=Tb+ν₁  (16)

P-0075[0075] wherein z:=Q₁^Hx, and ν₁:=Q₁^Hn. Thus, since Q₁is unitary, the transformed noise vector ν₁remains Gaussian and uncorrelated in character.

P-0076[0076] Because T is upper-triangular, the last component of {circumflex over (b)} can be determined simply, at a last element determination step <b>82</b>, by:

{circumflex over (b)}_k=α(Z_K/T_KK)   (18)

P-0077[0077] Assuming that the columns of S were properly ordered at step <b>80</b>, this step should give the symbol value for one of the strongest user signals, so that the likelihood of error in determining {circumflex over (b)}_kis relatively small.

P-0078[0078] The decision value found at step <b>82</b> is substituted back into equation (16) to obtain a dimensionally-reduced model, at a row and column elimination step <b>84</b>:

z^(K-1)=T^(K-1)b^(K-1)+ν₁^(K-1)  (18)

P-0079[0079] Here b^(K-1)contains the first K-1 components of b, T^(K-1)contains the upper-left (K-1)×(K-1) components of T, and the K-1 components of z^(K-1)are given by z_i^(K-1)=z_i^(K)−T_iK{circumflex over (b)}_K. The model of equation (18) is again triangular in structure. Thus, it is now possible to repeat steps <b>82</b> and <b>84</b>, in order to find and eliminate {circumflex over (b)}_k-1. The method then proceeds iteratively in this manner until all of the elements of {circumflex over (b)} have been determined.

P-0080[0080] Having computed z and T in the model of equation (16), it is possible to use these values in place of x and S in the ALPS method of FIG. 4. Because of the triangular structure of T, the computational cost of the ALPS procedure is generally reduced.

P-0081[0081] The ALPS method of FIG. 4 may be applied to advantage to BPSK modulation (in which A=±1), which is the most commonly-used modulation scheme in currently-deployed CDMA systems. In this case, the alphabet lies both on the unit circle and on the real axis. Therefore, at step <b>50</b>, the values of b are initialized using a decision-feedback detector in which the decision values are constrained to the real axis. At steps <b>52</b> and <b>54</b>, the soft decision values of b are computed with the unit circle constraint, as described above, after which the final hard decision values are determined by constraining b to the actual, real alphabet.

P-0082[0082] A real-constrained decision feedback detector, which may be used at step <b>50</b>, is described in the above-mentioned U.S. Pat. No. 09/917,837. This model permits equation (5) to be restated as follows in terms of real values only:

{overscore (x)}(m)={overscore (S)}(m)b(m)+{overscore (n)}(m)   (19)

P-0083[0083] This equation uses the notation <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mrow><mrow><mover><mi>s</mi><mi>_</mi></mover><mo>:=</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>s</mi><mi>ℜ</mi></msub></mtd></mtr><mtr><mtd><msub><mi>s</mi><mi></mi></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math><img file="US20040101034A1-20040527-M00005.TIF" id="EMI-M00005" he="21.12075" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00005" attachment-type="nb" file="US20040101034A1-20040527-M00005.NB" /></attachments></maths>

P-0084[0084] in which S_Rand S_ℑ are the separate real and imaginary parts of S_{<img file="US20040101034A1-20040527-P00900.TIF" id="custom-character-00001" he="20" wi="20" img-format="tif" img-content="tx" />} respectively. Similar notation is used for the complex input signal x and noise n. S and x are replaced by {overscore (S)} and {overscore (x)} in the development of equation (16), as described above, and the decision operator α( ) is replaced simply by a sign operation (taking the sign of the soft decision to determine the hard decision value). Subject to these changes, the method of FIG. 6 is used to initialize the decision values substantially as described above.

P-0085[0085] For the purpose of steps <b>52</b> and <b>54</b>, the model of equation (9) is preferably also modified as follows to account for the real constellation:

f(φ)=∥{overscore (x)}−<i>{overscore (S)}e</i>^jφ∥²  (20)

P-0086[0086] Equation (20) combines both the unit circle and real axis constraints that apply to the BPSK constellation. Again, the ALPS procedure may be applied to z and T, as determined by the methods of FIG. 6 using {overscore (S)} and {overscore (x)}.

P-0087[0087] Although for the sake of simplicity, equations (8) and (9) relate to samples x(t) collected during a single symbol interval, the method embodied in these equations can readily be extended to multiple successive symbol intervals, i.e., to samples collected over [0,MT_b). Such an extended observation window may be necessary in order to deal with loss of synchronism among the user signals and to deal with impulse responses h_k(t) whose duration is longer than a single chip period (due to multi-path effects, for example). In this case, the model of equations (1) and (2) can be recast in the following form: <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mover><munder><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow></munder><mi>∞</mi></mover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><msub><mi>b</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mover><mi>s</mi><mi>˘</mi></mover><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>,</mo><mi>m</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>+</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>21</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00006.TIF" id="EMI-M00006" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00006" attachment-type="nb" file="US20040101034A1-20040527-M00006.NB" /></attachments></maths>

P-0088[0088] Here the symbol signature waveform s_k(t;m) of equation (6) is replaced by a composite symbol signature waveform, given by:

{overscore (s)}_k(t, m)=h_k(t) * [c_k(t)p_Tb(t−mT_b)]  (22)

P-0089[0089] The composite symbol signature waveform can vary from symbol to symbol and is of finite duration, say (N+L_k) chip intervals. The size of L_kreflects the duration of the impulse responses.

P-0090[0090] If we now restrict our attention to the particular observation window [<b>0</b>,MT_b), equation (21) can be rewritten as follows: <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><munder><mo>∑</mo><mi>m</mi></munder><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><msub><mi>b</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>s</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>;</mo><mi>m</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>+</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>0</mn><mo>≤</mo><mi>t</mi><mo>&lt;</mo><msub><mi>MT</mi><mi>b</mi></msub></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>23</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00007.TIF" id="EMI-M00007" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00007" attachment-type="nb" file="US20040101034A1-20040527-M00007.NB" /></attachments></maths>

P-0091[0091] wherein s_k(t; m):={haeck over (s)}_k(t; m)p_MTb(t), and the summation in m is over all the symbols having non-zero truncated signatures s_k(t;m) in the observation window. Ordering the symbols according to their signature-start-times, the sample vector x can now be expressed in the form given by equation (5), x=Sb+n, except that now x is a NM×1 vector, and the columns of S are the sampled truncated signatures. Typically, the columns of S contain a few leading zero entries, followed by (N+L_k) non-zero entries, and ending with trailing zeros.

P-0092[0092] Because equation (23) is formally identical to equation (5), multi-user detection block <b>38</b> can operate on asynchronous signals in the same manner as was described above with respect to synchronous signals. In other words, the restriction of {tilde over (b)} to the unit circle and the application of equation (10) to find the values of {tilde over (b)}_kcan be performed on asynchronous signals, as well. The performance of block <b>38</b> in the asynchronous case depends on the width of the observation window. For ideal channels and an observation window synchronized with a symbol interval of one of the users, b should typically have (2K-1) elements, compared with K elements in the synchronous case. For improved performance under non-ideal conditions, the observation window may be even wider.

Maximum Likelihood Estimation of Channel Responses

P-0093[0093]FIG. 7 is a block diagram showing details of signals conveyed in system <b>20</b>, which will be useful in understanding the operation of channel estimator <b>36</b> (FIG. 3). The symbols b_k(m) transmitted by the k-th user <b>24</b> are up-sampled and modulated by the user's spreading code c_k(i) to generate chips d_k(i). Each user channel is assumed to have a linear response h_k(i) The signal x(i) at the receiver of base station <b>22</b> is a superposition of all the user signals, together with noise n(i). Assuming for simplicity that the receiver samples the superposed signal at the chip rate, the received baseband signal can be represented as: <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><mrow><msub><mi>h</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>*</mo><mrow><msub><mi>d</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>+</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>24</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00008.TIF" id="EMI-M00008" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00008" attachment-type="nb" file="US20040101034A1-20040527-M00008.NB" /></attachments></maths>

P-0094[0094] This equation is a simplified form of equation (1). Note that higher sampling rates may also be used, as described further hereinbelow.

P-0095[0095] Equation (2) can likewise be recast to express the chips d_k(i) as a function of the spreading gain (or spreading response) N_kand the code sequence c_k(i) <maths id="MATH-US-00009" num="9"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>d</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mover><munder><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow></munder><mi>∞</mi></mover><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mrow><msub><mi>b</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>w</mi><msub><mi>N</mi><mi>k</mi></msub></msub><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>-</mo><msub><mi>mN</mi><mi>k</mi></msub><mo>-</mo><msub><mi>T</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>25</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00009.TIF" id="EMI-M00009" he="24.01245" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00009" attachment-type="nb" file="US20040101034A1-20040527-M00009.NB" /></attachments></maths>

P-0096[0096] Here T_kis an integer between 1 and N_kthat indicates the symbol start-time, and w_Nkis a rectangular window function, which is 1 for i in [1, N_k), and zero elsewhere. We refer to the product w_N_{<sub2>k</sub2>}(i−mN_k−T_k)c_k(i) as the “signature” of symbol b_k(m). Channel estimator <b>36</b> (or some other element of the receiver) typically performs a clock recovery function to determine T_kfor each user.

P-0097[0097] The problem to be solved by channel estimator <b>36</b> can be stated as follows: Given a vector x of M consecutive samples x(i) of the signal received at base station <b>22</b>, estimate the channel impulse responses h_k(i) for all user channels k. For the purposes of the estimation, the channel impulse responses are assumed to be finite in time (i.e., FIR) and constant over each observation interval, i=1, . . . , M, so that equation (24) can be rewritten as: <maths id="MATH-US-00010" num="10"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><mrow><msubsup><mi>d</mi><mi>k</mi><mi>T</mi></msubsup><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo></mo><msub><mi>h</mi><mi>k</mi></msub></mrow></mrow><mo>+</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>26</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00010.TIF" id="EMI-M00010" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00010" attachment-type="nb" file="US20040101034A1-20040527-M00010.NB" /></attachments></maths>

P-0098[0098] Here the superscript T indicates the transpose of a vector and d_k(i):=(d_k(i) d_k(i−1), . . . , d_k(i−L_k+1))^T, wherein L_kis the length of the channel vector h_k:=(h_k(1), h_k(2), . . . , h_k(L_k))^T. Preferably, for accurate estimation of h_k, M is chosen to be considerably greater than <maths id="MATH-US-00011" num="11"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><msub><mi>L</mi><mi>k</mi></msub><mo>.</mo></mrow></mrow></math><img file="US20040101034A1-20040527-M00011.TIF" id="EMI-M00011" he="24.97635" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00011" attachment-type="nb" file="US20040101034A1-20040527-M00011.NB" /></attachments></maths>

P-0099[0099] It is also assumed that the code sequences {c_k(i)} are independent of the symbols and consist of independent identically-distributed complex random variables with zero mean. All the code sequences are assumed to be known at the receiver, and are mutually orthogonal. This is a reasonable assumption with the regard to the long PN spreading codes used in IS-95 and other modern CDMA standards. For simplicity in the derivation that follows, we assume that users <b>24</b> apply BPSK modulation. Other alphabets may also be used with minor modifications to the channel estimator, as described below. When BPSK modulation is used, the chip sequences {d_k(i)} are also mutually orthogonal.

P-0100[0100] Based on equation (26), the vector x of received samples can be expressed as x=Dh+n, wherein h:=(h₁^T, . . . , h_K^T)^T, and the chip matrix D is given by:

D:=[D₁, . . . , D_K]

D_k:=[d_k^T(1), . . . , d_k^T(M)]^T  (27)

P-0101[0101] It can be seen from equation (25) that the elements of the chip matrix depend on the (unknown) symbols {b_k(m)}.

P-0102[0102] Channel estimator <b>36</b> performs a maximum likelihood estimation (MLE) of h by maximizing a log-likelihood function given by:

L(b, h)=−∥x−Dh∥²  (28)

P-0103[0103] over the unknown parameters b and h. The solution to equation (28) for any fixed b is given by:

ĥ=(D^HD)⁻¹D^Hx   (29)

P-0104[0104] Based on the mutual orthogonality of the chip sequences noted above (and hence the mutual orthogonality of the columns of D), D^HD≈MI for large M, wherein I is the identity matrix. Substituting equation (29) back into equation (28) then gives: <maths id="MATH-US-00012" num="12"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mi>b</mi><mo>)</mo></mrow></mrow><mo>≈</mo><msup><mrow><mo></mo><mrow><msup><mi>D</mi><mi>H</mi></msup><mo></mo><mi>x</mi></mrow><mo></mo></mrow><mn>2</mn></msup></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><msup><mrow><mo></mo><mrow><msubsup><mi>D</mi><mi>k</mi><mi>H</mi></msubsup><mo></mo><mi>x</mi></mrow><mo></mo></mrow><mn>2</mn></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>30</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00012.TIF" id="EMI-M00012" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00012" attachment-type="nb" file="US20040101034A1-20040527-M00012.NB" /></attachments></maths>

P-0105[0105] L(b) can be cast as an explicit function of b by using the definition of d_k(i) in equation (25): <maths id="MATH-US-00013" num="13"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>D</mi><mi>k</mi></msub><mo>=</mo><mrow><munder><mo>∑</mo><mrow><mi>m</mi><mo>∈</mo><msub><mi>B</mi><mi>k</mi></msub></mrow></munder><mo></mo><mrow><mrow><msub><mi>b</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>C</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>31</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00013.TIF" id="EMI-M00013" he="21.12075" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00013" attachment-type="nb" file="US20040101034A1-20040527-M00013.NB" /></attachments></maths>

P-0106[0106] B_krepresents the set of symbols that affect D_k, i.e., those symbols having non-zero matrix elements in the signature matrix C_k(m) for user k. The signature matrix is a M×L_kToeplitz matrix. The elements of the signature matrix are completely determined by the transmitted signature of the symbol b_k(m), as described above in reference to equation (25). In other words, the i-th entry in the first column of C_kis the signature w_N_{<sub2>k</sub2>}(i−mN_k−T_k)c_k(i) Subsequent columns contain delayed versions of this signature, so that the i-th entry in the j-th column of C_kis w_N_{<sub2>k</sub2>}(i−j−mN_k−T_k)c_k(i−j). The overall form of the signature matrix is as follows: <maths id="MATH-US-00014" num="14"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>C</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo>=</mo></mrow></mtd></mtr><mtr><mtd><mrow><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd><mtd><mi>⋮</mi></mtd><mtd><mi>⋯</mi></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>K</mi></msub><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd><mtd><mi>⋮</mi></mtd><mtd><mi>⋯</mi></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><msub><mi>N</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mi>⋮</mi></mtd><mtd><mi>⋯</mi></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><msub><mi>N</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mi>⋯</mi></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mrow><msub><mi>mN</mi><mi>k</mi></msub><mo>+</mo><msub><mi>T</mi><mi>k</mi></msub><mo>+</mo><msub><mi>N</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd><mtd><mi>⋮</mi></mtd><mtd><mi>⋯</mi></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>⋯</mi></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00014.TIF" id="EMI-M00014" he="171.14895" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00014" attachment-type="nb" file="US20040101034A1-20040527-M00014.NB" /></attachments></maths>

P-0107[0107] Substituting equation (31) into equation (30) gives the following expression for the likelihood function: <maths id="MATH-US-00015" num="15"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mi>b</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mo>∑</mo><mi>k</mi></munder><mo></mo><msup><mrow><mo></mo><mrow><munder><mo>∑</mo><mrow><mi>m</mi><mo>∈</mo><msub><mi>B</mi><mi>k</mi></msub></mrow></munder><mo></mo><mrow><mrow><msub><mi>f</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msubsup><mi>b</mi><mi>k</mi><mo>*</mo></msubsup><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo></mo></mrow><mn>2</mn></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>32</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00015.TIF" id="EMI-M00015" he="29.0304" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00015" attachment-type="nb" file="US20040101034A1-20040527-M00015.NB" /></attachments></maths>

P-0108[0108] f_kis a “fingerprint vector” of length L_k, matched to the signature of the (k,m)-th symbol, which is given by:

f_k(m):=C_k^H(m)x   (33)

P-0109[0109] Collecting the consecutive symbols {b_k(m)} for all mεB_kinto a column vector b_k, and collecting the corresponding fingerprints into a L_k×|B_k| fingerprint matrix F_k(wherein |B_k| is the number of elements in the set B_k), allows equation (32) to be rewritten as: <maths id="MATH-US-00016" num="16"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mi>b</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mo>∑</mo><mi>k</mi></munder><mo></mo><msup><mrow><mo></mo><mrow><msub><mi>F</mi><mi>k</mi></msub><mo></mo><msubsup><mi>b</mi><mi>k</mi><mo>*</mo></msubsup></mrow><mo></mo></mrow><mn>2</mn></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>34</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00016.TIF" id="EMI-M00016" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00016" attachment-type="nb" file="US20040101034A1-20040527-M00016.NB" /></attachments></maths>

P-0110[0110] Since the symbol vectors b_kare separate and independent, equation (34) is maximized over b simply by maximizing each of the individual user components of L(b), i.e., for each k, finding b_kto maximize:

L_k(b_k):=∥F_kb_k*∥²  (35)

P-0111[0111] Preferably, the maximization is carried out over the known alphabet A of the symbol constellation.

P-0112[0112] Reference is now made to FIGS. 8 and 9, which schematically illustrate a method used by channel estimator <b>36</b> to determine the channel response vector h_kfor each channel k, based on the fingerprint matrices F_k, in accordance with a preferred embodiment of the present invention. FIG. 8 is a flow chart showing the method itself, while FIG. 9 is a block diagram showing a portion of the circuitry that may be used to implement the method in the channel estimator.

P-0113[0113] The method of FIG. 8 begins with calculation of the fingerprint matrix F_kfor each user channel, at a matrix calculation step <b>90</b>. (In order to determine the propagation delay τ_kbetween the transmitter of user k and the base station receiver, a number of matrices may be calculated, each for a different value of τ_k, as described further hereinbelow.) To calculate the fingerprints f_kfor successive symbols b_k(1), . . . , b_k(M), the received samples x(i) are input to a bank of matched filters <b>92</b>, as shown in FIG. 9. Filters <b>92</b> have coefficients corresponding to the elements of the columns of the signature matrices C_k(1), . . . , C_k(M). Successive products of the sample values x(i) by the filter coefficients are entered into the columns of a fingerprint matrix array <b>94</b>. Each column of array <b>94</b> corresponds to the fingerprint f_k(m) for one of the M symbols in the observation interval. Each of the columns comprises a sequence of taps <b>96</b>, with a one-chip delay between the taps imposed by delay elements <b>98</b>. Each tap holds the value of one of the elements of F_k.

P-0114[0114] A matrix processor <b>99</b> reads out and processes the elements of F_kfrom taps <b>96</b> of array <b>94</b> in order to maximize L_k(b_k), at a matrix processing step <b>100</b>. For simplicity, as noted above, we assume for the moment that BPSK modulation is used in system <b>20</b>. The real symbol alphabet then allows equation (35) to be rewritten as follows:

L_k(b_k):=∥{overscore (F)}_kb_k*∥²  (36)

P-0115[0115] Here <maths id="MATH-US-00017" num="17"><math overflow="scroll"><mrow><mrow><mover><mi>F</mi><mi>_</mi></mover><mo>:=</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>F</mi><mi></mi></msub></mtd></mtr><mtr><mtd><msub><mi>F</mi><mi></mi></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math><img file="US20040101034A1-20040527-M00017.TIF" id="EMI-M00017" he="21.12075" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00017" attachment-type="nb" file="US20040101034A1-20040527-M00017.NB" /></attachments></maths>

P-0116[0116] a real matrix made by stacking the real and imaginary parts of F, in the manner of {overscore (S)} described above. The maximization of L_kover the real constellation of b_kis ambiguous, in that the maximum can be determined only up to multiplication of b_kby a real scalar (such as −1).

P-0117[0117] To maximize the value of equation (36) for each k, processor <b>99</b> preferably performs a singular value decomposition (SVD) of {overscore (F)}_k, as is known in the art:

{overscore (F)}_k=U_kΣ_kV_k^T  (37)

P-0118[0118] wherein U and V are unitary matrices, and Σ is diagonal. Efficient methods for SVD are described in the above-mentioned text by Golub et al. Equation (36) can be maximized by setting symbol values b_kto the soft decision values:

{tilde over (b)}={square root}{square root over (|B_k|)}v_k(1)   (38)

P-0119[0119] Here v_k(1) is the first column of V_k, and the scaling factor {square root}{square root over (|B_k|)} is added so that the absolute values of the elements of {tilde over (b)}_kwill be close to one.

P-0120[0120] Based on the above decomposition of {overscore (F)}_k, processor <b>99</b> can determine a vector of hard decision values {circumflex over (b)}_ksimply by taking the sign of each element of {tilde over (b)}_k, at a decision step <b>102</b>. As noted earlier, the determination of the elements of {circumflex over (b)}_kis uncertain as to multiplication by ±1, and other means must be applied in order to resolve this ambiguity. (One possibility is the use of known pilot signals, as described below.) Given the hard decision values of the symbols {circumflex over (b)}_k, the channel response vector for each user k can be determined by substituting these values into equation (29), in which the chip matrix D has been replaced by the equivalent fingerprint matrix F_k: <maths id="MATH-US-00018" num="18"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mover><mi>h</mi><mo>^</mo></mover><mi>k</mi></msub><mo>=</mo><mrow><mfrac><mn>1</mn><mi>M</mi></mfrac><mo></mo><msub><mi>F</mi><mi>k</mi></msub><mo></mo><msub><mover><mi>b</mi><mo>^</mo></mover><mi>k</mi></msub></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>39</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00018.TIF" id="EMI-M00018" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00018" attachment-type="nb" file="US20040101034A1-20040527-M00018.NB" /></attachments></maths>

P-0121[0121] In estimating {circumflex over (b)}_kand ĥ_kin this manner, the individual user channels are decoupled, so that each channel is estimated independently based on the superposed samples x(i) of all the channels and the spreading code of the individual channel.

P-0122[0122] Alternatively, the channel response vectors may be estimated based on the soft decision values {tilde over (b)}_kgiven by equation (38). In this case: <maths id="MATH-US-00019" num="19"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mover><mi>h</mi><mo>^</mo></mover><mi>k</mi></msub><mo>=</mo><mrow><mfrac><msqrt><mrow><mrow><mo></mo><msub><mi>B</mi><mi>k</mi></msub><mo></mo></mrow><mo></mo><mrow><msub><mi>σ</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></mrow></msqrt><mi>M</mi></mfrac><mo></mo><mrow><msub><munder><mi>u</mi><mi>_</mi></munder><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>40</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00019.TIF" id="EMI-M00019" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00019" attachment-type="nb" file="US20040101034A1-20040527-M00019.NB" /></attachments></maths>

P-0123[0123] Here σ_k(1) is the first (i.e., largest) singular value in Σ_k, and u_k(1) is the first column of U_k. The notation <u>u</u> with underbar denotes the inverse of the overbar operation used earlier, i.e., “unstacking” of u from a real vector of length 2L to a complex vector of length L. An advantage of deriving ĥ_kdirectly from the fingerprint matrix F_kin this manner is that it allows matrix processor <b>99</b> to update the channel response vectors easily as new samples are received, and corresponding new fingerprints are added to array <b>94</b>. For example, the matrix processor may use subspace tracking methods, as are known in the art, to compute the new major singular vector <u>u</u>_k(1) and the corresponding singular value σ_k(1) iteratively, based on the previous values. An efficient method for subspace tracking is described, for example, by Yang in “Projection Approximation Subspace Tracking,” <i>IEEE Transactions on Signal Processing </i>43:1 (January, 1995), pages 95-107, which is incorporated herein by reference.

P-0124[0124] Optionally, matrix processor <b>99</b> also estimates the propagation delay τ_kof signals transmitted from user k to base station <b>22</b>, at a delay estimation step <b>104</b>. These delays vary depending on the distances of the users from the base station, and they may not be known a priori. One way to estimate the delay is to pad the channel response vector h_kbeyond the necessary length L_kby adding zeroes at the ends of the vector. In estimating ĥ_k, as described above, matrix processor <b>99</b> will implicitly find an estimate of the propagation delay τ_k, and will incidentally estimate the actual response length L_k, as well.

P-0125[0125] An alternative method for estimating τ_kis to define a delay vector τ:=(τ₁, . . . , τ_K)^T, and to use the delay vector as an additional parameter in the MLE. For any given vector τ, the maximization of L(b,h) can be performed as described above, wherein the values of τ_kwill come to bear in the relative locations of the entries in the columns of the signature matrix C_k(m). (Note that each τ_kis estimated in quanta of a chip period, since sub-chip variations are implicitly estimated by h_k.) Using this formulation, and referring back to equation (36), the delay vector can be estimated by:

τ_k=arg max ∥{overscore (F)}_k(τ_k){circumflex over (b)}_k(τ_k)∥²  (41)

P-0126[0126] To perform the estimation, a number of different fingerprint matrices F_kare preferably calculated for different values of τ_k, at step <b>90</b> in the method of FIG. 8. Typically, the uncertainty in the propagation delay is small enough so that only a few different delay values need to be considered. Furthermore, since the fingerprint matrices for successive values of τ_kshare a common sub-matrix, the subspace tracking function of matrix processor <b>99</b> can be used to find the singular vectors and values of the successive matrices efficiently. Thus, it is generally possible to maximize the estimation of equation (41) exhaustively over τ_kat low computational cost.

P-0127[0127] Channel estimator <b>36</b> and the method described above can also be used when the received signal x(t) is sampled at a rate that is a multiple of the chip rate. Taking the sampling multiple to be J, the channel estimator will receive M×J samples during an observation interval of M chip periods. The basic model that x=Dh+n can be re-expressed as x^(J)=Dh^(J)+n^(J), wherein x^(J)=[x(j), x(J+j), . . . , x( (M−1)J+j)]^T. In other words, each x^(j)contains the samples for the j-th sub-chip, and the channel vector h^(j)and noise vector n^(J)are defined accordingly. The fingerprint matrix F_kis now a JL_kx|B_k| matrix, which is generated by stacking the sub-chip fingerprint matrices F_k^(j): <maths id="MATH-US-00020" num="20"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>F</mi><mi>k</mi></msub><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><msubsup><mi>F</mi><mi>k</mi><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></msubsup></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><msubsup><mi>F</mi><mi>k</mi><mrow><mo>(</mo><mi>J</mi><mo>)</mo></mrow></msubsup></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>42</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00020.TIF" id="EMI-M00020" he="36.9684" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00020" attachment-type="nb" file="US20040101034A1-20040527-M00020.NB" /></attachments></maths>

P-0128[0128] The decision values {circumflex over (b)}_kand ĥ_kare determined based on this extended fingerprint matrix substantially as described above.

P-0129[0129] This same technique may be used in estimating the channel response vectors when base station <b>22</b> has multiple receive antennas. Multiple antennas are commonly deployed in order to enhance signal reception by means of spatial diversity. In this case, each x^(j)represents the signal samples received by the j-th antenna. The fingerprint matrix for the multiple antennas is constructed in the manner of equation (42), and the decision values are determined accordingly.

P-0130[0130] Although for the sake of simplicity, the operation of estimator <b>36</b> is described above with respect to BPSK modulation, the method of FIG. 8 may be adapted in a straightforward way for other constellations, including complex-valued constellations. For example, when QPSK modulation is used, equation (31) should be recast as follows: <maths id="MATH-US-00021" num="21"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>D</mi><mi>k</mi></msub><mo>=</mo><mrow><munder><mo>∑</mo><mrow><mi>m</mi><mo>∈</mo><msub><mi>B</mi><mi>k</mi></msub></mrow></munder><mo></mo><mrow><mo>[</mo><mrow><mrow><mrow><msub><mi>b</mi><mrow><mi>k</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>ℜ</mi></mrow></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>c</mi><mrow><mi>k</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>ℜ</mi></mrow></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mi>j</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><msub><mi>b</mi><mrow><mi>k</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi></mi></mrow></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>c</mi><mrow><mi>k</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi></mi></mrow></msub><mo></mo><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>43</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00021.TIF" id="EMI-M00021" he="21.12075" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00021" attachment-type="nb" file="US20040101034A1-20040527-M00021.NB" /></attachments></maths>

P-0131[0131] There are now two code matrices in the equation: C_{k<img file="US20040101034A1-20040527-P00900.TIF" id="custom-character-00002" he="20" wi="20" img-format="tif" img-content="tx" />} and C_kℑ, corresponding to the real and imaginary parts of the symbol sequences b_kℑ and b_kℑ. The fingerprint matrix F_kaccordingly has twice the number of columns as in the BPSK case. In other respects, matrix processor <b>99</b> estimates the channel response vectors substantially as described above.

P-0132[0132]FIG. 10 is a flow chart that schematically illustrates a method for channel estimation and multi-user detection based on alternate-searching likelihood maximization (ASLM), in accordance with a preferred embodiment of the present invention. This method is carried out in collaboration between channel estimator <b>36</b> and multi-user detection block <b>38</b>. It begins from the initial estimate of ĥ determined by estimator <b>36</b> using the method of FIG. 8, at an initialization step <b>110</b>. As noted above, this value is an approximation made for each user channel k in a manner that is decoupled from the other channels.

P-0133[0133] To refine the estimated channel response vectors, multi-user detection block <b>38</b> first computes decision values of {circumflex over (b)}, at a symbol estimation step <b>112</b>. Referring back to equations (5) and (6), we recall that the signature matrix S is a function of h. The function of block <b>38</b> at step <b>112</b> is to find {circumflex over (b)} so as to minimize ∥x−S(ĥ)b∥². This operation is preferably carried out as described above with reference to FIGS. 4 and 6. Alternatively, if the symbol constellation is real-valued, the multi-user detector described in the above-mentioned U.S. patent application Ser. No. 09/917,837 may be used. Other multi-user detectors known in the art may be used here, as well. Further alternatively, other methods of multi-user detection may be used, as are known in the art.

P-0134[0134] Once {circumflex over (b)} is known, it can be used to calculate the estimated values of chips d_k(i), as given by equation (25), at a chip calculation step <b>114</b>. The chip values are in turn used to construct the estimated chip matrix {circumflex over (D)}:=D({circumflex over (b)}), based on equation (27). The chip matrix can now be used to find a new estimate of ĥ, based on equation (29), at a channel re-estimation step <b>116</b>. The procedure of steps <b>112</b>, <b>114</b> and <b>116</b> continues iteratively until the values of {circumflex over (b)} have converged, at a convergence step <b>118</b>. Convergence may be measured, for example, based on the number of symbols whose values have changed in {circumflex over (b)} from one iteration to the next. Once the computation has converged, detector <b>38</b> outputs the values of {circumflex over (b)}, at an output step <b>120</b>. An accurate channel estimate ĥ has been computed and can be output at the same time.

P-0135[0135] Accurate computation of ĥ at step <b>116</b> requires inversion of the matrix {circumflex over (D)}^H{circumflex over (D)}, which may be computationally difficult. Instead, ĥ can be determined by solving the linear equation Rĥ=y, wherein R:={circumflex over (D)}^H{circumflex over (D)} and y:={circumflex over (D)}^Hx. Since a good initial guess for ĥ is available, this equation can be efficiently solved using standard iterative methods, such as the Gauss-Seidel or conjugate gradient algorithms described in the above-mentioned text by Golub et al. These methods do not require explicit inversion of R.

P-0136[0136] In some cellular systems, users <b>24</b> transmit a known pilot sequence p_k(i) along with the data-bearing traffic chip sequence d_k(i) defined by equation (25). The pilot sequence can be used to enhance the channel estimation, including resolving the sign ambiguity of the estimated symbols noted above. In the presence of the pilot signal, the model x=Dh+n, as expressed by equation (26), is now recast as x=(D+P)h+n. Here P is a known matrix composed of the pilot chips, given by P=[P₁, . . . , P_K], <maths id="MATH-US-00022" num="22"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>P</mi><mi>k</mi></msub><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><msubsup><mi>p</mi><mi>k</mi><mi>T</mi></msubsup><mo></mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mrow><msubsup><mi>p</mi><mi>k</mi><mi>T</mi></msubsup><mo></mo><mrow><mo>(</mo><mi>M</mi><mo>)</mo></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>44</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00022.TIF" id="EMI-M00022" he="36.9684" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00022" attachment-type="nb" file="US20040101034A1-20040527-M00022.NB" /></attachments></maths>

P-0137[0137] and p_k(i):=[p_k(i), p_k(i−1), . . . , p_k(i−L+1)]^T, in analogy to d_k(i).

P-0138[0138] The MLE function of equation (36) is now given by: <maths id="MATH-US-00023" num="23"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>L</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><msub><mi>b</mi><mi>k</mi></msub><mo>)</mo></mrow></mrow><mo>:=</mo><msup><mrow><mo></mo><mrow><mrow><mo>[</mo><mover><mrow><msub><mi>π</mi><mi>k</mi></msub><mo></mo><msub><mi>F</mi><mi>k</mi></msub></mrow><mi>_</mi></mover><mo>]</mo></mrow><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd></mtr><mtr><mtd><msub><mi>b</mi><mi>k</mi></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo></mo></mrow><mn>2</mn></msup></mrow></mtd><mtd><mrow><mo>(</mo><mn>45</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00023.TIF" id="EMI-M00023" he="22.08465" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00023" attachment-type="nb" file="US20040101034A1-20040527-M00023.NB" /></attachments></maths>

P-0139[0139] Here F_kis the fingerprint matrix defined above, taken in the absence of pilot signals. The fingerprint matrix is extended by the pilot fingerprint, given by n_k=P_k^Hx. Applying the SVD of equation (37) to {overscore (n_kF_k)} gives a soft decision value (assuming BPSK modulation):

{tilde over (b)}_k=sign(V_k(1,1)({square root}{square root over (|B)}_k|+1)v_k(1)   (46)

P-0140[0140] By comparison with equation (38), it can be seen that the sign ambiguity of the estimated symbol vector is now resolved by V_k(1,1), which is the first entry in the first column of the matrix V_k. {dot over (v)}_k(1) represents the first column of V_k, without the first entry V_k(1,1). The hard decision values of {circumflex over (b)}_kare given simply by the sign of the corresponding soft decision values, and the channel estimate is: <maths id="MATH-US-00024" num="24"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mover><mi>h</mi><mo>^</mo></mover><mi>k</mi></msub><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>β</mi></mrow><mo>)</mo></mrow><mo></mo><mi>M</mi></mrow></mfrac><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>F</mi><mi>k</mi></msub><mo></mo><msub><mover><mi>b</mi><mo>^</mo></mover><mi>k</mi></msub></mrow><mo>+</mo><msub><mi>π</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>47</mn><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20040101034A1-20040527-M00024.TIF" id="EMI-M00024" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00024" attachment-type="nb" file="US20040101034A1-20040527-M00024.NB" /></attachments></maths>

P-0141[0141] wherein β is the (known) ratio of pilot signal power to data traffic signal power.

P-0142[0142] The symbol decision values and pilot-based channel response estimates are preferably refined using the ASLM procedure of FIG. 10, with appropriate modification. The known pilot signals are removed from the received signals x(i) to give a “pilot-free” input, x−Pĥ to multi-user detection block <b>38</b> at step <b>112</b>. The detection block then finds {circumflex over (b)} so as to maximize ∥(x−Pĥ)−S(ĥ)b∥². After computation of the chip matrix {circumflex over (D)} at step <b>114</b>, the channel estimate is updated at step <b>116</b> using:

ĥ=(({circumflex over (D)}+P)^H({circumflex over (D)}+P))⁻¹({circumflex over (D)}+P)^Hx   (48)

P-0143[0143] The procedure continues through steps <b>118</b> and <b>120</b>, as described above.

P-0144[0144] It will be appreciated that the preferred embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.