Screening for undetected errors in data transmission systems

Details Screening for undetected errors in data transmission systems Screening for undetected errors in data transmission systems

2000-04-18

2001-03-06

Tu, Christine T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S795000, C714S800000

Reexamination Certificate

active

06199186

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the screening for errors in data transmission systems, in particular for errors undetected, for example, by either an error correction code, an error detection code or a combined error correction/detection code.
BACKGROUND OF THE INVENTION
Convolutional codes, error detection codes, error correction codes or combined error detection/correction codes, and the use of a Viterbi decoder as a maximum likelihood decoder for convolutional codes are well known in the art.
In the transmitter of an illustrative data transmission system, a convolutional encoder proceeds through a sequence of states as it accepts data bits and produces output that subsequently is used to define an output sequence of symbols that is transmitted over a (noisy or otherwise impaired) channel. The output sequence of symbols corresponds to a path through the trellis that describes that encoder operation.
In the receiver, a Viterbi decoder determines the output sequence of data bits that was transmitted based on the received corrupted version of the transmitted sequence of symbols and knowledge of the code used by the encoder. The output sequence corresponds to the “best path”, that is, the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example, the determination of the output sequence is made by correlating with the received version all possible transmitted sequences (corresponding to paths through the trellis) and then choosing, as the “maximum likelihood” sequence, the sequence where the correlation is maximum.
Also known in the art is a group of extended Viterbi algorithms referred to as the List Viterbi algorithms. Whereas the “regular” Viterbi algorithm described above identifies the single best path through the trellis, a List Viterbi algorithm identifies the L best paths, or L best candidates, through the trellis. (The case in which L=1 is the regular Viterbi algorithm.) Versions of the List Viterbi algorithms produce a rank ordered list of the L best candidate decodings corresponding to a block of convolutional coded data. See, for example, our co-pending, commonly-assigned applications, U.S. Pat. application Ser. No. 09/055,082 entitled “List Viterbi Algorithms for Continuous Data Transmission” and U.S. Pat. application Ser. No. 09/054,676 entitled “List Viterbi Algorithms for Tailbiting Convolutional Codes” filed concurrently herewith; U.S. Pat. No. 5,208,816, issued May 4, 1993 to Seshadri and Sundberg; and U.S. Pat. No. 5,537,444 issued Jul. 16, 1996 to Nill and Sundberg.
List Viterbi algorithms are particularly effective in performing error detection/correction for convolutionally encoded data. As an example, consider a system in which a block of data to be transmitted is coded by a first, so-called outer code followed by a second, so-called inner code, where the outer code is an error detecting code and the inner code is a convolutional code. In the receiver, the decoder for the inner code is the first to operate on the received signal and it releases to the outer decoder the best decoded sequence based on the Viterbi algorithm. The outer decoder performs error detection on the best decoded sequence and, if an error is detected, may use error mitigation techniques in an attempt to repair the detected error. Such techniques may only be able to repair the error approximately, however.
On the other hand, if a List Viterbi algorithm is utilized, the L best decoded sequences can be provided, thereby eliminating the need for potentially erroneous error mitigation. In particular, if an error is detected, the second best of the L decoded sequences is tried. If it too has an error, the third best is tried, and so forth until one of the L decoded sequences satisfies the error code.
Although there is always the possibility that the decoded sequence released by the outer decoder has an error that the outer decoder did not detect, the likelihood of this occurring may be somewhat increased in those systems in which a List Viterbi algorithm is used. This is due in part to the fact that the sequence that satisfies the outer decoder may not be the first best of the L sequences identified by the List Viterbi algorithm. That is, although this sequence may satisfy the outer decoder, the List Viterbi decoder had determined that it was not the best sequence corresponding to the sequence that was transmitted and, therefore, the sequence may in fact have errors that escaped detection by the outer decoder.
Undetected errors in a sequence released by the outer decoder may be problematic in, for example, digital audio data transmission systems, such as Digital Audio Broadcasting systems. In such systems, if the outer decoder, for example, a Cyclic Redundancy Check (“CRC”) decoder, detects no error in the sequence provided by the Viterbi decoder, it releases the CRC-decoded sequence to an audio decoder and subsequently an analog audio signal corresponding to the released sequence is generated. On the other hand, if the CRC decoder detects an error in the sequence provided to it, an error flag is raised, thereby initiating audio decoder error mitigation routines. The error mitigation routines may provide, for example, for the substitution by an error mitigation signal for the audio signal that would correspond to the sequence in error. However, if a CRC error is not detected, no error flag is raised and the CRC-decoded sequence containing the error is released to the audio decoder, possibly causing significant errors in the resulting analog audio signal.
Increasing the number of error code bits for a block of information may alleviate this problem but results in a decreased information bit rate, given that the channel bandwidth is fixed. Thus, for transmission systems that utilize a List Viterbi algorithm, it would be advantageous to be able to further examine, or “screen”, the sequences that were found to satisfy an error code but which may contain an error undetected by the outer decoder.
SUMMARY OF THE INVENTION
In accordance with the invention, for a transmission system in which (a) a received sequence of symbols is processed by an inner decoder followed by an outer decoder and (b) the inner decoder is capable of providing to the outer decoder more than one output sequence corresponding to the received sequence, the decoded sequence released by the outer decoder is screened, if a predetermined criterion is satisfied, for errors undetected by the outer decoder. The predetermined criterion may, for example, be an indication of the reliability of the decoded sequence or may be the fact that the inner decoder was requested to release to the outer decoder more than one output sequence. The inner decoder may utilize a List Viterbi algorithm; the outer decoder may be an error detection decoder such as the Cyclic Redundancy Check decoder, an error correction decoder or a combined error detection/correction decoder.
For audio data transmission systems, one way in which the invention may be implemented is by generating an error indicator if the decoded sequence released by the outer decoder is deemed to contain an error—for example, if the discrepancy between an error mitigation signal and the audio signal corresponding to the decoded sequence is greater than a predetermined threshold value.
In preferred embodiments, upon the generation of the error indicator, the audio decoder substitutes the error mitigation signal for the signal corresponding to the decoded sequence. To avoid the false use of the error mitigation signal, the discrepancy between an error mitigation signal and the audio signal corresponding to the decoded sequence should be considerable. The predetermined threshold value (or other criterion used to determine whether the decoded sequence contains an error) may be experimentally determined depending on such factors as, for example, channel and source characteristics. Furthermore, to avoid undue increased complexity in the receiver, screening is performed only under certain conditions. The screening m

Affiliated with

Also associated with

Rating

Screening for undetected errors in data transmission systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Screening for undetected errors in data transmission systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Screening for undetected errors in data transmission systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2461057