Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-12-13
2004-02-24
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000
Reexamination Certificate
active
06697990
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data stream encoders, and more specifically to data stream encoders using parsed parallel concatenated codes. Even more specifically, the present invention relates to a pseudo random interleaver design within a data stream encoder using parsed parallel concatenated codes that accounts for the parsing function of the encoder resulting in improved asymptotic performance.
Third generation code division multiple access (CDMA) communications systems typically employ forward error correction (FEC) schemes using, for example, Turbo codes. As such, prior to being transmitted over a communications channel, for example, a data stream is often encoded such that the content of the data is not recoverable to those intercepting the transmitted data stream. Typically, such data streams may be encoded using a Turbo encoder, which consists of a parallel concatenation of two constituent encoders in which the input data stream x(k) is encoded by both encoders to produce parity bits y
1
(k) and y
2
(k). The first and second constituent encoders each see the input data stream as presented in a different order due to an embedded Turbo interleaver. Each constituent encoder encodes its interleaver. Each constituent encoder encodes its respective data bits to provide output coded bits x(k), y
1
(k), y
2
(k). These output coded bits are typically punctured to produce a desired code rate. For example, the natural rate of a conventional Turbo encoder is ⅓; however, the coded output is punctured to produce an output code rate of ½. At the receiver a respective Turbo decoder is required to decode the coded data stream. The operation and functionality of conventional Turbo codes, Turbo encoders and decoders is well known in the art.
More recently, encoders using parsed parallel concatenated codes are being implemented. A parsed parallel concatenated code (also referred to as P2CCC) is a code construction that is similar to the conventional turbo code structure, but with a parser to distribute subsets of information bits from the input data stream to various parallel constituent encoders. The parsing strategy breaks up the input sequences producing low Hamming weight error events, thereby improving the weight spectrum and asymptotic performance of the code, while not impacting the sharp “waterfall region” performance of the corresponding turbo code. Thus, the parsing function serves a similar function as the embedded turbo interleaver. The parsed streams are then separately interleaved and separately encoded by respective constituent encoders. The output of the constituent encoders is then punctured in a prescribed puncturing pattern to produce the overall code rate. In a typical design, the parser ideally ensures that every information bit in the input data stream is seen by at least two of the constituent encoders in order that soft-decision decoding will be able to efficiently refine the likelihood decision statistic for each information bit based on the outputs from multiple constituent decoders.
While it is known how to design interleavers reasonably well for conventional turbo codes, the parsing function makes the design of interleavers for P2CCC encoders a non-trivial problem. Using random interleavers, the P2CCC encoder has a performance advantage over the conventional turbo codes in the asymptotic region. However, when s-random interleavers (i.e. a pseudo random permutation that avoids mapping positions within a window of width S to new positions that are also within a window of width S, thus guaranteeing a minimum separation between positions) are used, the performance advantage of P2CCC is eliminated over conventional turbo codes. This is due to the fact that conventional s-random interleavers do not take into account the parsing function common to P2CCC encoders.
SUMMARY OF THE INVENTION
The present invention advantageously addresses the needs above as well as other needs by providing an interleaver design for a parsed parallel concatenated coder implementing coordinated s-random interleavers and accounting for the parsing function.
In one embodiment, the invention can be characterized as a method of interleaving an input data stream for parsed parallel concatenated code encoding comprising the steps of: parsing the input data stream into a plurality of parsed data substreams; and forming sets of shared information bits, wherein each of the sets of shared information bits comprises information bits in common with respective pairs of the plurality of parsed data substreams. In a variation of this embodiment, a further step comprises constructing constituent permutations of one or more of the sets of shared information bits. In yet a further variation of this embodiment, a further step comprises interlacing respective pairs of the sets of shared information bits to form respective interleaved data substreams.
In another embodiment, the invention can be characterized as an interleaver design for a parsed parallel concatenated code encoder including a parser for parsing an input data stream into a plurality of parsed data substreams. Also included is a plurality of interleavers coupled to the parser such that each of the plurality of interleavers constructs constituent permutations of respective ones of sets of shared information bits. Each of the sets of shared information bits comprises information bits in common to respective pairs of the plurality of parsed data substreams.
REFERENCES:
patent: 5666370 (1997-09-01), Gamesan et al.
patent: 5996104 (1999-11-01), Herzberg
patent: 0 920 164 (1998-11-01), None
patent: WO 00/19618 (2000-06-01), None
Bingeman et al., Symbol-based Turbo codes, Oct. 1999, IEEE Communications Letters, vol. 4, No. 10, p. 285-287.*
Caire et al., Parallel Concatenated codes with unequal error protection, May 1998, IEEE Transactions on communications, vol. 46, No. 5, p. 565-567.
El-Gamal Hesham
Eroz Mustafa
Hammons, Jr. A. Roger
Chase Shelly A
De'cady Albert
Hughes Electronics Corporation
Sales Michael
Whelan John T.
LandOfFree
Interleaver design for parsed parallel concatenated codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaver design for parsed parallel concatenated codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaver design for parsed parallel concatenated codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338845