Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-07
2002-11-19
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S341000
Reexamination Certificate
active
06484285
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed toward a method for decoding information signals and, more particularly, toward a method for decoding information signals that have been error-correction coded in cyclic blocks and/or have been received through a medium that introduces Inter-Symbol Interference (ISI), such block-cyclic decoders generally referred to as tailbiting decoders.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates in path form a prior art Stack decoding method, implemented by a prior art Stack decoder, for decoding continuously convolutionally coded signals. The method is described for steady-state operation after the Stack decoder has been operating for a relatively long time in relation to any special start-up operations. At the instant depicted in
FIG. 1
, the Stack decoder has tested a number of possible sequences represented by paths moving from left to right one symbol, or node, at a time. Every time a path is extended by one symbol, all possible values of the new symbol have to be considered, resulting in a new fork. If the symbols are binary symbols, or bits, that can take on only one of two values, then the forks each have two times corresponding to the next binary symbol being either a “1” or a “0”. At each node just before a new fork is generated, a number of numerical quantities are stored in a memory (not shown) associated with the node. The quantities describe at least the path, or symbol history, by which the Stack decoder reached the node, and a cumulative probability value for that path.
For example, two probability values are depicted in
FIG. 1
, namely, a value P
1
attached to a node
10
of highest probability, and a valve P
2
attached to a node
12
of second highest probability. The description of the path can, for example, be a string of symbols representing which of the previous forks were taken to reach the current node plus the probability at the current node. Accordingly, at the node
10
the description may include the symbol string . . .
010101
and the probability value P
1
, while at the node
12
the description may include the symbol string . . .
00
and the probability value P
2
. Alternatively, the description can include the symbol corresponding to the last fork taken, plus a pointer to the preceding node at which that fork was taken. The latter is sometimes more memory-efficient as only one symbol need be stored at each node. If it is desired to reproduce the string of symbols along the path, a “trace-back” operation may then be performed.
The prior art Stack algorithm shown in
FIG. 1
proceeds by extending the path of highest probability by one symbol and re-evaluating the probabilities for the extended paths. The path is extended by creating two new branches (in the case of binary symbols) from the previous node
10
of highest probability (P
1
). The two new branches are represented by dashed lines in FIG.
1
and end in two new nodes
14
and
16
for which new probability values xP
1
and yP
1
are respectively calculated. The sum of the multipliers (x+y) does not equal unity because the particular path chosen to be extended may be incorrect. The result of a trial-extension of an erroneous path may thus provide further evidence that the erroneous path was incorrect, reducing the probability of the path from P
1
to (x+y)P
1
. Multiplying this reduced path probability by the conditional branch probabilities x/(x+y) and y/(x+y), which do sum to unity, the probability for the two extended nodes xP
1
and yP
1
are obtained. The new probabilities xP
1
and yP
1
are then compared to the probabilities of other paths, particularly to the previous second highest probability P
2
, and to each other, to determine the node now having the highest probability which will be the next node extended to become two new nodes, and so forth.
Since multiplying the probability P
1
by x and y, respectively, both of which must be less than unity, can only reduce the probability below P
1
, it often happens in the prior art Stack algorithm that the previously second highest probability P
2
becomes the highest. When the node
12
having the probability P
2
is extended instead of one of the new nodes
14
(xP
1
) or
16
(yP
1
), this is termed “backtracking”, as the relative probabilities provide a hint that the path passing through the node
10
(P
1
) may not have been the correct path, and that decoding should perhaps be resumed along a previously abandoned path. Noise is one of the factors which may lead a Stack decoder astray along an incorrect path.
It is a disadvantage of the prior art Stack algorithm that, under noisy conditions, much backtracking takes place with a consequent increase in processing. The prior art Stack algorithm suffers from the deficiency that backtracking to any previously abandoned node, however far back (e.g., 10, 50, 100 or even 1,000 bits), could in principle occur, leading to the amount of computation required to determine the best path being unbounded. Consequently there is a need for improved Stack algorithms that do not suffer to the same extent from this deficiency.
In the prior art, the Stack algorithm was envisaged for continuous decoding, such as continuous convolutional decoding. However, as has been mentioned in the prior art, for example in “Error Control Coding” by Lin & Costello, (ISBN 0-13-283796-X), tail bits can be appended to a block of data prior to coding, the extra tail bits being transmitted so that the Stack decoder can end in a definitive end state. The use of tail bits adds additional redundancy and overhead to the transmission, causing the beginning and end bits to exhibit an improved error rate relative to bits in the middle of the transmission. This, however, may be of no utility since a lower error rate on all bits may be preferred, or alternatively, a transmission with lower overhead and therefore narrower bandwidth may also be preferred.
In a prior art decoding algorithm known as the Viterbi algorithm, the probability-indicating values are known as metrics. Because the Viterbi algorithm only compares probabilities for paths of the same length in symbols, indeterminate constants that add to, or multiply, the metrics do not affect the comparison, as they affect all paths alike. The Viterbi decoder can thus use simplified metrics which are the cumulative squared errors between hypothesized symbol coded values and received coded values. These simplified metrics are known as Euclidean distance metrics and are related to the logarithm of the reciprocal of the probability for the symbol sequence.
In the Stack algorithm, however, paths of different lengths must be compared, and the comparison is not then immune to additive terms that depend on the path length. Various methods are known to construct metrics for the Stack and similar algorithms that compare paths of different length. These metrics are generally Viterbi-type Euclidean-distance metrics modified by subtracting a value from the metric of a path every time the path is extended by one symbol. One such metric is known as the Fano metric which subtracts a value from the metric representative of the estimated mean square noise that is expected to be added per symbol extension, even to a correct path.
The present invention is directed toward overcoming one or more of the above-mentioned problems.
SUMMARY OF THE INVENTION
In a first embodiment of the present invention, a block of information symbols to be transmitted is generally regarded as a closed circle of information symbols. A coding algorithm is applied to the symbols lying in a segment of the circle to generate groups of coded symbols for each successive position of the segment, as the segment is moved around the circle one information symbol at a time. The groups of coded symbols are regarded as a closed circle of coded symbols corresponding to the closed circle of information symbols. The coded symbols are transmitted over a channel subject to error-inducing noise or other interference. This method of circular encoding is generally kno
Chase Shelly A
De'cady Albert
Ericsson Inc.
Moore & Van Allen PLLC
Stephens Gregory
LandOfFree
Tailbiting decoder and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tailbiting decoder and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tailbiting decoder and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2933069