Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-08-17
2001-06-26
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S790000, C714S792000
Reexamination Certificate
active
06253347
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital decoder circuits and, more particularly, to circuits for automatically determining a re-synchronization threshold to be used by, e.g., a trellis decoder.
BACKGROUND OF THE INVENTION
In various known trellis coding systems, different polynomials are used to encode different transmitted symbols. In order to properly decode a symbol stream received from such an encoder, a decoder must be synchronized such that it knows which received symbols were encoded with which polynomials. The outputs of the polynomials at the encoder (the encoded bits) are used to select the set partitions—subsets of the total set of symbol levels-to be transmitted. Additional, uncoded bits may be used to select levels within the selected set partitions. In decoding the received symbol, a trellis decoder determines the most likely sequence of set partitions used to generate the transmitted symbols. As part of this set-partition decoding process, the decoder must be properly synchronized to the sequence of polynomials used at the encoder.
Many trellis decoders maintain sets of what are referred to in the art as cumulative sums. These cumulative sums represent, e.g., a running estimate of errors associated with various decoding operations. In order to prevent the cumulative sums from exceeding the numerical capacity of registers used to store the cumulative sums, a fixed value is periodically subtracted from the stored cumulative sum values. This event is referred to as renormalization. Renormalization occurs at periodic intervals. The interval at which renormalization occurs normally varies as a function of the rate, e.g., an error rate, at which one or more of the cumulative sums grows. As the detected error rate increases the rate at which renormalization occurs increases in order to prevent the cumulative sums from overflowing the counters used to store the sums. The renormalization rate will generally be higher for a noisy signal than for a low noise signal. This is because more errors tend to occur in the case of high noise conditions. In addition, renormalization tends to occur more frequently in decoders in which the set partitions are improperly selected, e.g., the selection of set partitions used for decoding is not in sync with the actual set partitions original used to code the data being decoded. This can occur if synchronization with the sequence of transmitted polynomials is incorrect.
In some known trellis encoders, a set partition adjustment renormalization rate (SPARR) threshold is used to determine correct or incorrect polynomial and hence set partition synchronization. In the known systems the SPARR is an operator selected value that is supplied to the trellis decoder. The SPARR threshold is used to predict when the set partitions being used to decode data are incorrect and therefore synchronization of the set partition to be used when decoding received encoded data should be adjusted, in accordance with a corrected synchronization with a polynomial sequence. For example, if the SPARR threshold is exceeded, i.e., a renormalization rate which is higher than the threshold occurs, the set partition used to decode the received symbols will be adjusted in an attempt to achieve proper set partition synchronization with the received symbols.
A manually supplied SPARR threshold of prior art systems may be selected by an operator of the known system based upon some knowledge of the signal to noise ratio (SNR) of the communication channel used to transmit the received data and modified by the decoder operator during decoder use. This approach has the disadvantage of requiring a fair amount of operator input and can result, depending on the degree of operator input, in a decoder which is far less responsive to changing signal conditions than may be desired.
As an alternative to having an operator input the SPARR threshold, the threshold could be a pre-selected fixed value which was selected by the decoder designer to work over an anticipated range of signal conditions.
Unfortunately, a single pre-selected threshold may not work satisfactorily over the range of actual conditions encountered during decoder use.
In view of the above, it becomes apparent that there is a need for methods and apparatus of automatically selecting a satisfactory SPARR threshold for use by trellis decoders. It is desirable that any such methods and apparatus be relatively easy and inexpensive to implement. It is also desirable that any such methods and apparatus be responsive to changing signal conditions, e.g., SNR conditions, to automatically adjust the SPARR threshold as may be appropriate.
SUMMARY OF THE PRESENT INVENTION
As discussed above the present invention is directed to methods and apparatus for automatically determining a re-synchronization threshold, e.g., a SPARR threshold used by decoder, e.g., a trellis decoder.
In accordance with the present invention, a SPARR threshold is automatically calculated based upon the signal input, e.g., received symbols, to a trellis decoder. The automatic threshold determination method of the present invention is robust and can result in proper set partition synchronization over a wide and varying range of signal-to-noise conditions.
A trellis decoder operates, in part, by accumulating error metrics over time, which are the errors to particular set partitions. These error metrics are stored in the form of cumulative sums. Due to hardware architectures and limitations, these cumulative sums must, periodically, be decremented or “renormalized” by some fixed amount. In some trellis coding systems, the receiver must be synchronized with a pattern or grouping of symbols that recurs periodically. If this synchronization is incorrect, the cumulative sums will grow more rapidly than if the synchronization is correct: therefore, the cumulative sums will be renormalized more often than if the synchronization is correct. In order to determine the threshold above which the renormalization rate indicates incorrect synchronization, the current invention utilizes error metrics already existing in known trellis decoders.
The invention makes use of the inventor's observation that when the system is properly synchronized, the rate of growth of cumulative error sums closely corresponds to an accumulation of minimum set-partition errors. In accordance with the present invention a dummy accumulator is set up to accumulate the minimum set partition error for each symbol. If decoder set partition selection is correct the renormalization rate for the dummy accumulator(s) will be approximately the same as an accumulator set up for the normal operation. This assumes that the same or similar renormalization trigger conditions are applied to the dummy accumulator(s) and accumulator(s) used for normal operation. In accordance with one embodiment of the present invention, a fixed offset is added to this observed dummy renormalization rate, obtained through the use of the dummy accumulator, and the resulting sum is used as the automatically generated SPARR threshold.
The method and apparatus of the present invention can be implemented by adding relatively little hardware to that already in various known trellis decoders. In addition, the automatic threshold generation technique of the present invention has the advantage of dynamically providing a SPARR threshold which changes as a function of changing SNR conditions without the need for operator input to achieve the threshold changes.
REFERENCES:
patent: 4583236 (1986-04-01), Kromer et al.
patent: 4807230 (1989-02-01), Srinivasagopalan et al.
patent: 5050191 (1991-09-01), No
patent: 5241563 (1993-08-01), Paik et al.
patent: 5566214 (1996-10-01), Kroeger et al.
patent: 5598429 (1997-01-01), Marshall
patent: 5937016 (1999-08-01), Choi
patent: 6058101 (2000-05-01), Huang et al.
patent: 6092234 (2000-07-01), Azakami et al.
12 Mbps Convolutional Encoder—Viterbi Decoder STEL-2030A, Stanford Telecom, ASIC Custom Products Division, pp. 1-13, (Mar. 1992).
Convolutional Encodr, Viterbi Decoder STEL-
De'cady Albert
Hitachi America Ltd.
Straub Michael P.
Straub & Pokotylo
Ton David
LandOfFree
Automatic synchronization circuit for trellis decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic synchronization circuit for trellis decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic synchronization circuit for trellis decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2487720