Abstract:
A system is provided for increasing the number of users capable of communicating over a wireless network to permit multiple users to transmit information simultaneously on the same channel or frequency in which a Viterbi decoder-based signal separation system is used to pull apart or uncorrupt the otherwise interfering signals on the channel. In one embodiment, two users are assigned to the same channel, with a joint parameter estimation pre-processor being utilized to provide an estimation of the power, time and frequency offsets and phase of the incoming signals. The joint parameters estimated by the parameter estimation unit are applied to a signal separator which recovers and pulls apart the two signals. The subject system is capable of accommodating more than two simultaneously transmitted signals to provide signal packing over existing channels without requiring new waveforms through the utilization of stripping techniques and tail chopping techniques so as to minimize the computational load involved in separating the signals.

Description:
FIELD OF INVENTION  
         [0001]    This invention relates to communication systems and more particularly to a method and apparatus for uncorrupting or separating signals from multiple users transmitted simultaneously over the same frequency and in the same time or overlapping slot.  
         BACKGOUND OF THE INVENTION  
         [0002]    It will be appreciated that wireless networks have of late become overloaded due to the increasing number of users seeking to communicate with the cell towers. Various communications schemes have been proposed in order to multiplex the signals so that a large number of users can communicate with a given cell tower. In general for analog phones, the analog system provides one communication channel per user. As a result the analog service has become quickly overloaded with the large number of users seeking access to a cell tower. In order to accommodate the overloaded conditions, time division multiplexing, TDMA, frequency division multiplexing, FDMA, and code division multiplexing, CDMA, have been utilized to accommodate many users per tower. By multiplexing is meant multiple access in which the number of users communicating with the cell tower are organized so as not to interfere with one another, allowing an equitable sharing of the channel resource.  
           [0003]    The original premise for TDMA type systems was a 3 to 1 advantage which has in general been realized. CDMA systems have initially promised a 20 to 1 advantage, but practically have been able to realize only a 3 to 1 advantage.  
           [0004]    Additionally, satellite communications have required a certain amount of multiplexing to be able to accommodate users seeking to communicate through satellite uplinks and downlinks.  
           [0005]    While the above-mentioned techniques for providing multiple access have proved useful in accommodating the increasing number of users, the number of users for wireless services has increased beyond the capacity of present systems to be able to accommodate them.  
           [0006]    What is therefore necessary is a system that can accommodate simultaneous transmission from multiple users on the same frequency sharing the same time slot or channel. In order to be able to do this a system is required which can uncorrupt or separate simultaneously received signals. Not only is such a system required, it is also a requirement that the descrambling or separation be not computationally complex so that the computation can be carried out by processors in hand-held wireless units.  
           [0007]    By way of further background, the original inception of multiple access (MA) for the wireless medium was dictated primarily by the need for simple receivers. MA schemes have traditionally assigned user&#39;s waveforms and timing protocols for the sole purpose of eliminating or minimizing interference among the various users that simultaneously access a shared wireless channel so that a simple matched-filter receiver can reliably detect any signal of interest. Specifically, time division multiple access (TDMA), frequency division multiple access (FDMA), code division multiple access (CDMA) and hybrid schemes force signals to be orthogonal in which there is no interference whatsoever, e.g. different users are assigned completely different timeslots or nearly orthogonal wideband signals such that there is negligible interference between any two signals sharing the same bandwidth. These systems work well within the primary original motivating constraint, namely, lack of computing capabilities in the receiver. Bandwidth, on the other hand, was plentiful relative to the original appetite for throughput.  
           [0008]    Many decades later, three trends impact wireless communication: 1.) computing capabilities have improved many fold, 2.) the requirement for information throughput has increased exponentially, and 3.) the bandwidth available for typical MA systems has decreased. The imposition of orthogonal signal assignment coupled with limitations in available bandwidth result in MA systems that fall far short in capacity or throughput for today&#39;s needs.  
         SUMMARY OF THE INVENTION  
         [0009]    In order to uncorrupt or to separate simultaneously transmitted signals on the same frequency a Viterbi decoder is utilized to provide a shortest path procedure to pick a joint bit stream that has the highest probability of occurrence given the data received. In essence each of the two or more simultaneously transmitted signals has characteristics which can be ascertained which permit the separation of the signals and the descrambling thereof. It is the recognition that two simultaneously discretely modulated transmitted signals have enough identifying characteristics that makes possible their separation.  
           [0010]    Two signals which arrive simultaneously on the same frequency and not having vastly different received powers appear so scrambled that neither of the signals is intelligible. In short, one signal appears as noise to the other signal and vice versa. It has been found in the subject invention that there is sufficient information on the simultaneously transmitted signals to perform signal separation through the utilization of a parameter estimation pre-processor and the utilization of techniques which shorten the exhaustive search done by a Viterbi decoder in the signal separation process, first by a hybrid stripping based on power and secondly by inter-symbol interference tail chopping for the formulation of the receiver detector/decoder algorithm.  
           [0011]    Generally, the solution to the problem of increasing throughput without increasing bandwidth lies in the application of multi-user detection (MUD) theory. Multi-user detection is described in S. Verdu, Multi-user Detection, Cambridge University press, 1998, Chapter 4, which includes a detailed description of signal separation using an exhaustive search. This search analyzes all of the possibilities of data points when multiple signals are combined.  
           [0012]    More generally, the premise behind multi-user detection is not to treat the “other user” interference as noise. Indeed, the interference is nearly entirely deterministic in that much is known about the interfering signals such as the symbol waveform, modulation scheme, and symbol rates. The multi-user detector takes advantage of all that is known at the receiver about each of the interfering digitally modulated signals.  
           [0013]    It has been found that multi-user detection can: 1.) allow for robust operation of a communication link in the presence of other user interference, 2.) eliminate weak user dropout (the near-far problem) in a multiple access system employing “nearly orthogonal” signaling such as described in the IS-95 protocol, 3.) eliminate the need for power control to ensure that all signals are being received by the base station at the same power, and 4.) increase throughput since more simultaneous users can co-exist and transmit on the same frequency or channel since intentional interference is allowed.  
           [0014]    The subject invention involves improvements made to the theoretical techniques of multi-user detection to solve the practical problems associated with increasing the number of simultaneous users for any actual commercial system that employs orthogonal signaling such as TDMA, FDMA or hybrid of the two. One such example system that employs orthogonal TDMA/FDMA is the cellular GSM system in use in Europe and elsewhere.  
           [0015]    The present invention solves two challenges associated with the realization of MUD-based extensions to existing MA communication systems to allow for a many fold increase in user capacity.  
           [0016]    First, in general, the optimal exhaustive search MUD that can be implemented with a Viterbi algorithm (shortest path algorithm) is exponential in complexity per bit decoded, meaning that the number of states per stage, M^ (nK), is impractically large when n, the Inter-Symbol Interference (ISI) number, times K, the number of users is greater than 12. Thus, in a practical multi-user environment n×K could easily exceed 24 such that the complexity per bit decoded is many hundreds of gigaflops or floating point operations per bit. The largest handset computational capacity is on the order of megaflops which will not support an exhaustive multi-user search signal separator like that in Verdu, Chapter 4. As will be seen, the subject system reduces n by tail chopping. As to K, a grouping of signals based on power reduces K into two or more sub groups, with which each subgroup containing no more than k users, and for which n×K is not excessive.  
           [0017]    Second, all previously proposed methods to reduce complexity either require that one design new waveforms that will deviate from existing specifications for existing and upcoming wireless systems, or allow ad-hoc interference as long as the interfering waveforms comprise a linearly independent set. The requirement of linearly independent waveforms does not hold if one were to over-pack a GSM cellular timeslot in a single cell or an ACES satellite timeslot in a single spot beam, for example.  
           [0018]    Note that the subject system does not require the design of new waveforms and does not require the use of a linearly independent set in order to achieve over-packing for existing and proposed systems employing orthogonal signaling. Prior to the invention, such a method of over-packing would require the use of the computationally impractical exhaustive search optimal MUD detailed in the Verdu text.  
           [0019]    The exponential complexity problem has been solved by improving the theoretical insights corresponding to multi-user detection for asynchronous linearly dependent signals with intersymbol interference to eliminate this impractical complexity.  
           [0020]    The primary reason to reduce complexity is so that real time operation is possible with state of the art processors that can be inserted into current base stations, user phones, and other transmit/receive devices that may wish to employ the subject system.  
           [0021]    Furthermore, the user phone or small device can tolerate only small increases in complexity relative to what a base station can tolerate. The present invention involves a way to pack existing signals into the available bandwidth in such a way as to allow for a MUD procedure that is as computationally simple. The subject small device receiver algorithm is as computationally simple as a state of the art receiver and can be accomplished in real time within present state of the art processing for handsets.  
           [0022]    In one embodiment, the subject system consists of the following five core pieces:  
           [0023]    1. An asynchronous over-packing scheme for channels in the reverse link (mobile to base, or small computing device typically associated with the user to big computing device typically associated with a controller).  
           [0024]    2. A parameter estimation block that proceeds the signal separation block.  
           [0025]    3. A signal separation block for the controller (e.g. in the base station receiver) that outputs the channel bits to be processed by the existing system elements such as de-interleaving and error correction decoding.  
           [0026]    4. A synchronous packing scheme for the forward link (base to mobile or big device to little device).  
           [0027]    5. A signal separation block for the user&#39;s device (e.g. mobile telephone) that outputs the channel bits to be processed by the existing system elements such as de-interleaving and error correction decoding.  
           [0028]    A sixth power control scheme may be used for improving the bit error rate both on the forward and reverse links.  
           [0029]    The packing scheme for reverse link channel is very simple. The controller simply assigns one or more users to the exact same channel. Thus, in a GSM system, the base station controller would assign all empty time slots to active users. If a new user requests a time slot, the controller assigns a time slot that is already occupied.  
           [0030]    The parameter estimation block calculates estimates of each user&#39;s received power, baud timing offset, frequency offset, and oscillator phase. The controller, during acquisition with a new user, sends the received acquisition signal to the preliminary parameter estimation sub-block which computes maximum likelihood estimates for received power, baud timing offset, frequency offset, and oscillator phase. This information is then conveyed to the parameter refinement sub-block which refines the estimates of these parameters for the new user as well as the existing user or users in the shared time slot.  
           [0031]    The signal separation block consists of an algorithm which automatically alternates between two modes of operation within the receiver. It reverts to a simple stripping procedure whenever possible when relative received signal powers are favorable to stripping. Whenever stripping is not capable of giving the required bit error rate, the receiver reverts to an inter-symbol interference (ISI) tail-chopped version of the optimum asynchronous multi-user detector. For more than two users, a hybrid between the ISI chopped optimum multi-user detection and stripping is used.  
           [0032]    When the powers of the recovered signals are less than 6 dB apart, tail chopping is used to reduce computational complexity. The stripping procedure has the lowest complexity of all multi-user detection procedures, but suffers from bad bit error rate unless the received powers are greater than 6 dB apart in which the highest power signal dominates.  
           [0033]    The subject inter-symbol interference tail-chopped exhaustive search is an improvement over the optimal exhaustive MUD detailed in the Verdu text, and achieves a substantial reduction in complexity by reducing the number of states per stage in the Viterbi decoder used for finding the maximum likelihood joint sequence. It does so by ignoring the presence of inter-symbol interference tails in the formulation of the optimum exhaustive search MUD.  
           [0034]    For two or more users packed within the same channel, the grouped hybrid method is employed. This method groups signals into families according to their received power. In one embodiment, the lowest power signal in one family must be 6 dB higher than the highest power signal in the next lowest power family. The ISI-chopped exhaustive search MUD is performed on one family at a time, starting with the highest power family and working down in power order. After a bit stream is produced for each user in that family, the received signals are recreated using the entire signature pulse for each user in that family without the ISI tails chopped. This recreated interference signal is then subtracted from the original received signal to create an interference-reduced signal. Note, that prior to recreation of the interference signal, the bit streams may be corrected by applying the appropriate error correction if feasible. The above MUD-remod-strip procedure is repeated until all signal families are detected and/or decoded. This block requires all parameters estimated in the parameter block, along with the total number of users sharing each channel.  
           [0035]    As to tail chopping, tail chopping merely requires providing the replica of a user&#39;s signature pulse without tails to the extensive search multi-user detector. Note that when constructing the trellis (Viterbi decoder) that performs the exhaustive search to determine the optimal set of bit streams associated with the received signal comprised of the aggregate of a number of interfering signals, one must provide a replica of each user&#39;s signature pulse, and it is this signature pulse which is provided with tails removed to the Viterbi decoder.  
           [0036]    When one provides the complete pulse over its entire non-zero duration, which is typically more than 6 bit durations for K interfering signals, the resulting Viterbi decoder will have M^ (Kn) states per stage, where M corresponds to M-ary modulation (e.g. M=2 is binary phase shift keying), K is the number of interfering users, and n is the ISI number (e.g. the number of bit durations for which the signature pulse is non-zero).  
           [0037]    The computational complexity required for the Viterbi decoder to search all possible paths corresponding to all possible bit combinations is proportional to the number M^ (Kn) which is the number of states per stage of the trellis.  
           [0038]    In order realize a significant reduction in computation required per bit, in the subject invention, a tail-chopped version of each user&#39;s signature pulse is provided to the exhaustive search multi-user detector. In the case where one chooses to set the pulse to zero beyond the rth bit duration, where r&lt;n, one now has an exhaustive search via a Viterbi decoder with a reduced number of states per stage in the trellis, namely M^ (Kr).  
           [0039]    When the user signals are being received with similar powers, this tail chopping causes negligible degradation in the performance of the, now suboptimal, exhaustive search multi-user detector, but provides the desired bit streams with a significantly lower complexity.  
           [0040]    In the case where the received signals are separated by a larger power difference, such as 6-7 dB, the error rate in the bit stream associated with the lower power user is significantly degraded by using the tail-chopped version of the exhaustive search multi-user detector.  
           [0041]    To solve this degradation problem, the subject invention uses a power ordered stripping technique. When the power separation between highest power signal and the remaining signals is greater than 6 dB then the highest power signal is stripped off with a full tail, with lower power signals having tails chopped in the formulation of the Viterbi-decoder-based search to eliminate complexity that these tails cause in the optimal signal separation process.  
           [0042]    Thus, in the more general case of making use of stripping to reduce the complexity consider to the case where any two power-adjacent received signals are separated by a large amount, e.g. 6 dB. In this case one reduces the complexity by stripping off the group of higher power signals, thus reducing the number, K, of interfering users expected by the exhaustive search multi-user detector. Specifically, one tells the exhaustive search multi-user detector that there are only I users, the number of users in the highest power grouping. In effect, one has decided to treat all other users as background noise. Once these users have been decoded, they are recreated with full ISI tails and stripped from the received signal to create an interference-reduced signal, e.g. an estimate of what would have been received if none of the I signals in the highest power grouping were present.  
           [0043]    Since the other users are all much lower in received power, e.g. 6 dB lower than the lowest power user in the higher power grouping, this sub-optimal assumption causes negligible degradation to the bit error rates of the users in the high power grouping.  
           [0044]    The benefit of tail chopping and iteratively stripping off users is that the computational complexity required is at least an order of magnitude lower since the complexity required is only on the order of M^ (Ir) computations per bit decoded. This is significantly smaller than M^ (Kn) since I&lt;K and r&lt;n.  
           [0045]    Once the decoded bits associated with the I users in the highest power grouping have been decoded, the signals are reconstructed using the full signal with the full tails covering n bit durations and the reconstructed full signals are subtracted from the received signal. One now has an estimate of the received signal that does not include the I users in the highest power grouping. The process is then iterated, detecting and stripping off the next highest power group of signals until there are no more signals left.  
           [0046]    In one embodiment, the power grouping is done by the parameter estimation block. The parameter estimation block must determine each user&#39;s power as part of its function. It then orders the users by power. Once ordered, the users are grouped together according to power families for which there must be a large power difference, e.g. 6 dB, between the lowest power user in one family and the highest power user in the next lower power family.  
           [0047]    If there are only a total of two users, then the power grouping would either separate the two users in to two “groups” if there was 6 dB or greater difference between them, or group them together in one grouping if there was not.  
           [0048]    As to the forward link, the subject synchronous packing scheme for the forward link allows for a simple signal separation procedure in the user device. Here, the subject system takes the ability to perform an orderly signal packing in the controller prior to sending the signal out to the forward channel. This is useful in that any timing or phase offsets are known by the handset prior to parameter estimation.  
           [0049]    Note that, the separation algorithm block within the user device may be same as that in a base station.  
           [0050]    As a further improvement a power control scheme can be implemented to control the power at the handsets to provide for groups of received signals based on power levels to permit more rapid processing by, in effect, reducing K into sub-groups of smaller k&#39;s.  
           [0051]    The primary benefit of supersaturated communications is a significant increase in the throughput of existing cellular, PCS, and satellite multiple access communication systems, as well as systems currently being designed for future use such as next generation cellular, local wireless loop, and wireless local area networks for wireless internetworking of devices or appliances.  
           [0052]    In summary, a system is provided for increasing the number of users capable of communicating over a wireless network to permit multiple users to transmit information simultaneously on the same channel or frequency in which a Viterbi decoder-based signal separation system is used to pull apart or uncorrupt the otherwise interfering signals on the channel. In one embodiment, two or more users are assigned to the same channel, with a joint parameter estimation pre-processor being utilized to provide an estimation of the power, time and frequency offsets and phase of the incoming signals. The joint parameters estimated by the parameter estimation unit are applied to a signal separator which recovers and pulls apart all the signals assigned to the same channel. The subject system is capable of accommodating simultaneously transmitted signals to provide signal packing over existing channels without requiring new waveforms through the utilization of stripping techniques and tail chopping techniques so as to minimize the computational load involved in separating the signals. 
       
    
    
     BRIEF DISCRIPTION OF THE DRAWINGS  
       [0053]    These and other features of the subject invention will be better understood in connection with the Detailed Description in conjunction with Drawings of which:  
         [0054]    [0054]FIG. 1 is a diagrammatic illustration of multiple wireless users simultaneously communicating with a cell tower on a single frequency or channel, with the received signals being sorted out at a base station by signal processing to uncorrupt the interfering signals;  
         [0055]    [0055]FIG. 2 is a diagrammatic illustration of two signals sent at the same time on the same frequency and in the same time slot if TDMA is used, with the result being a corrupted or scrambled and undecipherable result;  
         [0056]    [0056]FIG. 3 is a diagrammatic illustration of a prior art system in which digitally encoded in-phase and quadrature signals are detected using matched filters typically having a root-raised cosine filtering characteristic in which the in-phase and quadrature components are sampled at the bit rate to provide either +1 or −1, with the sign of the bits conveying the transmitted information;  
         [0057]    [0057]FIG. 4A is block diagram of the present invention illustrating the transmission of two signals simultaneously on the same channel or frequency to a base station in which the individual signals are separated by first using a joint parameter estimation unit and providing these parameters in refined form to a signal separation unit which utilizes a Viterbi detector, an exhaustive search, and a method to limit the exhaustive search by ISI tail-chopping and stripping techniques;  
         [0058]    [0058]FIG. 4B is a detailed block diagram illustrating an implementation of the multi-user detection system of the present invention;  
         [0059]    [0059]FIG. 5 is waveform illustrating the existence of identical signals and the effect of a tail of a preceding portion of the signal;  
         [0060]    [0060]FIG. 6 is a of vector diagram illustrating the result of combining 2 BPSK in-phase detected signals, illustrating regions of uncertainty as to the data points;  
         [0061]    [0061]FIG. 7 shows two vector diagrams for two different signal realizations for {S 1 , S 2 } of the received constellation illustrating in two dimensions the uncertainty of the data points in the received constellation which is the result of the detection of simultaneous signals on the same channel or frequency but with arbitrary relative phases;  
         [0062]    [0062]FIG. 8 is a block diagram illustrating one technique for decreasing the computational complexity of signal separation in which the signal representing the highest power user is stripped off, if it is more that 6 dB higher in power than the second highest power signal. This is followed by processing the remaining signals with an exhaustive search multi-user detection algorithm in which inter-symbol interference tails beyond r symbols are ignored;  
         [0063]    [0063]FIG. 9 is a block diagram illustrating that if the interfering signals are not separated in power by a pre-determined amount (e.g. 6 dB), then an exhaustive search multi-user detection technique is applied;  
         [0064]    [0064]FIG. 10 is a block diagram illustrating that the number of signals currently assigned to a traffic channel is utilized in joint multiple-user parameter refinement along with single user parameter estimates and the received signals to provide parameters to the joint multiple-user signal demodulation section;  
         [0065]    [0065]FIG. 11 is diagrammatic illustration of the utilization of stripping in which various groups of users are processed separately based on power;  
         [0066]    [0066]FIG. 12 is a diagrammatic illustration of the utilization of inter-symbol interference tail modification in the formulation of the optimum asynchronous multi-user detector, followed by remodulation which recreates received signals with full inter-symbol interference tails for users in the current grouping so as to achieve an estimate of the received signal if the only users present were those having powers below those in the current grouping; and,  
         [0067]    [0067]FIG. 13 is a block diagram illustrating the joint parameter estimation process. 
     
    
     DETAILED DESCRIPTION  
       [0068]    Referring now to FIG. 1 what is shown is a typical GSM system in which in-phase and quadrature components of the transmitted signals are recovered to provide a bit stream which conveys the information transmitted. Here a network  10  is utilized to transmit the information to and from multiple users  12 ,  14  and  16  and a base station  18  through a wireless communication network to and from a cell tower  20 . The ability to overuse frequencies is depicted by a situation in which there are multiple simultaneous users all assigned to a single channel or TDMA time slot at a given frequency. Thus User  1  transmits on Channel  1 , as does User  2  and all other users assigned to that channel, up to User K. It is the purpose of the subject system to sort out the interfering signals with signal processing at the receiver, in this case at the base station. It will be appreciated that identical processing is carried out in each of the handsets so that full duplex, two-way communication can be achieved by multiple users on both the forward and reverse channels. By so doing, the channel capacity of a tower, a satellite or other transmit/receive point can be augmented by the amount or the number of users that can simultaneously utilize a given channel.  
         [0069]    Referring to FIG. 2, if two users, here illustrated at  22  and  24 , were to simultaneously transmit information over the same frequency, a base station  26  coupled to a matched filter  28 , in turn coupled to a decision unit  30  would provide as an output hopelessly corrupted signals. The reason is that the individual signals would be interfering with each other. In present systems, signals are intentionally coordinated to avoid interference because if one signal were to interfere with another signal and if no attempt was made to remove interference or to disambiguate the signals, the demodulated signal is corrupted beyond recognition.  
         [0070]    It has been found, however, that there is a significant amount of information carried by each of the signals which can be utilized to identify the signals and to separate them to provide intelligible information.  
         [0071]    Referring now to FIG. 3, the case is illustrated where there is one signal per channel. Here a transmitting source  32  transmits to a receiver  34  utilizing an in-phase, quadrature modulation scheme with a root raised cosine transmitter filter. A matched filter  36  is provided with a root raised cosine filter. This is followed by  37  in which they are separated, then in-phase and quadrature components sampled at  38  and in-phase and quadrature sample streams in which the information is carried in the sign of the samples. In the illustrated example the bits are either −1 or 1, with the in-phase and quadrature signals from the matched filter being sampled by clock  40  at the bit rate. These in-phase and quadrature signals are then supplied to an interleave re-assembler  42  which results in a demodulated output  44  corresponding to recovered in-phase and quadrature components of the modulated signal.  
         [0072]    Referring now FIG. 4A, in one embodiment, in the subject system two or more simultaneous signals are transmitted from handheld units  22  and  24  to a base station  26 . Here, the output from the base station is supplied to a joint parameter processing unit  50  which seeks to recover all relevant parameters of both signals in terms of power, offset and oscillator phase. As will be described, processor  50  may provide these joint parameter estimates through an estimation process. As illustrated at  52 , a power, offset and phase detector is utilized to provide an initial estimate of parameters from signals on the acquisition channel. Note, that detector  52  operates by calculating the parameters during the acquisition phase in which the new transmitter sends its signal over the control channel  54  without any interference from other users in that channel.  
         [0073]    It will be appreciated as illustrated at  56  that base station  56  assigns two users to the same channel, with the number of signals on the same frequency  58  being derived therefrom. This information is passed to the joint parameter estimation processor  50  and signal separator  60  so that the appropriate estimations are provided to signal separation unit  60 .  
         [0074]    The output of the base station, namely the scrambled signals, are coupled to signal separation unit  60 , the operation of which will be described hereinafter. Utilizing the power, offset and phase estimations, signal separation unit  60  disambiguates or recovers the data streams corresponding to the two signals based on multi-user detection techniques. It employs an exhaustive search algorithm which, in essence, runs through all the possibilities of data points in a received constellation and determines which data points belong to which signals. The ability for this algorithm to sort out the various data streams from the corrupted received signal is due in part, to the different powers, offsets, and phases. As can be seen in FIG. 4B, the description of multi-user detection is in accordance with the Verdu text, Chapter 4.  
         [0075]    The minimum bit error rate multi-user detector can be implemented by a dynamic programming algorithm that carries out an exhaustive search of all possible bits streams for all interfering users jointly to ascertain the most likely bit stream for each user. Having assigned bit streams to users means that the transmitted information corresponding to each interfering user is separated. The exhaustive search carries out two independent iterations each of which requires a computational effort proportional to the number of stages and to the number of states per stage M Kn . Therefore the complexity per bit is on the order of M Kn .  
         [0076]    It will be thus appreciated that the exhaustive search algorithm utilized to determine which of the data points pertain to which of the interfering signals requires an extensive amount of computation power. In general, multi-user detection has been accomplished with relatively massive computers. Such intense computations cannot presently be carried out by the CPUs within handsets or within the base station. It is therefore important to be able to cut down on the exhaustive search in order to be able to implement the signal separation bits in a handheld unit and in real time at the base station.  
         [0077]    Referring now to FIG. 5, how the computational reduction is accomplished is now described using a simplified example. It will be seen that two waveforms  62  and  64 , having identical phases, exist in respective envelopes, are summed as illustrated at  66  and are extracted by filter  68  and then sampled at  70 . The result has four possible values +A 1 +A 2 , +A 1 −A 2 , −A 1 +A 2 , or −A 1 −A 2 . These components can be plotted as data points in a received constellation and as illustrated in FIGS. 5, 6 and  7  where each shows a different phase and power relationship between the two signals. There is a certain amount of uncertainty as to these data points due to background and receiver noise as illustrated at  74 .  
         [0078]    It is the purpose of the exhaustive search, in effect, to be able to provide an estimate of the actual data point in the received constellation and it is this search that must be heavily curtailed or refined so as to reduce the computational load.  
         [0079]    One of the contributors to the total number of the data points to be searched is the length of the inter-symbol interference tail, here illustrated at  80 , which will be seen to exist from a latter portion of the signal  84  and is interfering with the main portion of pulse  82 .  
         [0080]    As one of the aspects of the subject invention, this tail is ignored to provide a more amenable number of data points in the received constellation. Specifically, this corresponds to less states per stage in the search trellis or Viterbi decoder.  
         [0081]    It will be appreciated that the effect of the tail of one user on the succeeding main portion of the pulse corresponding to the other user is power dependant. For instance, if the power of the signal which is interfering is relatively low compared to the highest power signal, then the effect of ignoring the lower power signal tail is minimal on the exhaustive search process results pertaining to the highest power signal. On the other hand, the effect of ignoring the high power signal tail is catastrophic on the results of the exhaustive search that pertain to the lower power signal. If both signals are received at relatively similar powers, then ignoring the tails causes only negligible increase in the size of the uncertainty cloud around each point in the constellation, while dramatically reducing the total number of points that must be searched. What this means is that the exhaustive search need not go through a tremendous number of possibilities in order to assign a data point to a given signal if ISI tails can be ignored.  
         [0082]    The two techniques of ignoring inter-symbol interference tails beyond r-symbols, r&lt;n, and the use of a stripping technique to strip off the highest power user or group of users are illustrated in FIG. 8. Here the simplest rendition is shown for which the highest power user is stripped off at  86  prior to the exhaustive search multi-user detection being performed, as illustrated at  88 . It will be appreciated that in the exhaustive search multi-user detection inter-symbol interference tails beyond r bit durations are ignored. The combination of the stripped-off highest power user and the ignoring of the tails reduces the computation load by, in general, at least five orders of magnitude in the recovery of the various bit streams, here illustrated by B 1  and B 2  . . . B k .  
         [0083]    As illustrated in FIG. 9, if the signals are of the same power, there is no stripping and the exhaustive search multi-user detection  88  is performed, again ignoring interference tails.  
         [0084]    Referring now to FIG. 10, more particularly, base station controller  90  provides the received signal in the acquisition channel over line  92  to a standard single user parameter estimation unit  94  which is in turn coupled to a joint multi-user parameter refinement and user grouping unit  96 . Also, an input to unit  96  is the number of signals currently assigned to traffic channel X as illustrated by line  98 .  
         [0085]    The received signal in traffic channel X is delivered over line  100  to unit  96  and to a joint multiple-user signal demodulation unit  102  which requires the output  104  of the parameter refinement and user grouping unit.  
         [0086]    Note that the standard single user parameter estimation unit is coupled to the joint parameter refinement and user grouping unit  96  via a line  106  which provides to this unit initial estimates of power, carrier phase, carrier offset, and timing offset. The output of the joint multiple-user parameter refinement and user grouping unit is a set of improved estimates of power, carrier offset, and timing offset for all the signals in traffic channel X. These five parameters and user groupings are utilized by the joint multiple user signal demodulation unit so as to be able to output a raw bit stream for user  1 , user  2 , user K, representing the separated signals.  
         [0087]    It will be noted that unit  96 , also functions to determine a grouping of the incoming signals in terms of their relative power.  
         [0088]    It will be appreciated that the raw bits streams may be run through the remaining processing already present in the system such as the deinterleaving, error correction decoding and other filtering techniques.  
         [0089]    Referring now to FIG. 11, the joint multiple user signal demodulation system is described. Here joint multiple user signal demodulation unit  102  has an input which is the received signal in channel X, here illustrated at  100 . As will be seen, the received signal is applied to a joint demodulation, remodulation, stripping and user grouping unit  110  which in essence processes a first group of q1 incoming signals which have been grouped according to power.  
         [0090]    The output of User Group 1 unit  110  is an estimate of the received signal if the only users present were those having received powers below those in the first grouping. This output is then applied to a joint demodulation, remodulation stripping unit for User Group 2 as illustrated at  112 , the output of which, again, is an estimate of received signal if the only users present were those having received powers below those in the second grouping.  
         [0091]    The process is iterative such that for all user groupings up to user grouping L the process continues until the signals are processed for user grouping L as indicated at  114 . It will be noted that the output of each of units  110 ,  112  and  114  are raw bit streams for all users in the particular groupings. For instance, the output on line  116  is the raw bit stream for all q1 users in the first grouping, on  118  the raw bit stream for all q2 users in the second grouping and on line  120  the raw bit stream for all qL users in the last grouping.  
         [0092]    Referring now to FIG. 12, the operation of a joint demodulation, remodulation and stripping unit is described.  
         [0093]    Here input signal  100  is applied to an optimum asynchronous multi-user detector  130  for a user in a current grouping, in this case the first grouping. This unit also takes into account ISI tail modifications.  
         [0094]    The optimum asynchronous multi-user detector or MUD  130  is the unit which performs the multi-user detection utilizing the techniques described in Verdu, Chapter 4 and in this case ignores the existence of intersymbol interference tails that exists beyond the appropriate number of symbols, say, r. This is done to significantly reduce the computational complexity of the exhaustive search provided in this unit.  
         [0095]    As indicated in Chapter 4 of Verdu, the multi-user detection algorithm requires the knowledge of received powers, phases, frequency offsets, and timing offsets for all users sharing the channel which is the output from the joint parameter estimation procedure. In addition, user-grouping information is also passed over line  104  to unit  130 .  
         [0096]    From this information unit  130  determines the q1 signals to be processed and the K-q1 signals to be ignored at this stage. By grouping together a small subset, q1, of the total number of users, K, one reduces the complexity of the optimum asynchronous multi-user detection and results in complexities M q1×r  where q1 is the number of users in this first sub-group. Recall that r is used to denote the reduced ISI number which is less than n, the actual ISI number.  
         [0097]    It will be appreciated that the output of unit  130  is a raw bit stream for all users in the current grouping as illustrated on line  132 , whereas another output of unit  130  is applied to a unit  134  which remodulates and recreates received signals with full ISI tails for users in the current grouping.  
         [0098]    The purpose of unit  134  is to recreate the received signal that would be present when the only users transmitting are those associated with the first grouping. Note that each user&#39;s signal is recreated with the full extent of ISI tails. This operation is accomplished at  136  such that the output at  138  is an estimate of the received signal if the only users present were those having received powers below those in the first grouping.  
         [0099]    It will be appreciated that the signals at output  138  are those which correspond only to a smaller number of transmitting signals. For example, if FIG. 12 were to represent the joint demod-remod-strip block associated with the first user grouping, output  138  would correspond to only K-q1 users.  
         [0100]    It will be appreciated that block  110  is repeated in order to stepdown a number of users so that the computational complexity of the optimum synchronous MUD is significantly reduced. The overall result is to reduce the computational complexity by at least five orders of magnitude when power grouping is possible.  
         [0101]    It will be appreciated that in order for the optimum synchronous multi-user detection unit to operate properly, it is important that the inputs thereto be accurate in terms of the receive powers, phases, frequency offsets and timing offsets of all of the users sharing the channel.  
         [0102]    In essence there are two ways in which to estimate the above parameters. The first is an apriori way of estimating the parameters as illustrated by unit  94  which assumes a single user exists in the acquisition channel. Unit  94  performs a simple parameter estimation based on the signals in the acquisition channel. It will be noted that when a phone is turned on, the phone must communicate to the base station over the separate acquisition channel prior to being assigned to a traffic channel. If a user is all alone, the parameter estimation unit  94  can ascertain power, timing offset and frequency offset with state of the art technology. It is these signals which can be utilized to establish apriori an initial estimate of the powers, frequency offsets and timing offsets of all users sharing the channel. This system of parameter estimation works because only a single user is allowed to transmit over the acquisition channel at any time.  
         [0103]    It will be appreciated that only one user seeks to join the system at one given time. The result is that if one user is utilizing a given traffic channel and another user seeks to communicate with the base station, assuming that the base station has run out of available traffic channels, the second user can have its parameters ascertained in the above manner and then be connected over the same traffic channel. This is a continual process upon the access of an additional user on the traffic channel. Once a user hops off the acquisition phase over to the traffic channel, his or her parameters are refined. This is accomplished by unit  96  of FIG. 10.  
         [0104]    The joint multiple user parameter refinement and user grouping unit  96  calculates an estimate of phase and refines initial estimates of power, carrier offset and timing offset as illustrated in FIG. 13. While it is indeed possible to use unrefined parameters for signal separation, it is more useful to further refine these parameters so that a more robust signal separation can be accomplished by optimum asynchronous multi-user detector  130  of FIG. 12.  
         [0105]    Referring now to FIG. 13, how the refinement is accomplished is now described: As can be seen, incoming signal  100  here illustrated by r(t) goes to a unit  140  which functions to isolate the training sequence portion of the corrupted signal. In one embodiment of the subject invention a training sequence is established during acquisition by base station  26  of FIG. 4A, which assigns a unique training sequence to each user that is assigned the same traffic channel. The system uses the training sequence to allow for tracking of bit timing offset, a frequency offset and phase. Thus during acquisition the base station communicates with the handset to synchronize its timing with that of the base station, and, in effect, with the timing of the other users already in the traffic channel that will also be assigned to this new user. This is accomplished traditionally in any TDMA based commercial cellular or satellite system. This training sequence is utilized additionally in the subject system to provide means of separating the individual signals so that one can ascertain refined parameter estimates.  
         [0106]    Thus, as illustrated at  140 , the received signals are isolated based on zeroing out of the portions of the signals corresponding to the data bits, leaving the portions of the signal relating to training bits only as an output. The training sequence portion of the received signal corresponding to the transmitted signals occupying traffic channel X is illustrated at  142  and  144 , with the zeroing out of the signal due to the data portion of the received signal.  
         [0107]    The output of unit  140  is applied to a summing junction  146 . At  148 , signals corresponding to the training sequence portion of all user signals that were previously assigned to same traffic channel are recreated.  
         [0108]    Thus the output of  148  is an estimate of the training sequence portion of the received signal due to all of the users minus the newest. At  146 , the estimate of the training sequence portion of all but the newest user is subtracted from the training sequence portion of the received signal that contains all users including the newest. The result, on  150  is an estimate of the training sequence portion of the received signal that would be present if only the newest user were to exist alone on channel X. This is applied over line  150  to a maximum apostiori estimator for a user K&#39;s parameters, given the known training sequences and initial estimates for user K&#39;s parameters found during the acquisition stage, namely received power, oscillator phase, timing offset and frequency offset. This is accomplished by unit  152 .  
         [0109]    It will be appreciated that the information over line  150  reflects what the received signal would have been during the training sequence portion if only the newest user were present. Thus the above processing appears to unit  152  as if the other signals were not there. Note, unit  152  takes up where unit  94  left off. It will be remembered that the standard single user parameter estimation unit  94  assumes that there was only one user per channel, which was true because in the acquisition phase, there is only one user per channel.  
         [0110]    Now unit  152  utilizes the initial information based on the traffic channel and permits the refinement of parameters which are useful in separating the signals in the traffic channel.  
         [0111]    In estimation theory, it is well known that the quality of the parameter estimates measured in error variance of the estimate is inversely proportional to the duration over which the parameter estimation process is allowed to continue. In short, the longer you look, the better the parameter estimates.  
         [0112]    What therefore takes place in the estimator  152  is that given the number of users assigned to the traffic channel as illustrated over line  98  and the initial estimates for each user, namely timer offset, frequency offset, power and phase, as illustrated on  106 , estimator  152  continues to run, finding the improved estimates of the parameters of all signals on the communications channel assigned until adequate quality is obtained. This is done by refining the parameters of each user one at a time, always giving preference to the newest user to join channel X, but taking turns to further refine each of the parameter sets corresponding to each user on channel X.  
         [0113]    More particularly, the estimator operates as follows: The system initially takes in the prior estimates and puts them aside temporarily. Then it takes the interference adjusted signal  150  that corresponds to the training sequence portion of the signal transmitted by the new user only. It observes this signal over multiple burst periods, meaning a predetermined short time interval to be used to calculate another set of parameter estimates. In this predetermined interval or window, phase, power, timing offset and frequency offset is determined in exactly the same manner as illustrated at unit  94 , FIG. 10. This assumes the training sequence noted above.  
         [0114]    At this point, one has set aside the original estimates and, in addition, has a second set of estimates independent of the first set. The system averages the two to get a better estimate. This process is repeated, adding the new estimates based on the new intervals or windows with the appropriate weighting to reflect an evenly weighted average or giving a heavier weighting to more recent estimates. A maximum number of consecutive estimates is averaged iteratively until the desired accuracy is achieved.  
         [0115]    It will be appreciated that the multi-user detector needs estimates as soon as possible, preferably in real time and cannot wait until such time as an extremely large number of averages have taken place. In the subject system, the parameter refining unit outputs refined estimates at one time, but then keeps refining the estimates over a longer period of time so that as the system continues to operate, the estimates will become more and more refined, while at the same time providing real time estimates to the multi-user detector. Once a good quality estimate has been made for the newest user to join channel X, block  148  switches over to subtract out all but one of the older user&#39;s signals on channel X so as to allow a parameter refinement associated with this user. This process is repeated so that all users parameters are refined in turn.  
         [0116]    It will be appreciated that as one continues to average over successive time intervals, there will become a collection duration when an optimal averaging takes place for the given system. At this time, estimates based on prior collection intervals are tossed off or removed so that the estimation becomes as current as possible given the changes in the signals over time. This is referred to here as tracking. Thus the estimator  152  refines the parameter estimates with a sliding window of collected data so as to allow the estimates to vary with time. In addition, at any given point in time, up to date estimates of any of the K users assigned to channel X are being sent over  106  to the signal separation block as well as being fed back into  148 . The final result is that, on as close to a real time basis as possible, high quality parameter estimates are fed over  106  to the signal separation block.  
         [0117]    It will be appreciated that not only is the above parameter estimator useful in the separation of the signals which are simultaneously assigned to a given traffic channel, the estimator is also useful for every kind of multi-user detector which attempts to separate interfering signals, intentionally made to interfere or not. Thus the maximum apostiori estimator is used for not only the multi-user signal demodulation system described as the preferred embodiment hereof, it may be utilized in any case where any type of multi-user detection or stripping of signals is required.  
         [0118]    As a further aspect of the subject invention, the subject system can be made to operate even better through a power control scheme in which the power of an individual handheld units is more carefully controlled to enhance the performance of the signal separation block. The parameter estimator can therefore function to provide estimates of the powers of the individual signals so that their power can be carefully controlled in a closed loop overpacked system.  
         [0119]    Source Code for the subject hybrid multiuser detector is now presented: 
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
 
         [0120]    Having now described a few embodiments of the invention, and some modifications and variations thereto, it should be apparent to those skilled in the art that the foregoing is merely illustrative and not limiting, having been presented by the way of example only. Numerous modifications and other embodiments are within the scope of one of ordinary skill in the art and are contemplated as falling within the scope of the invention as limited only by the appended claims and equivalents thereto.