Encoding device and method, decoding device and method,...

Details Encoding device and method, decoding device and method,... Encoding device and method, decoding device and method,...

1999-09-07

2004-01-27

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S786000

Reexamination Certificate

active

06684365

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an encoding device and method, a decoding device and method, and providing medium, and in particular, to an encoding device and method, a decoding device and method, and a providing medium which can conveniently be applied when performing turbo encoding or decoding.
2. Description of the Related Art
One type of code having a performance near the Shannon limit which is the theoretical limit of coding performance is a turbo code. This turbo code encodes by a structure which combines plural convolution encoding circuits and interleavers (interleaving circuits), and on the decoding side, information about input data is exchanged between decoding circuits which output plural soft outputs so as to obtain a final decoding result.
FIG. 9
shows the structure of a conventional turbo encoding device
10
. This turbo encoding device
10
comprises a convolution encoding circuit
1
-
1
which performs convolution encoding on input data to obtain encoded data, interleavers
2
-
1
to
2
-(N−1) which perform sequential interleaving on this input data (hereafter, these will be referred to simply as the interleavers
2
when it is unnecessary to distinguish the interleavers
2
-
1
to
2
-(N−1) separately, the same practice being adopted for other devices), and convolution encoding circuits
1
-
2
to
1
-N which perform convolution encoding on the outputs of these interleavers
2
to obtain encoded data.
Herein, the convolution encoding circuit
1
performs a convolution computation on the input data, and the computation results are output as encoded data.
One advantage of convolution encoding is that soft determination decoding can be performed more simply than block decoding. The interleavers
2
involute the sequence of input data to generate an output. By rearranging a pattern which gives a low output weighting with one convolution code, the interleavers
2
can increase output with other convolution codes, and can construct a high performance code by increasing the minimum distance of code words.
FIG. 10
shows one example of the convolution encoding circuit
1
. The convolution encoding circuit
1
shown in
FIG. 10
is a feedback type convolution encoding circuit having a restriction length
3
.
This convolution encoding circuit comprises a termination circuit
21
, three exclusive “or” circuits (hereafter, “EXOR circuits”)
22
-
1
to
22
-
3
, and two shift registers
23
-
1
and
23
-
2
, and generates encoded data from input data.
Herein, the shift registers
23
function as a delay element which delays input data by one unit time, and the EXOR circuit
22
outputs the exclusive or of the input data. Input data is output until the termination circuit
21
has finished encoding all the input data, and feedback data is output for two unit times (times corresponding to the number of shift registers) from when encoding has finished. The processing subsequent to encoding of all input data is intended to restore all the contents of the shift registers to 0, which is referred to as “termination”, and decoding is performed on the decoding side assuming this processing has been performed.
The state transition diagram of the convolution encoding circuit
1
shown in
FIG. 10
is as shown in FIG.
18
. As shown in this diagram, the convolution encoding circuit
1
has an initial state S
0
, and three other states S
1
, S
2
and S
3
. As shown in the diagram, when a “0” bit is input in the state S
0
, the state returns to the current state S
0
, and the value “0” is output, whereas when a “1” is input, a transition to the state S
1
occurs and the value “1” is output. When a “0” bit is input in the state S
2
, a transition to the state S
3
occurs and “1” is output, whereas when a “1” is input, a transition to the state S
2
occurs and the value “0” is output. When a “0” bit is input in the state S
2
, a transition to the state S
1
occurs and the value “0” is output, whereas when a “1” is input, a transition to the state S
0
occurs and the value “1” is output. When a “0” bit is input in the state S
3
, a transition to the state S
2
occurs and the value “1” is output, whereas when a “1” is input, a transition to the state S
3
occurs and the value “0” is output.
The output of the convolution encoding circuit
1
relative to input data can be easily understood by referring to this state transition diagram.
In the convolution encoding circuit
1
shown in
FIG. 18
, if zero is input three times in succession, the state returns to the original state prior to input of zero. This is true even in any of the states S
1
, S
2
, S
3
which are different from the initial state S
0
(for example, if zero is input three times in succession in the state S
1
, the transition S
1
→S
2
→S
3
→S
1
occurs and the state returns to the state S
1
). Therefore, the period p of this convolution encoding circuit
1
is
3
.
FIG. 11
shows an example of the interleavers
2
. Input data input to the interleavers
2
is first stored in an input data storage memory
31
, and its sequence is then rearranged by a data substitution circuit
32
. The rearrangement of the data sequence is performed based on the contents (substitution position information) of a substitution data ROM (Read Only Memory)
34
. The data with a rearranged sequence are stored in an output storage memory
33
, and then output as output data.
FIG. 11
shows a typical case of operation wherein the size of the interleavers
2
is
5
, and the contents of the substitution data ROM
34
are as shown in FIG.
12
. Specifically, when the input data are “11010”, “00111” is output as output data due to the data substitution circuit
32
performing substitution processing on the input data according to the data stored in the substitution data ROM
34
.
The operation of the turbo encoding device
10
shown in
FIG. 9
will now be described. Input data is supplied to the convolution encoding circuit
1
-
1
. In this convolution encoding circuit
1
-
1
, a convolution computation is performed on the input data, termination is performed, and encoded data is output by an encoding which comprises termination.
The input data is also supplied to the series of interleavers
2
-
1
to
2
-(N−1), and after the sequence of the sequentially input data is involuted, the data is output. The data output by these interleavers
2
-
1
to
2
-(N−1) is supplied to corresponding convolution encoding circuits
1
-
2
to
1
-N. In these convolution encoding circuits
1
-
2
to
1
-N, a convolution computation is performed on the output data from the corresponding interleavers
2
-
1
to
2
-(N−1), termination is performed, and encoded data is output by an encoding which comprises termination.
FIG. 13
shows the relation of the data input to the turbo encoding device
10
, and the number of bits of encoded data. k bits of input data are converted to an n
1
bit code by the convolution encoding circuit
1
-
1
and a t
1
bit termination is added, so the result is a (n
1
+t
1
) bit code. Similarly, (n
2
+t
2
) to (n
N
+t
N
) bits of coded data are output from the convolution encoding circuits
1
-
2
to
1
-N.
FIG. 14
shows the construction of a prior art turbo decoding device
40
. This turbo decoding device
40
comprises plural soft output decoding circuits
51
-
1
to
51
-N corresponding to the number of encoded data (received data) output by the turbo encoding device
10
. The soft output decoding circuits
51
-
1
to
51
-N use a “soft output decoding scheme” having the function of a MAP (Maximum A Posteriori Probability) decoder or SOVA (Soft Output Viterbi Algorithm) decoder which compute the probability of the input data being 0 or 1 on the encoding side. Soft output is a scheme wherein reliability information about a decoding result is attached to the decoding result.
The operation of the turbo decoding device
40
shown in
FIG. 14
will now be described. The received data (encoded data) is supplied to the soft output decoding circ

Affiliated with

Also associated with

Rating

Encoding device and method, decoding device 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 Encoding device and method, decoding device and method,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding device and method, decoding device and method,... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3240330