Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-07-30
2001-09-11
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S701000
Reexamination Certificate
active
06289486
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to adaptive channel encoding methods and devices for communications systems, and in particular, to adaptive channel encoding methods and devices for use in transmission of voice and data.
2. Description of the Related Art
A turbo encoder, constituted in a parallel or serial structure, generates parity symbols from an input N-information bit frame with two simple component (or constituent) encoders. It uses a recursive systematic convolutional (RSC) code as a component (or constituent) code.
FIG. 1
is a block diagram of a conventional parallel turbo encoder, disclosed in U.S. Pat. No. 5,446,747 by Berrou. In the turbo encoder of
FIG. 1
, an interleaver
12
is interposed between first and second component encoders
11
and
13
. The interleaver
12
has a size equivalent to the frame length N of the input information bits, and modifies the sequence of information bits received in the second component encoder
13
to reduce correlation between information bits.
FIG. 2
is a block diagram of a conventional serial turbo encoder also having the interleaver
12
connected between the first and second component encoders
11
and
13
.
The above turbo encoders produce a turbo code for use in space communications. Though a constraint length K in the component encoders
11
and
13
is shorter than that of a conventional convolutional code (i.e., K=9), the interleaver
12
uses a very large memory, resulting in a very long delay at decoding.
FIG. 3
is a block diagram of a turbo decoder for decoding the output of the parallel turbo encoder shown in
FIG. 1
, also disclosed in U.S. Pat. No. 5,446,747 by Berrou.
FIG. 4
is a block diagram of a turbo decoder for decoding the output of the serial turbo encoder shown in
FIG. 2
, proposed by Benedetto in an article of IEEE Electronics Letters, Vol. 32, No. 13, June 1996.
The parallel turbo decoder of
FIG. 3
advantageously enhances performance characteristics in terms of bit error rate (BER) by repeatedly decoding input data in frame units, using an iterative decoding algorithm. An interleaver
323
contributes to an increase in an error correction capability by distributing burst error patterns which were not corrected by a first decoder
319
, prior to correction of the burst error patterns in a second decoder
327
.
The iterative decoding refers to repeated decoding of symbols which were decoded in a specific procedure, using resulting extrinsic information, to achieve excellent decoding performance. Iterative decoding algorithms are SOVA (Soft-Output Viterbi Algorithm: see Proceedings of IEEE Vehicular Technology Conference, pp. 941-944, May 1993) and MAP (Maximum Aposteriori Probability: see IEEE Transactions on Information Theory, pp. 429-445, Vol. 42, No. 2, March 1996). SOVA is a modification of a Viterbi algorithm which produces a soft decision output and can minimize codeword error rate. On the other hand, MAP can minimize symbol error rate.
In the decoder of
FIG. 3
, outputs y
1k
and y
2k
of a depuncturer
313
are y
k
and zero, respectively, when a parity symbol y
k
is received from the first component encoder
11
of
FIG. 1
, whereas they are zero and y
k
, respectively, when the parity symbol y
k
is received from the second component encoder
13
of
FIG. 1. Z
k+1
is a soft decision symbol used as extrinsic information in an iterative decoding algorithm and an input for decoding in a next stage. Data elements ({haeck over (D)}) obtained by subjecting the Z
k+1
of the final decoding stage to hard decision are taken into account at output of the last module as intended. The performance of the turbo code depends on interleaver size, interleaver structure, and the number of iterative decodings.
As shown in
FIG. 1
, the turbo encoder includes the interleaver
12
. The interleaver
12
causes turbo encoding/decoding to be implemented in frame units. Thus, the complexity of turbo code is proportional to the product of frame size of a memory necessary for first and second iterative decoders
319
and
327
shown in FIG.
3
and the state number of component codes for the first and second component encoders
11
and
13
. The turbo code cannot find its application in voice and data transmission due to use of very large frames. Increasing the state number of the component codes for the turbo encoder in order to achieve better performance leads to increased complexity of the first and second component encoders
11
and
13
.
With a burst error in the decoder as shown in
FIG. 3
, the output of the first iterative decoder
319
has a correlation, which impedes reliable decoding in the second iterative decoder
327
in the next decoding stage. Hence, errors are incurred in a whole block and cannot be corrected in a next iterative decoding stage. In this context, there is an ever increasing need for an interleaver and a deinterleaver which can distribute burst errors in a single frame of a code subject to iterative decoding without correlation.
Due to the advantage of low correlation, a random interleaver increases the performance of the turbo code. With small frame size, however, the random interleaver has limitations in its effectiveness for distributing burst errors without correlation and requires a look-up table. Hence, voice transmission or low-rate data transmission require small frame size and a small number of component code states to minimize delay time. Voice transmission or low-rate data transmission further need a structured interleaver. In short, the conventional turbo code is not viable in the voice and data transmission because of the unacceptability of the constraint length of the component codes and the large interleaver. Nevertheless, efforts are increasingly expended on realization of an encoder and a decoder for a communications system, taking the advantages of the conventional turbo code into account.
Therefore, a need exists for a turbo encoder having a performance equal to or higher than that of a convolutional encoder in a conventional communications system. A further need exists for an interleaver having excellent performance with small component code states and minimized delay time. Though the performance of the interleaver
12
of
FIG. 1
or
2
for use in a turbo encoder is generally proportional to the interleaver size, the frame size of the turbo code is limited. In this case, it is preferable to use an interleaver that maximizes a minimum hamming distance of the turbo code in terms of a block code. A structured interleaver can be employed for small frames.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide turbo encoding method and device, which can encode voice and low transmission rate-data in a communications system.
Another object of the present invention is to provide a parallel or serial turbo encoding method and device, in which a diagonal interleaver is used to interleave input data regardless of frame size in a communications system.
A further object of the present invention is to provide a parallel or serial turbo encoding method and device, in which a circular shifting interleaver is used to interleave input data regardless of frame size in a communications system.
Still another object of the present invention is to provide a method and device for transmitting tail bits and parity bits generated from the tail bits on a channel in a device for encoding voice and data signals to a turbo code.
Yet another object of the present invention is to provide a method and device for adjusting a data transmission rate by puncturing data and parity information in a device for encoding voice and data signals to a turbo code.
To achieve the above objects, there is provided a turbo encoder. The turbo encoder includes a plurality of component encoders for encoding input information bits, and a diagonal interleaver connected to an input port of one of the component encoders and having a table for storing column and row information corresponding to a variable frame size
Kim Young
Kong Jun Jin
Lee Hyeon Woo
Lee Pil Joong
Park Chang Soo
Chase Shelly A
De'cady Albert
Dilworth & Barrese LLP
Samsung Electronics Co,. Ltd.
LandOfFree
Adaptive channel encoding method and device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive channel encoding method and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive channel encoding method and device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459471