Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-08
2003-01-14
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06507927
ABSTRACT:
TECHNOLOGICAL FIELD
The invention concerns generally the field of decoding an encoded digital signal after transmission through a noisy transmission channel. Specifically the invention concerns the problem of estimating the correctness of a certain decoded sequence of digital symbols.
BACKGROUND OF THE INVENTION
The widely known principle of convolutional encoding and its further developed forms like turbo encoding and concatenated convolutional encoding are commonly used for protecting a digital transmission against the detrimental error-introducing effects of a noisy transmission channel. Encoding is typically applied to discrete sequences of digital information, like frames or Protocol Data Units (PDUs). A receiver arranged to receive such an encoded transmitted sequence will apply a so-called Viterbi decoding algorithm to remove the encoding and to reconstruct the original digital sequence. As a background of the present invention we will briefly discuss some known features of Viterbi decoding.
A symbol sequence that has been constructed with a basically convolutional encoder of some kind will consist of a number of discrete symbols. Each symbol may be seen to represent k bits. Most practical implementations use binary convolutional encoding where the symbol length is one bit, although consecutive symbols may be grouped to form states.
FIG. 1
a
illustrates a simple convolutional encoder that produces a ½ rate convolutional code. Input bits A(t) are fed from the left at the rate of one bit per unit time and two output bits X(t) and Y(t) per unit time are obtained at the right. The memory
101
of the convolutional encoder is represented as a shift register or an array of serially concatenated one bit memory cells (e.g. D-type flip-flops). The state of an encoder is represented as the contents of its memory, so the encoder of
FIG. 1
a
a has the possible states
00
,
01
,
10
and
11
. The length of the shift register determines the number of output bits in one output line to the values of which a single input bit has an influence: said number of output bits is known as the constraint length and in
FIG. 1
a
it is three. An output bit may be calculated from an input bit and the known state of the encoder. For example in
FIG. 1
a
, Y(t)=A(t)+A(t−1)+A(t−2) and the bit which at time t is known as A(t) will also influence the value of the output bits Y(t+1) and Y(t+2).
FIG. 1
b
illustrates a state matrix showing all possible states of the encoder of
FIG. 1
b
at eight consecutive time instants. The correct sequence to be found through decoding corresponds to a path through the state matrix from left to right so that in each column the path goes through exactly one state. An exemplary path is shown in
FIG. 1
b
as a continuous line. A graph showing states and paths through them is known as a trellis diagram and a path is also known as a trellis path.
It is a feature of the convolutional encoding and Viterbi decoding principle that from each known state there are only a certain number of allowed transitions to following states. A Viterbi decoder will find a number of possible paths through the trellis diagram by starting from a certain first state and propagating with allowed transitions from state to state. The observed transitions in the received, error-corrupted symbol sequence are seldom unequivocal but give rise to different interpretations with certain transition probabilities. The Viterbi decoder will use the information about the allowed state transitions and the observed transition probabilities to construct the possible trellis paths. In theory it would be possible to simulate every possible trellis path in the receiver and calculate its probability value in the light of the received sequence; however, the practical sequences are so long and the timing constraints are so tight that the exponentially growing number of possible paths would soon make the problem computationally impossibly complex. Practical Viterbi algorithms use certain reliability metrics to select at each state a single “surviving” path or a limited number of “candidate” paths to go on with. The path which provides the best estimated reliability in the log-likelihood sense at the final state will be declared to represent the decoded digital sequence.
In some cases the Viterbi algorithm will not be able to provide a single most probable path through the trellis diagram, or the most probable path still contains errors. Several approaches have been proposed for dealing with such a situation, one of them having been published in the article H. Yamamoto and K. Itoh: “Viterbi Decoding Algorithm for Convolutional Codes with Repeat Request”, IEEE Transactions on Information Theory, vol. IT-26, no.5, pp. 540-547, September. 1980, which is incorporated herein by reference. In the proposed method the surviving path for some i:th state is declared as unreliable if the metric difference between the two best paths to this state is smaller than a given threshold value or if the winning surviving path has at some previous time instant been declared as unreliable. If, at some time instant, the surviving paths to every state are declared as unreliable, the whole received sequence will be marked as unreliable and an erasure of information is declared. An advantage of the proposed method is that it requires only minimal overhead in processing or storage capacity when compared to straightforward Viterbi decoding. The article A. R. Raghavan and C. W. Baum: “A Reliability Output Viterbi Algorithm with Applications to Hybrid ARQ”, IEEE Transactions on Information Theory, vol. IT-44, no.3, pp. 1214-1216, May. 1998, also incorporated herein by reference, proposes another approach in which a conditional a posteriori probability is calculated for errors in the decoded sequence. The theoretical performance of the latter approach is good but it requires a prohibitively complex calculational arrangement for practical applications in present-day communication devices.
A so-called list decoding or look-up decoding approach is also known in which the Viterbi decoding algorithm will not give a single output sequence with the highest log-likelihood value but a list of mutually alternative sequences in the order of diminishing likelihood values. A CRC (Cyclic Redundancy Check) checksum calculation or a similar other decoding method is then used to detect whether the n:th sequence in the list contains errors, starting with n=1. If there are errors in a certain sequence at place n in the list, the sequence at place n+1 is tried next until either an error-free sequence is found or all sequences in the list have been tried. Such an approach is known from e.g. the patent publication EP 0 606 724 A1 and the article Nill et al.: “List and Soft Symbol Output Viterbi Algorithms: Extensions and Comparisons”, IEEE Transactions on Communications, Vol. 43, No. 2/3/4, February/March/April 1995. An advantage of the list decoding approach is that in many cases it saves time: making another “guess” of the correct form of the received sequence (in the form of taking another sequence from the list) and performing a CRC check is enormously faster than asking for and providing a retransmission from the transmitting device, so even if in some cases the whole list has to be exhausted and even then a restransmission must be requested, it suffices that for a significant number of times a retransmission can be avoided by actually finding the correct error-free sequence on the list.
A drawback of the list decoding principle is that it is quite memory-intensive: a number of mutually alternative sequences (and even the associated state-specific reliability values) must be temporarily stored in the receiving device, and only one of the stored sequences will ultimately be used. To reduce the amount of required storage capacity the patent publication WO 97/43834 proposes the concept of a decision window. A decision window is a structure containing a fixed number of columns from the trellis diagram. Initi
Chase Shelly A
De'cady Albert
Nokia Mobile Phones Ltd.
Perman & Green LLP
LandOfFree
Method and device for estimating the reliability of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for estimating the reliability of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for estimating the reliability of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3021246