Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-03-13
2004-04-20
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06725417
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to sequential decoding, and more specifically to techniques for sequentially decoding an incoming (received) data sequence in an attempt to find the most likely path in a code tree.
2. Description of Related Art
Prior to turning to the present invention, it is deemed preferable to describe, with reference to
FIGS. 1-5
, sequential decoding technology known as the Fano algorithm.
Reference is made to
FIG. 1
, a simple example of an encoder
10
, which takes the form of a binary convolutional encoder, is illustrated in block diagram form. The encoder
10
is comprised of a shift-register consisting of three flip-flops
12
a
-
12
c
and two exclusive-or gates
14
a
-
14
b
, all of which are coupled as shown. In order to initialize the flip-flops
12
a
-
12
c
, a control signal, which takes a logic level 0 (for example), is applied to the flip-flops
12
a
-
12
c
by way of an input terminal
16
c
. Each of the flop-flops
12
a
-
12
c
, in response to logic level 0 of the control signal, is cleared to zero. After the initialization of the flip-flops
12
a
-
12
c
, the control signal continues to assume a logic level 1. When a plurality of information symbols are successively applied to the flip-flop
12
a
via an input terminal
16
b
while the control signal takes a logic level 1, they are shifted one by one to the subsequent flop-flops
12
b
and
12
c
in synchronism with a clock signal applied to the flip-flops
12
a
-
12
c
by way of an input terminal
16
a
. In the above, each of the information symbols applied to the encoder
10
via the input terminal
16
b
is binary, and therefore, to be precise, has to be referred to as an information bit. However, in the instant disclosure, for the sake of convenience of description, the information bit may typically be referred to as information symbol.
The exclusive-or gate
14
a
has four inputs respectively coupled to receive directly the information symbol by way of the input terminal
16
b
and the outputs of the flip-flops
12
a
-
12
c
, and then applies the output thereof to an output terminal
18
b
. The other exclusive-or gate
14
b
has three inputs for respectively directly receiving the information symbols via the input terminal
16
b
and the outputs flip-flops
12
b
and
12
c
, and applies the output thereof to an output terminal
18
c
. On the other hand, the incoming information symbol is directly fed to an output terminal
18
a.
Assuming that information symbols u
1
, u
2
, u
3
, . . . are sequentially applied to the encoder
10
through the input terminal
16
b
. The initial information symbol u
1
determines first three encoded data sequence x
1
(1)
, x
1
(2)
, x
1
(3)
(=x
1
) which appear at the output terminals
18
a
-
18
c
. The next three encoded data sequence x
2
(1)
), x
2
(2)
), x
2
(3)
(=x
2
) are functions of the first two information symbols u
1
and u
2
, and the following three encoded symbols x
3
(1)
), x
3
(2)
), x
3
(3)
)(=x
3
) are functions of u
1
, u
2
, u
3
, and so forth. This dependence of the encoded data sequence upon the inputted information symbol sequence imposes a treelike structure on the set of the encoded data sequences, which is illustrated in FIG.
2
.
Referring to
FIG. 2
, the leftmost node of code tree, indicated by a black circle, is called an origin node, while the rightmost nodes of the code tree are respectively called terminal nodes. The leftmost symbol triplets 111 and 000 along the upper and lower branches stemming from the origin node, correspond to the responses of the encoder
10
to the initial information symbol (viz., u
1
) 1 or 0. Branching off to the right from the response 111 to an initial 1 are the responses to a 1 or 0 following an initial 1, and so forth. By way of example, the response of the encoder
10
to the information sequence u
1
=1, u
2
=1, u
3
=0, u
4
=0 is highlighted in the tree code of FIG.
2
.
As mentioned above, the encoder
10
forms a path through the code tree corresponding to an incoming information symbol sequence to be encoded. It follows that sequential decoding can be regarded as the process of determining the path in the code tree which was followed by the encoder. That is to say, a sequential decoder reconstructs the encoder's path through the tree on the basis of the received data sequence.
FIG. 3
is a diagram showing a code tree for use in sequentially decoding a received data sequence. Although the code tree of
FIG. 3
is exactly identical to that shown in
FIG. 2
(viz., replica of code tree of FIG.
2
), it is reiterated for the sake of convenience of description.
Assuming that the encoder
10
of
FIG. 1
outputs a data sequence 111 101 001 000 which is transmitted to a receiver via a binary symmetrical communication channel, and the received data sequence is 101 101 001 000 due to deterioration during the transmission over a noisy channel. In this case, the second bit of the first block is erroneously received.
As mentioned above, the first three symbols (bits) of the received data sequence should be either 111 or 000, and in this particular case, it is hypothesized that the first three symbols transmitted are 111 in that the Hamming distance is shorter than the other triplet 000. If this assumption is correct, it is hypothesized that the next three symbols are 101, and in a similar manner, it is further hypothesized that the following symbols are 001 000. That is, it is hypothesized that the data sequence 111 101 001 000 has been transmitted as highlighted in a bold line in FIG.
3
. The sequential hypothesizing as mentioned above is able to reduce the number of data sets (i.e., 111, 001, . . . along each branch) to be searched only two at each of the hypothesizing operations in this case.
As in the above case, assuming that the data sequence 111 101 001 000 has been transmitted. However, in this instance, it is assumed that due to more noisy channel circumstances, the received data sequence is contaminated as 010 101 001 000. In such a case, it is hypothesized that the first three symbols are 000 due to the shorter Hamming distance. Since this hypothesis is correct, it follows that the following code symbols are hypothesized as 111 101 001. Thus, the data sequence received is hypothesized as 000 111 101 001 as indicated by a phantom line in FIG.
3
. In this case, however, 4 symbol (bits) are erroneously presumed. This implies that once an erroneous hypothesis is made, the subsequently decoded symbols tend to be rendered uncorrelative or irrelevant with the received data sequence.
Throughout the instant disclosure, a term “path” implies a trail or passage from the origin node to a certain point (node) in the tree, or the most likely path up to a certain terminal node in the tree (viz., solution of the decoder). Further, a partial sequence
x
j
denotes a path at j-th level in the code tree as shown in FIG.
3
. As will be understood, the number of paths at the level 1 (viz., x
1
) is two, and that at the level 2 (viz., x
2
) is four, and so on. However, the partial sequences at the same level will not be discriminated with one another in the following descriptions.
In
FIG. 3
, a plurality of nodes in the code tree are denoted by n
0
, n
1
(
1
), n
1
(
2
), n
2
(
1
), . . . , n
4
(
15
), and n
4
(
16
), while a plurality of branches in the tree are denoted by b
1
(
1
), b
1
(
2
), . . . , b
4
(
15
), and b
4
(
16
).
The decoder is configured such as to notice that if the decoded data symbols are found to deviate from those of the received data sequence in excess of a predetermined threshold, the previous hypothesis has been erroneous. More specifically, if the decoder notices that the earlier hypothesis is erroneous at a given preceding node, the decoder returns to this node, changing the suspected branch (or node), and proceeds along a new branch or path in the tree. Each of these successive hypotheses is able to reduce the number of selections to be checked, simplifying the
Shimada Michio
Suzuki Hisashi
Chase Shelly A
De'cady Albert
Machine Learning Laboratory, Inc.
LandOfFree
Sequential decoding apparatus 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 Sequential decoding apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequential decoding apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3215168