US 2003/0193966 A1 · Method and apparatus for improved turbo multiuser detector

Abstract

A multi-user turbo decoder combining multi-user detection and forward error correction decoding is disclosed that utilizes iterative decoding of received, interfering signals, and the construction of a decoding tree of the decoder is changed for each iteration of the decoding based on the previous conditional probability estimates of the value of the data bits of each signal making up the received, interfering signals. Before each iteration of multi-user decoding, a probability estimate is calculated that the value of the bit in a signal has a certain value for all of the data bits. Using the probability estimate a new decoding tree is constructed before each iteration of decoding such that the signal bit having the most reliable estimate is assigned to the lowest or root level of the tree. Using the probability estimate for the other signal bits, the signal bit having the next most reliable estimate is assigned to the second level of the tree, and so forth, with the signal bit having the least reliable estimate being assigned to the highest level of the tree adjacent the terminating nodes or leaves of the tree. By building the decoding tree in this manner for each iteration of symbol decoding, a reduced complexity search is more likely to include paths (and nodes) in the tree containing the correct value for the channel symbols.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims22

Dependent claims

A method for decoding a sequence of received, interfering signals corrupted by multi-user interference by performing multiple iterations of decoding on the signals to identify the value of signal points for decoding the signals, the method uses a multi-user decoder and a plurality of single user decoders, the multi-user decoder using an algorithm defining a tree diagram having a number of node levels equal to the number of signals from which the signal points are derived, with the first/highest order term of the algorithm being assigned to the first/root node level of the tree, the second/next highest term of the algorithm being assigned to second node level of the tree, and so on, and the method for decoding the signals in each block of data comprising the steps of:

(a) performing a first decoding of the received, interfering signals in a block of data in the multi-user decoder to determine first channel symbol estimates for each of the signals;
(b) performing a first decoding of the signals in the block of data in the single user decoders, with each signal being assigned to and processed by a single user decoder, and using the first channel symbol estimates determined in step (a) for each signal in the assigned one of the single user decoders to determine a first probability estimate for each of the data bits in the signals, the decoding in steps (a) and (b) accomplishing a first iteration of decoding;
(c) performing a subsequent decoding of the received, interfering signals in the block of data in the multi-user decoder initially using the first probability estimates determined in step (b) for each of the signals, after assigning the signal that has a probability estimate closest to a predetermined value to the first term of the algorithm, assigning the signal that has a probability estimate next closest to the predetermined value to the second term of the algorithm, and so forth, to determine a revised channel symbol estimate for each of the channel symbols;
(d) performing a subsequent decoding of the signals in the block of data in the single user decoders, with each signal being assigned to and processed by a single user decoder, and using the revised channel symbol estimates determined in step (c) for each signal in the assigned one of the single user decoders to determine a revised probability estimate of the data bits for each of the signals, the decoding in steps (c) and (d) accomplishing a first iteration of decoding;
(e) repeating steps (c) and (d) for third and subsequent iterations of decoding, with channel symbol estimates for each iteration of decoding determined in step (c) being used by the single user decoders in step (d), and revised data bit probability estimates for each iteration of decoding determined in step (d) being used is step (c);
and
(f) decoding the signals in the block of data using the value of signal points determined as a result of the iterative decoding steps (a)-(e).

4 more elements

Apparatus for decoding a sequence of received, interfering signals corrupted by multi-user interference by performing multiple iterations of decoding on the signals to identify the value of signal points for decoding the signals, the decoding being based on an algorithm defining a tree diagram having a number of node levels equal to the number of signals from which the signal points are derived, with the first/highest order term of the algorithm being assigned to the first/root node level of the tree, the second/next highest term of the algorithm being assigned to second node level of the tree, and so on, the apparatus comprising:

a multi-user decoder for performing a first decoding of the received, interfering signals to determine a first estimate for each channel symbol contained in each of the signals;
and
a plurality of single user decoders each performing a first decoding on one of the signals using the first channel symbol estimate for each signal to determine a first data bit probability estimate for each signal;
wherein said multi-user decoder performs a second decoding of the signals using the first probability estimates to determine a revised set of channel symbol estimates for the signals;
wherein said plurality of single user decoders each perform a second decoding on one of the signals using the revised channel symbol estimates determined by the multi-user decoder for each signal to determine second probability estimate for each data bit in each signal;
wherein iterative decoding is repeatedly performed by the multi-user decoder and single user decoders with the revised probability estimates from the single user decoders being used to assign the signal that has a probability estimate being closest to a predetermined valueto the first term of the algorithm, assigning the signal that has a probability estimate being next closest to the predetermined value to the second term of the algorithm, and so forth, to determine subsequent channel symbol estimate for each of the signals;
and
wherein the signals are decoded using the value of signal points determined as a result of the iterative decoding steps performed by the multi-user and single user decoders.

5 more elements

A computer readable medium containing executable instructions for decoding a sequence of received, interfering signals corrupted by multi-user interference by performing multiple iterations of decoding on the signals to identify the value of signal points for decoding the signals, the method uses a multi-user decoder and a plurality of single user decoders, the multi-user decoder using an algorithm defining a tree diagram having a number of node levels equal to the number of signals from which the signal points are derived, with the first/highest order term of the algorithm being assigned to the first/root node level of the tree, the second/next highest term of the algorithm being assigned to second node level of the tree, and so on, and the executable program instructions for decoding each block of data comprising instructions for:

(a) performing a first decoding of the received, interfering signals in a block of data in the multi-user decoder to determine a first channel symbol estimate for each of the signals;
(b) performing a first decoding of the signals in the block of data in the single user decoders, with each signal being assigned to and processed by a single user decoder, and using the first channel symbol estimate determined in step (a) for each signal in the assigned one of the single user decoders to determine a first data bit probability estimate for each of the signals, the decoding in steps (a) and (b) accomplishing a first iteration of decoding;
(c) performing a second decoding of the received, interfering signals in the block of data in the multi-user decoder using the first probability estimate determined in step (b) for each of the signals, after assigning the signal that has a probability estimate closest to a predetermined value to the first term of the algorithm, assigning the signal that has a probability estimate next closest to the predetermined value to the second term of the algorithm, and so forth, to determine a second channel symbol estimate for each bit in the signals;
(d) performing a second decoding of the signals in the block of data in the single user decoders, with each signal being assigned to and processed by a single user decoder, and using the second channel symbol estimate determined in step (c) for each data bit in the signal in the assigned one of the single user decoders to determine a second data bit probability estimate for each of the data bits in the signals, the decoding in steps (c) and (b) accomplishing a second iteration of decoding;
(e) repeating steps (c) and (d) for third and subsequent iterations of decoding, with revised channel symbol estimates for each iteration of decoding determined in step (c) being used in step (d), and revised data bit probability estimates for each iteration of decoding determined in step (d) being used is step (c);
and
(f) decoding the signals the block of data using the value of signal points determined as a result of the iterative decoding steps (a)-(e).

4 more elements

A method for decoding bits of received, interfering signals corrupted by multi-user interference by performing multiple iterations of decoding on the signals to identify the value of signal points for decoding the bits of the signals, the method uses a multi-user decoder and a plurality of single user decoders, the method for decoding each block of data comprising the steps of:

(a) decoding the signal bits in the multi-user decoder to determine a first parameter for each of the signals;
(b) decoding the signal bits in the single user decoders after decoding in the multi-user decoder, to determine a second parameter for each of the data bits in the signals;
(c) ordering the signal bits based on the second parameters determined by the single user decoders;
(d) performing subsequent decoding in the multi-user decoder of the reordered signal bits and utilizing the second parameters to determine a revised first parameter for each of the signals;
(e) performing a subsequent decoding in the single user decoders of the signal bits using the revised first parameter determined in step (d) to determine a revised second parameter for each of the data bits in the signals;
(f) ordering the signal bits based on the revised second parameters determined by the single user decoders before the signal bits are again decoded in the multi-user decoder;
(g) repeating steps (d) through (f) for subsequent iterations of decoding, with the revised first parameters for each iteration of decoding determined in step (d) being used in step (e), and the revised second parameters for each iteration of decoding determined in step (e) being used is step (d);
and
(h) decoding the signals using the value of signal points determined as a result of the iterative decoding steps (a)-(g).

6 more elements

Dependencies are inferred from the claim text.

Description7,102 words

Summary3,421 words

#This invention relates to the field of communications and more particularly to an improved method and apparatus in a receiver for iterative turbo multi-user detection utilizing tree pruning.

#The present invention belongs to the art of multiple access communications systems such as, but not limited to, wireless Local Area Networks (Wireless LANS), cellular land-mobile communications systems, mobile satellite communications systems, and memory storage and retrieval devices. Such systems are characterized by at least one fixed base or relay station attempting to maintain communications with a plurality of subscriber stations or terminals that are each assigned a different time slot (TDMA), a different frequency slot (FDMA), or different signature waveform (CDMA), to name a few examples.

#In such systems, capacity to support a large number of subscribers is measured in units such as Erlangs per MHz per square kilometer, a sum capacity (e.g. the sum of the information data rates—Bits/sec—of all the users in the system). Of primary interest is the maximum number of users that can operate within the system without having to decrease the information rate that they are already accustomed to using or increase the total bandwidth occupied by the system. The capacity can be increased by using more MHz of bandwidth, by reducing the area covered by each base station so that there are more base stations per square kilometer, by decreasing the frequency spacing between channels, and by transmitting more than one signal in the same frequency channel or time slot. However, reducing cell size or reducing the number of signals received by the detector is not always possible or economically feasible. When such action is possible, it increases the infrastructure cost. In addition, some of the above listed solutions increase inter-symbol interference (ISI) and multi-user interference (MUI), also called co-channel interference, that may be caused by a signal being received along with a delayed version thereof caused by a reflection of the signal from an object such as a large building, or receipt of another, weaker signal having the same frequency and meant to be received at a different receiver. In addition, received signals are typically corrupted by additive Gaussian noise.

Brief description of the drawings3 figures

#The invention will be better understood upon reading the following Detailed Description in conjunction with the drawing in which:

#FIG. 1 is a simplified block diagram of a portion of a prior art receiver circuitry utilizing iterative turbo decoding to separate multiple interfering signals on the same communication channel;

#FIG. 2 is a simplified block diagram that features the teaching of the invention by showing a portion of a prior art receiver circuitry implementing turbo decoding with the addition of probability estimate ordering in the levels of the tree for each decoding iteration in accordance with the teaching of the invention; and

Detailed description3,571 words

#In FIG. 1 is shown a simplified block diagram of a portion of a prior art receiver circuitry utilizing iterative turbo decoding to separate multiple interfering signals on the same communication channel. It shows an implementation of a prior art turbo multi-user detector (turboMUD) used to incorporate turbo decoding techniques into MUD with forward error correction (FEC) decoding.

#The operation of this prior art, turbo multi-user detector (turboMUD) assumes knowledge of various parameters about received signals such as relative received timing offsets, carrier phase, frequency offsets, received amplitudes, and multi-path structure for each of the interfering signals present in the received signal. A parameter estimation unit 12 is therefore needed. In a turboMUD system decoding, probability estimate and channel symbol estimate information is repeatedly passed between a multi-user decoder (MUD) 14 and a plurality of single-user decoders 16. Soft output decoders, such as maximum a posteriori (MAP) decoders, or approximations of MAP decoders, or soft output Viterbi algorithm (SOVA) decoders, are used for both the MUD 14 and single user decoders 16 so that soft output information is available as is known in the prior art. The MUD 14 unit uses relationships between interfering signals to correct errors within a block of received data due to multi-user interference. The plurality of single user decoders 16 uses the coding relation imposed on each user at the transmitter by an error correction encoder to exploit relations within the sequence of symbols transmitted by each individual user to correct for received symbol errors. Together, MUD 14 and the single user decoders 16 work in concert to estimate the transmitted sequence of symbols from all users within a time frame, also called a block, that is under consideration.

#A digitized signal passes through conventional receiver circuitry (not shown) and is then input to parameter estimation unit 12 which utilizes unique apriori knowledge of each of the received signals to help identify parameters for each interfering signal, regardless of the fact that the signals exist in the same communications bandwidth and at the same instant in time. These parameters includes the received power, the phase of the oscillator which generated each received signal, the timing offset relative to the base station clock, carrier frequency, any frequency offset of the carrier (phase difference), and the structure of multi-path replicas. This knowledge is typically derived using a parameter estimator in a manner well known in the art, such as the training signal method disclosed in the above identified patent application entitled “System For Parameter Estimation And Tracking Of Interfering Digitally Modulated Signals”. However, it is not assumed that training sequences are employed for the MUD receiver to operate correctly.

Method and apparatus for improved turbo multiuser detector

Life of this patent

Method and apparatus for improved turbo multiuser detector

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims22

Description7,102 words

Drawings

Classification7 codes

Life of this patent

Description7,102 words