Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2001-09-18
2002-11-05
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
Reexamination Certificate
active
06476739
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method and processing system for estimating likelihood rations for input symbol values and, more particularly, a method and processing system for determining a soft decision metric for each input symbol.
2. Description of the Related Art
The Viterbi algorithm is a standard tool in communications receivers, which are used to perform various functions such as demodulation, decoding, equalization, etc. It is also known to employ two Viterbi algorithms in a concatenated fashion. For example, Trellis-Coded Modulation (TCM) and Continuous-Phase Modulation (CPM) communication systems both employ a Viterbi algorithm for data demodulation. By employing an additional outer convolutional code in such systems, another Viterbi algorithm must be used to perform the forward error correction (FEC) decoding operation after the Viterbi data demodulator. However, a problem with such an application is that since the inner Viterbi algorithm only generates hard (binary) decisions on code symbols, the outer Viterbi algorithm can only perform hard-decision decoding of the received data, resulting in sub-optimum decoding performance.
There are a variety of cases in which an outer receiver stage would perform better if soft decisions could be derived for each symbol at an inner receiver stage. For example, in order to optimize the decoding performance in a digital data transmission system employing FEC code, the data demodulator must supply soft data decisions to the FEC decoder. There is not, however, any direct way to extract soft decisions for each individual symbol in the conventional Viterbi algorithm.
SUMMARY OF THE INVENTION
In accordance with one embodiment of the present invention, a method for approximating a posteriori probabilities of input symbols to a finite state machine includes the steps of: exercising a Viterbi algorithm over M differently constrained trellises, one trellis for each of M possible input symbol values, and taking a difference of maximum state metrics of the differently constrained trellises to form likelihood ratios. A key aspect of the present invention is the design of the differently constrained trellises (e.g., +1 and −1 trellises) and the exploitation of the Viterbi algorithm to efficiently determine the bit likelihood ratios on a bit-to-bit basis.
In accordance with another embodiment of the present invention, a method for determining a soft decision metric for a n
th
input symbol includes the steps of: computing trellis branch metrics based on a received sample sequence; updating initial state metrics from time (n−1) with a Viterbi algorithm (VA); constraining M trellises differently at time n such that only state transitions caused by an input value associated with a particular trellis are allowed; executing the VA on each of the M constrained trellises for a finite number (N
d
) steps; and computing likelihood ratios by taking a difference of a maximum state metric at time (n+N
d
) for each trellis with a maximum state metric of a reference trellis.
In accordance with another embodiment of the present invention, a method for estimating likelihood ratios of the input symbol values of an encoded sequence includes the steps of: providing an optimal decision metric for symbol-by-symbol detection; making relaxations or simplifications to the optimal decision metric to provide an approximation to the optimal decision metric; and processing a sample sequence employing a Viterbi algorithm (VA) and differently constrained trellises to implement the approximation to the optimal decision metric. In a preferred method, the processing step includes the steps of: exercising the VA over the differently constrained trellises for samples of the sample sequence; and taking a difference of maximum state metrics of the differently constrained trellises.
In accordance with another embodiment of the present invention, a processing system for estimating likelihood ratios for input symbol values includes a processor configured to compute likelihood metrics on a symbol-by-symbol basis to determine an approximation to a maximum a posteriori estimate of a given symbol based on computing a maximum correlation of a received signal with all possible transmitted signals using a Viterbi algorithm over differently constrained trellisses. In a preferred processing system, the differently constrained trellises are M differently constrained trellises, where M is a number of possible input values. In a preferred embodiment, the processor is configured to decode signals provided to the processor in accordance with a concatenated coding scheme. In a preferred embodiment, the processor is configured to implement hard or soft demodulation of continuous phase modulation (CPM) signals, e.g., uncoded CPM signals, coded CPM signals, binary CPM signals, 4-ary CPM signals, etc.
In accordance with another embodiment of the present invention, a processing system for estimating likelihood ratios for input symbol values includes a decoder configured to implement a Viterbi algorithm (VA) on M differently constrained trellises for M values that an input to the decoder can take on at any given instant. By way of example, for a binary input, the M differently constrained trellises comprise two trellises.
Thus, the method and processing system of the present invention are embodied in a soft output Viterbi algorithm (SOVA) that provides a high performance metric that can be applied to either hard or soft decoding of error corrected code and pre-coded CPM signals (e.g., with a modulation index of 0.5), resulting in simplification of instrumentation in terms of computational and storage requirements.
The above described and many other features and attendant advantages of the present invention will become apparent as the invention becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings.
REFERENCES:
patent: 5162797 (1992-11-01), Murata
patent: 5181209 (1993-01-01), Hagenauer et al.
patent: 5881106 (1999-03-01), Cartier
J. Hagenauer and P. Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and its Applications,”Proc. of Globecom '89, Dallas, TX, USA, Nov. 1989, pp. 47.1.1-47.1.7.
C. Berrou, P. Adde, E. Angui, and S. Faudeil, “A low complexity soft-output Viterbi decoder architecture,”Proc. IEEE ICC '93, Geneva, Switzerland, pp. 737-740, May 1993.
H. Zheng, “Turbo Codes—Soft Output Viterbi Algorithm Realization and Phase Synchronization in Low SNRS,” Masters Thesis submitted to The University of Utah, Mar. 1998.
H. Mathis, “Differential Detection of GMSK Signals with Low BT Using the SOVA,”IEEE Transacations on Communications, vol. 46, No. 4, pp. 428-430, Apr. 1998.
Lui Gee L.
Tsai Kuang
Henricks Slavin & Holmes LLP
The Aerospace Corporation
Young Brian
LandOfFree
Method and processing system for estimating likelihood... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and processing system for estimating likelihood..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and processing system for estimating likelihood... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2922937