Multiuser detector for variable spreading factors

ηιυυοηη ιονβ *υΐ)> aa ’Nb>

Multiuser detector for variable spreading factors

InterDigital Technology Corporation C.138180 WO 01/22610 PCT/US00/02621

MULTIUSER DETECTOR FOR VARIABLE SPREADING FACTORS

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates generally to multiple access digital 5 communication systems. More specifically, the invention relates to a multiuser detector system and me±od for the simultaneous reception of data from multiple users having different spreading factors.

Description of the Related Art A multiple-access communication system allows a plurality of users to access 10 the same communication medium to transmit or receive information. The media may comprise, for example, a network cable in a local area network or lan, a copper wire in the classic telephone system, or an air interface for wireless communication. A prior art multiple access communication system is shown in FIG. 1. The communication media is referred to as a communication channel. Communication 15 techniques such as frequency division multiple access or FDMA, time division multiple access or TDMA, carrier sense multiple access or CSMA, code division multiple access or CDMA and others allow access to the same communication medium for more than one user. These techniques can be mixed together creating hybrid varieties of multiple access schemes. For example, time division duplex or SUBSTITUTE SHEET (RULE 26) WO 01/22610 PCT/US00/02621 TDD mode of the proposed third generation W-CDMA standard is a combination of TDMA and CDMA.

An example CDMA prior art communication system is shown in FIG. 2. CDMA is a communication technique in which data is transmitted with a broadened 5 band (spread spectrum) by modulating the data to be transmitted with a pseudo-noise signal. The data signal to be transmitted may have a bandwidth of only a few thousand Hertz distributed over a frequency band that may be several million Hertz.

The communication channel is being used simultaneously by K independent subchannels. For each subchannel, all other subchannels appear as interference. 10 As shown, a single subchannel of a given bandwidth is mixed with a unique spreading code which repeats a predetermined pattern generated by a wide bandwidth, pseudo-noise (pn) sequence generator. These unique user spreading codes are typically pseudo-orthogonal to one another such that the cross-correlation between the spreading codes is close to zero. A data signal is modulated with the pn 15 sequence producing a digital. spread spectrum signal. A carrier signal is then modulated with.the digital spread spectrum signal and transmitted in dependence upon the transmission medium. A receiver demodulates the transmission extracting the digital spread spectrum signal. The transmitted data is reproduced after correlation with the matching pn sequence. When the spreading codes are 20 orthogonal to one another, the received signal can be correlated with a particular user signal related to the particular spreading code such that only the desired user signal related to the particular spreading code is enhanced while the other signals for all SUBSTITUTE SHEET (RULE 26) WO 01/22610 PCT/US00/02621 other users are not enhanced.

Each value of the spreading code is known as a chip and has a chip rate that is the same or faster than the data rate. The ratio between the chip rate and the subchannel data rate is the spreading factor. 5 To extend the possible range of values of the data signal, a symbol is used to represent more than two binary values. Ternary and quaternary symbols take on three and four values respectively. The concept of a symbol allows for a greater degree of information since the bit content of each symbol dictates a unique pulse shape. Depending upon the number of symbols used, an equal number of unique 10 pulse or wave shapes exist. The information at the source is converted into symbols which are modulated and transmitted through the subchannel for demodulation at the destination.

The spreading codes in a CDMA system are chosen to minimize interference between a desired subchannel and all other subchannels. Therefore, the standard 15 approach to demodulating the desired subchannelhas been to· treat all other subchannels as interference, similar to interference that manifests itself in the communication medium. Receivers designed for this process are single-user, matched filter and RAKE receivers.

Since different subchannels do interfere with each other somewhat, another 20 approach is to demodulate all subchannels at a receiver. The receiver can listen to all of the users transmitting at once by running a decoding algorithm for each of them in parallel. This ideology is known as multiuser detection. Multiuser detection -3- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 can provide a significant performance improvement over single-user receivers.

Referring to FIG. 3, a system block diagram of a prior art CDMA receiver using a multiuser detector is shown. As one skilled in this art realizes, the receiver may include such functions as radio frequency or rf down conversion and associated 5 filtering for radio frequency channels, analog-to-digital conversion or optical signal demodulation for a specific communication media. The output of the receiver is a processed signal, either analog or digital, containing the combined spread signals of all active subchannels. The multiuser detector performs multiuser detection and outputs a plurality of signals corresponding to each active subchannel. All or a 10 smaller number of the total number of subchannels may be processed.

Optimal multiuser detectors are computationally intensive devices performing numerous complex mathematic operations and are therefore difficult to implement economically. To minimize expense, suboptimal multiuser detectors such as linear detectors have been developed requiring less computational complexity as a 15 compromise approximating the performance of optimal detectors. Linear detectors include decorrelators, minimum mean square error or MMSE detectors, and zero-forcing block linear equalizers or ZF-BLEs. A system block diagram of a prior art linear multiuser detector for synchronous or asynchronous CDMA communication is shown in FIG. 4. Data 20 output from the communication media specific receiver (as in FIG. 3) is coupled to a subchannel estimator which estimates the impulse response of each symbol transmitted in a respective subchannel. The linear detector uses the impulse response -4- SUBSTITUTE SHEET (RULE 26) WO 01/22610 PCT/US00/02621 estimates along with a subchannel’s spreading code to demodulate each subchannel’s data. The data is output to subchannel data processing blocks for respective users.

To effect parallel detection of K subchannel users in a physical system, linear multiuser detector methods are executed as fixed gate arrays, microprocessors, digital 5 signal processors or DSPs and the like. Fixed logic systems allow for greater system speed while microprocessor driven systems offer programming flexibility. Either implementation that is responsible for the multiuser detection performs a sequence of mathematic operations. To describe the functions, the following variables typically define the structure and operation of a linear multiuser detector: .10 K = the total number of users/transmitters that are active in the system.

Nc = the number of chips in a data block. The number of chips is required since with varying spreading factors this number is a measure common to all users. The number of chips is divisible by the largest spreading factor allowed. For the case of synchronous CDMA, a 15 symbol from the user with the largest spreading factor may constitute a block of data. Therefore, Nr can be reduced to be equal to the largest spreading factor. W = the communication channel impulse response length in chips.

This is generally a predefined parameter of the system. -5- ςιιρς-π-ππτ cucct row P 9R1 WO 01/22610 PCT/US00/02621

Q(k} = the spreading factor of user k. The spreading factor is equal to the number of chips that are used to spread a symbol of user’s data. A system knows the spreading factors in advance and does not need to estimate them from the received data. 5 Nfr = the number of symbols sent by user k. Nsw = NCI Qw. κ

Nf= y = the total number of symbols sent. t=i c¥ = the data (information) sent by user k. The data is presented in the form of a vector, where a vector is an array of data indexed by a single index variable. For the purposes of vector and matrix operations 10 which follow, all vectors are defined as column vectors. The n'h element of c¥ is the n,h symbol transmitted by the F1' user. hw = the impulse response of the subchannel experienced by user k presented as a vector. This quantity needs to be estimated at the receiver. The receiver’s estimates of the subchannel impulse 15 responses are referred to as h(k\ The elements of the vector h(k} are typically complex numbers, which model both amplitude and phase -6- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 variations that can be introduced by the subchannel. v(k} = the spreading code of user k, presented as a vector. For the purposes of linear multiuser detection, it is useful to think of vectors containing the section of the spreading code which spreads a particular 5 symbol. Therefore, the vector v(M) is defined as the spreading code which is used to spread the n“' symbol sent by the Eh user. Mathematically, it is defined as: v/*·'0 = v/A) for (n-l)<2w+l £ i <. nQ(k} and 0 for all other z, where i is the index of vector elements. i-M = a vector which represents user k’s data, spread by the spreading 10 sequence and transmitted through that user’s subchannel h(k\ The vector represents channel observations performed during the period of time when a block of data arrives. The i'1' element of the vector dk) can be defined as: (Λ) ) 7+1 π=1

Equation 1 15

The signal received at the receiver includes all user signals plus noise. Therefore, we can define the received data vector r as follows: -7- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/US00/02621

K 10 10

<img img-format="tif" img-content="drawing" file="IL148607AD00021.tif" id="idf0001" />

k=l

Equation 2

The vector n in Equation 2 represents noise introduced by the communication channel. FIG. 5 shows a system and method of a prior art linear multiuser detector. The estimated subchannel impulse response vectors /i(t) and the spreading codes vw are used to create a system transmission response matrix for each user k. A matrix is a block of numbers indexed by two indexing variables and is arranged as a rectangular grid, with the first indexing variable being a row index and the second indexing variable being a column index. A system transmission response matrix for user k is typically denoted as A{k\ The /''-row, /7"'-column element is denoted as A/} and is defined as:

<img img-format="tif" img-content="drawing" file="IL148607AD00022.tif" id="idf0002" />

7 = i /-7+1

Equation 3

Each column of the matrix A(k} corresponds to a matched filter response for a particular symbol sent by user k during the period of interest. Referring back to FIG. 5, the received data r is matched to a combination of all user’s spreading codes and subchannel impulse responses. Therefore, AU) contains matched filter responses. -8- SUBSTITUTE SHEET (RULE 26) WO 2001/022610 PCT/US2000/002621

The columns of Aw are of the form (k) ll

Equation 4 where each vector bfr has a dimension of Q{k) + W-1,

Equation 5 and is offset from the top of the matrix A,® by

Equation 6

Since the spreading codes are not periodic over symbol times; b^ * bfr for i * j. The elements of a vector which may be non-zero values are referred to as the support of the vector. Therefore, is the support of A„w.

Once a system transmission matrix for each user is created, a total system -9- SUBSTITUTE SHEET (RULE 26) WO 01/22610 PCT/US00/02621 transmission response matrix, denoted as A is created by concatenating the system transmission matrices for all the users as shown below: A _ f/ld) aW 4(/0-1 . „ /1 j/i ,..^/1,..^/1 j Equation 7 5 In accordance with prior art modulation techniques, the elements of h{k} can be complex numbers. It then follows that the non-zero elements of A can be complex numbers.

An example total system transmission response matrix A for a hypothetical prior art multiuser detector assembled in accordance with Equations 4, 5, 6 and 7 is -IO- SUBSTITUTE SHEET (RULE 261 WO 01/22610 PCT/USOO/02621 L(l) bu 0 0 0 0 0 0 0 !ά(2&gt; p.l 0 0 0 ill) bl.2 0 0 0 0 0 0 0 1,(2) 1 1.2 0 0 0 b(i} vl,3 L( 1) b2A 0 0 0 0 0 0 l°1.3 0 0 0 bw vi.4 bw 0 0 0 0 0 0 r 1.4 0 0 0 £,(1) bl.5 b?3 0 0 0 0 0 !k&lt;-&gt; ri.s fo(2) °2.1 0 0 0 b^.\ b^ 0 0 0 0 0 \b(2} 1 1.6 b(2) *+2.2 0 0 0 ,(1) b2.5 άιη ^4.1 0 0 0 0 b{2} °2.3 0 0 0 0 bw ϋ3.4 b?2 0 0 0 0 ! o b{2) U2A 0 0 0 0 a&lt;‘&gt; ϋ3.5 bw 0 0 0 ! o b(2} t+2 5 h(2) ^3.1 0 0 0 0 bw ^4.4 bw US.2 0 0 0 ! 0 b(2) u2.6 z?&lt;2) ^3.2 0 0 0 0 bw ^4.5 bw DS.3 ,0) b&amp;amp;.i 0 0 ! 0 1 b(2} υ2.7 fe(2). U3.3 0 0 0 0 0 bw ^5.4 v6.2 0 0 ! o 0 b(2} v3.4 0 0 0 0 0 ,( 1) bS.5 dit b6.3 z?(1) v7.l 0 ! o 0 b™ v3.5 r(2) ^4.1 0 0 0 0 0 ,(1) ®6.4 V7.2 0 ! o 0 r(2l b3.6 l(D ^4,2 0 0 0 0 0 r(l) ^6.5 b"&gt; V7.3 fcl'l ^8.1 1 θ 0 bl2&gt; a(2&gt; b4.3 0 0 0 0 0 0 u1.1 lGi ^8.2 ! 0 0 0 r(2) b4.4 0 0 0 0 0 0 r(l) b1.5 b" 8, j ! o 1 0 0 r(2) b4.5 0 0 0 0 0 0 0 h(1) σ8.4 ! o 1 0 0 b™ °4.(, 0 0 0 0 0 0 0 bw US.5 ! o 0 0 a&lt;2) b4J A in A™

Equation 8 -11- SUBSTITUTE SHEET (RULE 261 WO 01/22610 PCT/USOO/02621 for two (k - 2) users, A(U and A(2), having sixteen chips in a data block (Λζ = 16), a channel impulse response length of four (W = 4) and a spreading factor for the first user of two (&lt;2(l&gt; = 2) and a spreading factor for the second user of four (Q(r&gt; = 4).

In the resultant total system transmission response matrix A, bnfr denotes the ilh 5 element of the combined system and channel response for the n‘h symbol of the Kh user.

The received data r is processed using the total system transmission response matrix A which represents a bank of matched filter responses to create a vector of matched-filter outputs which is denoted as y. The matched filtering operation is 10 defined as y = /1 r‘ Equation 9

The matrix AH represents the Hermitian (or complex) transpose of the matrix A. The Hermitian transpose is defined as = A'/ where the over-bar denotes the

operation of taking a conjugate of a complex number. The matched filter outputs are 15 then multiplied by the inverse of an objective matrix O. The objective matrix O represents the processing which differentiates each type of linear receiver model. It is derived from the system transmission matrix A.

The zero-forcing block linear equalizer (ZF-BLE) receiver is a linear receiver -12- r*t in ι rr *·»· «ι /η·«ι r* ***** WO 01/22610 PCT/US00/02621 ♦ with an objective matrix specified as &lt;9 = AHA. The minimum mean square error block linear equalizer (MMSE-BLE) receiver is a linear receiver with an objective matrix specified as O = AHA + &lt;rl where cr is the variance of the noise present on each of the symbols of the received data vector r and the matrix I is known as an 5 identity matrix. An identity matrix is square and symmetric with Is on its main diagonal and zeros everywhere else. The size of the identity matrix is chosen so as to make the addition operation valid according to the rules of linear algebra.

For a decorrelator (decorrelating receiver), matrix A is simplified by ignoring the channel responses hlk&gt;, considering only the spreading codes and their cross- 10 correlation (interference) properties. A cross-correlation matrix, commonly referred

to as R, is generally constructed for decorrelator type receivers. This matrix can be constructed by assuming that W=1 and /i, &lt;A)=l in the definition of A above (i.e. the channel response of every subchannel is an impulse). Then the cross correlation matrix R is the objective matrix O as defined for the ZF-BLE receiver. A 15 decorrelator often serves as a sub-process of a more complex multiuser detection receiver. Once the objective matrix is created, the multiuser detector will invert the matrix, denoted as O '.

The inverse of the objective matrix is then multiplied by the matched filter output vector v to produce estimates of the data vector d where J(estimate) = O’'y. 20 The inversion of the objective matrix O is a complex, computationally intensive process. The number of operations required to perform this process increase as the cube of the size of the matrix O. For most asynchronous CDMA receivers, the size -13- SUBSTITUTE SHEET (RULE 251 WO 01/22610 PCT/USOO/02621 of 0 is very large which makes the process of inversion impracticable.

To overcome this limitation, and to make the system physically realizable, a numerical method due to Cholesky is used. Cholesky decomposition can significantly reduce the computational complexity of inverting the matrix O if the 5 matrix is banded. A banded matrix is a square matrix that contains non-zero values only on several diagonals away from the main diagonal. The number of non-zero diagonals adjacent to the main diagonal that have at least one non-zero element is referred to as bandwidth. Thus, a symmetric matrix M is said to be banded with bandwidth p 10 if zn,·,· = 0 for all j&gt; i + p, Equation 10 where m,Ί is an element of M, with i being the row index and j the column index. For a banded matrix with size denoted as n and bandwidth denoted as p, Cholesky decomposition can reduce the required numeric operations of inverting the objective 15 matrix O from varying as the cube of the size of the matrix, n3, to varying as the size of the matrix times the square of the bandwidth, np2.

As discussed above, the objective matrix for a ZF-BLE receiver is O = AHA. To illustrate the numeric complexity, the objective matrix O for the total system response matrix A shown in Equation 6 is -14- SUBSTTTUTE SHEET (RULE 2S)

<img img-format="tif" img-content="drawing" file="IL148607AD00023.tif" id="idf0003" />

WO 01/22610 PCT/USOO/02621 X X X 0 0 0 0 0 X X 0 0‘ X X X X 0 0 0 0 X X 0 0 X X X X X 0 0 0 X X X 0 0 X X X X X 0 0 X X X 0 0 0 X X X X X 0 0 X X X 0 0 0 X X X X X 0 X X X 0 0 0 0 X X X X 0 0 X X 0 0 0 0 0 X X X 0 0 X X X X X X 0 0 0 0 X X 0 0 X X X X X X 0 X X X X 0

X -X 0 0 x x

X X

X X

X X 0 X 0 0

X X

X X

Equation 11 where zeros denote all elements that by mathematical operation yield zero and with x’j representing non-zero values. If the non-zero elements of the i"' row and j"1 column of the total system response matrix A do not have the same vector index, then 5 the corresponding element of objective matrix O with row index i and column index j will be 0. The bandwidth of O (Equation 11) is equal to 9 since there are non-zero elements as far as nine columns away from the main diagonal.

The objective matrix O as it is constructed in the prior art receiver shown in FIG. 5 is not well banded. Therefore, Cholesky decomposition cannot be used 10 effectively to reduce the operational complexity when inverting matrix O. However, -15- SUBSTTTUTE SHEET (RULE 26) the prior art discloses that when all users transmit with equal spreading factors, a rearrangement of the total system transmission response matrix A can be performed, prior to calculating an objective matrix 0, turning matrix O into a banded matrix. A system block diagram for this process is shown in FIG. 6.

The process which computes the column re-arrangement of matrix A performs the re-arrangement without any additional information. The re-arrangement reduces the operational complexity when inverting the matrix. Once the detection procedure is complete, a user data vector d is computed, a reversed re-arrangement process is performed descrambling vector d back to its original form for further processing.

In a typical asynchronous CDMA system, the bandwidth of a re-arranged objective matrix is at least ten times less than its original size. Therefore, a savings of at least a factor of 100 in processing time is achieved when Cholesky decomposition is performed on an objective matrix based upon a re-arranged total systemresponse matrix. However, the prior ait has not addressed a re-arrangement method for when different spreading factors are in use between active users.

Klein et al., "Zero Forci ng and MinimumMean-S quare-Eiror Equalization for Multiuser Detection in Code-Division Multiple-Access Channels," IEEE Transactions on Vehicular Technology, Vol. 45, No. 2, May 1996, pp. 276-287, discloses multiuser detection approaches. These approaches use a system response matrix in a zero forcing equalizer and a minimum mean square error equalization to recover data.

Karimi et al., "A Novel andEfficient Solution to Block-Based Joint-Detection -16-

Empf,zeit:20/'

AMENDED SHEET 0012

VOLPE AND EOENIC PC

Using Approximate Cholesky Factorization,” IEEE International Symposium in Personal, Indoor and Mobile Radio Communications, XX, XX, Vol. 3, 1998, pp. 1340-1345, discloses a zero forcing-block linear equalizer using an approximate Cholesky factor. The Cholesky factor is derived using a system response matrix,

Accordingly, there exists a need to determine a method to reduce the number of inversion steps when different spreading factors are in use.

SUMMARY OF THE INVENTION

The present invention relates to a multiuser detector that detects and decodes synchronous or asynchronous CDMA subchannels having different spreading factors with reduced computational complexity. The multiuser detector of the present

Empf.zeit:20/ll

AMENDED SHEET -16a- WO 01/22610 PCT/USOO/02621 ♦ invention is compatible with ZF-BLE, MMSE, decorrelating detectors and the like using Cholesky decomposition to minimize numeric operations. The system and method arranges the columns of system transmission response matrices representing the response characteristics of individual users into a well-banded total system 5 transmission response matrix which represents a plurality of matched-filter responses for a given block of received data. The invention in conjunction with Cholesky decomposition reduces the number of required mathematic operations prior to parallel matched filtering. -

Accordingly, it is an object of the invention to detect a plurality of users 10 transmitting over a CDMA interface with reduced computational complexity where each user may employ a different spreading factor.

It is another object of the invention to use existing linear detectors in a multiuser detector without requiring a uniform spreading factor among all CDMA subchannels. 15 It is a further object of the invention to efficiently limit the bandwidth of a matrix that represents a plurality of matched filters prior to inversion.

Other objects and advantages of the system and the method will become apparent to those skilled in the art after reading the detailed description of the preferred embodiment.

20 BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a simplified block diagram of a prior art multiple access -17- SUBSTITUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 * communication system. FIG. 2 is a simplified block diagram of a prior art CDMA communication system. FIG. 3 is a simplified block diagram of a prior art CDMA receiver with 5 multiuser detection. FIG. 4 is a simplified block diagram of a prior art multiuser detector. FIG. 5 is a block diagram of a prior art linear multiuser detector. FIG. 6 is a block diagram of a prior art linear multiuser detector using

Cholesky decomposition. 10 FIG. 7 is block diagram of a linear multiuser detector of the present invention. FIG. 8 depicts system transmission response matrix A(k) top and bottom column offsets. FIG. 9 depicts matrix column index value assignment. 15 FIGs. 10A and 10B are flow diagrams of an alternative method implementing the present invention. FIG. 11 depicts the steps for assembling a spreading factor group matrix ACU). FIG. 12 depicts the steps for assembling an A' matrix in accordance with the present invention.

20 DETAILED DESCRIPTION OF THE INVENTION

The embodiments will be described wi± reference to the drawing figures -18- SUBSTTTUTE SHEET (RULE 25)

<img img-format="tif" img-content="drawing" file="IL148607AD00024.tif" id="idf0004" />

ivurc λιόι HUfcJilG PC @013 where like numerals represent like elements throughout

Shown in FIG. 7 is a multiuser detector 17 of the present invention for detecting, after reception, a plurality of users transmitting over a common CDMA channel. The multiuser detector 17 comprises a plurality of processors having collateral memory which perform, various vector and matrix operations. Alternate embodiments of the invention include fixed, gate arrays and DSPs performing the functions of die various processors. The detector 17 also comprises a first input 19 for inputting individual k subchannel impulse response estimates modeled as vectors A 03 to correct intersymbol interference or ISI caused by a subchannel’s own symbols and multiple access interference or MAI caused by symbols from other user’s subchannels for all received data signals, a second input 21 for inputting data from, all users k transmitted in a discreet block of time in the form of an input vector r containing the combined data from each user’s subchannel and.an output 23 for outputting user data dP3 for each user k from the received channel data r in· the form of an output vector. The total number of users K and the spreading factor for each user (k = 1,2, 3... K) are known a priori.

To obtain user data d!® for a specific user from the combined user data r, the user data must be filtered using a matched filter 25 or the like. One knowledgeable in this art recognizes that a matched filter 25 requires a response characteristic which is the complex conjugate of the combination of the spread pulse shape and the user’s subchannel impulse response to produce an output with a level representative of the signal prior to transmission. Signals input to the filter 25 which do not match with -19-

EmPf-.zeit :70/1 AMENDED SHEET WO 01/22610 PCT/USOO/02621 ♦ a given response characteristic produce a lower output.

Each individual k subchannel impulse response estimate h(k} is input to a first memory 27 where it is combined with the same user’s spreading code 29 (Equation 3) creating a system transmission response estimate matrix A(k} for that user. An 5 arrangement processor 33 of the present invention 17 performs a re-ordering of all matrix An(fc) columns. The arrangement method 99 requires that each subchannel system transmission response matrix A(t) have the column structure defined by Equation 4 which is typical of linear receivers. If the system transmission response matrices Aik) are not of the form defined by Equation 4, the arrangement processor 10 33 first re-arranges the columns to the structure defined by Equation 4. The present invention 17 does not require that all system transmission response matrices A® be concatenated into a total system transmission response matrix A as defined by

Equation 7.

The arrangement processor 33 examines each system transmission response 15 matrix A(1),A(2),A(3), ...Α(λ) column for the number of zero-value elements from the support of each vector bn(k} (Equation 4) defining top σ(λ)Γπ and bottom offsets o(k)Bn as shown in FIG. 8 (for one matrix). As previously described, each system transmission response matrix A(i) has the same number of rows; only the number of columns vary. As shown in FIG. 9, the arrangement processor 33 assigns an index 20 value n; for each column of each system transmission response matrices A(t) based upon their respective top owTn and bottom offsets. The column values are assigned in the order of increasing magnitude from columns having minimal top -20- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 offset with maximum bottom offset to columns having maximum top offset with minimal bottom offset.

If two columns are encountered where one has a greater top offset and a greater bottom offset than another, if the difference between top offsets is greater 5 than the difference between bottom offsets, the column with the lower top offset is assigned the lower index If the difference between bottom offsets is greater than the difference between top offsets, the column with the greater bottom offset is assigned the lower index /2,. If the differences between top and bottom offsets are equal, either of the two columns can be assigned the lower index /2,. 10 The arrangement processor 33 assembles a total system transmission response matrix A' in the order of the assigned column indices nt. The column indices ns are retained in memory 33 for use during the descrambling process 45. As an example, using the total system response matrices A(I) and A(2) described and shown in Equation 8, the arrangement method 99 of the present invention 17 produces the total system 15 transmission response matrix A shown below -21- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 .1,(2) vl,l 0 0 0 0 0 0 0 0 0 0 ’ bm W1.2 0 0 0 0 0 0 0 0 0 0 hl2) W1.3 bw uz.\ 0 0 0 0 0 0 0 0 0 b^ h(2) w1.4 bw 0 0 0 0 0 0 0 0 0 bS b(2} U\.5 b^ bw u3.l άί2) ^2.1 0 0 0 0 0 0 0 0 bw ϋ1.ύ b^ ba&gt; U3.2 b% 0 0 0 0 0 0 0 0 h(2&gt; ^1,7 b% bm W3.3 b2.3 b\'i 0 0 0 0 0 0 0 0 0 bw W3.4 b{2} U2A b?2 0 0 0 0 0 0 0 0 0 h(1) ^3.5 bc'} bw u4.3 b(l) uS.l bl2) v3.l 0 0 0 0 0 0 0 0 a(2) b2.6 h(1&gt; v4.4 b(l&gt; U5.2 b{2} U3.2 0 0 0 0 0 0 0 0 b'2} h(1) ^4.5 bw U5.3 u3.3 bw ^6.1 0 0 0 0 0 0 0 0 0 U5.4 b(2} U3.4 bw U6.2 0 0 0 0 0 0 0 0 0 b'" US.S b(2} U3.5 b(" U6.3 b('} U1.1 b(2} W4.1 0 0 0 0 0 0 0 0 b% b(" u6.4 U7.2 bi2} υ4.2 0 0 0 0 0 0 0 0 bZ bw U6.5 bw u1.3 bl2} U4.3 Ain ϋ8.1 0 0 0 0 0 0 0 0 0 bw ^7,4. b{2' u4.4 Μ» ^8.2 0 0 0 0 0 0 0 0 0 I_ (1) b7.5 b% A&lt;‘&gt; W8.3 0 0 0 0 0 0 0 0 0 0 b% ά(1) ^8,4 0 0 0 0 0 0 0 0 0 0 b% bw σ8.5

Equation 12 -22- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621

The arrangement method 99 indexed the eight columns (1-8) of system transmission response matrix A(1) and the four columns (9-12) of system transmission response matrix A(2) in an order of 1,9,2, 3, 10,4, 5, 11, 6, 7, 12, 8 to create a well-banded total system transmission response matrix A (Equation 12). 5 The arrangement method 99 embodiment described above involves an examination of each system transmission response matrix AU), A(2), A(3), ... A(*’ comparing each column with every other column for top o(k\„ and bottom o{k}Bn offsets. Given the special structure of each system transmission response matrix A(t&gt;, namely, that the columns of each matrix are arranged in order of increasing top offsets and 10 decreasing bottom offsets as you progress from left to right (reference Equation 8, matrices A(1) and A(2)), an alternative method 199 can be performed without having to examine each system transmission response matrix A&lt;fc) directly.

The alternative method 199 is shown in FIGs. 10A and 10B. All system transmission response matrices A(k} corresponding (step 201) to users having equal 15 spreading factors are grouped together (step 203). For each spreading factor group g, memories are allocated within the processor 33 capable of storing all of the columns from all system transmission matrices A(1),A(2),A&lt;3),... Aw. The spreading factor groups g are arranged in order of increasing spreading factor.

An exemplary system illustrating the performance of the present invention 199 20 contains seven users having four different spreading factors Q(k} assigned as follows:

Userl(gn’) = 8 User 2 (0(2)) = 8 User 3 (β(3&gt;) = 8 User 4 (Qw) = 32 -23- SIlRSTmiTF SHEET fRULE 261 * WO 01/22610 PCT/USOO/02621

User 5 (0&lt;S)) = 16 User 6 (g(6)) = 16 User 7 (0(7)) = 4.

Using the system and method 199 of the present invention 17, the system transmission response matrices Aw are separated into spreading factor groups: group 1 (spreading factor 4) ' A(7) group 2 (spreading factor 8) group 3 (spreading factor 16) group 4 (spreading factor 32) A(1),A(2),A(3) a(5),a(6)

Aw. A respective spreading factor group g comprises at least one system transmission response matrix AU), where each matrix Aw is arbitrarily indexed from 1 to LX Each 10 spreading factor group g is indexed according to increasing spreading factor magnitude.

Within each spreading factor group, the columns of the associated system transmission response matrices A(k} are assembled into common spreading factor group transmission response matrices AGX where g = 1, 2, 3, ... G (step 205). As shown in FIG. 11, the method 199 copies the first column' of the system transmission response

15 matrix having index one to the first blank column of AGte); the first column of the system transmission response matrix having index two to the second blank column of AGX continuing throughout the remaining system transmission response matrices in a respective spreading factor group g until all first columns are copied. The method 199 proceeds with copying the second columns, the third columns, etc., for each matrix A

20 in the respective spreading factor group AGX

All matrices in a spreading factor group g have the same number of columns due -24- SUBSTTTUTE SHEET (RULE 25) WO 01/22610 PCT/USOO/02621 to the same spreading factor. Therefore, the assembled spreading factor group transmission response matrices Af*' will have Ifr' times the number of columns in one associated system transmission response matrices A(k\ For equal spreading factors, the arrangement method as-applied to each individual system transmission response matrix 5 per group is similar to prior art techniques for assembling a total system transmission response matrix A.

To assemble a total system transmission response matrix A' accommodating variable spreading factors, the spreading factor group transmission response matrix Acte) having the lowest spreading factor is copied sequentially (step 207) into memory 33a, 10 beginning with the first column, i.e., column one of A^’, to the first allocated column of A'. The spreading factor group transmission response matrix Ασω having the lowest spreading factor has the maximum number of columns. All other spreading factor group transmission response matrix columns will be inserted into this base matrix A'.

If the system spreading factors are even integer multiples of each other (step 209), 15 the processor 33 assembles the total system transmission, matrix A' (step 211) by considering the remaining spreading factor group transmission matrices AG(i) in any order (step 209). For each spreading factor group transmission matrix AcUi, the processor 33 derives a column placement reference index m. m = n-

<img img-format="tif" img-content="drawing" file="IL148607AD00025.tif" id="idf0005" />

(1) (i)

Equation 13 -25- siiRSTmrrp sufft/hule 2bt WO 01/22610 PCT/USOO/02621 • where Ο^} denotes the spreading factor associated with the spreading factor group transmission matrix AGte) under consideration, Q(l) denotes the lowest spreading factor among all groups and tt is the column of the spreading factor group transmission response matrix AG^’ under consideration where n = 1, 2, 3,... N (step 211). 5 To use the column placement index in, a reference location in A' is derived (step 215) using the total number of system transmission response matrices Lw that constitute the spreading factor group matrix having the lowest spreading factor, inxL{l). Equation 14

The processor 33 derives a column set from the spreading factor group transmission 10 response matrix A,^’ under consideration (step 217) using the number of system transmission response matrices that belong to the spreading factor group currently under consideration, LU) x (zz - 1) + 1. through L®xn. Equation 15 15 The processor 33 copies the column set defined by Equation 15 from Aand inserts it (step 219) into the base matrix A' after the column of Ac(1) which has the reference location defined by Equation 14 as shown in FIG. 12. The remaining columns of the spreading factor group matrix under consideration are copied and inserted into the base -26- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 matrix A' similarly (step 221). After all columns from one spreading factor group matrix are placed, the processor 33 chooses the next spreading factor group matrix Αθω

(step 223) and executes the above method. Equations 13, 14 and 15 allow the fA columns from the remaining spreading factor group transmission matrices Af^ to be 5 placed in A' after an mth column that has similar support (step 225).

When the system spreading factors are not even integer multiples of each other, the right side expression of Equation 13 does not yield an integer. In this case, the processor 33 will round the result of Equation 13 to the nearest integer above or the nearest integer below the value (step 213). The rounding direction has negligible effect 10 on overall system performance. The order in which the rest of the group system transmission matrices Acte) are considered may have some effect on the system performance. A priori knowledge of the spreading factors can be used to choose an optimum order in advance.

Using the arrangement techniques described above, and for the case when 15 spreading factors are even integer multiples of each other, a matrix bandwidth B can be achieved which can be shown to be bounded as: W-l if

MAX

β V ^MAX Q{k) &lt;B&lt; W-l

Qmax

β V Umax Zj ntk) k=l V -1

Equation 16

Equation 16 predicts that the bandwidth of the total system transmission response -27- SUBSTTTUTE SHEET (RULE 26) WO 01/22610 PCT/USOO/02621 • matrix of Equation 11 will be between 3 and 6. An examination of Equation 12 reveals that the bandwidth after either arrangement method 99,199 of the present invention 17 is 4.

The improvement the present invention 17 provides is further appreciated as the 5 number of transmitted symbols increase. If a system transmitted 16,000 chips (800 symbols for a first user and 400 symbols for a second user), the bandwidth of the matrix AHA would be approximately 800. Using the arrangement method 99 to produce a total system response matrix A, the bandwidth of A'HA' remains four since bandwidth (Equation 16) is independent of the number of transmitted symbols. After all of the 10 elements of objective matrix O are derived, the inverse 41 is performed. Since the complexity of inverting a matrix is proportional to the square of its bandwidth, the present invention 17 provides a reduction of computational complexity by a factor of approximately (800/4)2=2002=40,000.

The total system transmission response matrix A' provides the response 15 characteristics to the matched-filter 25. Each column of the system response matrix A' is a vector which represents the response characteristics of a particular symbol. The received data vector r is input to the matched-filter 25 where it is matched with every response characteristic from the. total system transmission response matrix A' to produce a matched filter output vector y. Each element of output vector y corresponds to a 20 preliminary estimate of a particular symbol transmitted by a given user. The output vector y from the matched-filter 25 is loaded into a multiplier 43 with the inverted objective matrix O. Both the -matched-filter 25 output vector y and the inverted -28- SUBSTTTUTE SHEET (RULE 25) WO 01/22610 PCT/USOO/02621 objective matrix 0 are multiplied yielding a user data vector d. The user data vector d contains all of the data transmitted from all users during the discreet time block. Since the objective matrix 0 and the matched filter 25 output are based on the total system response matrix A', the user data vector d must be de-scrambled. The de-scrambling 5 process 149 is the inverse of the arrangement methods 99,199. A descrambler 45 re-arranges each element of the user data vector d based upon the column re-assignments performed while undergoing either arrangement method 99, 199. The elements of the data vector d are in the same order dictated by the total transmission response matrix A, 1,9,2, 3, 10,4,5,11, 6, 7, 12, 8, transposed vertically. 10 The descramber 45 allocates a memory space having the same dimension and places each vector element in sequential order, 1-12. After the user data vector d is descrambled 149, the user data is output 23 for further processing.

While the present invention has been described in terms of the preferred embodiment, other variations which are within the scope of the invention as outlined in 15 the claims below will be apparent to those skilled in the art. * * . * -29- SUBSTTTUTE SHEET (RULE 26) , crrixan rwzn arn ιγπερ&amp;amp;ώ pnow pns?n irn nr “|»ob ,Ρ’ηη ηχΰ- πώοβπβ mzrna π^πίώώ np’ioz .zruwan ms rnp’nn pmi1? oxnm □ιηπη Pi? _____ZZzzst SB04003 01 J' ·aoi 08512*40200 .(moiB nzrnn) cras&amp;amp;’Bn nwa