Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-10-29
2002-06-18
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06408418
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a device and method for. decoding data and, more particularly, to a reduced-state device and method for decoding data by generating accumulated conditional probabilities (ACPs) for certain states out of all possible states of an encoder.
2. Description of Related Art
A conventional convolutional encoder encodes information bits using a shift register and a plurality of adders.
FIG. 1
shows a schematic diagram of a conventional ½ rate convolutional encoder. As shown therein, the conventional convolutional encoder
100
includes a shift register
11
composed of a plurality of memory units M
0
-M
7
connected in series to each other, and first and second adders
10
and
12
coupled to the shift register
11
for generating first and second coefficients C
0
and C
1
. Each of the memory units M
0
-M
7
is a one-bit memory for storing a bit input thereto while shifting the bit already stored therein to a next one-bit memory.
Since there are 8 one-bit memory units M
0
-M
7
in the shift register
11
, the shift register
11
has 256 possible states (from state
0
to state
255
). The term “state” indicates the content of the shift register
11
at a given time. It is known that the state of the shift register
11
is an even state if the arriving information bit (i.e., the bit ready to be input to the first memory unit M
0
) of the previous state of the shift register
11
is zero, or an odd state if the arriving information bit of the previous state of the shift register
11
is one.
An operation of the conventional convolutional encoder
100
of
FIG. 1
is as follows. Information bits to be encoded are input to the first memory unit M
0
one bit at a time. A block of information bits (e.g., 196 bits) are typically processed at one time. Each new information bit input to the encoder
100
is pushed into the first memory unit M
0
of the shift register
11
as the previous content of the first memory unit M
0
is shifted to the second memory unit M
1
, the previous content of the second memory unit M
1
to the third memory unit M
2
, the previous content of the third memory unit M
2
to the fourth memory unit M
3
, and so forth. A controller (not shown) generates a clock signal to shift the bits of the memory units M
0
-M
7
at a predetermined time interval.
The first adder
10
adds the arriving information bit of the shift register
11
with bits stored in the memory units M
0
, M
1
, M
2
, M
4
, M
6
, and M
7
to generate the first coefficient C
0
. The second adder
12
adds the arriving information bit with bits stored in the memory units M
1
, M
2
, M
3
and M
7
to generate the second coefficient C
1
. According to this process, as one bit of information data is input to the encoder
100
, a pair of coefficients C
0
and C
1
are output from the encoder
100
as encoded data. Hence, the encoder
100
has the ½ process rate. Although the conventional ½ rate convolutional encoder
100
has been described above, encoders having other process rates, e.g., {fraction (1/3, 2/3)}, and others, are also known in the art.
The first and second coefficients C
0
and C
1
(encoded data) generated by the encoder
100
pass through communication channels to other encoders/decoders. During this process, however, the encoded data suffer from bit corruption and become less reliable. For example, as the encoded data pass through communication channels, certain zero (“0”) bits may change to one (“1”) bits and vice versa, such that corrupted coefficients CC
0
and CC
1
are transmitted as encoded data, and are decoded by a conventional convolutional decoder.
To decode the corrupted coefficients CC
0
and CC
1
, a conventional convolutional decoder assumes all possible states of the shift register
11
of the encoder
100
, and attempts to determine what the original, uncorrupted coefficients C
01
and C
1
are. If the original coefficients C
0
and C
1
output from the encoder
100
can be determined, then accurate input data (i.e., arriving information bits of the encoder
100
) can be recovered as decoded data.
FIG. 2
shows a block diagram of such a conventional convolutional decoder
200
for decoding encoded data, such as, corrupted coefficients CC
0
and CC
1
. The decoder
200
includes a state counter
20
, a previous state locator
22
, first and second encoders
24
A and
24
B, a modulo
2
unit
26
, first and second quantizers
28
A and
28
B, first and second adders
30
A and
30
B, a maximum selector
32
, a memory unit
34
, and a decoding unit
36
, connected as shown.
The state counter
20
counts from state
0
to state
255
for each pair of the corrupted coefficients CC
0
and CC
1
to cover all
256
possible states of the shift register
11
in the conventional encoder
100
. The state counting by the state counter
20
is performed based on a clock signal generated from the memory unit
34
. Based on each current state count value, the previous state locator
22
determines two possible previous states (i.e., two possible contents of the memory units M
0
-M
7
of the shift register
11
shown in
FIG. 1
) according to a known process. One of the two possible previous states is output to the first encoder
24
A, and the other possible previous state is output to the second encoder
24
B.
The modulo
2
unit
26
receives the state count value from the state counter
20
, and generates 0 or 1 based on each state count value. The 0 and 1 output from the modulo
2
unit
26
represent possible information bits (0 and 1) to be recovered by the decoder
200
.
Each of the first and second encoders
24
A and
24
B receives the bit from the modulo
2
unit
26
and one of the two possible previous states determined by the previous state locator
22
to generate theoretical coefficients TC
0
and TC
1
. For each input to the first and second encoders
24
A and
24
B, the first encoder
24
A generates a pair of first theoretical coefficients TC
0
and TC
1
, and the second encoder
24
B generates a pair of second theoretical coefficients TC
0
and TC
1
. This process is repeated for each of the 256 possible states, so that 256 pairs of theoretical coefficients TC
0
and TC
1
are sequentially output from each of the first and second encoders
24
A and
24
B.
Each of the first and second quantizers
28
A and
28
B receives a pair of the theoretical coefficients TC
0
and TC
1
for each state count value, and encoded data bits (pairs of corrupted coefficients CC
0
and CC
1
) input to the decoder
200
. Each of the first and second quantizers
28
A and
28
B determines, assuming that uncorrupted coefficients C
0
and C
1
are input to the decoder
200
, the conditional probability of each pair of the corrupted coefficients CC
0
and CC
1
based on the sequentially received pairs of theoretical coefficients TC
0
and TC
1
, and then quantizes the conditional probability into a certain number of levels, e.g., 32 or 64 levels. The quantized values output from each of the first and second quantizers
28
A and
28
B indicate how well each pair of inputted corrupted coefficients CC
0
and CC
1
match the 256 pairs of theoretical coefficients TC
0
and TC
1
. Accordingly, the conventional convolutional decoder
100
carries out a full search algorithm by determining conditional probabilities for the entire 256 possible states of the encoder
100
.
Whenever a quantized value is output from the quantizers
28
A and
28
B, each of the first and second adders
30
A and
30
B adds the current quantized value with the corresponding accumulated quantized value (i.e., ACP) stored in the memory unit
34
to generate updated ACPs. The maximum selector
32
receives two ACPs from the adders
30
A and
30
B at a given time, compares the two ACPs to each other, and selects the greater one of the two ACPs. The selected ACP is referred to hereinafter as the winning ACP, and the previous state which results in the winning ACP is referred to hereinafter as the winning previous state (PS). The win
De'cady Albert
Harness & Dickey & Pierce P.L.C.
Lamarre Guy
Lucent Technologies - Inc.
LandOfFree
Reduced-state device and method for decoding data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reduced-state device and method for decoding data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced-state device and method for decoding data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2966230