Patent Publication Number: US-6904106-B2

Title: Method and apparatus for spread spectrum interference cancellation

Description:
TECHNICAL FIELD 
   This invention relates in general to the field of radio communications and more specifically to a method and apparatus for spread spectrum interference cancellation. 
   BACKGROUND 
   Code Division Multiple Access (CDMA) has been extensively used in such applications as cellular and satellite communications. CDMA signals increase the spectrum required for the transmission of a particular data rate by modulating each information symbol with a spread spectrum code having a rate larger than the data rate. The same spreading code is used for each information symbol. Typically, the spreading code includes a few tens or a few hundreds elements, called chips, and is chosen from the set of orthogonal (Walsh) codes of the given code length. To decrease the correlations among spreading codes assigned to different users and thereby reduce the interference among different users, the data stream after spreading is typically scrambled with a pseudonoise (PN) code that is generated serially and cyclically and has a larger period than the spreading code. PN codes have considerably better correlation properties than orthogonal codes. Examples of such CDMA signal spreading are the schemes used by the IS-95/CDMA2000 and Wideband Code Division Multiple Access (WCDMA) systems. 
   With CDMA, the signals from all users simultaneously occupy the same frequency band. The receiver discriminates the multiple signals by exploiting the properties of the spreading and scrambling codes that are applied to the signal of each user. The receiver attempts to match in time with the codes of the desired signal a replica of those spreading and scrambling codes. Only then is the demodulation result meaningful; otherwise it appears noise-like. Thus, if the arriving signals have different codes or different code offsets, they can be discriminated at the receiver. 
   In the downlink of cellular communication systems, i.e. the communication from base stations to mobile terminals, the wireless channel may introduce multipath propagation. Even if the signals transmitted by the base station are spread using orthogonal codes (Walsh codes), the multipath propagation will destroy the orthogonality and produce Multiple-Access Interference (MAI). In the uplink (i.e., the communication from mobile terminals to base stations), the signals are asynchronously transmitted. Orthogonality in this case cannot be achieved and each user&#39;s signal will experience MAI. 
   Interference cancellation (IC) attempts to suppress the MAI by estimating and subtracting the contribution of each interferer from the received signal. Because the capacity of CDMA systems is MAI limited, estimating and canceling the MAI will increase the capacity. Alternatively, IC can reduce the signal-to-noise ratio (SNR) required to achieve a specific symbol-error-rate (SER) value for a specific number of users, thereby increasing battery life and decreasing transmission power or increasing the communication range. 
   The challenge in the implementation of IC is that it may have to be performed for many code signals (and their multipath components) at the symbol rate or faster. The associated computation and data storage requirements can place a significant burden on the overall receiver design, not to mention the increase in design cost. 
   The prevailing considerations governing the implementation of IC are complexity and performance with the former being the dominant consideration. One prior art implementation is to perform IC by regenerating the MAI based on a tentative decision for each user, the channel medium estimates and delays of the associated multipaths, and the spreading and scrambling codes. The regenerated MAI is then subtracted from the received signal before despreading. Another prior art approach that avoids signal regeneration is based on the computation of the code cross-correlations among all signals and multipaths. The effect of MAI on the despread signal can then be evaluated and removed. For K users and L multipaths per user&#39;s transmitted signal, this approach results in complexity proportional to (KL) 2  while the approach based on signal respreading can have complexity proportional to (KL) as it will be later discussed. Both approaches offer theoretically the same performance. 
   In addition to IC, MAI suppression can be achieved using linear Multiuser Detection (MUD) methods such as the decorrelating and the Minimum-Mean-Squared Error (MMSE) detectors. With the exception of IC using signal regeneration, all other approaches require knowledge of the code cross-correlations for all signal multipaths of all users. In the case of a long scrambling code having a considerably larger period than the data symbol period (e.g. by a factor of 1000 or more), the code cross-correlations computations need to be performed every symbol period. The total number of code cross-correlations is proportional to the square of the product of the number of interferers and the number of multipaths (KL) 2 . The decorrelating and MMSE detectors need to invert a code cross-correlation matrix with size proportional to the product of the observation window size, the number of users and the number of multipaths per user&#39;s signal. Because matrix inversion has cubic complexity relative to the matrix size, the decorrelating and MMSE detectors are not practical choices in CDMA systems employing long codes. IC based on code cross-correlation computations suffers from similar complexity drawbacks because it requires an equal number of code cross-correlation computations as the decorrelating and MMSE detectors. It also needs to perform the same number of interference subtractions as the computed code cross-correlations. Performing these computations at the symbol rate will substantially increase the corresponding receiver complexity relative to the complexity of a receiver that does not perform multi-user detection or IC. 
   A CDMA system employing short scrambling codes with a period a few times larger than the symbol period, e.g. 8 times, can alleviate the computational requirements of MUD/IC. This is because the code cross-correlations have the same values after every scrambling code period and have to be recomputed only when there is a change in the MAI such as a user signal or multipath being added or deleted, an existing multipath changing its arrival time, etc. Those changes occur at a rate that is much slower than the symbol rate. Nevertheless, the complexity order is still comparable with the one described for long codes, with the only exception that computations related to the evaluation of code cross-correlations are performed at a slower rate. 
   The implementation alternatives for IC are the Parallel IC (PIC) and the Serial IC (SIC). With PIC, all users are simultaneously demodulated, a tentative decision is made for their information symbols, the MAI is regenerated and the process is repeated a number of times until all significant improvements in the Frame-Error-Rate (FER) performance are achieved. With SIC, a similar process is performed with the exception that a decision on the stronger user is first made, the interference from that user on the decision statistic of the next stronger user is subsequently removed and a decision for the next stronger user is made, etc. 
   The main advantage of SIC relative to PIC is that the decision for the stronger users is more reliable than the decision for the weaker ones and therefore, the MAI removal of the stronger users is reliable and this benefits the weaker users. The main disadvantage of SIC relative to PIC is the decision delay associated with SIC because of its serial nature and the architecturally difficult re-ordering of the detection process each time the relative signal strengths change. There are also several modifications that can be applied to the IC process. For example, the decisions made at each IC stage can be hard, soft, clipped or threshold-based, the estimated IC can be weighted to account for the bias that exists in the decisions and for the reliability of the individual decisions depending on the IC stage. 
   The complexity of PIC can be made linear with the number of users and multipaths by using PIC with signal regeneration as suggested in an article entitled “Real-Time DSP Implementation of a Coherent Partial Interference Cancellation Multiuser Receiver for DS-CDMA”, pages 1536-1540, ICC 1998, by N. S. Correal, et al. Each user has its multipath signals regenerated, time adjusted by their corresponding delays, and then added to construct the estimated MAI before despreading. Since this MAI estimate contains all signals subtracting it from the received signal will also cancel the contribution of the desired user&#39;s multipath component and therefore the estimated desired user&#39;s multipath component should also be added. The estimated MAI term is common for all users and only the desired user&#39;s estimated multipath contribution needs to be individually added for each multipath. This is the reason for the complexity reduction from quadratic to linear with the number of users and multipaths. By subtracting the estimated MAI from the received signal, despreading and then adding the estimated desired signal path to effectively remove its presence from the estimated MAI, all signals interfering with the desired signal path are eliminated from the detection of the desired signal. This assumes that the estimated MAI is correct which in turn requires a correct tentative data decision and accurate channel medium and delay estimates. The exemplary embodiment of this invention considers PIC. 
   The exemplary setup in  FIG. 1  describes a conventional receiver (Rake receiver), as it is well known in the art, for K users with L multipaths per user&#39;s signal. It includes a plurality of despreading means, a plurality of timing means, a plurality of spread spectrum processing means, and a plurality of adding means. The signal, which is the superposition of KL signal paths and noise, is received at antenna  10  and is subsequently downconverted and digitized by a down converter  20  and an analog-to-digital (A/D) converter  30  respectively. The searcher  40  identifies L or more paths for each of the K users. Subsequently, L paths for each user&#39;s signal are passed to despreaders  51 ,  52 , etc. Notice that L is generally different for each user. Each despreader (or finger) uses a replica of the spread spectrum code of the particular user&#39;s code that is appropriately delayed in time to synchronize with the corresponding multipath. The l th  despreader output for the l th  path of the k th  user is denoted as D k,l . 
   The plurality of despreaders is shown as 1 st  despreader through K th  despreader. Each despreader includes a chip-code signal generator, a modulo-2 adder and a summer (not shown). In addition to the despread signal paths, the despreader (possibly together with another unit) also provides a channel medium estimate for all multipaths of each user&#39;s signal (C k,l , . . . , C k,L  for user k). The channel medium estimates are needed by the conventional receiver to combine the multipaths and by the IC to regenerate the despread signals. After despreading, the multipath signals for each user and the corresponding channel medium estimates are provided to decision devices,  61 ,  62 , which in the exemplary embodiment comprises a Rake receiver. The Rake receiver performs maximal ratio combining (MRC) on the multipaths of each user&#39;s signal and provides a decision d 0   l    63 , d 0   K    64  for the corresponding information symbol. The decision can be either hard or soft and, for the purposes of IC, it can be either clipped (the soft value is clipped at −1 and +1 for binary transmission) or thresholded (e.g., similar to the clipped one but the soft decision is set to zero if its absolute value is smaller than a threshold). For a receiver employing IC, the Rake decisions constitute the initial decisions and are subsequently provided to the IC system. In an alternate design, the initial decisions can be made with an equalizer circuit. 
     FIG. 2  describes the regeneration process of the signal at the input of the receiver after digitization. Based on the (possibly modified) decisions from the Rake receiver of each user (or another receiver such as a MUD or an equalizer), the IC system first regenerates in the plurality of respread channel blocks  71 ,  72  the signal from each transmitter by spreading the decision  63 ,  64  for each user with the corresponding spread spectrum chip code (CDMA code). Different users may have different spread spectrum chip codes. Subsequently, to account for the channel medium effects on each user&#39;s multipath signals, the respread signal is multiplied with the channel medium estimate for each multipath using blocks  81 - 84  and time delayed by the corresponding multipath delay using delay blocks  91 - 94 . Adder  100  sums all multipaths for the signals of all users and the result  102  is an estimate of the signal at the input of the receiver before despreading. 
   Since the regenerated received signal contains the received signal for each user, its subtraction from the originally received signal will not only remove the interference relative to a desired user but it will also remove the signal of that user. Therefore, for the demodulation of a particular user&#39;s signal, the estimated signal for that user (including the multipaths) should be added to the received signal estimate that is commonly utilized by all users. This can be done prior to, or after, despreading with the second option being the more efficient one since it requires substantially less operations. The estimated signal of each user, including possible multipaths, after despreading is simply given by the estimated information data multiplied with the channel medium response estimate for each multipath.  FIG. 3  describes these corresponding operations using devices  111 - 114  one for each of the multpaths. 
   The conventional (prior art) approach to perform IC is to subtract the estimated regenerated signal from the received signal before despreading. This IC approach is depicted in FIG.  4 . In subtractor  120 , the regenerated signal estimate  102  is subtracted from the received signal  101 . Conventional despreading for each identified multipath of each user follows in the plurality of finger blocks  131 - 134 . The desired user multipath component for each multipath is added in the plurality of adder blocks  141 - 144 . Finally, in the plurality of Rake combiner blocks  151 ,  152 , the multipaths are combined by a Rake combiner and a decision signal  153 ,  154  for the information symbol of each user is produced. The IC process is then repeated several times (IC stages) and typically 3 or 4 IC stages are enough to achieve essentially all performance gains. The regenerated signal at each stage may be weighted (scaled) with different weights having values smaller than or equal to one. This is done in order to remove a decision bias and to reflect that the decisions at the latter IC stages are more reliable. This approach was suggested in U.S. Pat. No. 5,553,062 entitled “Spread Spectrum CDMA Interference Canceller System and Method”, by D. L. Schilling, et. al. 
   For the k th  user, denoting by w k , c k,l , and d k , the spread spectrum code, the channel estimate of the l th  path and the data decision, respectively, the equation describing the despread signal 
       D     k   ,   l       (   i   )         
 
at the i th  IC stage (i&gt;0) is 
               D     k   ,   l       (   i   )       =         w   k   T     ⁡     [       r   _     -     (       ∑       k   ′     ,     l   ′         ⁢       w     k   ′       ⁢     c       k   ′     ,     l   ′         ⁢     d     k   ′       (     i   -   1     )           )       ]       +         c   _       k   ,   l       ⁢       d   k     (     i   -   1     )       .                 (   1   )             
 
   A problem with the IC approach used in  FIG. 4  is its computational complexity. The memory size required with the above approach is proportional to N s N c , where N c  is the number of chips per information signal and N s  is the number of samples per chip, and therefore a large amount of memory is required. A need thus exist in the art for a method and apparatus that can provide IC with reduced complexity and reduced memory requirements as compared to the prior art IC techniques. 
   SUMMARY OF THE INVENTION 
   The present invention describes a reduced complexity spread spectrum code division multiple access (CDMA) interference canceller (IC) implementation to suppress multiple access interference (MAI) in a CDMA communication system. 
   Each of the communication signals is spread spectrum processed by a spread spectrum code. This spread spectrum code may be a pseudo-random (PN), an orthogonal code (Walsh code) or, as in the proposed third generation CDMA-based cellular systems, a code resulting by superimposing a Walsh and a PN code (CDMA code). The uniqueness of the code may be based on different spreading codes or on delayed versions of the same CDMA code. 
   The interference canceller at the receiver includes a MAI regeneration unit and multiple IC units. The MAI regeneration unit utilizes initial decisions made by a receiver to reconstruct the MAI. The receiver making the initial decisions may be a single-user receiver (typically a Rake receiver) or a more complex receiver structure, such as MUD or an equalizer. Using the initial decisions for all users and the corresponding spread spectrum codes, the MAI regeneration unit first performs a function analogous to that of the transmitters and generates the estimated transmitted signal for each user. This signal simply comprises of the corresponding spread spectrum CDMA code modulated by the estimated information symbol. The regenerated transmitted signals have the same time reference. The effects of the channel medium are then mapped on the regenerated transmitted signals. The regenerated signal for each user is delayed by a time period corresponding to each corresponding multipath and multiplied with the channel medium estimate for the particular multipath. The delay and channel medium information for each multipath are typically obtained as a byproduct of the signal detection process (e.g. a Rake receiver is already provided with delay and channel medium estimates for each multipath) and do not add on the overall IC complexity. Once the multipath signals corresponding to each user are reconstructed, they are added to represent the received signal corresponding to the particular user. Once the received signals for all users are reconstructed, they are added to represent the received signal from the plurality of users which is an estimate of the signal observed at the input of the receiver. The regenerated signal is then despread at the time instant of each identified multipath and the result is subtracted from the received despread signal for the corresponding multipath. Because the despread regenerated signal includes the multipath component of a particular path, the estimated despread signal for that particular path is also added after the despread regenerated signal is subtracted. Subsequently, new decisions are made and the previous process may be iterated several times. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features of the present invention, which are believed to be novel, are set forth with particularity in the appended claims. The invention, may best be understood by reference to the following description, taken in conjunction with the accompanying drawings, in the several figures of which like reference numerals identify like elements, and in which: 
       FIG. 1  is a block diagram of a prior art spread spectrum CDMA Rake receiver. 
       FIG. 2  is a block diagram for the received signal regeneration before despreading which is employed by the spread spectrum CDMA interference canceller of the invention and the prior art. 
       FIG. 3  is a block diagram for the regeneration of the signal components corresponding to the communication signals paths after despreading which is employed by the spread spectrum CDMA interference canceller of the invention and the prior art. 
       FIG. 4  is a block diagram describing the architecture for the interference canceller of the prior art. 
       FIG. 5  is a block diagram describing the architecture for the interference canceller of the disclosed invention, according to one embodiment of the invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
   While the specification concludes with claims defining the features of the invention that are regarded as novel, it is believed that the invention will be better understood from a consideration of the following description in conjunction with the drawing figures. 
   The following description can apply to both the base station and the mobile station of a spread spectrum code division multiple access (CDMA) communication system. A system with K users and L multipaths per user&#39;s signal is assumed. Also, although the discussion will use the same number of multipaths for each user&#39;s signal, the number of multipaths for each can be different for each user&#39;s signal but this does not affect the applicability of the disclosed invention while it makes its description clearer. 
   The proposed IC approach in accordance with the present invention is described in FIG.  5 . According to the invention, the regenerated estimated signal  102  is first despread in the IC block  500  by a plurality of blocks (fingers)  161 - 164  for each user using the spread spectrum code of that user at the appropriate time instant defined by the estimated delay of each multipath for that user. The subtraction of the estimated interference from each multipath of each user is performed after despreading in the plurality of blocks  171 - 174 . The estimated multipath component for the desired user is subsequently added in the plurality of blocks  181 - 184 . Clearly, the order of blocks  171 - 174  and  181 - 184  in IC block  500  of  FIG. 5  can be reversed without affecting the invention. Finally, the multipaths of each user are combined in a plurality of decision circuits such as Rake receiver combiner blocks  191 - 192  and tentative decisions are made regarding the information symbol of each user&#39;s signal. In an alternate design, the decisions can be made with an equalizer circuit. Using the same notation as in Equation (1), the equation describing the despread signal for the l th  path of the k th  user with the proposed IC at the i th  stage (i&gt;0) is 
               D     k   ,   l       (   i   )       =       D     k   ,   l       (   0   )       -       w   k   T     ⁡     (       ∑       k   ′     ,     l   ′         ⁢       w     k   ′       ⁢     c       k   ′     ,     l   ′         ⁢     d     k   ′       (     i   -   1     )           )       +         c   _       k   ,   l       ⁢       d   k     (     i   -   1     )       .                 (   2   )             
 
   The difference in the order of operations of Equations (1) and (2) is the same as the one reflected in  FIGS. 4 and 5 . Equation (1) and  FIG. 4  describe the prior art while Equation (2) and  FIG. 5  describe the disclosed invention. 
   The IC process can be repeated several times (several IC stages) until all performance benefits of performing repetitive ICs are exhausted. Typically, this will be up to three or four repetitions. In fact, as suggested by the corresponding equations, the prior art IC method has identical performance with that of the IC method described in the disclosed invention. 
   Comparing to  FIG. 4  which describes the established prior art approach of performing IC, the approach in  FIG. 5  that is proposed in this invention involves KL more adders but the corresponding additions are performed after despreading. Assuming N s  samples per chip and N c  chips per information symbol, the rate at which additions are performed is reduced by N s N c . The number of additions for subtracting the interference before depreading is N s N c  while the number of additions for subtracting the interference after despreading is KL. Typically, for a CDMA communications system operating at or below capacity, KL&lt;N s N c . Therefore, for a system operating at capacity, the number of additions with the IC approach proposed in this invention is smaller than the number of additions with the established IC approach. Also, the corresponding additions are performed at a much lower rate. The proposed IC method has considerably reduced computational complexity relative to the computational complexity of the IC method considered in prior art. This reduction is even larger for communication systems operating below capacity. 
   The memory size for storing the received signal with the established approach is proportional to N s N c , while with the approach proposed in this invention the memory size is proportional to KL. The size (number of bits representing the signal) of the received data stored after despreading is larger than the size of the received data stored before despreading by a factor of 1.5-2 depending on the value of N c . Because the IC performance degrades rapidly for time errors above T c /10, where T c  is the chip duration, typical values of N s  for systems performing IC are N s =8 and N s =16. 
   At capacity, the memory size required by the IC approach in this invention is about four to twelve times smaller than the memory size required with the prior art IC approach. The same is true about the reduction in the number of additions associated with interference subtraction. The IC device and method described herein substantially reduce implementation complexity thereby reducing cost, while retaining all features of interference cancellation. 
   Several other modifications for the proposed IC method and architecture may be devised by those skilled in the art.