Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-03
2002-07-02
Chung, Phung M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000, C714S755000
Reexamination Certificate
active
06415414
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an encoding apparatus and method, a decoding apparatus and method, and a providing medium, and particularly to an encoding apparatus and method, a decoding apparatus and method, and a providing medium which are suitably applied when encoding or decoding of a turbo code is performed.
A turbo code is known as a code showing performance close to Shannon limit as a theoretical limit of code performance. In this turbo code, encoding is performed through a structure in which a plurality of convolution encoding circuits and interleavers (interleave circuits) are combined, and at a decoding side, exchange of information concerning input data is made among a plurality of decoding circuits outputting soft outputs, so that a final decoding result is obtained.
FIG. 1
shows a structure of a conventional turbo encoding apparatus
10
. This turbo encoding apparatus
10
includes a convolution encoding circuit
1
-
1
for performing convolution encoding with respect to input data to obtain encoded data, interleavers
2
-
1
to
2
-(N−1) for sequentially interleaving the input data (hereinafter, in the case where it is not necessary to distinguish the interleavers
2
-
1
to
2
-(N−1) individually, each is merely referred to as an interleaver
2
. It is the same with other devices.), and convolution encoding circuits
1
-
2
to
1
-N for performing convolution encoding with respect to the output data of the interleavers
2
respectively to obtain encoded data.
Here, the convolution encoding circuits
1
perform convolution encoding operations with respect to inputted data, and output the operation results respectively as encoded data. The interleavers
2
alter the sequence of inputted data and output them.
FIG. 2
shows an example of the convolution encoding circuit
1
. The convolution encoding circuit shown in
FIG. 2
is a feedback type convolution encoding circuit with a constraint length of three. This convolution encoding circuit
1
includes a termination circuit
21
, three exclusive OR circuits (hereinafter referred to as “EXOR circuit”)
22
-
1
to
22
-
3
, and two shift registers
23
-
1
and
23
-
2
, and generates encoded data from input data.
Here, the shift register
23
functions as a delay element for delaying inputted data by one unit time, and the EXOR circuit
22
outputs exclusive OR of inputted data. The termination circuit
21
outputs the input data until all of the input data are encoded, and outputs feedback data for only a two-unit time (time corresponding to the number of the shift registers) from the point of time when encoding is completed. A process after all the input data are encoded is called a termination in which all the contents of the shift registers
23
are returned to zero, and the decoding side performs decoding on the assumption of this process.
FIG. 3
shows an example of the interleaver
2
. The input data inputted to the interleaver
2
are temporarily stored in an input data holding memory
31
, and then, sequence is rearranged by a data replacement circuit
32
. The rearrangement of the sequence of the data is performed on the basis of the contents (replacement position information) of a replacement data ROM (Read Only Memory)
34
. The data in which the sequence is rearranged are stored in an output data holding memory
33
, and then, are outputted as output data.
FIG. 3
shows an example of an operation of the interleaver
2
in the case where the size of the interleaver
2
is five and the contents of the replacement data ROM
34
are as shown in FIG.
4
. That is, when the input data are “11010”, in accordance with the data stored in the replacement data ROM
34
, the data replacement circuit
32
performs a replacement process of the input data, so that “00111” are outputted as output data.
The operation of the turbo encoding apparatus
10
shown in
FIG. 1
will be described. The input data are supplied to the convolution encoding circuit
1
-
1
. In this convolution encoding circuit
1
-
1
, a convolution encoding operation is performed to the input data, and the termination is subsequently performed, so that encoded data through the encoding process including the termination are outputted.
Besides, the input data are supplied to the series circuit of the interleavers
2
-
1
to
2
-(N−1), and the sequence of the inputted data is sequentially altered and the data are outputted. The output data of the interleavers
2
-
1
to
2
-(N−1) are supplied to the corresponding convolution encoding circuits
1
-
2
to
1
-N, respectively. In the convolution encoding circuits
1
-
2
to
1
-N, the convolution encoding operation is performed to the output data of the corresponding interleavers
2
-
1
to
2
-(N−1) respectively, and the termination is subsequently performed, so that encoded data through the encoding process including the termination are outputted.
FIG. 5
shows the relation between the number of bits of input data and that of encoded data in the turbo encoding apparatus
10
. After the inputted k-bit input data are converted into a n
1
-bit code by the convolution encoding circuit
1
-
1
, a t
1
-bit termination code is further added, so that the data become a (n
1
+t
1
)-bit code in total. Similarly, (n
2
+t
2
) to (n
m
+t
m
)-bit encoded data are outputted from the convolution encoding circuits
1
-
2
to
1
-N.
FIG. 6
shows a structure of a conventional turbo decoding apparatus
40
. This turbo decoding apparatus
40
includes a plurality of soft output decoding circuits
51
-
1
to
51
-N corresponding to the number of encoded data (reception data) outputted from the turbo encoding apparatus
10
. The soft output decoding circuits
51
-
1
to
51
-N are structured by using a so-called soft output decoding system having a function to calculate a probability that the input data at the encoding side is 0 or 1, such as a MAP (Maximum Aposteriori Probability) decoder and a SOVA (Soft Output Viterbi Algorithm) decoder.
The operation of the turbo decoding apparatus
40
shown in
FIG. 6
will be described. The reception data (encoded data) are supplied to the soft output decoding circuits
51
-
1
to
51
-N, respectively. The respective decoding circuits
51
-
1
to
51
-N mutually use estimation probability value data with respect to the input data except the termination bit at the encoding side, and several to several tens repetitive decoding operations are performed. Final decoded data are outputted from an arbitrary decoding circuit (in
FIG. 6
, the decoding circuit
51
-
1
).
FIG. 7
shows the relation among the number of bits of the reception data of the turbo decoding apparatus
40
, that of the estimation probability value data, and that of the decoded data, and corresponds to the relation of the respective numbers of bits in the turbo encoding apparatus
10
in FIG.
1
. The soft output decoding circuits
51
-
1
to
51
-N calculate k-bit estimation probability value data of the input data except the termination bit from the (n
1
+t
1
) to (n
m
+t
m
)-bit reception data. The k-bit estimation probability value data are exchanged among the respective decoding circuits, and k-bit decoded data are finally outputted.
Now, for the purpose of obtaining a high error correction capability in a turbo encoding apparatus and a decoding apparatus, in general, it is necessary that the interleaver
2
satisfies the following two conditions at the same time.
[Condition 1] The sum of distances between arbitrary two points after-replacement becomes sufficiently larger than that before the replacement.
[Condition 2] In the case where replacement positions are regarded as a sequence, the sequence satisfies a mathematical property called k-equidistributioness.
The foregoing two conditions relate to performance index values defined for an error correction code, which are called a minimum distance of a code and a multiplicity of a minimum distance code. These two conditions are necessitat
Hattori Masayuki
Murayama Jun
Chung Phung M.
Frommer William S.
Frommer & Lawrence & Haug LLP
LandOfFree
Encoding apparatus and method, decoding apparatus and... 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 apparatus and method, decoding apparatus and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding apparatus and method, decoding apparatus and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2852019