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.
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 xe2x80x9cmultipathxe2x80x9d), 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 xe2x80x9cViterbixe2x80x9d 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 ML 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 ML sequences which builds a xe2x80x9cpath historyxe2x80x9d 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 Lxe2x88x921 symbols after each iteration, and the number of remembered path histories with associated metrics is thus MLxe2x88x921.
Prior art descriptions of MLSE (Viterbi) algorithms are contained in, for example, U.S. Pat. No. 5,331,666 to Applicant entitled xe2x80x9cAdaptive Maximum Likelihood Demodulator;xe2x80x9d U.S. Pat. No. 5,335,250 to Applicant entitled xe2x80x9cMethod and Apparatus for Bidirectional Demodulation of Digitally Modulated Signals;xe2x80x9d U.S. Pat. No. 5,467,374 to Chennakeshu et al. entitled xe2x80x9cLow Complexity Adaptive Equalizer for U.S. Digital Cellular Receivers;xe2x80x9d U.S. Pat. No. 5,577,068 to Dent and Bottomley entitled xe2x80x9cGeneralized Diect Update Viterbi Equalizer;xe2x80x9d U.S. Pat. No. 5,557,645 to Applicant entitled xe2x80x9cChannel-Independent Equalizer Device;xe2x80x9d U.S. Pat. No. 5,577,053 to Applicant entitled xe2x80x9cMethod and Apparatus for Decoder Optimization,xe2x80x9d 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 Lxe2x88x921 by the number of symbols in the path history that are used for signal prediction. In this algorithm, known as xe2x80x9cper-survivor processing,xe2x80x9d 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 xe2x80x9cMxe2x80x9d 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 xe2x80x9cnxe2x80x9d 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.
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 hypothesized sequences including whole symbols and partial symbols in associated with the likelihood values and selecting symbol sequences having the greatest of the determined likelihood values to be the decoded information symbols. Each of the decided symbols belongs to one of the sub-groups of symbols identified by the hypothesized partial symbols.
In accordance with another aspect of this invention, a decoder is disclosed that decodes a signal modulated with information symbols belonging to an alphabet of symbols. The decoder comprises a maximum likelihood sequence estimator that hypothesizes alphabetic sub-groups containing the information symbols, to hypothesize symbols within the alphabet and to determine a sequence of the information symbols having a highest likelihood indication. The decoder also includes a channel estimator to estimate coefficients describing a channel through which the signal has propagated, a signal predictor that combines the channel estimates with corresponding samples of the signal to obtain a metric, and a metric accumulator to accumulate the metrics for hypothesized symbol sequences to determine the likelihood indications.