Reduced complexity demodulator for multi-bit symbols

Details Reduced complexity demodulator for multi-bit symbols Reduced complexity demodulator for multi-bit symbols

1999-01-11

2002-02-12

Chin, Stephen (Department: 2734)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

Reexamination Certificate

active

06347125

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to the field of wireless communication, and, more specifically, to demodulating and decoding information symbols from a symbol-modulated radio signal that has suffered inter-symbol interference.
BACKGROUND OF THE INVENTION
Signals in a wireless communications system are subject to a number of phenomena that degrade signal quality. Each signal is reflected from many different man-made and natural objects. The receiver thus receives a number of signals delayed by one or more signal periods (called “multipath”), as each reflected signal is received. If the period of delay is more than the time required to transmit one symbol (inter-symbol interference), then the decoder in the receiver may not be able to decode the symbol, causing poor sound (or data) quality to the user. Many different algorithms are used at the receiver to attempt to compensate for such effects. One such algorithm is the Maximum Likelihood Sequence Estimator (MLSE) or “Viterbi” algorithm.
Viterbi decoding of an information symbol modulated signal comprises sampling the signal to obtain samples that each depend on a limited number (L) of sequential information symbols, and then hypothesizing all possible M
L
sequences of the L sequential symbols that affect a given signal sample. The hypothesized sequences are used to predict the sample value, the sample value is compared to the received signal and the prediction error is accumulated in a metric for each sequence of symbols. When the sequence is advanced one symbol to predict the next sample, the oldest symbol drops out of the window of L consecutive symbols on which the next prediction sample depends and a tentative decision for that symbol is made. A tentative symbol decision is associated with each of the remaining M
L
sequences which builds a “path history” associated with each remaining sequence. It is known that the tentative decisions may be made before the next symbol is hypothesized so that the number of symbols hypothesized reduces to L−1 symbols after each iteration, and the number of remembered path histories with associated metrics is thus M
L−1
.
Prior art descriptions of MLSE (Viterbi) algorithms are contained in, for example, U.S. Pat. No. 5,331,666 to Applicant entitled “Adaptive Maximum Likelihood Demodulator;” U.S. Pat. No. 5,335,250 to Applicant entitled “Method and Apparatus for Bidirectional Demodulation of Digitally Modulated Signals;” U.S. Pat. No. 5,467,374 to Chennakeshu et al. entitled “Low Complexity Adaptive Equalizer for U.S. Digital Cellular Receivers;” U.S. Pat. No. 5,577,068 to Dent and Bottomley entitled “Generalized Diect Update Viterbi Equalizer;” U.S. Pat. No. 5,557,645 to Applicant entitled “Channel-Independent Equalizer Device;” U.S. Pat. No. 5,577,053 to Applicant entitled “Method and Apparatus for Decoder Optimization,” all of which are incorporated herein by reference. Further descriptions are found in U.S. patent Ser. No. 08/218,236 (Dent and Croft, filed Mar. 28, 1994); Ser. No. 08/305,727 (Dent, filed Sep. 14, 1994); and Ser. No. 08/393,809 (Dent, filed Feb. 24, 1995), all of which are incorporated herein by reference.
In all of the above prior art, decoded symbols are entirely located in the set of sequences being postulated, in the set of path histories associated thereto, have been already extracted from the decoder or have not yet been hypothesized by the decoder at all. The prior art has thus addressed the need to limit decoder complexity by limiting the number of retained sequences through various means of limiting the number of sequential symbols that have to be jointly hypothesized. This can include just omitting one or more symbols and tolerating a loss of performance.
Another prior art method utilizes symbols that have already passed from the hypothesis stage to the path history on which signal samples depend to predict the next signal sample. This is disclosed in U.S. Pat. No. 5,307,374 to Baier, which is incorporated herein by reference. Thus, the number of sequential symbols retained in the hypothesis stage is reduced from L−1 by the number of symbols in the path history that are used for signal prediction. In this algorithm, known as “per-survivor processing,” not all combinations of symbols that have passed into path history are tested, which results in a small loss of performance. However, in common with the previously discussed prior art, symbols are either entirely in the path history or not.
The number of retained states may also be less than a power of the alphabet size when using another prior art method called the “M” algorithm. The M algorithm reduces the number of retained states by discarding those that have low likelihood metrics. Only the best M states are retained. The best M states, however, are not guaranteed to contain all values of the most recently hypothesized symbol. Having all values of the most recently hypothesized symbol is desirable in equalizers to demodulate signals that have propagated through multiple paths of differing delay, and wherein the path containing the greatest energy is not the path of shortest delay.
The M algorithm is also described in connection with the processing of partial symbols, in U.S. Pat. No. 4,484,338 to Clark. Clark uses the M algorithm to limit the number of retained hypotheses to a desired number M. Each retained hypothesis in Clark comprises, however, a number “n” of complete symbols, not partial symbols. Clark uses the concept of partial symbols only to reduce the effort in expanding the number of retained hypotheses from M to M times the alphabet size by postulating a new symbol, down-selecting to the best M again, performing the expansion in two smaller expansion stages, and down-selecting to M again after each expansion stage. However, the technique of Clark involves premature selection after the first stage of expansion of values of the just-hypothesized partial symbol. This premature selection can lead to degraded performance because not all values of the partial symbol or alphabetic subgroup are guaranteed to be retained for further evaluation. The above '338 patent to Clark, moreover, only discloses the possibility of dividing symbols into partial symbols when a whole symbol can be reconstructed from the linear, weighted sum of the partial symbols.
The current invention solves one or more of the deficiencies of the prior art.
SUMMARY OF THE INVENTION
The current invention describes how symbols may be allowed to straddle the region containing hypothesized symbols and the path history region, so that symbols exist partially in both states. This allows those parts of the symbol that are most important for predicting signal samples to be retained in the hypothesized state while the remaining parts can pass to the path history. This novel approach confers the advantage that, when using symbol alphabets larger than the binary alphabet, the decoder complexity can be tailored to values lying between two powers of the alphabet size, thereby allowing decoders of a maximum practical complexity (and thus performance) to be used. The prior art teaches decoders of only much less than the maximum practical complexity and performance or alternatively greater than the maximum practical complexity, i.e., impractical decoders.
In accordance with one aspect of this invention, a method is disclosed for processing samples of a signal that has propagated from a transmitter to a receiver via multiple propagation paths in order to decode information symbols belonging to an alphabet of symbols. The method includes the step of hypothesizing symbol sequences having symbols from the alphabet of symbols and partial symbols, wherein the partial symbols identify sub-groups of symbols from the alphabet. The method further includes predicting an expected value of the signal samples for each of the hypothesized sequences and comparing actual values of the signal samples with the predicted values in order to determine a likelihood value for each of the sequences. The method further includes storing hypoth

Affiliated with

Also associated with

Rating

Reduced complexity demodulator for multi-bit symbols does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduced complexity demodulator for multi-bit symbols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced complexity demodulator for multi-bit symbols will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2964414