Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-11-05
2001-02-13
Baker, Stephen M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000
Reexamination Certificate
active
06189126
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to decoding methods, and specifically to fast decoding of codes using a trellis.
BACKGROUND OF THE INVENTION
Transmission of digital data is inherently prone to interference which may introduce errors into the transmitted data. Error detection schemes have been suggested to determine as reliably as possible whether errors have been introduced into the transmitted data.
When the transmitted data is not used on-line, it is possible to request re-transmission of erroneous data when errors are detected. However, when the transmission is performed on-line, such as in telephone lines, cellular phones, remote video systems, etc., it may not be possible or practical to request re-transmission.
Convolution codes, and other similar codes, have been introduced to allow receivers of digital data to correctly determine the transmitted data even when errors may have occurred during transmission. The convolution codes introduce redundancy into the transmitted data by representing each input bit of data by more than one coded bit in the transmitted data. Usually, the coded bits of the transmitted data are packed into packets in which the value of each coded bit is dependent on earlier bits in the sequence. Thus, when a few errors occur, the receiver can still deduce the original data by tracing back possible sequences in the received data.
In some decoders, rather than determining immediately whether received signals originating from a single transmitted, coded bit are zero or one, the receiver assigns each of the signals a word which has a value on a multi-level scale representative of the probability that the coded bit is one. An exemplary scale, referred to as LLR probabilities, represents each transmitted coded bit by a 6-bit word, representing an integer in the range {−32,31}. If words of a different number of bits are used, the range is adjusted accordingly. The LLR probability of a coded bit is calculated by taking the logarithm of the ratio of the probability that the bit is one to the probability that the bit is zero, or the logarithm of the reciprocal of the ratio. The value of 31 signifies that the transmitted bit was a zero with very high probability, and the value of −32 signifies that the transmitted bit was a one with very high probability. A value of zero indicates that the value is indeterminate.
When a transmitter transmits a coded packet of bits, in which each coded bit has a definite value of “1” or “0”, over a noisy channel, the receiver receives a packet in which each bit has a variable voltage value, which may be interpreted as a LLR probability, due to interference introduced by the channel. A decoder must determine the transmitted packet based on the received packet. A simple method involves determining a “difference” between the received packet and all possible packets and determining which possible packet has the smallest difference. However, due to the large number of different possible values of the packets, this method is usually impractical.
In convolution coding methods, and in other related methods, an uncoded input packet is fed into an encoder which has a number of possible states. As each data bit of the uncoded packet is fed into the encoder, it causes a change in the state of the encoder and provides a group of one or more output coded bits which are a function of the state and the input. The groups of output coded bits form a coded packet which is transmitted. The number of bits in each group is a factor of redundancy introduced by the code as a result of the convolution. A code in which each group, for example, includes two bits has a code rate of 1/2, meaning that the actual information content of a packet is equal to half the number of coded bits in the packet.
Convolutional codes are generally decoded in accordance with decoding schemes which use a trellis, such as MAP decoding (or APP decoding), SOVA decoding and Viterbi decoding. A decoder receives the words representing the probabilities of the received coded bits in the coded packet (together with noise introduced during transmission) and decodes the coded packet by retracing the steps of the encoder. The decoder calculates for each possible state of the encoder a difference between the words representing the received packet and a preferred transmitted packet, which would have brought the encoder to that state. This difference is referred to as a state metric. For each group of words representing a group of received bits, the decoder updates the state metric of each possible state according to the difference between the probability values of the received bits and the ideal hypothetical values that would have been required for a specific state transition (referred to as a trellis transition) of the encoder. In Viterbi decoding, when transitions from different states lead to the same resultant state, the transition resulting in a state metric with the highest probability prevails. In MAP and APP decoding, the value of the new state metric is a function of all the transitions leading into the state, for example, a sum thereof.
The state metric rapidly increases with each bit that is processed, and with packets of thousands of bits may require representation in 15-20 bits or even more. When the decoding is performed in software by, for example, a digital signal processor, such sizes do not in themselves cause much of a problem. However, since the decoding must be performed under critical time constraints, dedicated hardware processors are preferably used. In such processors, it is necessary to limit the number of bits used to represent the state metric, in order to achieve fast decoding without excessive hardware cost.
A common solution involves using 8 bit registers to store the state metrics. In order to prevent saturation, a normalization metric (NM) comprising the minimal state metric is calculated periodically, preferably after each successive trellis transition, and the NM is subtracted from all the registers. However, calculation of the minimal state metric is time-consuming. Generally, the NM is calculated in parallel with the operation of the decoder, and the NM is subtracted at a later, delayed stage when the minimum is determined. In the meanwhile, the registers may saturate, losing valuable data. In addition, such a solution requires additional hardware for saving the NM to be used at the later stage, and for subtracting from the NM at the later stage previous values of the NM already subtracted from the state metric registers during the delay.
A. P. Hekstra, in “An Alternative to Metric Rescaling in Viterbi Decoders,” IEEE Trans. Commun. Vol. 37, No. 11 (November 1989), pp. 1220-1222, which is incorporated herein by reference, suggests using a modular calculation method to prevent saturation of the state metrics. In order to prevent saturation, a few additional bits are used to represent the state metric together with the modular calculation result. For example, for a four-state, 1/2 rate code with 6-bit data words, 11-bit registers as used to store the state metrics. However, every additional bit in the registers requires more calculation time and raises the cost of the decoder.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide methods and apparatus for fast state normalization in decoders using a trellis.
It is another object of some aspects of the present invention to provide apparatus for state normalization which is less prone to saturation than apparatus known in the art.
In preferred embodiments of the present invention, a decoder using a trellis, such as an A Posteriori Probability (APP) (or a Maximal A Posteriori (MAP)) decoder, a Viterbi decoder or a soft-output Viterbi algorithm (SOVA) decoder, calculates a minimum state metric used in normalization only approximately. The damage from the approximate calculation is negligible, relative to the savings in time due to the approximation. Preferably, the approximate minimum is less than or equal to the ac
Stein Jeremy M.
Ulmer Elisha J.
Baker Stephen M.
Qualcomm Incorporated
Rouse Thomas R.
Wadsworth Philip R.
LandOfFree
Efficient trellis state metric normalization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient trellis state metric normalization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient trellis state metric normalization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598129