Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-05-28
2002-04-23
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06378106
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital cellular communication systems and more particularly to error correcting decoders employed in digital cellular communications.
2. Description of the Related Art
The Viterbi algorithm is used in numerous communications systems receivers to decode symbols generated in a corresponding transmitter through the forward error correction technique of convolutional encoding. The Viterbi algorithm has been shown to provide, at the receiver, the maximum likelihood estimate of the sequence of bits originally entering the convolutional encoder of the transmitter. In essence, if the receiver is able (or willing) to make only one guess at the transmitted sequence of bits, then the guess that the Viterbi algorithm produces will be correct more often, in a statistical sense, than any other guessing method.
Many of the communications systems which employ convolutional coding as a forward error correction technique transmit data in finite length packets consisting, typically, of several tens to several thousands of bits. These packets of bits may be appended with a small block code, such as a cyclic redundancy code (CRC), as an error detection device. The packet of bits, together with the appended block code, are passed through the transmitter convolutional encoder before being transmitted.
The purpose of the error detection code is to indicate if there is reason to believe the packet of data has been corrupted by the transmission channel to such a degree that the forward error correction techniques are unable to recover. Often, the error detection code is only powerful enough to derive whether or not an error has been detected in the received and decoded packet, and is usually incapable of specifying where in the packet the error(s) occurred or how many of the decoded bits might be in error. If, after decoding via the Viterbi algorithm, the appended error detection block code indicates that no errors were found in the transmitted packet, the packet is accepted as good. If, after decoding via the Viterbi algorithm, the appended error detection block code indicates that errors were found in the transmitted packet, the entire packet will, typically, be rejected as corrupt, resulting in a packet (or frame) erasure.
The presence of packet erasures at the receiver is an indication that the maximum likelihood sequence of transmitted bits (i.e., the sequence of bits outputted by the Viterbi algorithm) is not the correct sequence of transmitted bits. In other words, the Viterbi algorithm, which produces, at the receiver, the “best guess” of the bits sent by the transmitter, has guessed incorrectly.
If it is known, through evidence provided by the error detection code, that a packet has been unsuccessfully decoded through the normal Viterbi algorithm, then receiver performance may be improved by decoding according to some method other than the normal Viterbi algorithm, for example, a decoding method that does not produce the maximum likelihood estimate of the sequence of bits originally entering the convolutional encoder of the transmitter. A number of such algorithms have been proposed, including the various list Viterbi decoders.
A list Viterbi decoder, as described for example in “List Viterbi Decoding Algorithms with Application,” Seshadri et al., IEEE Transactions on Communications, Vol. 42, No. 2/3/4, February/March/April 1994, keeps track not only of the best (and most likely) sequence of transmitted bits, but also the second best sequence, the third best sequence, the fourth best sequence, etc., up to the L best sequence, where L is an integer greater than 1. After decoding, these sequences are evaluated with the same error detection code that is used to evaluate the maximum likelihood sequence, and, if a sequence is found for which no errors are detected, that sequence is outputted from the receiver instead of the maximum likelihood sequence. List Viterbi decoders provide receiver performance improvements at the cost of additional processing circuitry and decoding operations.
SUMMARY OF THE INVENTION
The present invention is directed to a recursive technique which exceeds the performance of the general Viterbi algorithm and the various conventional list Viterbi decoders, which is much less computationally and physically complex.
In particular, the present invention is directed to a recursive technique which requires no additional circuitry or processing to keep track of a running list of the L best paths. If the most likely (ML) path fails frame quality metric tests, a search is made through the trellis using the existing survivor (trace back) information stored in the survivor (trace back) memory. An iteration in the recursive algorithm includes tracing back along the ML path to a particular stage, then deviating from the ML path and following the survivor information along that new deviant path, and finally checking the fully decoded frame to see if the frame quality metrics are acceptable for the frame. These same trace back steps can be performed for every stage in the trellis, deviating from a different stage on the ML path each time.
The add-compare-select operations for the recursive Viterbi technique of the present invention are identical to the conventional Viterbi decoder. The traceback information is also stored in the same manner as is done for the conventional Viterbi decoder. The traceback operations, however, are completely different for the recursive Viterbi technique of the present invention. In fact, multiple trace backs may be made through the stored trellis of trace back information in order to improve the estimate of the original transmitted data sequence beyond what is possible with the conventional Viterbi decoder. In the recursive traceback technique of the present invention:
a normal traceback is performed, identical to the algorithm described above for the conventional Viterbi decoder. The error detection code (usually a CRC code) is used to determine if any bits in the decoded frame are erroneous. If the error detection code indicates that no errors were made in the decoded frame, no further trace back operations are performed, and the maximum likelihood decoded sequence is outputted as the estimate of the transmitted data sequence; and
if an error or errors are detected using the error detection code, then additional trace back steps are applied in an attempt to recover from bit errors that would otherwise lead to a corrupted frame. For a binary code, up to an additional B−I complete trace back operations (tracing back from the last stage of the trellis to the first stage of the trellis B−I times) may be performed, where B is the number of bits in a frame, with an evaluation of the newly decoded frame using the error detection code being performed after each trace back recursion. The additional trace back operations are performed just like normal Viterbi decoder traceback operations, except, at a single chosen stage in the trellis, the traceback information for the state of the maximum likelihood path is deliberately ignored, and the traceback continues down one of the other paths that merged into that state. When the traceback operation makes its way back to the beginning of the trellis, the new estimate of the transmitted sequence is checked against the error detection code. If no errors are found, the new sequence is outputted from the decoder. If errors are still detected, the traceback recursion is repeated, except the deviation from the maximum likelihood path occurs at a stage in the trellis that has not yet been used as the deviation point.
If it is known that some bits somewhere in this decoded frame are in error, an error detection code, such as a CRC, will give this information, then the information stored in the traceback memory (or “survivor” memory) is traversed again down a path that is effectively one wrong turn off of the maximum likelihood path. The recursion is repeated until either a path is found for which the error detection code indicates
Allpress Stephan A.
Hahm Mark D.
Birch Stewart Kolasch & Birch
Chase Shelly A
De'cady Albert
LandOfFree
Viterbi decoding using single-wrong-turn correction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Viterbi decoding using single-wrong-turn correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding using single-wrong-turn correction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2909087