1. Field of the Invention
This invention relates generally to the field of trellis codes, and, more specifically, to locating burst errors and assigning reliability metrics to bits or symbols during the decoding of trellis codes.
2. Related Art
Trellis codes are codes that can be represented through a diagram of states and state transitions known as a trellis. Examples of trellis codes include convolutional codes, concatenations of convolutional codes, and some block codes. A characteristic of trellis codes is that, during the decoding process, a decoding error can manifest itself in the form of a burst of errors in the bit or symbol estimates output by the decoder. The length of a burst event, and its probability of occurrence, is governed by the free distance and weight distribution of the code. Decoded information that is the product of burst errors may be unreliable, although difficult to detect.
Several techniques are available for producing reliability indicators for decoded information produced by decoders of trellis codes. Examples include a maximum a posteriori (MAP) decoder proposed by Bahl that maximizes the probability that a particular bit in the decoded stream was reliably transmitted given knowledge of the entire received data record. See L. R. Bahl et al., “Optimal Decoding of Linear Codes For Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, vol. IT-20, pp. 284–87 (1974), which is incorporated herein by reference. An adjunct of this method, called the a posteriori probability (APP) algorithm, can be used to provide soft outputs concerning the reliability decision.
Another example is the technique proposed by Krieger and Kent, which uses a different set of recursions to achieve similar performance. See A. Krieger & M. Kent, “Apparatus and Methods for Signal Recovery in a Digital Communication System,” U.S. Pat. No. 5,841,817, which is incorporated herein by reference.
Viterbi applied a simplified dual-maxima sliding approximation coupled with an improved memory management system to the APP algorithm, and was thereby able to reduce the complexity of MAP-type algorithms to about four-times that of the original Viterbi algorithm. See A. J. Viterbi, “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 2, pp. 260–64 (February 1998), which is incorporated herein by reference.
Hagenauer and Hoeher proposed a soft output Viterbi algorithm (SOVA), which, in comparison to the APP algorithm, does not strive to optimize probability estimates, but instead strives for a compromise between complexity and performance. See J. Hagenauer & P. Hoeher, “A Viterbi Algorithm With Soft-Decision Outputs and its applications,” Proceedings of IEEE GLOBECOM, Dallas, Tex. sec. 47.1.1–47.1.7 (1989); U.S. Pat. No. 5,181,209, both of which are incorporated herein by reference.
Finally, Nill and Sundberg proposed a soft list Viterbi algorithm (Soft-LVA). See C. Nill & C. E. Sundberg, “List and Soft Symbol Output Viterbi Algorithms: Extensions and Comparisons,” IEEE Transactions on Communications, vol. 43, nos. 2/3/4, pp. 277–87 (Feb. Mar. April 1995); U.S. Pat. No. 5,537,444, both of which are incorporated herein by reference. This technique uses a serial list Viterbi algorithm to trace back in the trellis diagram the L most likely paths over the data. For every bit location, it assigns the path metric difference between best path and the first alternative path having a bit output different from the best path, this path metric difference being used as the reliability metric.
However, these approaches are either computationally intensive and require data termination, which makes them unsuitable for applications requiring constant assessment of streaming data, or provide bit-specific reliability indicators which are inadequate indicators of burst errors.
In the Soft-LVA algorithm, for example, data termination is required: a continuous data stream overwhelms the algorithm. Moreover, a bit location is assigned full confidence if all of the Soft-LVA algorithm's alternative paths decode that bit the same way as the best path. This process yields overly optimistic estimates of reliability when differentials between the best and alternative path metrics are small A phenomenon related to this is that the “granularity” of the Soft-LVA algorithm is not very fine. Alternative paths span only a small number of bit locations in the data record; therefore, when the decoding outcome is the same over all alternative paths, there is no way to differentiate between them, and a large number of bits may thus anomalously be assigned a maximum reliability indicator. Furthermore, the bit metrics assigned by the Soft-LVA algorithm are not good indicators of symbol reliability, as one decoded bit within a symbol may erroneously align itself with the best-path decoded bit. Likewise, the Soft-LVA algorithm does not provide a good burst error indicator because individual bits within a burst may erroneously be assigned a high reliability.