Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-11
2004-01-06
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06675348
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to forward error correction encoders and decoders and more particularly, to turbo-like forward error correction encoders and decoders with improved weight spectrum and reduce degradation in the waterfall performance region.
2. Description of the Related Art
FIG. 1
illustrates a conventional Turbo encoder
10
which, as illustrated, includes two parallel constituent encoders
12
,
14
. An input stream x(k) is encoded by the constituent encoders
12
,
14
to produce parity bits y
1
(k) and y
2
(k). The encoder
14
sees the input stream x(k) presented in a different order than the encoder
12
due to the presence of an embedded Turbo interleaver
16
. The output coded bits x(k), y
1
(k), y
2
(k) are then punctured by puncturer
18
to produce the desired overall code rate. In the example, the natural rate of the Turbo encoder
10
is 1/3.
FIG. 1
shows a periodic puncturing pattern that produces an output code rate equal to 1/2.
FIG. 2
illustrates another encoder
20
for a conventional turbo code proposed for third generation CDMA systems. The encoder
20
, as illustrated, includes two constituent coders
22
,
24
that are systematic recursive convolutional coders having the transfer function G(D). The exemplary constituent coders
22
,
24
are rate 1/2 (producing one parity bit for each input information bit) and have 8 trellis states (each shift register has three delay elements
221
-
223
and
241
-
243
). The overall rate of the turbo code is thus R=1/3, since each information bit produces two parity bits, one from each encoder
22
,
24
. Various puncturing patterns are shown in
FIG. 2
to increase the code rate.
FIG. 3
illustrates a general block diagram for a Turbo code decoder
30
as generally described in C. Berrou et al., “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes,” Proceedings of ICC (Geneva, Switzerland), May 1993 and S. Benedetto et al., “Design of Parallel Concatenated Convolutional Codes,” IEEE Transactions on Communications, May 1996, Vol. COM-44, pp. 591-600. Soft-decision (likelihood) information for the systematic and parity bits from a first constituent coder (such as encoder
12
in
FIG. 1
) are sent to a first decoder
32
. The first decoder
32
generates updated soft-decision likelihood values for the information bits that are passed to a second decoder
34
as a priori information after reordering in accordance with a Turbo interleaver
36
.
In addition, the second decoder
34
accepts updated likelihood information for the systematic bits via an interleaver
38
, and the soft-decision information from the channel for the parity bits from a second constituent encoder (such as encoder
14
in FIG.
1
). A soft-decision output of the second decoder
34
regarding updated likelihood information for the systematic bits is then fed back to the first decoder
32
via a de-interleaver
40
. This process can be iterated as many times as desired. However, only a relatively small number of iterations is usually needed, since additional iterations generally produce diminishing returns. Hard decisions on the systematic information bits are made after the last decoder iteration is completed. If puncturing is used as depicted in
FIG. 1
, there is no likelihood information available for the corresponding parity bits. This is readily accounted for in the Turbo decoder
30
by using neutral values (favoring neither a 0-decision or a 1-decision) for the missing channel data.
If the two constituents encoders
12
,
14
or
22
,
24
are identical, the Turbo decoder
30
need only implement one constituent decoder
32
or
34
provided the VLSI hardware clock rate or DSP processing speed is able to support its reuse every half iteration.
Turbo codes as described above in conjunction with
FIGS. 1-3
are the current state of the art. Additional details can be found in U.S. Pat. No. 5,446,747 to Berrou and Turbo codes implemented on the Turbo encoder and decoder structures described in conjunction with
FIGS. 1-3
operate in two regions; a waterfall region and an error asymptote region. It is known that adding additional constituent encoders to a Turbo encoder can improve the error asymptote performance. However, this improvement comes at the cost of degrading the performance in the waterfall region. Research has shown that the performance in the waterfall region is largely due to convergence characteristics of the iterative decoder rather than the code rate spectrum. In general, the more complicated the code, the less efficient the error of decoder, leading to a degradation in waterfall performance.
SUMMARY OF THE INVENTION
The present invention is directed to an encoder, a decoder, a method of encoding, and a method of decoding, which preserve performance in the waterfall region, while improving upon performance in the error asymptote region.
The present invention is a modification of the basic Turbo encoder and decoder structures that preserves the Turbo coder performance in the waterfall region while improving upon performance in the error asymptote region.
The present invention provides a new code construction based on the Turbo code structure (in one example, parallel concatenation of constituent codes) that shares the performance of Turbo codes at low SNR while improving upon their asymptotic performance (so-called error floor region). The present invention includes applying a parser (or other similar element) to the input bit stream, the purpose of which is to assign input bits to a subset of the constituent encoders in a pseudo-random fashion. Provided each bit is presented to at least two of the constituent encoders, iterative decoding can still be accomplished in a similar fashion as for a Turbo code. As a result, each constituent decoder may only update the likelihood information associated with the information bits parsed to the corresponding encoder. The parsing strategy breaks up input sequences producing low Hamming weight error events, thereby improving the weight spectrum and asymptotic performance of the code, while not impacting the waterfall region performance of the corresponding Turbo code.
The addition of the parser may also strengthen the weight spectrum without adversely affecting convergence of the iterative decoder.
REFERENCES:
patent: 5729560 (1998-03-01), Hagenauer et al.
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6289486 (2001-09-01), Lee et al.
“Code and Parse Trees for Lossless Source Encoding” by Abrahams, J. in Proceedings Compression and Complexity of Sequences Jun. 11-13, 1997 Page(s): 145-171.*
“Analysis of Puncturing Pattern for High Rate Turbo Codes” by Fan Mo et al. in Military Communications Conference Proceedings, 1999. (MILCOM 1999) IEEE vol.: 1, 1999 Page(s): 547-550.
El Gamal Hehsam
Hammons, Jr. A. Roger
Britt Cynthia
De'cady Albert
Hughes Electronics Corporation
Sales Michael
Whelan John T.
LandOfFree
Turbo-like forward error correction encoder and decoder with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Turbo-like forward error correction encoder and decoder with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo-like forward error correction encoder and decoder with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3203279