Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-08-19
2003-02-11
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000, C714S792000
Reexamination Certificate
active
06519732
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an encoding apparatus, and more specifically to an error-correcting encoding apparatus.
Encoding technology is widely utilized in various fields. For example, in transmitting data, a source apparatus encodes data to be transmitted and sends the encoded data through a communications path so that a destination apparatus receives and decodes the encoded data. When data is stored in a storage device, it is encoded and written to a disk, etc. The encoded data is then decoded after being read from the disk. Encoding normally refers to converting a data sequence from an information source into a different data sequence, and thus the new data sequence obtained by the conversion is referred to as a code.
When encoded data is transmitted, an error may occur in the transmission path. An error may also occur when the encoded data is read for reproduction from a storage device that stores the encoded data. To detect an occurrence of such an error, or to correct such an error, an error-correcting code is frequently used.
A convolutional code is known as one type of error-correcting code. Each time n-bits of data is input for processing a convolutional code. Data of m (m>n) bits is then determined depending on the n-bit data and s-bit data, which is input immediately before the n-bit data is output. Thus, in processing the convolutional code, data of (m−n) bits is added for error correction to the data to be transmitted. As a result, the redundancy of the data is increased, thereby reducing the decoding error rate when the data is decoded.
The ratio of the amount of data to be transmitted (number of bits of source data) to the amount of data obtained by the encoding process (number of bits of output data) is commonly referred to as an encoding rate (or an information rate) R, and is represented by the following equation.
R=n/m
The encoding rate R is always lower than 1 in an error-correcting code. Generally, the encoding rate R is one of the parameters for determining the error correction capability. For example, the lower the encoding rate R is, the higher the error correction capability becomes.
FIG. 20
is a block diagram showing an example of an existing error-correcting encoding apparatus using a convolutional code. The error-correcting encoding apparatus
500
includes two convolution units
501
,
502
provided in parallel with each other. An encoding apparatus including plural convolution units connected in parallel with each other are often referred to as a “turbo-encoding apparatus”.
The error-correcting encoding apparatus
500
generates, for source data d, a data sequence x and parity data sequences y
1
,y
2
for correcting the data sequence x. The data sequence x and the parity data sequences y
1
,y
2
are then multiplexed and output. This output is the encoded data of the source data d. Described below is the operation performed when N-bits of source data d is encoded.
The source data d is output as the data sequence x as is, and is also transmitted to the convolution unit
501
and an interleaver
503
. The convolution unit
501
performs a convolutional encoding process on the source data d and outputs the parity data sequence y
1
. The interleaver
503
temporarily stores the source data d and, then reads and outputs the stored source data in an order different from the input order. Thus, the source data d is randomized. The output from the interleaver
503
is then provided to the convolution unit
502
. The convolution unit
502
also performs a convolutional encoding process on the output from the interleaver
503
, and outputs the parity data sequence y
2
.
In the above described operations, the error-correcting encoding apparatus
500
generates an N-bit data sequence x, an N-bit parity data sequence y
1
, and an n-bit parity data sequence y
2
for N-bits of source data d. The data sequence x and parity data sequences y
1
,y
2
are, for example, multiplexed for each bit and output as the encoded data. Therefore, in this case, the error-correcting encoding apparatus
500
outputs
3
×N bits of data for every N-bits input. As a result, the encoding rate R is 1/3.
FIG. 21
is a block diagram showing an example of a variation of the error-correcting encoding apparatus shown in FIG.
20
. The error-correcting encoding apparatus
510
is realized by providing a selection unit
511
for the error-correcting encoding apparatus
500
shown in FIG.
20
. According to a predetermined selection pattern, the selection unit
511
selects the parity data sequences y
1
, y
2
respectively generated by the convolutional units
501
,
502
, and outputs it as a parity data sequence Z. The operation of the selection unit
511
is referred to as a “puncturing” process.
The selection unit
511
alternately selects one bit from the outputs of the convolution units
501
,
502
. Table 1 shows the output sequence Z produced by the selection unit
511
. In Table 1, y
1
(i) indicates the output from the convolutional unit
501
corresponding to the i-th data element of the source data d, and y
2
(i) indicates the output from the convolution unit
502
corresponding to the i-th data element of the source data d. When N-bits of source data d is input to the error-correcting encoding apparatus
510
, the selection unit
511
outputs a N-bit output sequence Z (y
1
(
1
), y
2
(
2
), y
1
(
3
), y
2
(
4
), . . . , y
1
(N−1), y
2
(N)).
y
1
(1)
y
1
(3)
. . . .
y
1
(N-1)
y
2
(2)
y
2
(4)
. . . .
y
2
(N)
The puncturing operation performed by the selection unit
511
is represented by the following equation.
Z
=
D
·
P
=
y1
(
i
)
y2
(
i
)
1
0
y1
(
i
+
1
)
y2
(
i
+
1
)
0
1
(
i
=
1
,
3
,
5
,
…
,
N
-
1
)
The output sequence Z is obtained by multiplying the data matrix D by the puncturing matrix P. For example, for the i-th data element of the source data d, y
1
(i) is obtained by multiplying the first row of the data matrix D by the first column of the puncturing matrix P. For the (i+1) the data element of the source data d, y
1
(i+1) is obtained by multiplying the second row of the data matrix D by the second column of the puncturing matrix P. Therefore, the operation of the selection unit
511
for alternately selecting the outputs of the convolution units
501
,
502
bit by bit is represented as an operation of repeatedly performing the above described arithmetic operations.
With the above described configuration, the error-correcting encoding apparatus
510
generates an N-bit data sequence x and an N-bit parity data sequence Z for N-bits of source data d. The data sequence x and the parity data sequence Z are multiplexed bit by bit, and then output as encoded data. Since the error-correcting encoding apparatus
510
outputs 2N bits of data for every N-bits input, the encoding rate R is ½.
U.S. Pat. No. 5,446,747 discloses in detail the above described error-correcting encoding apparatus shown in
FIGS. 20 and 21
.
In mobile terminal communications systems, it is required to optionally set the data length M of an output sequence from an encoding apparatus in relation to the data length N (number of bits) of source data d. For example, voice data, etc. is normally divided into data having a predetermined data length, and is then transmitted after being stored in a frame having a predetermined data length. Thus, when encoded data is processed in a mobile terminal communications system, voice data, etc. is divided into data having a predetermined data length, encoded and then stored in a frame.
However, the encoding rate R of the conventional error-correcting encoding apparatus shown in
FIGS. 20
or
21
is fixed. Therefore, since the data has a predetermined fixed length (the frame in the above-described example), useless information has to be stored to fill the data storage area of the frame.
FIG. 22A
shows the process for encoding source data u
Baker Stephen M.
Fujitsu Limited
Katten Muchin Zavis & Rosenman
LandOfFree
Error-correcting encoding apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error-correcting encoding apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error-correcting encoding apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173373