Load balancing computational methods in a short-code spread-spectrum communications system

• US 7,203,221 B2
• Filed: 03/14/2002
• Issued: 04/10/2007
• Est. Priority Date: 03/14/2001
• Status: Active Grant

• Current Assignee: Mercury Systems, Incorporated
• Original Assignee: Mercury Computer Systems Incorporated
• Inventors: Oates, John H.
• Primary Examiner(s): Bocure; Tesfaldet
• Application Number:
  US10/099,916
• Publication Number:
  US 20030091106A1
• Time in Patent Office: 1,853 Days
• Field of Search: 375/343, 375/130, 375/142, 375/147, 375/148, 375/150
• US Class Current: 375/150
• CPC Class Codes: H04B 1/707 using direct sequence modulation
• CPC Class Codes: H04B 1/7093 Matched filter type
• CPC Class Codes: H04B 1/7105 Joint detection techniques, e.g. linear detectors
• CPC Class Codes: H04B 1/71052 using decorrelation matrix
• CPC Class Codes: H04B 1/71075 Parallel interference cancellation
• CPC Class Codes: H04B 1/7115 Constructive combining of multi-path signals, i.e. RAKE receivers
• CPC Class Codes: H04B 2201/70707 Efficiency-related aspects
• CPC Class Codes: H04B 2201/70711 with modular structure

Abstract

The invention provides methods and apparatus for multiple user detection (MUD) processing that have application, for example, in improving the capacity CDMA and other wireless base stations. One aspect of the invention provides a multiprocessor, multiuser detection system for detecting user transmitted symbols in CDMA short-code spectrum waveforms. A first processing element generates a matrix (hereinafter, “gamma matrix”) that represents a correlation between a short-code associated with one user and those associated with one or more other users. A set of second processing elements generates, e.g., from the gamma matrix, a matrix (hereinafter, “R-matrix”) that represents cross-correlations among user waveforms based on their amplitudes and time lags. A third processing element produces estimates of the user transmitted symbols as a function of the R-matrix.

Claims

1. A method of processing spread spectrum waveforms transmitted by a plurality of users of a spread spectrum system, comprising

distributing among a plurality of logic units parallel tasks each for computing a portion of a matrix indicative of cross correlations among the waveforms transmitted by the users,

partitioning computation of the cross-correlation matrix such that a computational load associated with a task distributed to one of said logic units is substantially equal to computational load associated with another task distributed to another logic unit,

executing with the plurality of logic units the distributed tasks,

generating detection statistics corresponding to symbols transmitted by the users and encoded in the waveforms as a function of the cross correlation matrix, and

generating estimates of the symbols based on the detection statistics.

2. The method of claim 1, further comprising the step of defining a metric associated with each partition in accord with the relation:

B_i=A_i−

A<sub>i−

1</sub>

wherein

A_i represents an area of a portion of the cross-correlation matrix corresponding to the ith partition, and

i represents an index corresponding to the number of logic units.

3. The method of claim 2, further comprising the step of representing the cross-correlation matrix as a composition of a rectangular component and a triangular component.

4. The method of claim 3, wherein each area A_i includes a first portion corresponding to the rectangular component and a second portion corresponding to the triangular component of the cross-correlation matrix.

5. The method of claim 4, wherein the step of partitioning the matrix includes selecting the matrix associated with the partitions to be substantially equal.

6. The method of claim 3, wherein the cross-correlation matrix is computed as a composition of a first component that represents correlations among time lags and code sequences associated with the waveforms transmitted by the users and a second component that represents correlations among multipath signal amplitudes associated with the waveforms transmitted by the users.

7. A method of processing spread spectrum waveforms transmitted by a plurality of users of a spread spectrum system, comprising

partitioning computation of a matrix representing cross-correlations among the waveforms transmitted by the users in accord with a pre-defined metric,

distributing among a plurality of logic units parallel tasks each corresponding to one of said partitions for computing a portion of the matrix,

executing with the plurality of logic units the distributed tasks,

assembling said computed portions to generate the cross-correlation matrix,

representing the cross-correlation matrix as a composition of a first component that represents correlations among time lags and code sequences associated with the waveforms transmitted by the users and a second component that represents correlations among multipath signal amplitudes associated with the waveforms transmitted by the users,

generating detection statistics corresponding to symbols transmitted by the users and encoded in the waveforms as a function of the cross correlation matrix, and

estimating the symbols based on the detection statistics.

8. The method of claim 7, wherein the step of partitioning comprises defining the metric in accord with the relation:

B_i=A_i−

A<sub>i−

1</sub>

wherein

A_i represents an area of a portion of the cross-correlation matrix corresponding to the ith partition, and

i represents an index corresponding to the number of logic units.

9. A method of processing spread spectrum waveforms transmitted by a plurality of users of a spread spectrum system, comprising

partitioning computation of a matrix representing cross-correlations among the waveforms transmitted by the users in accord with a pre-defined metric,

distributing among a plurality of logic units parallel tasks each corresponding to one of said partitions for computing a portion of the matrix,

executing with the plurality of logic units the distributed tasks,

assembling said computed portions to generate the cross-correlation matrix,

representing the cross-correlation matrix as a composition of a first component that represents correlations among time lags and code sequences associated with the waveforms transmitted by the users and a second component that represents correlations among multipath signal amplitudes associated with the waveforms transmitted by the users,

generating detection statistics corresponding to symbols transmitted by the users and encoded in the waveforms as a function of the cross correlation matrix, and

generating estimates of the symbols based on the detection statistics

wherein correlations among the code sequences associated with the respective users are computed in accord with the relation:

${\mathrm{\Gamma <br><br>}}_{l<br><br><br><br>k}<br><br>\left[m\right]\equiv <br><br>\frac{1}{2<br><br>N_l}<br><br>\underset{n=0}{\overset{N-1}{\sum <br><br>}}<br><br>c_l^{*}<br><br>\left[n\right]·<br><br>c_k<br><br>\left[n-m\right]$

wherein

Γ

_lk[m] represents correlation between l and k user codes corresponding to a shift of m chips,

c^*_l[n] represents complex conjugate of the code sequences associated with the lth user,

c_k[n−

m] represents the code sequences associated with kth user,

N represents the length of the code, and

N_l represent the number of non-zero length of the code.

10. The method of claim 9, further comprising the step of computing the first component of the cross correlation matrix as a matrix component (herein referred to as C matrix) in accord with the relation:

$C_{l<br><br><br><br>k<br><br><br><br>q<br><br><br><br>q}·<br><br>\left[m^{\mathrm{\prime <br><br>}}\right]=\underset{m}{\sum <br><br>}<br><br>g<br><br>\left[m<br><br><br><br>N_c+\mathrm{\tau <br><br>}\right]·<br><br>{\mathrm{\Gamma <br><br>}}_{l<br><br><br><br>k}<br><br>\left[m\right]$

wherein

g is a pulse shape vector,

N_c is the number of samples per chip,

τ

is a time lag, and

Γ

_lk[m] represents correlation between l and k user codes corresponding to a shift of m chips.

11. The method of claim 10, further comprising the step of computing the cross-correlation matrix (herein referred to as r matrix) in accord with the relation:

$r_{\mathrm{lk}}<br><br>\left[m^{\mathrm{\prime <br><br>}}\right]=\underset{q=1}{\overset{L}{\sum <br><br>}}<br><br>\underset{q^{\mathrm{\prime <br><br>}}=1}{\overset{L}{\sum <br><br>}}<br><br>R<br><br><br><br>e<br><br>\left\{{\hat{a}}_{l<br><br><br><br>q}^{*}<br><br>a_{k<br><br><br><br>q}·<br><br>C_{l<br><br><br><br>k<br><br><br><br>q<br><br><br><br>q<br><br>}·<br><br>\left[m^{\mathrm{\prime <br><br>}}\right]\right\}=R<br><br><br><br>e<br><br>\left\{a_l^H·<br><br>C_{l<br><br><br><br>k}<br><br>\left[m^{\mathrm{\prime <br><br>}}\right]·<br><br>a_k\right\}$

wherein

â

_lq^* is an estimate of α

_lq^*, which represents a complex conjugate of one multipath amplitude component of the 1^th user,

α

_kq, is one multipath amplitude component associated with the k^th user, and

C denotes the aforesaid C matrix.

12. The method of claim 11, wherein the step of generating detection statistics comprises computing the detection statistics in accord with the relation:

$y_l<br><br>\left[m\right]=r_{l<br><br><br><br>l}<br><br>\left[0\right]<br><br>b_l<br><br>\left[m\right]+\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>r_{l<br><br><br><br>k}<br><br>\left[-1\right]<br><br>b_k<br><br>\left[m+1\right]+\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>\left[r_{l<br><br><br><br>k}<br><br>\left[0\right]-r_{l<br><br><br><br>l}<br><br>\left[0\right]<br><br>{\mathrm{\delta <br><br>}}_{l<br><br><br><br>k}\right]<br><br>b_k<br><br>\left[m\right]+\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>r_{l<br><br><br><br>k}<br><br>\left[1\right]<br><br>b_k<br><br>\left[m-1\right]+{\mathrm{\eta <br><br>}}_l<br><br>\left[m\right]$

wherein

y_l[m] represents detection statistic for the mth symbol transmitted by the lth user,

r_ll[0]b_l[m] represents a signal of interest, and

remaining terms of the relations represent Multiple Access Interference (MAI) and noise.

13. The method of claim 12, wherein the step of generating symbol estimates comprises computing the estimates in accord with the relation:

${\hat{b}}_l<br><br>\left[m\right]=s<br><br><br><br>i<br><br><br><br>g<br><br><br><br>n<br><br>\left\{y_l<br><br>\left[m\right]-\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>r_{l<br><br><br><br>k}<br><br>\left[-1\right]<br><br>{\hat{b}}_k<br><br>\left[m+1\right]-\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>\left[r_{l<br><br><br><br>k}<br><br>\left[0\right]-r_{l<br><br><br><br>l}<br><br>\left[0\right]<br><br>{\mathrm{\delta <br><br>}}_{l<br><br><br><br>k}\right]<br><br>{\hat{b}}_k<br><br>\left[m\right]-\underset{k=1}{\overset{K_v}{\sum <br><br>}}<br><br>r_{l<br><br><br><br>k}<br><br>\left[1\right]<br><br>{\hat{b}}_k<br><br>\left[m-1\right]\right\}$

wherein

{circumflex over (b)}_l[m] represents an estimate of the mth symbol transmitted by the lth user,

g is a pulse shape vector,

N_c is the number of samples per chip,

τ

is a time lag, and

Γ

represents the Γ

matrix.